Theoretische Grundlagen der Informatik
von: Rolf Socher
Carl Hanser Fachbuchverlag, 2005
ISBN: 9783446404236
Sprache: Deutsch
188 Seiten, Download: 1920 KB
Format: PDF, auch als Online-Lesen
| Vorwort | 6 | ||
| Inhaltsverzeichnis | 7 | ||
| 1 Einleitung | 9 | ||
| 2 Endliche Automaten | 14 | ||
| 2.1 Einführung | 14 | ||
| 2.2 Grundlegende Begriffe | 15 | ||
| 2.3 Deterministische endliche Automaten | 17 | ||
| 2.4 Minimierung endlicher Automaten | 22 | ||
| 2.5 Nichtdeterministische endliche Automaten | 28 | ||
| 2.6 Automaten mit Übergängen | 35 | ||
| 2.7 Anwendung endlicher Automaten | 38 | ||
| 3 Reguläre Sprachen | 43 | ||
| 3.1 Reguläre Ausdrücke | 43 | ||
| 3.2 Das Pumping- Lemma | 51 | ||
| 3.3 Der Satz von Myhill- Nerode | 53 | ||
| 3.4 Abgeschlossenheitseigenschaften regulärer Sprachen | 57 | ||
| 4 Grammatiken | 63 | ||
| 4.1 Grundlegende Definitionen | 64 | ||
| 4.2 Reguläre Grammatiken | 66 | ||
| 4.3 Kontextfreie Grammatiken | 72 | ||
| 4.4 Normalformen für kontextfreie Grammatiken | 73 | ||
| 4.5 Eigenschaften kontextfreier Sprachen | 80 | ||
| 4.6 Kellerautomaten | 84 | ||
| 4.7 Kontextfreie Grammatiken und Kellerautomaten | 91 | ||
| 4.8 Typ- 1- und Typ- 0- Grammatiken | 94 | ||
| 4.9 Die Chomsky- Hierarchie | 96 | ||
| 5 Turing- Maschinen und Berechenbarkeit | 100 | ||
| 5.1 Einführung | 100 | ||
| 5.2 Das Basismodell | 102 | ||
| 5.3 Modifikationen des Basismodells | 107 | ||
| 5.4 Linear beschränkte Automaten und Typ- 1- Grammatiken | 112 | ||
| 5.5 Die Sprachklassen der Chomsky- Hierarchie | 113 | ||
| 5.6 Turing- Berechenbarkeit | 115 | ||
| 5.7 Andere Berechnungskonzepte | 118 | ||
| 5.8 Die universelle Turing- Maschine | 127 | ||
| 5.9 Die Churchsche These | 129 | ||
| 6 Entscheidbarkeit | 133 | ||
| 6.1 Entscheidbarkeit und Semi- Entscheidbarkeit | 133 | ||
| 6.2 Unentscheidbare Probleme | 137 | ||
| 6.3 Das Halteproblem | 140 | ||
| 6.4 Reduktionstechniken | 144 | ||
| 6.5 Der Satz von Rice | 149 | ||
| 7 Komplexität | 151 | ||
| 7.1 Einführung | 151 | ||
| 7.2 Komplexität von Algorithmen | 153 | ||
| 7.3 Die Klassen P und NP | 160 | ||
| 7.4 NP- Vollständigkeit | 170 | ||
| 8 Anhang: Mathematische Grundlagen | 179 | ||
| 8.1 Mengen | 179 | ||
| 8.2 Relationen | 179 | ||
| 8.3 Graphen | 181 | ||
| 8.4 Aussagenlogik | 183 | ||
| LITERATURVERZEICHNIS | 185 | ||
| Mehr eBooks bei www.ciando.com | 0 |