Die meisten Studierenden der Mathematik oder Informatik werden mir zustimmen, wenn ich in vielen Büchern zu diesem Thema eine lernorientierte, flüssige und konzise Darstellung vermisse. Zu oft wird man mit Definitionen und Theoremen allein gelassen und versteht größere Zusammenhänge erst viel später oder gar nicht.
Christel Baier und Alexander Asteroth schaffen hier, diese Lücke zwischen Theorie, Verständnis und Anwendung zu schließen. Hilfreich sind dabei natürlich die schon im Titel versprochenen Beispiele, die den Text sinnvoll begleiten. Sie sind weder zu leicht gewählt, was dem Thema nicht gerecht würde, noch zu schwer, was dem Verständnis abträglich wäre. Vielmehr konkretisieren sie, zeigen Probleme oder präsentieren die in Prüfungen so oft gebrauchten Gegenbeispiele.
Das Buch läßt sich aber sicherlich nicht auf eine bloße Ansammlung von Beispielen reduzieren. Der Stoff wird formal und genau eingeführt und ist klassisch in Definitionen und Theoreme gegliedert. Dazwischen ist aber viel motivierender Text, der Zusammenhänge aufzeigt und die Problemstellungen unter verschiedenen Anschauungen beleuchtet. Jedes Kapitel wird außerdem von einem Satz Übungen beendet, die ich zur Lernkontrolle sehr brauchbar fand. Besonders gut hat mir auch das Layout gefallen. Algorithmen, Theoreme und Grafiken sind klar abgesetzt, unterlegt und stimmig betitelt. Auf diese Weise kann man auch beim Nachschlagen schnell fündig werden.
Die behandelten Themen umfassen den Kern der Theoretischen Informatik: Turing- und Registermaschinen, sowie Kellerautomaten und die zugehörgen formalen Sprachen. Berechenbarkeit und Komplexität werden ebenso ausführlich behandelt wie das Halteproblem und viele andere klassische Fragestellungen. Darüber hinaus gibt es einige Ausblicke in weitergehende Themen. Den mathematischen Anforderungen des Textes sollte sich jeder Studierende im Grundstudium Mathematik/Informatik gewachsen sehen. Es wird kein Verständis komplizierter Zusammenhänge, Symbole oder Programmiersprachen vorausgesetzt.
Ich hatte Gelegenheit, das Buch während der Vorbereitungen zur Diplomprüfung in Theoretischer Informatik mit anderen zu vergleichen und fand in diesem Antworten auf viele Fragen und eine sorgfältige didaktische Aufbereitung. Meine Bewertung ist deshalb ganz klar fünf Sterne zusammen mit einer Empfehlung an Studierende der Mathematik und Informatik und alle anderen Interessierten.
