Das Buch "Theoretische Grundlagen der Informatik" ist als DinA5-gebundenes, recht schmales Softcover mit 187 Seiten und einer CD erschienen.

Das Buch besteht aus acht Kapiteln und beginnt mit dem einleitenden ersten Kapitel, in dem erklärt wird, wofür Theorie gebraucht wird und wo die Grenzen der Theorie sind.

Das zweite Kapitel behandelt die Automatentheorie, also Automaten, die verschiedene Zustände annehmen können. Detaillierter betrachtet werden hier deterministische endliche Automaten, Minimierung endlicher Automaten, nichtdeterministische endliche Automaten mit und ohne Epsilon-Übergängen. Zum Schluss werden dann anhand von Praxisbeispielen endliche Automaten noch einmal genauer erklärt, um das Thema Automaten verständlicher zu machen.

Das dritte Kapitel behandelt reguläre Sprachen sowie die abstrakte Beschreibung einer Sprache, wobei man sich hier keine gesprochene Sprache vorstellen sollte, sondern in der Informatik eher so etwas wie beschriebene Sprachen, die verwendet werden, um Automaten zu beschreiben. Hier werden als Erstes reguläre Ausdrücke behandelt, im Anschluss daran die nicht regulären Sprachen. Um dies noch weiter zu führen, werden am Ende des Kapitels die Abgeschlossenheitseigenschaften regulärer Sprachen erklärt.

Das vierte Kapitel handelt von Grammatiken, also dem Aufbau einer Sprache. Dies wird dann unter anderem anhand der Grammatiken der Programmiersprache Prolog gezeigt. Als Erstes werden die Grundlagen gezeigt, als Nächstes folgen dann die regulären Grammatiken und kontextfreie Grammatiken. Für die kontextfreien werden die Normalformen und die Eigenschaften behandelt, dies auch im Zusammenhang mit Automaten.

Das fünfte Kapitel handelt von Turing-Maschinen und Berechenbarkeit. Dabei handelt es sich um ein mathematisches Modell, das mit nur drei Zuständen die Probleme lösen kann, die auch ein Computer löst. Nach einer kurzen Einführung werden das Basismodell und dann die möglichen Modifikationen des Basismodells erklärt. Anschließend wird gezeigt, wie man Turing-Maschinen berechnet und welche weiteren Berechnungskonzepte es gibt. Zur besseren Darstellung wird am Ende eine universelle Turing-Maschine erklärt.

Das sechste Kapitel handelt allgemein von Entscheidbarkeit. Damit ist die Behandlung der Frage gemeint, ob ein Problem überhaupt durch ein Modell gelöst werden kann oder nicht. Diese Entscheidbarkeiten oder Semi-Entscheidbarkeiten werden anhand unterscheidbarer Probleme - unter anderem dem Halteproblem - behandelt. Das Halteproblem, das besser als Endlosschleife bekannt ist, wird als Beispiel gebracht für ein Problem, das nicht über einen Algorithmus abgefangen werden kann.

Das letzte Kapitel behandelt Komplexitäten. Damit ist gemeint, dass man durch Algorithmen lösbare Probleme berechnet, um zu sehen, wie lange sie zum Lösen eines Problems benötigen. Dies wird unter anderen anhand der Türme von Hanoi erklärt, einer Übung, die wahrscheinlich jeder Informatikstudent aus seinem Studium kennen wird.

Das achte Kapitel ist an sich ein Anhang, in dem noch einmal kurz die wichtigsten mathematischen Grundlagen gezeigt werden, die für dieses Buch benötigt werden. Es handelt sich hier um eine ausführlichere Formelsammlung, die aber nicht dem Umfang des Studienstoffs gerecht wird.
Auf der beiliegenden CD ist ein Programm, mit dem man sowohl Automaten also auch Grammatiken und reguläre Ausdrücke recht einfach darstellen kann. Angenehm ist, dass man sich dann zu diesem Automaten den Quelltext in den Sprachen Prolog und Java anzeigen lassen kann.

Zusammenfassend kann man sagen, dass es sich grundsätzlich um ein recht gutes Buch handelt, um sich vor dem Studium etwas vorzubereiten und anzusehen, was man an mathematischen Grundlagen wissen sollte. Für das Studium selber reicht es aber leider nicht aus, da viele Themen fehlen oder zu kurz kommen, wie zum Beispiel boolesche Algebra und Beweisführung.