Suchen und Finden
Theoretische Grundlagen der Informatik
von: Rolf Socher
Carl Hanser Fachbuchverlag, 2007
ISBN: 9783446414457 , 232 Seiten
3. Auflage
Format: PDF, OL
Kopierschutz: Wasserzeichen
Preis: 19,99 EUR
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
Alle Preise verstehen sich inklusive der gesetzlichen MwSt.