Berechenbarkeitstheorie, Komplexitätstheorie, formale Sprachen und Automaten – in dieser Reihenfolge behandelt das Buch
[AB 02] A. Asteroth, C. Baier: Theoretische Informatik. Pearson Studium (2002)
die klassischen Themen der theoretischen Informatik. Das Buch ist sehr klar und verständlich geschrieben und übersichtlich dargestellt; es enthält viele Beispiele und Übungsaufgaben zu jedem Kapitel.
Ein anspruchsvolles Buch über formale Sprachen und Automaten sowie Berechenbarkeit ist
[EP 08] K. Erk, L. Priese: Theoretische Informatik. 3. Auflage, Springer (2008)
Teilweise erscheint das Buch sehr technisch, auf der anderen Seite aber werden auch schwierigere Beweise geführt und nicht, wie in anderen Büchern, übergangen. Eine Besonderheit dieses Buches ist ein Kapitel über alternative Berechnungsmodelle, die genauso universell wie die Turingmaschine sind.
Der "Hopcroft-Ullman" war seit den 70er Jahren lange Zeit das Standardwerk zum Thema formale Sprachen und Automaten. Die heutige Ausgabe, unter Mitwirkung von R. Motwani und in sehr guter deutscher Übersetzung, ist
[HMU 02] J.E. Hopcroft, R. Motwani, J.D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. 2. Auflage, Pearson Studium (2002)
Nach wie vor liegt der thematische Schwerpunkt auf den formalen Sprachen und Automaten, aber auch die Berechenbarkeits- und die Komplexitätstheorie werden ausführlich behandelt. Jeder Abschnitt des Buches schließt mit Übungsaufgaben ab, in denen das Gelernte sofort angewendet werden kann. Die hohe didaktische Qualität des Buches spiegelt die langjährige Lehrerfahrung der Autoren wider.
Ein in seiner Reichhaltigkeit großartiges Buch ist
[Hof 11] D.W. Hoffmann: Theoretische Informatik. 2. Auflage, Hanser (2011)
An ein Kapitel zu den mathematischen Grundlagen schließt sich ein ausführliches Kapitel über Logik an; es folgen die klassischen Inhalte zu den Themen formale Sprachen und Automaten, Berechenbarkeits- und Komplexitätstheorie. Was dieses Buch so besonders anschaulich macht, sind die zahlreichen Bezüge zu Anwendungen, zu bereits Bekanntem, zu Analogien aus dem täglichen Leben, ferner die vielen Abbildungen, Beispiele und tabellarischen Übersichten. Zu jedem Kapitel gibt es einen Satz von Übungsaufgaben.
Eine kompakte Darstellung der Themen formale Sprachen und Automaten, Berechenbarkeit und Komplexität findet sich in
[Hol 07] B. Hollas: Grundkurs Theoretische Informatik. Spektrum (2007)
Das Interessante an diesem Buch ist die große Anzahl von Aufgaben und – im Anhang angegebenen – zugehörigen Lösungen. Ferner enthält das Buch zu jedem Kapitel einen Satz von Prüfungsfragen, die typischerweise in einer mündlichen Prüfung gestellt werden.
Im Vordergrund des Buches
[Hro 04b] J. Hromkovič: Theoretische Informatik. 2. Auflage, Teubner (2004)
stehen die algorithmischen Aspekte der theoretischen Informatik. Ausgehend von endlichen Automaten und Turingmaschinen werden die Berechenbarkeit und Komplexität von Problemen dargestellt. Daran schließt sich ein Ausflug in die Algorithmik für schwere Probleme an. Die Theorie der formalen Sprachen wird nicht behandelt.
Wie eine Vorlesungsreihe eingeteilt in Lektionen aus den Bereichen formale Sprachen und Automaten sowie Berechenbarkeit ist das Buch
[Koz 97] D.C. Kozen: Automata and Computability. Springer (1997)
Die Konzentration auf jeweils ein Thema in einer Lektion macht das Buch sehr übersichtlich. Die Darbietung des Stoffs wird ergänzt durch einen Satz von Hausaufgaben sowie durch eine Sammlung von Übungsaufgaben. Zu den schwierigeren Übungsaufgaben gibt es im Anhang Hinweise und Lösungen.
Ausführlich, präzise, teilweise technisch, aber verständlich behandelt das Buch
[LP 81] H.R. Lewis, C.H. Papadimitriou: Elements of the Theory of Computation. Prentice Hall (1981)
die Themen formale Sprachen und Automaten, Berechenbarkeit und Komplexität, sowie ferner Aussagen- und Prädikatenlogik. Jedes Kapitel enthält eine umfangreiche Sammlung von Übungsaufgaben.
Aus der bekannten für Dummies-Reihe stammt
[Schmi 19] R. Schmitz: Theoretische Informatik für Dummies. Wiley (2019)
Das Buch ist genauso eingehend und exakt geschrieben wie die anderen hier aufgeführten Bücher, aber leider auch einschließlich des theoretische-informatik-typischen Symbolformalismus mit Σ, δ, ⊥, ... .
Das Buch enthält viele Beispiele. Zu jedem Kapitel gibt es einen Satz von Aufgaben.
Das Wichtigste aus den Gebieten formale Sprachen und Automaten, Berechenbarkeits- und Komplexitätstheorie, dargestellt in Kürze, aber dennoch fundiert und fern jeder Oberflächlichkeit, findet sich in
[Schö 92] U. Schöning: Theoretische Informatik kurz gefasst. BI-Wissenschaftsverlag (1992)
Das Buch ist sehr gut geschrieben, auf das Wesentliche konzentriert, übersichtlich und klar dargeboten.
In seiner Präzision und didaktischen Klarheit unübertroffen ist
[Sip 96] M. Sipser: Introduction to the Theory of Computation. PWS Publishing Company (1996)
Das Buch behandelt die Themen mathematische Grundlagen, formale Sprachen und Automaten, Berechenbarkeitstheorie und in sehr umfassender Darstellung Komplexitätstheorie. Jedes Kapitel enthält Übungsaufgaben, in denen das Gelernte anzuwenden ist, und Probleme, in denen Beweise gefordert werden.
Das Buch
[Soc 05] R. Socher: Theoretische Grundlagen der Informatik. 2. Auflage, Fachbuchverlag Leipzig (2005)
ist sehr kompakt, aber es behandelt alle wesentlichen Aspekte der Themen formale Sprachen und Automaten, Berechenbarkeit und Komplexität. Jedes Kapitel enthält einige Übungsaufgaben.
Eine ausführliche Darstellung der Themen reguläre Sprachen und endliche Automaten, kontextfreie Sprachen und Stackautomaten sowie die Turingmaschinen und Berechenbarkeit findet sich in
[VW 02] G. Vossen, K.U. Witt: Grundlagen der Theoretischen Informatik mit Anwendungen. 2. Auflage, Vieweg (2002)
Jedes Kapitel enthält einen Satz von Übungsaufgaben.
Ausgehend von der Theorie der Berechenbarkeit und Komplexität geht das Buch
[Weg 99] I. Wegener: Theoretische Informatik -- eine algorithmische Einführung. 2. Auflage, Teubner (1999)
über zu endlichen Automaten, zu formalen Sprachen und hier insbesondere kontextfreien Sprachen. Sehr lesenswert ist bereits die Einleitung, die den Sinn und den Zusammenhang der behandelten Themen deutlich macht. Das Buch ist sehr klar und verständlich geschrieben. Es enthält keine Übungsaufgaben, aber einen Satz von Prüfungsfragen.
Weiter mit: [up]