Inhalt

Theoretische Informatik

Organisatorisches

Pflichtveranstaltung im 4. Semester (Sommer) des Studiengangs Bachelor Informatik. Die Materialien zur Veranstaltung werden über den Moodle-Kurs "THI" bereitgestellt.

Inhalt

Während die meisten Teilbereiche der Informatik sich der handwerklichen Frage widmen, wie ein konkretes Problem mit bestimmten konkreten Hilfsmitteln gelöst werden kann, stellt die theoretische Informatik die philosophische Frage, welche Probleme überhaupt mit Rechnern gelöst werden können und wie man diese Probleme klassifizieren kann.

Die Vorlesung gibt eine Einführung in folgende Fragestellungen:

Berechenbarkeit
Welche Probleme lassen sich überhaupt mit Rechnern lösen?
Komplexität
Welche Probleme lassen sich effizient lösen? Was bedeutet "effizient"?
formale Sprachen
Wie lassen sich Grammatiken klassifizieren? Welche dieser Klassen sind geeignet, moderne Programmiersprachen zu beschreiben?

Klausur

Die Fachprüfung erfolgt über eine benotete schriftliche Klausur. Zugelassene Hilfsmittel sind ein Buch Ihrer Wahl und ein handschriftlicher Din A4 Spickzettel. Ausdrücklich nicht zugelassen sind die Vorlesungsunterlagen.

Literatur

Bitte beachten Sie, dass die Einschätzung der Literatur mein subjektiver Eindruck ist. Erfahrungsgemäß weichen die Meinungen der Studierenden darüber, welche Bücher gut sind, erheblich von den Meinungen der Lehrenden ab!

Asteroth, Baier: Theoretische Informatik. Pearson Studium 2002
Gutes Einführungswerk, das den Schwerpunkt auf eine verständliche Darstellung und zahlreiche Beispiele setzt. Als einziges Buch dieser Liste in meinen Augen ohne Einschränkungen "fachhochschultauglich".
Schöning: Theoretische Informatik - kurzgefasst. Spektrum 1995
Knappes Kompaktwerk. Die Komplexitätstheorie ist besonders knapp gehalten. Dafür wird als Bonbon der berühmte "Gödelsche Satz" bewiesen, der in den meisten Lehrbüchern zum Thema merkwürdigerweise nicht einmal erwähnt wird.
Sipser: Introduction to the Theory of Computation. PSW Publishing 1997
Dieses zurecht vielgelobte Buch hat das Buch von Hopcroft/Ullmann als "Standard"-Lehrwerk zum Thema abgelöst. Der Schwerpunkt liegt auf der Vermittlung der Ideen, so wird z.B. formalen Beweisen immer eine "Beweisidee" vorangestellt.
Hopcroft, Motwani, Ullmann: Introduction to Automata Theory, Languages and Computation. Addison Wesley 2001 (2nd edition)
Die erste Auflage von 1979 galt lange Zeit als das "Standard"-Lehrwerk zum Thema. Die komplett überarbeitete zweite Auflage richtet sich an Studenten im Grundstudium und ist entsprechend didaktisch aufbereitet.