Del 0 - XLeitfäden der Informatik

Komplexitätstheorie Band I: Grundlagen

Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus

Häftad, Tyska, 1999

AvK. 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.

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

659 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

499 kr

Mer från samma serie

Elektrotechnik für Informatiker

Reinhold Paul

Häftad

729 kr

Algorithmische Grundlagen der Bioinformatik

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

Häftad

599 kr

Mustererkennung mit Markov-Modellen

Gernot A. Fink

Häftad

529 kr

Theorie der stochastischen Automaten

Häftad

659 kr

Elektrotechnik und Elektronik für Informatiker

Reinhold Paul

Häftad

919 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, Klaus Kran