Theoretische Informatik für Dummies

Roland Schmitz ist promovierter Mathematiker und seit 2001 Professor für Internet-Security im Studiengang Medieninformatik an der Hochschule der Medien in Stuttgart. Vorher war er sechs Jahre lang wissenschaftlicher Mitarbeiter am Technologiezentrum der Deutschen Telekom mit den Hauptarbeitsgebieten Sicherheit mobiler Kommunikation sowie Standardisierung digitaler Signaturen.

• Über den Autor 7Einleitung 17Was ist theoretische Informatik? 17Über dieses Buch 18Wie dieses Buch aufgebaut ist 18Symbole in diesem Buch 20Wie Sie dieses Buch lesen sollten 20Teil I Endliche Automaten 21Kapitel 1 Deterministische Endliche Automaten (DFAs) 23Einführung 23Erste Beispiele 24Grundlegende Definitionen 27Symbole und Wörter 27Die Definition eines DFAs 28Reguläre Sprachen 30Die erweiterte Übergangsfunktion 30Beispiele regulärer Sprachen 31Das Pumping Lemma 34Minimalautomaten 38Der Satz von Myhill und Nerode 45DFAs mit Ausgabe (Moore- und Mealy-Automaten) 50Aufgaben zu DFAs 54Kapitel 2 Nichtdeterministische Endliche Automaten (NFAs) 57Nichtdeterminismus 57Definition eines NFA 58Der Satz von Rabin-Scott 60NFAs mit 𝜖-Übergängen 64Abschlusseigenschaften regulärer Sprachen 67Reguläre Ausdrücke 70Stochastische Automaten und Markov-Ketten 75Hidden Markov Models 80Aufgaben zu NFAs 80Kapitel 3 Kellerautomaten (PDAs) 83Nichtdeterministische Kellerautomaten 83Deterministische Kellerautomaten 89Die Grenzen von PDAs 91Aufgaben zu PDAs 92Kapitel 4 Turing-Maschinen 93Deterministische Turing-Maschinen 93Turing-Berechenbarkeit 102Mehrband-Turing-Maschinen 105Registermaschinen 109Nichtdeterministische Turing-Maschinen 110Linear beschränkte Turing-Maschinen 112Universelle Turing-Maschine (UTM) 113Die Grenzen von Turing-Maschinen 115Aufgaben zu Turing-Maschinen 120Teil II Formale Sprachen 123Kapitel 5 Grammatiken 125Einführung 125Ein erstes Beispiel 126Syntaxbäume 127Definition einer Grammatik 128Die von einer Grammatik erzeugte Sprache 128Wie man 𝜖-Regeln loswird 129Das Wortproblem 131Chomsky-Hierarchie 131Aufgaben zu Grammatiken 133Kapitel 6 Reguläre (Typ-3-)Sprachen 135Beispiele für Typ-3-Sprachen 135Das Wortproblem für Typ-3-Sprachen 136Aufgaben zu Typ-3-Sprachen 139Kapitel 7 Kontextfreie (Typ-2-)Sprachen 141Erste Beispiele 141Backus-Naur-Form (BNF) 142Erweiterte Backus-Naur-Form (EBNF) 142Chomsky-Normalform 144Die Grenzen kontextfreier Sprachen 146Ein äquivalentes Maschinenmodell 150Deterministisch kontextfreie Sprachen 153Das Wortproblem für kontextfreie Sprachen 154Abschlusseigenschaften 156Aufgaben zu kontextfreien Sprachen 157Kapitel 8 Kontextsensitive und Phasen-Struktur-Sprachen 159Ein erstes Beispiel 159Das Wortproblem für Typ-1-Sprachen 160Das Wortproblem für Typ-0-Sprachen 161Äquivalente Maschinenmodelle 162Typ-0-Sprachen 162Typ-1-Sprachen 164Teil III Harte Probleme 167Kapitel 9 Zeitkomplexität von Algorithmen 169Einführende Überlegungen 169Zeit- und Speicherkomplexität von Algorithmen 171Die O-Notation 175Komplexitätsklassen von Sprachen 177Aufgaben zur Komplexität von Algorithmen 179Kapitel 10 Die Klassen P und NP 181Die Klasse P 181Die Klasse NP 182Zertifikate 182Das SAT-Problem 185Reduktion 188SAT, KNF-SAT und 3-SAT 190Reduktion und Entscheidbarkeit 196Aufgaben zu P und NP 197Kapitel 11 NP-Vollständigkeit 199Der Satz von Cook 199Boolesche Schaltkreise und deterministische Turing-Maschinen 200Boolesche Schaltkreise und nichtdeterministische Turing-Maschinen 206Reduktion von CIRCUIT-SAT auf 3-SAT 208Beispiele NP-vollständiger Sprachen 210SUBSET-SUM-Problem 210Hamilton-Kreise 213Das Travelling-Salesman-Problem 219Das Cliquen-Problem 221Ist P = NP? 223Quantencomputer 223Die Klasse BQP 225Aufgaben zur NP-Vollständigkeit 227Teil IV Mathematische Grundlagen 229Kapitel 12 Logische Grundlagen 231Boolesche Variablen und boolesche Formeln 231Aussagen und Beweise 233Beweistechniken 234Aufgaben zur Logik 238Kapitel 13 Mengen und Relationen 239Grundbegriffe 239Mengenoperationen 241Relationen 242Äquivalenzrelationen 242Ordnungsrelationen 244Funktionen 245Aufgaben zu Mengen und Relationen 247Kapitel 14 Graphen und Bäume 249Graphen und ihre Eigenschaften 249Zusammenhängende Graphen 251Darstellung von Graphen im Computer 253Bäume 256Tourenprobleme 258Gewichtete Graphen 260Näherungsweise Lösung des TSP 261Aufgaben zu Graphen und Bäumen 265Teil V Top-Ten-Teil 267Kapitel 15 Top-Ten-Theoretiker 269Charles Babbage (1791–1871) 269Ada Lovelace (1815–1852) 270Alonzo Church (1903–1995) 270Alan Turing (1912–1954) 271Claude Shannon (1916–2001) 272Richard Feynman (1918–1988) 273Noam Chomsky (geboren 1928) 274Michael Rabin (geboren 1931) und Dana Scott (geboren 1932) 274Stephen Cook (geboren 1939) 275Peter W. Shor (geboren 1959) 275Kapitel 16 Die Top-Ten-Bücher zum Weiterlesen 277Teil I: Endliche Automaten 277Teil II: Formale Sprachen 277Teil III: Harte Probleme 278Teil IV: Mathematische Grundlagen 278Teil V: Top-Ten-Teil 278Symbolverzeichnis 281Stichwortverzeichnis 283

"...das Buch wendet sich an Studienanfänger ..., [Der Autor] versucht, theoretische Informatik 'formelfrei' zu besprechen und viele Formeln noch einmal umgangssprachlich zu erklären. ... Didaktisch gut aufgebaut. Jeder der drei Teile wird mit einem kurzen Absatz eingeleitet; ein nichtkonsekutives Durcharbeiten des Buches ist somit leicht möglich. ..."(EKZ 28. Oktober 2019)