Komplexitätstheorie Band I: Grundlagen

Name: Komplexitätstheorie Band I: Grundlagen
SKU: 9783519122753
Price: 699 SEK
Availability: InStock
Author: K. Rüdiger Reischuk
ISBN: 9783519122753

Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus

Häftad, Tyska, 1999

AvK. Rüdiger Reischuk

699 kr

Beställningsvara. Skickas inom 5-8 vardagar. Fri frakt för medlemmar vid köp för minst 249 kr.

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

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, 1998

679 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

519 kr

Mer från samma serie

Kompendium Theoretische Informatik — eine Ideensammlung

Ingo Wegener

Häftad, 1996

539 kr

Elektrotechnik für Informatiker

Reinhold Paul

Häftad, 2004

749 kr

Algorithmische Grundlagen der Bioinformatik

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

Häftad, 2003

609 kr

Approximationsalgorithmen

Rolf Wanka

Häftad, 2006

539 kr

Mustererkennung mit Markov-Modellen

Gernot A. Fink

Häftad, 2003

549 kr

Protocol Engineering

Hartmut König

Häftad, 2003

609 kr

Randomisierte Algorithmen

Juraj Hromkovic

Häftad, 2004

699 kr

Moderne Kryptographie

Ralf Küsters, Thomas Wilke

Häftad, 2011

449 kr

Theorie der stochastischen Automaten

Springer Fachmedien Wiesbaden

Häftad, 1995

679 kr

Elektrotechnik und Elektronik für Informatiker

Reinhold Paul

Häftad, 1995

949 kr

Du kanske också är intresserad av

Ausgezeichnete Informatikdissertationen 1996

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

Häftad, 1998

679 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

519 kr

Fuzzy-Systeme

Frank Klawonn, Jörg Gebhardt

Häftad, 1995

1 079 kr

Randomisierte Algorithmen

Juraj Hromkovic

Häftad, 2004

699 kr

Petrinetze

Wolfgang Reisig

Inbunden, 2010

519 kr

Elektrotechnik und Elektronik für Informatiker

Springer Fachmedien Wiesbaden

Häftad, 1999

679 kr

Programmieren mit Modula-2 Grundkurs Angewandte Informatik I

Wolffried Stucky, W. Stucky

Häftad, 1994

679 kr

Multimediale Datenbanken

Klaus Meyer-Wegener

Häftad, 2003

469 kr

Moderne Kryptographie

Ralf Küsters, Thomas Wilke

Häftad, 2011

449 kr

Computergrafik und Geometrisches Modellieren

Beat Brüderlin, Andreas Meier, Beat Brüderlin, Andreas Meier

Häftad, 2001

609 kr

Del i serien XLeitfäden der Informatik

Komplexitätstheorie Band I: Grundlagen

Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus

Häftad, Tyska, 1999

AvK. Rüdiger Reischuk

699 kr

Beställningsvara. Skickas inom 5-8 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.