Komplexitätstheorie Band I: Grundlagen

Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus

Häftad, Tyska, 1999

Av K. Rüdiger Reischuk

679 kr

Beställningsvara. Skickas inom 7-10 vardagar

Fri frakt för medlemmar vid köp för minst 249 kr.

Produktinformation

Utgivningsdatum1999-01-01
Mått162 x 229 x 21 mm
Vikt586 g
FormatHäftad
SpråkTyska
SerieXLeitfäden der Informatik
Antal sidor355
Upplaga2
FörlagSpringer Fachmedien Wiesbaden
ISBN9783519122753

Tillhör följande kategorier

Systemvetenskap och AI inom Data och it
Programmeringsböcker inom Data och it

1 Das TM-Modell.- 1.0 Vorbemerkungen.- 1.1 Turing-Maschinen.- 1.2 Das Rechnen mit TM.- 1.3 Mathematische Grundlagen.- 1.4 Die Komplexität von TM.- 1.5 Übungsaufgaben.- 1.6 Bemerkungen und Literaturhinweise.- 2 Weitere Maschinenmodelle.- 2.1 Registermaschinen.- 2.2 Schaltkreis-Familien.- 2.3 Arithmetische Modelle, Entscheidungsgraphen.- 2.4 Übungsaufgaben.- 2.5 Bemerkungen und Literaturhinweise.- 3 Hierarchie-Sätze.- 3.1 Untere Schranken und Komplexitätslücken.- 3.2 Deterministische Hierarchien.- 3.3 Translation.- 3.4 Nichtdeterministische Hierarchien.- 3.5 Das Komplexitätsmaß Reversal.- 3.6 Abstrakte Komplexitätstheorie.- 3.7 Übungsaufgaben.- 3.8 Bemerkungen und Literaturhinweise.- 4 Vergleich von Speicherstrukturen.- 4.1 Ein allgemeines Speichermodell.- 4.2 1-dimensionale Speicher.- 4.3 Untere Schranken für Speicherzugriffe.- 4.4 Obere Schranken für Speicherzugriffe.- 4.5 Übungsaufgaben.- 4.6 Bemerkungen und Literaturhinweise.- 5 Zeit- versus Platzkomplexität.- 5.1 Time-Space-Relationen für 1-Band TM.- 5.2 Das Pebble-Game.- 5.3 Platzeffiziente Simulation von TM und RAMs.- 5.4 Simultane Ressource-Schranken.- 5.5 Übungsaufgaben.- 5.6 Bemerkungen und Literaturhinweise.- 6 Sequentielle Komplexitätsklassen.- 6.1 Einführung.- 6.2 Die Klassen von L bis P.- 6.3 NP-vollständige Probleme.- 6.4 Von NP bis PSP ACE.- 6.5 Linguistische Klassifikationen.- 6.6 Übungsaufgaben.- 6.7 Bemerkungen und Literaturhinweise.- Stichwortverzeichnis.- Symbolverzeichnis.- Zeitschriftenverzeichnis.- Konferenzverzeichnis.- Verzeichnis von Fachorganisationen.

Du kanske också är intresserad av