Dirk Hoffmann
Theoretische Informatik
Theoretische Informatik
4
Vorwort
6
Inhaltsverzeichnis
8
1 Einfu?hrung
12
1.1 Was ist theoretische Informatik?
12
1.2 Zuru?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 Natu?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.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.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 fu?r reguläre Sprachen
173
4.3.3 Satz von Myhill-Nerode
175
4.3.4 Reguläre Ausdru?cke
177
4.4 Kontextfreie Sprachen
180
4.4.1 Definition und Eigenschaften
180
4.4.2 Normalformen
180
4.4.3 Pumping-Lemma fu?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 Ausdru?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.6 Alternative Berechnungsmodelle
296
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-Kalku?l
350
7.1.2 Rechnen im O-Kalku?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 Abku?rzungsverzeichnis
402
C Glossar
404
Literaturverzeichnis
420
Namensverzeichnis
424
Sachwortverzeichnis
426
© 2009-2024 ciando GmbH