| Vorwort | 6 |
| Inhaltsverzeichnis | 8 |
| 1 Einführung | 12 |
| 1.1 Was ist theoretische Informatik? | 12 |
| 1.2 Zurück zu den Anfängen | 15 |
| 1.2.1 Die Mathematik in der Krise | 15 |
| 1.2.2 Metamathematik | 19 |
| 1.2.3 Die ersten Rechenmaschinen | 23 |
| 1.2.4 Der Computer wird erwachsen | 25 |
| 1.2.5 Berechenbarkeit versus Komplexität | 27 |
| 1.3 Theoretische Informatik heute | 33 |
| 1.4 Übungsaufgaben | 35 |
| 2 Mathematische Grundlagen | 38 |
| 2.1 Grundlagen der Mengenlehre | 39 |
| 2.1.1 Der Mengenbegriff | 39 |
| 2.1.2 Mengenoperationen | 42 |
| 2.2 Relationen und Funktionen | 45 |
| 2.3 Die Welt der Zahlen | 53 |
| 2.3.1 Natürliche, rationale und reelle Zahlen | 53 |
| 2.3.2 Von großen Zahlen | 56 |
| 2.3.3 Die Unendlichkeit begreifen | 58 |
| 2.4 Rekursion und induktive Beweise | 66 |
| 2.4.1 Vollständige Induktion | 67 |
| 2.4.2 Strukturelle Induktion | 69 |
| 2.5 Übungsaufgaben | 71 |
| 3 Logik und Deduktion | 82 |
| 3.1 Aussagenlogik | 83 |
| 3.1.1 Syntax und Semantik | 83 |
| 3.1.2 Normalformen | 92 |
| 3.1.3 Beweistheorie | 97 |
| 3.1.3.1 Hilbert-Kalkül | 99 |
| 3.1.3.2 Resolutionskalkül | 105 |
| 3.1.3.3 Tableaukalkül | 110 |
| 3.1.4 Anwendung: Hardware-Entwurf | 113 |
| 3.2 Prädikatenlogik | 118 |
| 3.2.1 Syntax und Semantik | 119 |
| 3.2.2 Normalformen | 123 |
| 3.2.3 Beweistheorie | 125 |
| 3.2.3.1 Resolutionskalkül | 131 |
| 3.2.3.2 Tableaukalkül | 136 |
| 3.2.4 Anwendung: Logische Programmierung | 139 |
| 3.3 Logikerweiterungen | 146 |
| 3.3.1 Prädikatenlogik mit Gleichheit | 147 |
| 3.3.2 Logiken höherer Stufe | 148 |
| 3.3.3 Typentheorie | 150 |
| 3.4 Übungsaufgaben | 151 |
| 4 Formale Sprachen | 162 |
| 4.1 Sprache und Grammatik | 163 |
| 4.2 Chomsky-Hierarchie | 169 |
| 4.3 Reguläre Sprachen | 171 |
| 4.3.1 Definition und Eigenschaften | 171 |
| 4.3.2 Pumping-Lemma für reguläre Sprachen | 173 |
| 4.3.3 Satz von Myhill-Nerode | 175 |
| 4.3.4 Reguläre Ausdrücke | 177 |
| 4.4 Kontextfreie Sprachen | 180 |
| 4.4.1 Definition und Eigenschaften | 180 |
| 4.4.2 Normalformen | 180 |
| 4.4.2.2 Backus-Naur-Form | 182 |
| 4.4.3 Pumping-Lemma für kontextfreie Sprachen | 183 |
| 4.4.4 Entscheidungsprobleme | 187 |
| 4.4.5 Abschlusseigenschaften | 189 |
| 4.5 Kontextsensitive Sprachen | 192 |
| 4.5.1 Definition und Eigenschaften | 192 |
| 4.5.2 Entscheidungsprobleme | 193 |
| 4.5.3 Abschlusseigenschaften | 194 |
| 4.6 Phrasenstruktursprachen | 194 |
| 4.7 Übungsaufgaben | 196 |
| 5 Endliche Automaten | 202 |
| 5.1 Begriffsbestimmung | 203 |
| 5.2 Deterministische Automaten | 205 |
| 5.2.1 Definition und Eigenschaften | 205 |
| 5.2.2 Automatenminimierung | 207 |
| 5.3 Nichtdeterministische Automaten | 209 |
| 5.3.1 Definition und Eigenschaften | 209 |
| 5.3.2 Satz von Rabin, Scott | 211 |
| 5.3.3 Epsilon-Übergänge | 213 |
| 5.4 Automaten und reguläre Sprachen | 217 |
| 5.4.1 Automaten und reguläre Ausdrücke | 218 |
| 5.4.2 Abschlusseigenschaften | 219 |
| 5.4.3 Entscheidungsprobleme | 221 |
| 5.4.4 Automaten und der Satz von Myhill-Nerode | 222 |
| 5.5 Kellerautomaten | 224 |
| 5.5.1 Definition und Eigenschaften | 224 |
| 5.5.2 Kellerautomaten und kontextfreie Sprachen | 227 |
| 5.5.3 Deterministische Kellerautomaten | 229 |
| 5.6 Transduktoren | 231 |
| 5.6.1 Definition und Eigenschaften | 231 |
| 5.6.2 Automatenminimierung | 232 |
| 5.6.3 Automatensynthese | 234 |
| 5.6.4 Mealy- und Moore-Automaten | 235 |
| 5.7 Petri-Netze | 239 |
| 5.8 Zelluläre Automaten | 244 |
| 5.9 Übungsaufgaben | 247 |
| 6 Berechenbarkeitstheorie | 254 |
| 6.1 Berechnungsmodelle | 255 |
| 6.1.1 Loop-Programme | 255 |
| 6.1.2 While-Programme | 261 |
| 6.1.3 Goto-Programme | 265 |
| 6.1.4 Primitiv-rekursive Funktionen | 270 |
| 6.1.5 Turing-Maschinen | 278 |
| 6.1.5.1 Einband-Turing-Maschinen | 278 |
| 6.1.5.2 Einseitig und linear beschränkte Turing-Maschinen | 286 |
| 6.1.5.3 Mehrspur-Turing-Maschinen | 287 |
| 6.1.5.4 Mehrband-Turing-Maschinen | 287 |
| 6.1.5.5 Maschinenkomposition | 289 |
| 6.1.5.6 Universelle Turing-Maschinen | 290 |
| 6.1.5.7 Zelluläre Turing-Maschinen | 294 |
| 6.1.6 Alternative Berechnungsmodelle | 296 |
| 6.1.6.1 Registermaschinen | 297 |
| 6.1.6.2 Lambda-Kalkül | 301 |
| 6.2 Church’sche These | 303 |
| 6.3 Entscheidbarkeit | 310 |
| 6.4 Akzeptierende Turing-Maschinen | 313 |
| 6.5 Unentscheidbare Probleme | 320 |
| 6.5.1 Halteproblem | 320 |
| 6.5.2 Satz von Rice | 323 |
| 6.5.3 Reduktionsbeweise | 326 |
| 6.5.4 Das Post’sche Korrespondenzproblem | 327 |
| 6.5.5 Weitere unentscheidbare Probleme | 331 |
| 6.6 Übungsaufgaben | 334 |
| 7 Komplexitätstheorie | 342 |
| 7.1 Algorithmische Komplexität | 343 |
| 7.1.1 O-Kalkül | 350 |
| 7.1.2 Rechnen im O-Kalkül | 353 |
| 7.2 Komplexitätsklassen | 357 |
| 7.2.1 P und NP | 360 |
| 7.2.2 PSPACE und NPSPACE | 366 |
| 7.2.3 EXP und NEXP | 368 |
| 7.2.4 Komplementäre Komplexitätsklassen | 370 |
| 7.3 NP-Vollständigkeit | 372 |
| 7.3.1 Polynomielle Reduktion | 372 |
| 7.3.2 P-NP-Problem | 373 |
| 7.3.3 Satz von Cook | 374 |
| 7.3.4 Reduktionsbeweise | 381 |
| 7.4 Übungsaufgaben | 387 |
| Anhang | 396 |
| A Notationsverzeichnis | 398 |
| B Abkürzungsverzeichnis | 402 |
| C Glossar | 404 |
| Literaturverzeichnis | 420 |
| Namensverzeichnis | 424 |
| Sachwortverzeichnis | 426 |
