Vorwort
Das vorliegende Buch ist aus einem Skript zur Vorlesung Informatik IV an der Universität Ulm hervorgegangen. Diese Vorlesung richtet sich an Informatik-Studierende im Grundstudium und soll die wesentlichen Grundlagen der Theoretischen Informatik vermitteln.
Bei der Umgestaltung des Vorlesungsskripts zum Buch wurde natürlich einiges verändert, jedoch habe ich darauf geachtet, dass die ursprüngliche Kompaktheit der Darstellung nicht verloren ging. Das Buch behandelt drei unterschiedliche Teilbereiche der Theoretischen Informatik (Automatentheorie und Formale Sprachen, Berechenbarkeitstheorie, Komplexitätstheorie), wobei es mir insbesondere darum ging, die Querbezüge zwischen diesen Gebieten aufzuzeigen.
Ich hoffe, dass Nina, Saskia und Verena unter diesem Buchprojekt nicht allzu sehr gelitten haben.
Ulm, Januar 1992
U. Schöning
Vorwort zur zweiten Auflage
Aufgrund verschiedener Leserzuschriften - für die ich mich herzlich bedanke - habe ich einige Textpassagen überarbeitet und Tippfehler beseitigt.
Ulm, Herbst 1994
U. S.
Vorwort zur dritten Auflage
Das Buch wird von vielen Kollegen als Grundlage für ihre Vorlesungen verwendet. Aus diesen Erfahrungen heraus sind ein Reihe von Vorschlägen, auch von Studierenden, bei mir eingegegangen, wie das Material noch sinnvoll ergänzt oder anders gestaltet werden könnte. In der dritten Auflage habe ich mehrere derartige Erweiterungen eingearbeitet, wie zum Beispiel den Komplementabschluss der kontextsensitiven Sprachen, die Greibach- und Kuroda-Normalform, weitere Unentscheidbarkeitsergebnisse für kontextfreie Sprachen, einen Beweis für die Äquivalenz von LOOP-Berechenbarkeit und primitiver Rekursivität, einen Hinweis auf das 10. Hilbertsche Problem, weitere NP-Vollständigkeitsresultate, sowie eine etwas anders gestaltete Darstellung der Ackermann-Funktion. Ferner wurde das Literaturverzeichnis aktualisiert.
Ich bedanke mich herzlich bei allen, die mir Anregungen gegeben haben. Ulm, Sommer 1997
U. S.
Vorwort zur vierten Auflage
In der vierten Auflage wurde der Text auf die neue Rechtschreibung umgestellt sowie einige kleinere Textkorrekturen und -ergänzungen durchgeführt.
Ulm, Sommer 2000
U. S.
Vorwort zur fünften Auflage
In der fünften Auflage wurden einige kleinere Fehler und Ungenauigkeiten ausgemerzt (von denen es leider immer noch welche gab).
Ulm, Frühjahr 2008
U.S.