Theoretische Informatik für Dummies
Die Grundideen verständlich dargestellt. Mit vielen Beispielen.
1st Edition
Published on 11. September 2019
Book
Paperback/Softback
286 pages
978-3-527-71431-5 (ISBN)
Description
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.
Reviews / Votes
"...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)
More details
Other editions
Additional editions
Roland Schmitz
Theoretische Informatik für Dummies
E-Book
10/2019
1st Edition
Wiley-VCH
€18.99
Available for download
Person
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.
Content
UEber den Autor 7
Einleitung 17
Was ist theoretische Informatik? 17
UEber 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
Einfuehrung 23
Erste Beispiele 24
Grundlegende Definitionen 27
Symbole und Woerter 27
Die Definition eines DFAs 28
Regulaere Sprachen 30
Die erweiterte UEbergangsfunktion 30
Beispiele regulaerer 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 ??-UEbergaengen 64
Abschlusseigenschaften regulaerer Sprachen 67
Regulaere Ausdruecke 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 beschraenkte 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
Einfuehrung 125
Ein erstes Beispiel 126
Syntaxbaeume 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 Regulaere (Typ-3-)Sprachen 135
Beispiele fuer Typ-3-Sprachen 135
Das Wortproblem fuer 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 aequivalentes Maschinenmodell 150
Deterministisch kontextfreie Sprachen 153
Das Wortproblem fuer kontextfreie Sprachen 154
Abschlusseigenschaften 156
Aufgaben zu kontextfreien Sprachen 157
Kapitel 8 Kontextsensitive und Phasen-Struktur-Sprachen 159
Ein erstes Beispiel 159
Das Wortproblem fuer Typ-1-Sprachen 160
Das Wortproblem fuer Typ-0-Sprachen 161
AEquivalente Maschinenmodelle 162
Typ-0-Sprachen 162
Typ-1-Sprachen 164
Teil III Harte Probleme 167
Kapitel 9 Zeitkomplexitaet von Algorithmen 169
Einfuehrende UEberlegungen 169
Zeit- und Speicherkomplexitaet von Algorithmen 171
Die O-Notation 175
Komplexitaetsklassen von Sprachen 177
Aufgaben zur Komplexitaet 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-Vollstaendigkeit 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-vollstaendiger 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-Vollstaendigkeit 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
AEquivalenzrelationen 242
Ordnungsrelationen 244
Funktionen 245
Aufgaben zu Mengen und Relationen 247
Kapitel 14 Graphen und Baeume 249
Graphen und ihre Eigenschaften 249
Zusammenhaengende Graphen 251
Darstellung von Graphen im Computer 253
Baeume 256
Tourenprobleme 258
Gewichtete Graphen 260
Naeherungsweise Loesung des TSP 261
Aufgaben zu Graphen und Baeumen 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-Buecher 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
Einleitung 17
Was ist theoretische Informatik? 17
UEber 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
Einfuehrung 23
Erste Beispiele 24
Grundlegende Definitionen 27
Symbole und Woerter 27
Die Definition eines DFAs 28
Regulaere Sprachen 30
Die erweiterte UEbergangsfunktion 30
Beispiele regulaerer 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 ??-UEbergaengen 64
Abschlusseigenschaften regulaerer Sprachen 67
Regulaere Ausdruecke 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 beschraenkte 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
Einfuehrung 125
Ein erstes Beispiel 126
Syntaxbaeume 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 Regulaere (Typ-3-)Sprachen 135
Beispiele fuer Typ-3-Sprachen 135
Das Wortproblem fuer 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 aequivalentes Maschinenmodell 150
Deterministisch kontextfreie Sprachen 153
Das Wortproblem fuer kontextfreie Sprachen 154
Abschlusseigenschaften 156
Aufgaben zu kontextfreien Sprachen 157
Kapitel 8 Kontextsensitive und Phasen-Struktur-Sprachen 159
Ein erstes Beispiel 159
Das Wortproblem fuer Typ-1-Sprachen 160
Das Wortproblem fuer Typ-0-Sprachen 161
AEquivalente Maschinenmodelle 162
Typ-0-Sprachen 162
Typ-1-Sprachen 164
Teil III Harte Probleme 167
Kapitel 9 Zeitkomplexitaet von Algorithmen 169
Einfuehrende UEberlegungen 169
Zeit- und Speicherkomplexitaet von Algorithmen 171
Die O-Notation 175
Komplexitaetsklassen von Sprachen 177
Aufgaben zur Komplexitaet 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-Vollstaendigkeit 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-vollstaendiger 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-Vollstaendigkeit 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
AEquivalenzrelationen 242
Ordnungsrelationen 244
Funktionen 245
Aufgaben zu Mengen und Relationen 247
Kapitel 14 Graphen und Baeume 249
Graphen und ihre Eigenschaften 249
Zusammenhaengende Graphen 251
Darstellung von Graphen im Computer 253
Baeume 256
Tourenprobleme 258
Gewichtete Graphen 260
Naeherungsweise Loesung des TSP 261
Aufgaben zu Graphen und Baeumen 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-Buecher 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