Theoretische Informatik

Literatur

 aufwärts

Berechenbar­keitstheorie, Komplexitäts­theorie, 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 über­sicht­lich dargestellt; es enthält viele Beispiele und Übungs­aufgaben zu jedem Kapitel.

Ein anspruchs­volles Buch über formale Sprachen und Automaten sowie Berechenbar­keit 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 Berechnungs­modelle, die genauso universell wie die Turing­maschine sind.

Auf die wesent­lichsten Aspekte der formalen Sprachen und Automaten konzentriert sich das Buch

[Hed 03]U. Hedtstück: Einführung in die Theoretische Informatik. 2. Auflage, Oldenbourg (2003)

Behandelt werden reguläre Sprachen und endliche Automaten, kontextfreie Sprachen und Stack­automaten sowie die Turing­maschine.

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 Berechenbar­keits- und die Komplexitäts­theorie werden ausführlich behandelt. Jeder Abschnitt des Buches schließt mit Übungs­aufgaben ab, in denen das Gelernte sofort angewendet werden kann. Die hohe didaktische Qualität des Buches spiegelt die langjährige Lehr­erfahrung der Autoren wider.

Ein in seiner Reich­haltig­keit großartiges Buch ist

[Hof 11]D.W. Hoffmann: Theoretische Informatik. 2. Auflage, Hanser (2011)

An ein Kapitel zu den mathe­matischen Grundlagen schließt sich ein ausführliches Kapitel über Logik an; es folgen die klassischen Inhalte zu den Themen formale Sprachen und Automaten, Berechenbar­keits- und Komplexitäts­theorie. 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 Übungs­aufgaben.

Eine kompakte Darstellung der Themen formale Sprachen und Automaten, Berechenbar­keit 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üfungs­fragen, die typischer­weise 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 Turing­maschinen werden die Berechenbar­keit 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 Vorlesungs­reihe eingeteilt in Lektionen aus den Bereichen formale Sprachen und Automaten sowie Berechenbar­keit 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 über­sicht­lich. Die Darbietung des Stoffs wird ergänzt durch einen Satz von Hausaufgaben sowie durch eine Sammlung von Übungs­aufgaben. Zu den schwierigeren Übungs­aufgaben 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, Berechenbar­keit und Komplexität, sowie ferner Aussagen- und Prädikaten­logik. Jedes Kapitel enthält eine umfangreiche Sammlung von Übungs­aufgaben.

Das Wichtigste aus den Gebieten formale Sprachen und Automaten, Berechenbar­keits- und Komplexitäts­theorie, dargestellt in Kürze, aber dennoch fundiert und fern jeder Ober­flächlich­keit, 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, über­sicht­lich und klar dargeboten.

In seiner Präzision und didaktischen Klarheit unüber­troffen ist

[Sip 96]M. Sipser: Introduction to the Theory of Computation. PWS Publishing Company (1996)

Das Buch behandelt die Themen mathe­matische Grundlagen, formale Sprachen und Automaten, Berechenbar­keitstheorie und in sehr umfassender Darstellung Komplexitäts­theorie. Jedes Kapitel enthält Übungs­aufgaben, 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, Berechenbar­keit und Komplexität. Jedes Kapitel enthält einige Übungs­aufgaben.

Eine ausführliche Darstellung der Themen reguläre Sprachen und endliche Automaten, kontextfreie Sprachen und Stack­automaten sowie die Turing­maschinen und Berechenbar­keit 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 Übungs­aufgaben.

Ausgehend von der Theorie der Berechenbar­keit 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 kontext­freien 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 Übungs­aufgaben, aber einen Satz von Prüfungs­fragen.

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 14.02.2007   Updated: 13.05.2016
Valid HTML 4.01 Transitional