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.
- Woeginger: The P-versus-NP page. Eindhoven University of Technology, 2016
- Sammlung von Informationen zum P versus NP Problem, darunter historische Überblicke, Cartoons, launige Kommentare und zahlreiche Publikationen, die behaupten, das Problem gelöst zu haben. Leider ist der Autor der Seite mittlerweile verstorben, so dass unklar ist wie lange sie noch zugänglich ist.