Über den Autor 7

Einleitung 17

Was ist theoretische Informatik? 17

Über dieses Buch 18

Wie dieses Buch aufgebaut ist 18

Symbole in diesem Buch 20

Wie Sie dieses Buch lesen sollten 20

Teil I Endliche Automaten 21

Kapitel 1 Deterministische Endliche Automaten (DFAs) 23

Einführung 23

Erste Beispiele 24

Grundlegende Definitionen 27

Symbole und Wörter 27

Die Definition eines DFAs 28

Reguläre Sprachen 30

Die erweiterte Übergangsfunktion 30

Beispiele regulärer Sprachen 31

Das Pumping Lemma 34

Minimalautomaten 38

Der Satz von Myhill und Nerode 45

DFAs mit Ausgabe (Moore- und Mealy-Automaten) 50

Aufgaben zu DFAs 54

Kapitel 2 Nichtdeterministische Endliche Automaten (NFAs) 57

Nichtdeterminismus 57

Definition eines NFA 58

Der Satz von Rabin-Scott 60

NFAs mit ¿-Übergängen 64

Abschlusseigenschaften regulärer Sprachen 67

Reguläre Ausdrücke 70

Stochastische Automaten und Markov-Ketten 75

Hidden Markov Models 80

Aufgaben zu NFAs 80

Kapitel 3 Kellerautomaten (PDAs) 83

Nichtdeterministische Kellerautomaten 83

Deterministische Kellerautomaten 89

Die Grenzen von PDAs 91

Aufgaben zu PDAs 92

Kapitel 4 Turing-Maschinen 93

Deterministische Turing-Maschinen 93

Turing-Berechenbarkeit 102

Mehrband-Turing-Maschinen 105

Registermaschinen 109

Nichtdeterministische Turing-Maschinen 110

Linear beschränkte Turing-Maschinen 112

Universelle Turing-Maschine (UTM) 113

Die Grenzen von Turing-Maschinen 115

Aufgaben zu Turing-Maschinen 120

Teil II Formale Sprachen 123

Kapitel 5 Grammatiken 125

Einführung 125

Ein erstes Beispiel 126

Syntaxbäume 127

Definition einer Grammatik 128

Die von einer Grammatik erzeugte Sprache 128

Wie man ¿-Regeln loswird 129

Das Wortproblem 131

Chomsky-Hierarchie 131

Aufgaben zu Grammatiken 133

Kapitel 6 Reguläre (Typ-3-)Sprachen 135

Beispiele für Typ-3-Sprachen 135

Das Wortproblem für Typ-3-Sprachen 136

Aufgaben zu Typ-3-Sprachen 139

Kapitel 7 Kontextfreie (Typ-2-)Sprachen 141

Erste Beispiele 141

Backus-Naur-Form (BNF) 142

Erweiterte Backus-Naur-Form (EBNF) 142

Chomsky-Normalform 144

Die Grenzen kontextfreier Sprachen 146

Ein äquivalentes Maschinenmodell 150

Deterministisch kontextfreie Sprachen 153

Das Wortproblem für kontextfreie Sprachen 154

Abschlusseigenschaften 156

Aufgaben zu kontextfreien Sprachen 157

Kapitel 8 Kontextsensitive und Phasen-Struktur-Sprachen 159

Ein erstes Beispiel 159

Das Wortproblem für Typ-1-Sprachen 160

Das Wortproblem für Typ-0-Sprachen 161

Äquivalente Maschinenmodelle 162

Typ-0-Sprachen 162

Typ-1-Sprachen 164

Teil III Harte Probleme 167

Kapitel 9 Zeitkomplexität von Algorithmen 169

Einführende Überlegungen 169

Zeit- und Speicherkomplexität von Algorithmen 171

Die O-Notation 175

Komplexitätsklassen von Sprachen 177

Aufgaben zur Komplexität von Algorithmen 179

Kapitel 10 Die Klassen P und NP 181

Die Klasse P 181

Die Klasse NP 182

Zertifikate 182

Das SAT-Problem 185

Reduktion 188

SAT, KNF-SAT und 3-SAT 190

Reduktion und Entscheidbarkeit 196

Aufgaben zu P und NP 197

Kapitel 11 NP-Vollständigkeit 199

Der Satz von Cook 199

Boolesche Schaltkreise und deterministische Turing-Maschinen 200

Boolesche Schaltkreise und nichtdeterministische Turing-Maschinen 206

Reduktion von CIRCUIT-SAT auf 3-SAT 208

Beispiele NP-vollständiger Sprachen 210

SUBSET-SUM-Problem 210

Hamilton-Kreise 213

Das Travelling-Salesman-Problem 219

Das Cliquen-Problem 221

Ist P = NP? 223

Quantencomputer 223

Die Klasse BQP 225

Aufgaben zur NP-Vollständigkeit 227

Teil IV Mathematische Grundlagen 229

Kapitel 12 Logische Grundlagen 231

Boolesche Variablen und boolesche Formeln 231

Aussagen und Beweise 233

Beweistechniken 234

Aufgaben zur Logik 238

Kapitel 13 Mengen und Relationen 239

Grundbegriffe 239

Mengenoperationen 241

Relationen 242

Äquivalenzrelationen 242

Ordnungsrelationen 244

Funktionen 245

Aufgaben zu Mengen und Relationen 247

Kapitel 14 Graphen und Bäume 249

Graphen und ihre Eigenschaften 249

Zusammenhängende Graphen 251

Darstellung von Graphen im Computer 253

Bäume 256

Tourenprobleme 258

Gewichtete Graphen 260

Näherungsweise Lösung des TSP 261

Aufgaben zu Graphen und Bäumen 265

Teil V Top-Ten-Teil 267

Kapitel 15 Top-Ten-Theoretiker 269

Charles Babbage (1791-1871) 269

Ada Lovelace (1815-1852) 270

Alonzo Church (1903-1995) 270

Alan Turing (1912-1954) 271

Claude Shannon (1916-2001) 272

Richard Feynman (1918-1988) 273

Noam Chomsky (geboren 1928) 274

Michael Rabin (geboren 1931) und Dana Scott (geboren 1932) 274

Stephen Cook (geboren 1939) 275

Peter W. Shor (geboren 1959) 275

Kapitel 16 Die Top-Ten-Bücher zum Weiterlesen 277

Teil I: Endliche Automaten 277

Teil II: Formale Sprachen 277

Teil III: Harte Probleme 278

Teil IV: Mathematische Grundlagen 278

Teil V: Top-Ten-Teil 278

Symbolverzeichnis 281

Stichwortverzeichnis 283