Komplexitätstheorie Band I: Grundlagen

Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus

AvK. Rüdiger Reischuk

Häftad, Tyska, 1999

Del i serien XLeitfäden der Informatik

512 kr

Beställningsvara. Skickas inom 7-10 vardagar. Fri frakt över 249 kr.

Produktinformation

Utgivningsdatum:1999-01-01
Mått:162 x 229 x 21 mm
Vikt:586 g
Format:Häftad
Språk:Tyska
Serie:XLeitfäden der Informatik
Antal sidor:355
Upplaga:2
Förlag:Springer Fachmedien Wiesbaden
ISBN:9783519122753

Utforska kategorier

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

Innehållsförteckning

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.

Mer från samma författare

Ausgezeichnete Informatikdissertationen 1996

Wolfgang Bibel, H. Fiedler, W. Grass, Peter Gorny, Otto Kerner, K. Rüdiger Reischuk, Friedrich Roithmayr

Häftad

500 kr

Ausgezeichnete Informatikdissertationen 1999

Herbert Fiedler, Oliver Günther, Werner Grass, Steffen Hölldobler, Günter Hotz, K. Rüdiger Reischuk, Bernhard Seeger, Dorothea Wagner

Häftad

382 kr

Mer från samma serie

Elektrotechnik für Informatiker

Reinhold Paul

Häftad

549 kr

Algorithmische Grundlagen der Bioinformatik

Hans-Joachim Böckenhauer, Dirk Bongartz, Hans-Joachim Böckenhauer, Dirk Bongartz

Häftad

451 kr

Mustererkennung mit Markov-Modellen

Gernot A. Fink

Häftad

401 kr

Theorie der stochastischen Automaten

Häftad

500 kr

Elektrotechnik und Elektronik für Informatiker

Reinhold Paul

Häftad

697 kr

Arndt Bode, Ulrich Brüning, Mario Dal Cin, Wolfgang Händler, Friedrich Hertweck, Ulrich Herzog, Fridolin Hofmann, Rainer Klar, Claus-Uwe Linster, Wolfgang Rosenstiel, Hans-Jürgen Schneider, Jörg Wedeck, Hans Zima, B. M. Chapman, Klaus Waldschmidt