|
|
Bei Amazon kaufen|
Umschlagtext
Dieses Lehrbuch stellt eine Einführung in die theoretischen Grundlagen der Informatik dar. Es beschränkt sich auf die klassischen Themen: formale Sprachen, endliche Automaten und Grammatiken, Berechenbarkeit und Entscheidbarkeit, Komplexität und Logik. Das Konzept der Transformation zwischen den verschiedenen Formalismen zieht sich wie ein roter Faden durch das gesamte Buch. Auf eine anschauliche Vermittlung der Begriffe und Methoden der theoretischen Informatik und ihre Vertiefung in Aufgaben und Programmierprojekten wird großer Wert gelegt. Die dem Buch beiliegende CD enthält das Lernprogramm „Machines", mit dem endliche Automaten, Kellerautomaten, Grammatiken, reguläre Ausdrücke und Turing-Maschinen mit einer komfortablen grafischen Oberfläche realisiert und visualisiert werden können.
Zur Vertiefung auf der CD: • Lernprogramm "Machines" (lauffähig unter Windows, Linux, Mac OS) • aktuelle Java-Version 1.4 • Prolog-Programme Dr. Rolf Socher ist Professor an der FH Oldenburg/Ostfriesland/Wilhelmshaven. Seine Lehrgebiete sind Theoretische Informatik, Mathematik, Logische Programmierung, Wissensbasierte Systeme und Optimierung. Er ist Autor mehrerer Bücher. Rezension
Anschauliche Darstellung und Einführung in die grundlegenden Themen der theoretischen Informatik. Besonders das auf der CD befindliche Programm "Machines" zur Visualisierung des behandelten Stoffes überzeugt.
Florian Schimandl, lehrerbibliothek.de Inhaltsverzeichnis
1 Einleitung
2 Endliche Automaten 2.1 Einführung 2.2 Grundlegende Begriffe 2.3 Deterministische endliche Automaten 2.4 Minimierung endlicher Automaten 2.5 Nichtdeterministische endliche Automaten 2.6 Automaten mit e-Übergängen 2.7 Anwendung endlicher Automaten 3 Reguläre Sprachen 3.1 Reguläre Ausdrücke 3.2 Das Pumping-Lemma 3.3 Der Satz von Myhill-Nerode 3.4 Abgeschlossenheitseigenschaften regulärer Sprachen 4 Grammatiken 4.1 Grundlegende Definitionen 4.2 Reguläre Grammatiken 4.3 Kontextfreie Grammatiken 4.4 Normalformen für kontextfreie Grammatiken 4.5 Eigenschaften kontextfreier Sprachen 4.6 Kellerautomaten 4.7 Kontextfreie Grammatiken und Kellerautomaten 4.8 Typ-1- und Typ-O-Grammatiken 4.9 Die Chomsky-Hierarchie 5 Turing-Maschinen und Berechenbarkeit 5.1 Einführung 5.2 Das Basismodell 5.3 Modifikationen des Basismodells 5.4 Linear beschränkte Automaten und Typ-1-Grammatiken 5.5 Die Sprachklassen der Chomsky-Hierarchie 5.6 Turing-Berechenbarkeit 5.7 Andere Berechnungskonzepte 5.8 Die universelle Turing-Maschine 5.9 Die Churchsche These 6 Entscheidbarkeit 6.1 Entscheidbarkeit und Semi-Entscheidbarkeit 6.2 Unentscheidbare Probleme 6.3 Das Halteproblem 6.4 Reduktionstechniken 6.5 Der Satz von Rice 7 Komplexität 7.1 Einführung 7.2 Komplexität von Algorithmen 7.3 Die Klassen P und NP 7.4 NP-Vollständigkeit 8 Anhang: Mathematische Grundlagen 8.1 Mengen 8.2 Relationen 8.3 Graphen 8.4 Aussagenlogik Literaturverzeichnis Sachwortverzeichnis Weitere Titel aus der Reihe Informatik interaktiv |