Uni-Logo

Informatik III (Theoretische Informatik) - Übersicht

Dozenten: Prof. Dr. Bernhard Nebel und Prof. Dr. Georg Lausen

Assistenten: Prof. Dr. Marco Ragni, Kai Simon und Cai-Nicolas Ziegler

Nachklausur

Nachklausur: Einsicht diesen Freitag, den 9. September 2005 von 16:30-17:30 im Geb. 52, Raum 00-016.

Termine

Vorlesung: Mittwoch und Freitag 11:15-12:45
Übungen: wird in der 1. Woche bekannt gegeben
Klausur: Mittwoch, 9. März 2005 von 10:00-12:00
Nachklausur: Montag, 5. September 2005 von 10:00-12:00 im Geb. 101,Raum 036

Ort

Vorlesung: Gebäude 101, Hörsaal 00-036
Übungen: wird in der 1. Woche bekannt gegeben
Klausur: Gebäude 101, Hörsaal 00-026 und Hörsaal 00-036

Sprache

Die Vorlesung wird auf Deutsch gehalten. Übungen und Klausur sind auf Deutsch anzufertigen.

Vorlesungsinhalt

Die Vorlesung gibt eine Einführung in die Theoretische Informatik. Zu Beginn werden mehrere äquivalente präzise Fassungen des Berechenbarkeitsbegriffs eingeführt und es wird gezeigt, dass es Probleme gibt, die nicht algorithmisch lösbar sind. Daran schließt sich eine Einführung in die Komplexitätstheorie, speziell die Theorie der NP-Vollständigkeit, an. Im zweiten Teil der Vorlesung werden dann die Themen endliche Automaten, formale Sprachen und Grammatiken behandelt, wobei die Korrespondenzen zwischen diesen hergestellt werden.

Voraussetzungen

Die Vorlesung richtet sich an Informatik-Studenten im Grundstudium (Diplomstudiengang und Nebenfach) und Studenten im Bachelor-Studiengang. Vorausgesetzt werden informatische und mathematische Grundkenntnisse entsprechend den Vorlesungen Informatik I und Diskrete Algebraische Strukturen.

Übungen

Jeden Freitag wird ein Übungsblatt in der Vorlesung ausgelegt bzw. ins Netz gestellt. Es muss innerhalb einer Woche bearbeitet werden. Die Abgabe der Lösungen erfolgt am darauffolgenden Freitag zu Beginn der Vorlesung bzw. bis 11:15 Uhr in die dafür vorgesehenen Briefkästen im Gebäude 051, Erdgeschoss. Die Lösungen werden in den Übungsgruppen besprochen; außerdem werden dort Fragen zum Vorlesungsstoff beantwortet.

Die Übungsaufgaben sollen dazu dienen, den Stoff der Vorlesung zu vertiefen. Daher stellen sie nur dann eine sinnvolle Ergänzung zur Vorlesung dar, wenn sich jeder Teilnehmer aktiv daran beteiligt. Wir erwarten, dass jeder Teilnehmer

  1. den Stoff der Vorlesung regelmäßig nacharbeitet (ggfs. unter Zuhilfenahme der Literatur aus der Bibliothek),
  2. die Übungsblätter selbstständig allein oder zu zweit bearbeitet und
  3. falls es sinnvoll erscheint, Lösungsansätze mit anderen Teilnehmern diskutiert. (Das Bilden von Lerngruppen wird ausdrücklich gewünscht.)

Abschlussklausur

Die Voraussetzungen für die Zulassung zur Klausur umfassen die Teilnahme an den Übungen sowie die sinnvolle Bearbeitung der Übungsblätter. Sowohl in der ersten wie auch der zweiten Hälfte der Vorlesung müssen jeweils mindestens 50% der Aufgaben sinnvoll bearbeitet worden sein.

Durch Vorrechnen der Aufgaben in den Übungsstunden können Bonuspunkte für die Klausur erworben werden. Hierbei wird für die Anfertigung einer schlüssigen Lösungsskizze an der Tafel die auf dem Übungsblatt vermerkte Punktezahl für die jeweilige Aufgabe gutgeschrieben. Das Klausurergebnis kann hierdurch maximal um 15 Punkte verbessert werden, was bei regulär erreichbaren 100 Punkten einer Verbesserung um eine Note entspricht. Auf diese Weise ist auch ein nachträgliches Bestehen der Klausur mittels Bonuspunkten möglich.

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

Begleitende Literatur

  • Ingo Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung, 2. Auflage 1999, Teubner, Stuttgart. ISBN 3-5191-2123-9.
  • Uwe Schöning: Theoretische Informatik kurzgefasst, Spektrum Hochschultaschenbuch, 3. Auflage, 1997, Spektrum Akademischer Verlag, Heidelberg. ISBN 3-8274-0250-6.
  • 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.