Theoretische Grundlagen der Informatik

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