Informatik III (Theoretische Informatik) - Übersicht

Assistenten: Prof. Dr. Christian Becker-Asano und Moritz Göbelbecker

Termine

Vorlesung: Montag und Mittwoch 14:15-16:00
Übungen: Donnerstag 12:15-14:00 und/oder Freitag 8:15-10:00
Besprechung Probeklausur (Link): Donnerstag, 21. Februar 12:00-14:00. Gebäude 101, Hörsaal 00-036
Klausur: Freitag, 1. März, 2013, 14:00-16:00 (s.t.). Gebäude 101, Hörsääle 00-026 und 00-036.
Raumaufteilung wird noch bekanntgegeben.

Ort

Vorlesung: Gebäude 101, Hörsaal 00-036
Übungen: je nach Übungsgruppe in einem der folgenden Räume:

Gebäude 051, Hörsaal 03 026 (Gruppe 1);
Gebäude 051, Seminarraum 00-034 (Gruppe 2);
Gebäude 052, Hörsaal 02-017 (Gruppe 3);
Gebäude 051, Hörsaal 03-026 (Gruppe 4);
Gebäude 078, Raum 00-014 (Gruppe 8).

Sprache

Die Vorlesung wird auf Deutsch gehalten. Übungen und Klausur sind in deutscher oder englischer Sprache anzufertigen.

Lernziel und Vorlesungsinhalt

Die Vorlesung gibt eine eingehende Einführung in die Theoretische Informatik. Neben verschiedenen formalen Präzisierungen des Berechenbarkeitsbegriffs, werden als Themen endliche Automaten, formale Sprachen und Grammatiken, Entscheidbarkeit und Komplexitätstheorie behandelt. Das Lernziel der Vorlesung ist es, Studierende dazu zu befähigen, intuitive Konzepte wie Algorithmen, Berechenbarkeit, Komplexität formal und präzise zu fassen und deren grundsätzliche Bedeutung für die Lösbarkeit von Problemen mit Hilfe von Rechnern zu verstehen.

Kreditpunkte

8 ECTS-Punkte

Voraussetzungen

Die Vorlesung richtet sich an Informatik-Studenten im Bachelor-Studiengang. Vorausgesetzt werden informatische und mathematische Grundkenntnisse entsprechend den Vorlesungen Informatik I, Informatik II und Diskrete algebraische Strukturen.

Übungen

Jeden Montag wird ein Übungsblatt in der Vorlesung ausgelegt bzw. ins Netz gestellt, das innerhalb einer Woche bearbeitet werden muss. Die Abgabe der Lösungen erfolgt am darauffolgenden Montag vor der Vorlesung im Hörsaal oder per Email an Prof. Dr. Christian Becker-Asano. Die Lösungen werden in den Übungsgruppen besprochen; außerdem werden dort Fragen zum Vorlesungsstoff beantwortet.

Der Sinn von Übungsaufgaben besteht darin, sich mit dem Inhalt der Vorlesung auseinanderzusetzen und den Stoff der Vorlesung zu vertiefen. Aus diesem Grund werden (vollständig oder teilweise) abgeschriebene Abgaben nicht akzeptiert, d.h. das Abschreiben wie das Abschreiben-Lassen von Lösungen können dazu führen, dass die abgegebene Lösung nicht korrigiert und damit als nicht bearbeitet gewertet wird. Im Wiederholungsfall wird die Zulassung zur Prüfung nicht erteilt.

Zulassung zur Prüfung und Klausur

Voraussetzung für die Zulassung zur Prüfung ist, dass mindestens 50% der möglichen Punkte in den Übungen erzielt werden. Ferner soll jeder Student mindestens zweimal in den Übungen eine Aufgabe vorrechnen.

Nebenfachstudenten nehmen auch an der Klausur teil. Eine gesonderte mündliche Prüfung wird es nicht geben.

Begleitende Literatur

Uwe Schöning: Theoretische Informatik kurzgefasst, Spektrum Hochschultaschenbuch, 5. Auflage, 2008, Spektrum Akademischer Verlag, Heidelberg. ISBN 978-3827418241.
Ingo Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung, 2. Auflage 1999, Teubner, Stuttgart. ISBN 3-5191-2123-9.
Harry Lewis, Christos Papadimitriou: Elements of the Theory of Computation, 2. Auflage, 1997, Prentice Hall, New Jersey. ISBN 0-13-262478-8.
John Hopcroft, Jeffrey Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, 3. Auflage 1994, Addison Wesley, Bonn. ISBN 3-89319-744-3.
Uwe Schöning, Hans A. Kestler: Mathe-Toolbox - Mathematische Notationen, Grundbegriffe und Beweismethoden, 2010, Lehmanns Media. ISBN-13 978-3865413697.