Theoretische Informatik für Dummies

Theoretische Informatik stellt für viele Studenten ein Angstfach dar, sie gilt als abstrakt, stark formalisiert und dem Alltag entrückt. Das vorliegende Buch macht die Grundideen der Theoretischen Informatik auch für Studenten verständlich, deren erster Schwerpunkt nicht Informatik und schon gar nicht Mathematik ist. Automatentheorie, formale Sprachen und Grammatiken, Komplexität und Berechenbarkeit sind die wesentlichen Inhalte der Theoretischen Informatik, die in diesem Buch behandelt werden. Durch die Vielzahl der Beispiele, auch aus dem täglichen Leben, und den lockeren Schreibstil kann jeder interessierte Studierende die Hürde "Theoretische Informatik" nehmen - und vielleicht sogar etwas von der Faszination spüren, die von ihr ausgeht.

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 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