eBook.de : Ihr Online Shop für eBooks, Reader, Downloads und Bücher

Connect 01/2015 eBook-Shops: Testsieger im epub Angebot, Testurteil: gut Die Welt: Kundenorientierte Internetseiten Prädikat GOLD
+49 (0)40 4223 6096
€ 0,00

Zur Kasse

PORTO-
FREI

Komplexitätstheorie Band I: Grundlagen

Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdetermin…
Sofort lieferbar Pünktlich zum Fest*
Buch (kartoniert)
Buch € 49,95* inkl. MwSt.
Portofrei*
Produktdetails
Titel: Komplexitätstheorie Band I: Grundlagen
Autor/en: K. Rüdiger Reischuk

ISBN: 3519122758
EAN: 9783519122753
Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus.
'Leitfäden der Informatik'.
2. , völlig neu bearb. und erweiterte Aufl. 1999.
Book.
Vieweg+Teubner Verlag

1. Januar 1999 - kartoniert - 380 Seiten

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.
1 Das TM-Modell.- 1.0 Vorbemerkungen.- 1.0.1 Mengen.- 1.0.2 Graphen.- 1.0.3 Strings, Sprachen.- 1.1 Turing-Maschinen.- 1.1.1 Das allgemeine Modell.- 1.1.2 Verschiedene Speichertypen.- 1.1.3 Beispiele für die Arbeitsweise von TM.- 1.1.4 Berechenbarkeit.- 1.1.5 Nichtdeterministische Berechnungen.- 1.2 Das Rechnen mit TM.- 1.2.1 Elementare Techniken.- 1.2.2 Simulation, Band- und Kopf-Reduktion.- 1.2.3 Universelle Maschinen.- 1.3 Mathematische Grundlagen.- 1.3.1 Notation.- 1.3.2 Asymptotisches Wachstum.- 1.3.3 Wachstumsordnungen.- 1.3.4 Rekursionsgleichungen.- 1.4 Die Komplexität von TM.- 1.4.1 Schranken, Maße und Konstruierbarkeit.- 1.4.2 Komplexitätsklassen.- 1.4.3 Diagonalisierung.- 1.4.4 Bandkompression.- 1.4.5 Lineare Beschleunigung.- 1.5 Übungsaufgaben.- 1.6 Bemerkungen und Literaturhinweise.- 2 Weitere Maschinenmodelle.- 2.1 Registermaschinen.- 2.1.1 Das RAM-Modell.- 2.1.2 Komplexitätsmaße für RAMs.- 2.1.3 Simulation von RAMs durch TM.- 2.1.4 Simulation von TM durch RAMs.- 2.2 Schaltkreis-Familien.- 2.2.1 Boolesche Funktionen und Schaltkreise.- 2.2.2 Schaltkreiskomplexität.- 2.2.3 Uniformität.- 2.2.4 Simulation von Schaltkreisfamilien durch TM.- 2.2.5 Simulation von TM durch Schaltkreisfamilien.- 2.2.6 Universelle Schaltkreise.- 2.3 Arithmetische Modelle, Entscheidungsgraphen.- 2.3.1 Arithmetische RAMs und Schaltkreise.- 2.3.2 Entscheidungsbaum-Modelle.- 2.4 Übungsaufgaben.- 2.5 Bemerkungen und Literaturhinweise.- 3 Hierarchie-Sätze.- 3.1 Untere Schranken und Komplexitätslücken.- 3.1.1 Logarithmische Platzschranke.- 3.1.2 Quadratische Zeitschranke für 1-Band Maschinen.- 3.1.3 Komplexitätslücke bei zeitbeschränkten 1-Band TM.- 3.1.4 Komplexitätslücke bei kleinen Platzschranken.- 3.2 Deterministische Hierarchien.- 3.2.1 Allgemeiner Hierarchiesatz.- 3.2.2 Zeithierarchien.- 3.2.3 Platzhierarchien.- 3.3 Translation.- 3.4 Nichtdeterministische Hierarchien.- 3.4.1 Komplementabschluß von nichtdeterministischem Platz.- 3.4.2 Nichtdeterministischer Platzhierarchiesatz.- 3.4.3 Nichtdeterministischer Zeithierarchiesatz.- 3.5 Das Komplexitätsmaß Reversal.- 3.5.1 Reversalbeschränkte TM.- 3.5.2 Vergleich von Time und Reversal.- 3.5.3 Vergleich von Space und Reversal.- 3.5.4 Bandreduktion und Reversal für NTM.- 3.6 Abstrakte Komplexitätstheorie.- 3.6.1 Allgemeines Gap-Theorem.- 3.6.2 Speedup-Theorem.- 3.6.3 Union-Theorem.- 3.6.4 Abstrakte Komplexitätsmaße.- 3.7 Übungsaufgaben.- 3.8 Bemerkungen und Literaturhinweise.- 4 Vergleich von Speicherstrukturen.- 4.1 Ein allgemeines Speichermodell.- 4.1.1 On-line versus off-line.- 4.1.2 Konstruierbare Speicher.- 4.1.3 Lineare Bandsimulation konstruierbarer Speicher.- 4.2 1-dimensionale Speicher.- 4.2.1 Bandreduktion für NTM.- 4.2.2 Simulation von Mehrkopf-Maschinen.- 4.2.3 TM mit separatem Einweg-Eingabeband.- 4.2.4 1 versus 2 Bänder bei Zweiweg-Eingabe.- 4.3 Untere Schranken für Speicherzugriffe.- 4.3.1 Kolmogorov-Komplexität von Strings.- 4.3.2 Der Einfluß des Radius.- 4.4 Obere Schranken für Speicherzugriffe.- 4.4.1 Einbettung von Graphen.- 4.4.2 Kompaktifizierung.- 4.4.3 Schnelle Simulationen.- 4.5 Übungsaufgaben.- 4.6 Bemerkungen und Literaturhinweise.- 5 Zeit- versus Platzkomplexität.- 5.1 Time-Space-Relationen für 1-Band TM.- 5.1.1 Simulation platzbeschränkter 1-Band DTM.- 5.1.2 Simulation platzbeschränkter 1-Band NTM.- 5.1.3 Mehrdimensionale 1-Band TM.- 5.2 Das Pebble-Game.- 5.2.1 Berechnungsgraphen.- 5.2.2 Superkonzentratoren.- 5.2.3 Schichtungen von Graphen.- 5.3 Platzeffiziente Simulation von TM und RAMs.- 5.3.1 Lineare Speicher.- 5.3.2 Nichtlineare Speicher.- 5.3.3 Auxiliary Pushdown TM.- 5.4 Simultane Ressource-Schranken.- 5.4.1 Schaltkreisweite.- 5.4.2 Vergleich der Ressourcen von TM und Schaltkreisen.- 5.5 Übungsaufgaben.- 5.6 Bemerkungen und Literaturhinweise.- 6 Sequentielle Komplexitätsklassen.- 6.1 Einführung.- 6.1.1 Notation.- 6.1.2 Zeit-Platz-Hierarchie.- 6.1.3 Reduzierbarkeit, Vollständigkeit.- 6.2 Die Klassen von L bis P.- 6.2.1 Labyrinth-Probleme zur Charakterisierung von L und NL.- 6.2.2 P -vollständige Probleme.- 6.3 NP-vollständige Probleme.- 6.3.1 Das Erfüllbarkeitsproblem.- 6.3.2 Selbstreduzierbarkeit.- 6.3.3 Erfüllbarkeit für 3-CNF.- 6.3.4 Graphenprobleme: Cliquen, Kreise und Überdeckungen.- 6.3.5 Das Färbungsproblem für Graphen.- 6.3.6 Diskrete Optimierung.- 6.3.7 NP -Vollständigkeit im strengen Sinne.- 6.3.8 Obere Schranken und Parameterkomplexität.- 6.4 Von NP bis PSP ACE.- 6.4.1 Die Struktur von NP.- 6.4.2 Die Relation zwischen NP und co-NP.- 6.4.3 UP, Einweg-Funktionen und Kryptologie.- 6.4.4 PSP ACE -Vollständigkeit.- 6.5 Linguistische Klassifikationen.- 6.5.1 Formale Grammatiken.- 6.5.2 Die Chomsky-Hierarchie.- 6.5.3 Kontextfreie Sprachen und Log CFL.- 6.5.4 Reguläre Ausdrücke.- 6.6 Übungsaufgaben.- 6.7 Bemerkungen und Literaturhinweise.- Stichwortverzeichnis.- Symbolverzeichnis.- Zeitschriftenverzeichnis.- Konferenzverzeichnis.- Verzeichnis von Fachorganisationen.

Kundenbewertungen zu K. Rüdiger Reischuk „Komplexitätstheorie Band I: Grundlagen“

Noch keine Bewertungen vorhanden
Zur Rangliste der Rezensenten
Veröffentlichen Sie Ihre Kundenbewertung:
Kundenbewertung schreiben

Unsere Leistungen auf einen Klick

Unser Service für Sie

Zahlungsmethoden
Bequem, einfach und sicher mit eBook.de. mehr Infos akzeptierte Zahlungsarten: Überweisung, offene Rechnung,
Visa, Master Card, American Express, Paypal mehr Infos
Geprüfte Qualität
  • Schnelle Downloads
  • Datenschutz
  • Sichere Zahlung
  • SSL-Verschlüsselung
Servicehotline
+49 (0)40 4223 6096
Mo. - Fr. 8.00 - 20.00 Uhr
Sa. 10.00 - 18.00 Uhr
Chat
Ihre E-Mail-Adresse eintragen und kostenlos informiert werden:
* Alle Preise verstehen sich inkl. der gesetzlichen MwSt. Informationen über den Versand und anfallende Versandkosten finden Sie hier.
Artikel mit dem Hinweis "Pünktlich zum Fest" werden an Lieferadressen innerhalb Deutschlands rechtzeitig zum 24.12.2017 geliefert.
Bei als portofrei markierten Produkten bezieht sich dies nur auf den Versand innerhalb Deutschlands.

** im Vergleich zum dargestellten Vergleichspreis.
eBook.de - Meine Bücher immer dabei
eBook.de ist eine Marke der Hugendubel Digital GmbH & Co. KG
Folgen Sie uns unter: