دانلود کتاب Theoretische Informatik: Eine umfassende Einführung

فهرست مطالب :

Vorwort zur 1. Auflage
Vorwort zur 2. Auflage
Vorwort zur 3. Auflage
Vorwort zur 4. Auflage
Inhaltsverzeichnis
1. Einleitung
2. Begriffe und Notationen
2.1 Logische Formeln und Konnektoren
2.2 Grundkonzepte aus der Mengenlehre
2.2.1 Relationen
2.2.2 Funktionen
2.2.3 Isomorphie, Abzählbarkeit
2.3 Grundbegriffe aus der Algebra
2.4 Grundbegriffe aus der Graphentheorie
2.5 Grundbegriffe aus der Informatik
2.6 Probleme und Algorithmen
2.7 Zusammenfassung
3. Eine kurze Einführung in die Aussagenlogik
3.1 Syntax der Aussagenlogik
3.2 Semantik der Aussagenlogik
3.3 Wahrheitstafeln
3.4 SAT und TAUT
3.5 Äquivalenz von Formeln
3.6 Konjunktive und disjunktive Normalform
3.7 Zusammenfassung
Teil I Formale Sprachen
4. Grammatiken und formale Sprachen
4.1 Grammatiken
4.2 Die Sprachklassen der Chomsky-Hierarchie
4.3 Automaten
4.4 Zusammenfassung
5. Reguläre Sprachen und endliche Automaten
5.1 Verschiedene Automatentypen
5.1.1 Endliche Automaten
5.1.2 Indeterminierte endliche Automaten
5.1.3 Automaten mit ε-Kanten
5.1.4 Endliche Automaten mit Ausgabe: gsm
5.2 Rationale Sprachen und L3
5.3 Abschlusseigenschaften von L3
5.4 Eine weitere Charakterisierung von L3: über reguläre Ausdrücke
5.5 Eine weitere Charakterisierung von L3: über die Kongruenz ∼L
5.6 Minimale Automaten
5.7 Das Pumping-Lemma für L3
5.8 Entscheidbare Probleme für L3
5.9 Zusammenfassung
6. Kontextfreie Sprachen
6.1 Darstellung von kontextfreien Ableitungen in Baumform
6.2 Umformung von Grammatiken
6.3 Chomsky- und Greibach-Normalform
6.4 Das Pumping-Lemma für L2
6.5 Abschlusseigenschaften von L2
6.6 Push-Down-Automaten (PDA)
6.7 Determiniert kontextfreie Sprachen (DCFL)
6.8 Probleme und Algorithmen zu cf-Sprachen
6.8.1 Das Wortproblem
6.8.2 Andere Probleme
6.9 Zusammenfassung
7. Turing-Maschinen
7.1 Determinierte Turing-Maschinen
7.2 TM-Flussdiagramme
7.3 Entscheidbarkeit, Akzeptierbarkeit, Aufzählbarkeit
7.4 Variationen von Turing-Maschinen
7.5 Universelle Turing-Maschinen
7.5.1 Gödelisierung
7.5.2 Eine konkrete universelle Turing-Maschine
7.6 Zusammenfassung
8. Die Sprachklassen L, L0 und L1
8.1 L1 und beschränkte Grammatiken
8.2 Linear beschränkte Automaten und Turing-Maschinen
8.3 Entscheidbare Sprachen
8.4 L0 und L
8.5 Typ-1-Sprachen sind abgeschlossen gegen Komplement
8.6 Zusammenfassung
9. Abschlusseigenschaften von Sprachklassen
9.1 Überblick
9.2 Beweise der Abschlusseigenschaften
9.3 Zusammenfassung
Teil II Berechenbarkeit
10. Einleitung
10.1 Immer mächtigere Automaten
10.2 Die Churchsche These
10.3 Was es außer Turing-Maschinen noch gibt
10.4 Unentscheidbare Probleme
10.5 Komplexitätstheorie
10.6 Zusammenfassung
11. Registermaschinen
11.1 Registermaschinen und LOOP-Programme
11.2 WHILE-Programme
11.3 GOTO-Programme
11.4 GOTO-Programme und Turing-Maschinen
11.5 LOOP-Programme und Turing-Maschinen
11.6 Zusammenfassung
12. Rekursive Funktionen
12.1 Primitiv rekursive Funktionen
12.2 Arithmetische Funktionen, primitiv rekursiv ausgedrückt
12.3 ℘ und LOOP
12.4 μ-rekursive Funktionen
12.5 μ-rekursive Funktionen gleichmächtig wie Turing-Maschinen
12.6 Übersicht über die verschiedenen Berechenbarkeitsbegriffe
12.7 Eine weitere universelle Turing-Maschine, die auf Kleenes Theorem basiert
12.8 Zusammenfassung
13. Unentscheidbare Probleme
13.1 Entscheidbarkeit, Akzeptierbarkeit, Aufzählbarkeit
13.2 Eine Liste unentscheidbarer TM-Probleme
13.3 Das spezielle Halteproblem
13.4 Unentscheidbarkeits-Beweise via Reduktion
13.5 Der Satz von Rice
13.6 Unentscheidbarkeit und formale Sprachen
13.6.1 Semi-Thue-Systeme und Postsche Normalsysteme
13.6.2 Das PCP und unentscheidbare Probleme für L2
13.6.3 Entscheidbare und unentscheidbare Probleme für L2
13.6.4 Eine weitere Anwendung der Unentscheidbarkeit von K0
13.7 Zusammenfassung
14. Alternative Berechnungsmodelle
14.1 Ein-Registermaschinen
14.2 Zwei-Registermaschinen
14.3 Variationen über Zwei-Registermaschinen
14.3.1 Turing-Maschinen mit eingeschränktem Alphabet
14.3.2 Ein System mit zwei Stapeln von leeren Blättern
14.3.3 Push-Down-Automaten mit Queue oder zwei Stapeln
14.3.4 Ein Stein im N
14.4 Wang-Maschinen
14.5 Tag-Systeme
14.6 Rödding-Netze
14.7 Eine extrem kleine universelle zweidimensionale Turing-Maschine
14.8 Reversible Rechnungen
14.8.1 Abstrakte Rechenmodelle
14.8.2 Asynchrone Automaten und Netze
14.8.3 Berechnungsuniverselle chemisch reversible Netze
14.8.4 Chemisch reversible Grammatiken
14.8.5 Zweidimensionale Thue-Systeme
14.8.6 Physikalisch reversible Schaltwerke
14.8.7 Physikalisch reversible Turing-Maschinen
14.9 Splicing
14.9.1 H-Systeme
14.9.2 Test-tube-Systeme
14.10 Zusammenfassung
15. Komplexität
15.1 Abschtzung mit dem O-Kalkül
15.2 Aufwandberechnung und Turing-Maschinen
15.3 Abschätzung für determinierte und indeterminierte Maschinen
15.4 NP-vollständige Probleme
15.5 Zusammenfassung
Bibliographische Hinweise
Literaturverzeichnis
Sachverzeichnis