Vorwort

Die Theoretische Informatik ist eine Disziplin, die wegen ihrer mathematischen Natur von vielen Studenten als schwierig und teilweise auch uninteressant empfunden wird. Ein Grund für Letzteres ist, dass die Verbindungen zwischen theoretischer und praktischer Informatik oft erst in späteren Vorlesungen deutlich werden und damit in einführenden Veranstaltungen die Motivation fehlt. Eine besondere Schwierigkeit stellt häufig auch das Führen von Beweisen in Übungs- oder Klausuraufgaben dar. Immer wieder bin ich von Studenten gefragt worden, ob es ein Lehrbuch Theoretische Informatik gibt, das auch gelöste Übungsaufgaben enthält. Da ich auf dem Markt nichts Vergleichbares finden konnte, entstand die Idee, ein entsprechendes Buch zu verfassen. Meine Ziele dabei waren, den Stoff einer Grundvorlesung Theoretische Informatik

knapp, präzise und gut verständlich zu präsentieren,
durch Anwendungen zu motivieren,
durch Aufgaben zu vertiefen

und dabei auf alle wichtigen Techniken einzugehen, die für ein selbstständiges Arbeiten notwendig sind.

Der Text beginnt daher im ersten Kapitel mit dem Abschnitt Beweistechniken, der die Grundlage für alle folgenden Abschnitte bildet. Die oft sehr abstrakten Begriffe der Theoretischen Informatik werden - wenn möglich - zuerst anhand von einfachen Beispielen erläutert, bevor sie formal definiert werden. Damit Sie sich im Text besser orientieren können, sind diese formalen Definitionen grau unterlegt, die definierten Begriffe kursiv gesetzt. Vor schwierigen oder besonders wichtigen Beweisen habe ich zunächst die Beweisidee dargestellt. Auch schwierige Beweise enthalten oft eine Idee, die vergleichsweise einfach zu begreifen und im Beweis deutlich schneller wiederzufinden ist, wenn Sie die Beweisidee bereits verstanden haben. Durch dieses schrittweise Vorgehen vom Einfachen zum Komplizierten möchte ich nicht nur das Verständnis erleichtern, sondern auch eine höhere Lesegeschwindigkeit ermöglichen, so dass Sie sich in weniger Zeit mehr Wissen aneignen können.

Wo immer sich ein Anknüpfungspunkt ergibt, habe ich Anwendungen dargestellt. Insbesondere dem Compilerbau sind zwei optionale Abschnitte mit Programmierbeispielen gewidmet. Auf diese Weise möchte ich zeigen, dass die Theoretische Informatik kein Selbstzweck ist, sondern auch für praktisch relevante Probleme zu wichtigen und grundlegenden Erkenntnissen führt.

Jeder Abschnitt, der nicht optional ist, enthält unterschiedlich anspruchsvolle Übungsaufgaben, deren Schwierigkeitsgrad mit -- (sehr leicht) bis *** (sehr schwierig) gekennzeichnet ist. Darunter befinden sich auch Aufgaben, bei denen ein Fehler in einem Argument entlarvt werden soll, das auf den ersten Blick sehr plausibel erscheint. Viele dieser Aufgaben habe ich an der Universität Ulm als Übungs- oder Klausuraufgaben gestellt. Die Lösungen der Aufgaben sollen Ihnen helfen,

die Korrektheit der eigenen Lösung zu überprüfen,
Lösungen korrekt aufzuschreiben und Beweise selbst zu formulieren.

Um auch auf mündliche Prüfungen gut vorzubereiten, schließt jedes Kapitel mit einer Reihe typischer Prüfungsfragen ab. Hierbei habe ich versucht, den Ablauf einer mündlichen Prüfung dadurch wiederzugeben, dass jeweils mehrere Fragen aufeinander aufbauen. In einer mündlichen Prüfung werden typischerweise zuerst ein paar einfache, einleitende Fragen zum Thema gestellt. An die Antworten des Prüflings können dann weitere Fragen anknüpfen. Dieser Zyklus wiederholt sich, bis alle relevanten Themen behandelt sind oder die Zeit abgelaufen ist. Dabei werden die Fragen zu einem Thema weniger umfangreich sein als in den Prüfungsfragen.

Bei der Auswahl des Stoffs habe ich mich an den Themen orientiert, die an den meisten deutschen Universitäten in einer einsemestrigen Grundvorlesung Theoretische Informatik behandelt werden. Dabei habe ich versucht, die wichtigen Grundzüge der Theorie sowie Themen, die für spätere Vorlesungen im Hauptstudium von Bedeutung sind, ausführlich darzustellen. Dagegen habe ich technische Details sowie Dinge, bei denen der Leser wenig Neues lernt, kurz gehalten. Für manche Aussagen in der Automatentheorie habe ich anstelle eines Beweises lediglich das Beweisprinzip skizziert, da solche Beweise oft sehr technisch sind und die Beweisidee nur noch schwer zu erkennen ist. Abschnitte, die mit (+) gekennzeichnet sind, sind optional. Dies sind Abschnitte, die Themen enthalten, die über den Stoff einer Grundvorlesung hinausgehen, oder solche, die häufig behandelt, jedoch zum Verständnis der grundlegenden Konzepte nicht notwendig sind.

Unter der Adresse www.theoinf.de finden Sie weitere Informationen zum Buch und eine Liste eventueller Korrekturen.

Für Hinweise, Lob und Kritik bedanke ich mich bei meinen Kollegen in Ulm und bei den vielen Studenten, die zur Prüfungsvorbereitung frühe Versionen des Manuskripts gelesen und deren Kommentare ich in allen folgenden Versionen berücksichtigt habe. Weiterhin bedanke ich mich beim Elsevier-Verlag für die erfolgreiche Zusammenarbeit.