Theoretische Informatik

Nach der obligatorischen mathematischen Einführung wird die RAM und die Programmiersprache PASCALLI (eine PASCAL-ähnliche Sprache) eingeführt. Diese wird in den späteren Kapiteln immer wieder benutzt, um Algorithmen niederzuschreiben oder Beweise zu verdeutlichen.

Die folgenden Kapitel beschäftigen sich mit Turing-Maschinen, Entscheidbarkeit und Aufzählbarkeit, Berechnungskomplexität (speziell die Klassen P und NP), Boolsche Funktionen (Aussagenlogik, kombinatorische Schaltkreise) und endlichen Automaten.

Als achtes und letztes Kapitel drangeklebt, werden die Grammatiken und formalen Sprachen vermittelt. Hier habe ich noch kein Buch gefunden, daß einen guten Übergang zu diesem Thema findet.

Jedes Kapitel wird durch eine Aufgabensammlung abgeschlossen. Weder sind die Aufgaben in Schwierigkeitsgrade unterschieden noch gibt es deren Lösungen bzw. Lösungsansätze. Daher halte ich das Buch keineswegs für zum Selbststudium geeignet (woher soll man schließlich wissen, ob die selbsterarbeitete Lösung richtig ist? Concrete Mathematics wird wohl weiterhin ein Unikat in dieser Hinsicht bleiben).

Für uns Hamburger StudentInnen halte ich das Buch aufgrund seines anderen Formalismus und Stoffvermittlung für weniger geeignet. Bleibt aber noch zu vermerken, daß in Würzburg bereits im Grundstudium Stoff vermittelt wird, der bei uns erst im Hauptstudium drankommt. Da erfreut es ein (Ex-)SRA-Mitglied, daß die Erweiterung des theoretischen Anteils im Grundstudium von allen Mitgliedern (na ja, sagen wir mal fast allen), wie es das neue Curriculums-Konzept des SRA vorschlägt, positiv aufgenommen wurde, wenn aber noch nicht bis zu allen (na ja, sagen wir mal fast allen) durchgedrungen ist, daß dies der Grund für die Stundenkürzung der technischen und praktischen Informatik ist und nicht etwa die Einführung der human-wissenschaftlichen Informatik-Säule (deren Stunden auf die Verkürzung des Ergänzungsfaches zurückzuführen ist). Nun denne, ich mache mich jetzt auf den Weg in die ,,spannische Villa`` (na ja, sagen wir mal ...).

Fin

WAGNER
Einführung in die Theoretische Informatik
240 Seiten, DM 38, Springer
ISBN 3-540-58139-1