Rolf Socher
Theoretische Grundlagen der Informatik
Vorwort
6
Inhalt
8
1 Einleitung
10
2 Endliche Automaten
16
2.1 Einführung
16
2.2 Grundlegende Begriffe
17
2.3 Deterministische endliche Automaten
19
2.4 Minimierung endlicher Automaten
24
2.5 Nichtdeterministische endliche Automaten
30
2.6 Automaten mit e-Übergängen
36
2.7 Anwendung endlicher Automaten
40
3 Reguläre Sprachen
46
3.1 Reguläre Ausdrücke
46
3.2 DasPumping-Lemma
53
3.3 Der SatzvonMyhill-Nerode
56
3.4 Abgeschlossenheitseigenschaften regulärer Sprachen
60
4 Grammatiken
66
4.1 Grundlegende Definitionen
67
4.2 Reguläre Grammatiken
69
4.3 KontextfreieGrammatiken
75
4.4 DieChomsky-Normalform und der CYK-Algorithmus
76
4.5 Eigenschaftenkontextfreier Sprachen
83
4.6 Kellerautomaten
86
4.7 KontextfreieGrammatiken und Kellerautomaten
94
4.8 Typ-1- und Typ-0-Grammatiken
97
4.9 DieChomsky-Hierarchie
98
5 Turing-Maschinen und Berechenbarkeit
102
5.1 Einführung
102
5.2 DasBasismodel
104
5.3 Modifikationen des Basismodells
109
5.4 Linear beschränkte Automaten und Typ-1-Grammatiken
114
5.5 DieSprachklassen der Chomsky-Hierarchie
115
5.6 Turing-Berechenbarkeit
117
5.7 Andere Berechnungskonzepte
120
5.8 Die universelle Turing-Maschine
129
5.9 Die Churchsche These
132
6 Entscheidbarkeit
136
6.1 Entscheidbarkeit und Semi-Entscheidbarkeit
136
6.2 UnentscheidbareProbleme
141
6.3 DasHalteproblem
145
6.4 Reduktionstechniken
149
6.5 Der Satzvon Rice
158
7 Komplexität
160
7.1 Einführung
160
7.2 Komplexität vonAlgorithmen
162
7.3 Die Klassen P und NP
169
7.4 NP-Vollständigkeit
179
8 Anhang: Mathematische Grundlagen
188
8.1 Mengen
188
8.2 Partitionen
190
8.3 Relationen
190
8.4 Graphen
195
8.5 Aussagenlogik
196
Lösungen der Aufgaben
202
Register
226
© 2009-2024 ciando GmbH