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

526 kr

Beställningsvara. Skickas inom 5-8 vardagar. Fri frakt över 249 kr.

Fler format och utgåvor

E-bok

553 kr

Beskrivning

Die Komplexitätstheorie untersucht den algorithmischen Aufwand zur Lösung von Problemen mit Hilfe einer Maschine. Dabei werden Rechnermodelle wie Turing-Maschinen oder Registermaschinen verwendet, um von speziellen Architektur- und Implementationsdetails unabhängige Ergebnisse zu gewinnen. Neben den klassischen Komplexitätsmaßen Zeitaufwand und Speicherplatzbedarf werden eine Reihe weiterer Maße zur Strukturierung eingesetzt. Algorithmische Probleme werden diesbezüglich klassifiziert und in Beziehung zueinander gesetzt. Die Suche nach effizienten Lösungsstrategien wird komplementiert durch den (im allgemeinen sehr schwierigen) Nachweis unterer Schranken für den Lösungsaufwand.

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 1999

Dorothea Wagner, Bernhard Seeger, K. Rudiger Reischuk, Gunter Hotz, Steffen Holldobler, Werner Grass, Oliver Gunther, Herbert Fiedler

E-bok

2013

447 kr

Ausgezeichnete Informatikdissertationen 1996

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

E-bok

2013

537 kr

Ausgezeichnete Informatikdissertationen 1996

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

Häftad, 1998

513 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, 2000

392 kr

Mer från samma serie

Elektrotechnik für Informatiker

Reinhold Paul

Häftad, 2004

565 kr

Algorithmische Grundlagen der Bioinformatik

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

Häftad, 2003

463 kr

Approximationsalgorithmen

Rolf Wanka

Häftad, 2006

404 kr

Mustererkennung mit Markov-Modellen

Gernot A. Fink

Häftad, 2003

412 kr

Protocol Engineering

Hartmut König

Häftad, 2003

463 kr

Randomisierte Algorithmen

Juraj Hromkovic

Häftad, 2004

529 kr

Moderne Kryptographie

Ralf Küsters, Thomas Wilke

Häftad, 2011

340 kr

Theorie der stochastischen Automaten

Springer Fachmedien Wiesbaden

Häftad, 1995

514 kr

Elektrotechnik und Elektronik für Informatiker

Reinhold Paul

Häftad, 1995

717 kr

Parallelrechner

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