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.

Ü 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