Uni-Logo
Algorithms and Complexity
 

Vorlesung
"Informatik III (Theoretische Informatik)"
Wintersemester 2008/09
Prof. Dr. Susanne Albers


Vorlesung

  • Montags, 16-18 Uhr, HS 00-026, Geb. 101
  • Mittwochs, 16-18 Uhr, HS 00-026, Geb. 101
Die erste Vorlesung findet am Montag, den 20. Oktober statt.

Übungen

Hier geht es zur Übungsseite.

Die Anmeldung zu den Übungsgruppen erfolgt in der ersten Vorlesungswoche.

Aktuelles


24. März 2009
Die Klausureinsicht findet statt am Mi, 1. April 2009, von 14.00 - 15.00 Uhr im Raum 079 00 019, Geb. 79.

4. März 2009
Die Klausur wird am 23.03.2009, 14.00 - 16.00 Uhr in den Hörsäälen 026 und 036 im Gebäude 101 stattfinden. Hilfsmittel wie Bücher, Skripte, Taschenrechner, etc. sind nicht zugelassen.

7. Januar 2009
Abgabetermin für Übungsblatt 9 ist Montag, der 12. Januar 2009.

27. Oktober 2008
Die Einteilung der Übungsgruppen ist abgeschlossen. Aufgrund des starken Ungleichgewichts in den Prioritäten konnten leider nicht alle Wünsche berücksichtigt werden. Die Gruppenzuteilung kann hier eingesehen werden.

20. Oktober 2008
Ab sofort ist die Anmeldung zu den Übungen möglich.
<-->

Inhalt der Veranstaltung

Die Vorlesung gibt eine Einführung in die theoretische Informatik. Zunächst erarbeiten wir eine präzise Fassung des Berechenbarkeitsbegriffs. Insbesondere studieren wir das fundamentale Halteproblem, das sich mit der Frage beschäftigt, ob ein Computerprogramm auf einer Eingabe hält. Danach behandeln wir Grundlagen der Komplexitätstheorie, speziell der Theorie der NP-Vollständigkeit. Wir untersuchen die Frage, welche Probleme effizient gelöst werden können und welche Probleme schwer sind. Es folgt eine Untersuchung von endlichen Automaten und Grammatiken. Insbesondere stellen wir eine Verbindung zwischen Grammatikklassen und verschiedenen abstrakten Maschinenmodellen her.

Klausur


Die Vorlesung wird mit einer Klausur abgeschlossen. Die Klausur wird am 23.03.2009, 14.00 - 16.00 Uhr stattfinden.

Um an der Klausur teilnehmen zu können müssen mindestens 50% der Übungsaufgaben bearbeitet und mindestens zwei mal eine Lösung in der Übung an der Tafel vorgestellt worden sein.

Bei Erreichen von mindestens 60% der Übungspunkte wird in der Klausur ein Bonus von einer drittel Notenstufe gegeben.

Kreditpunkte


In dieser Veranstaltung können 8 ECTS-Punkte erworben werden.

Overhead-Folien


An dieser Stelle werden die in der Vorlesung verwendeten Overhead-Folien als pdf online gestellt.

Mo, 20. Oktober 2008Einleitung, RAM, Turingmaschine
Mi, 12. November 2008Satz von Cook

Literatur

  1. I.Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung, 2. Auflage 1999, Teubner, Stuttgart. ISBN 3-5191-2123-9.
  2. U. Schöning: Theoretische Informatik kurzgefasst, Spektrum Hochschultaschenbuch, 3. Auflage, 1997, Spektrum Akademischer Verlag, Heidelberg. ISBN 3-8274-0250-6
  3. H. Lewis, C. Papadimitriou: Elements of the Theory of Computation, 2. Auflage, 1997, 361 Seiten, kart., Prentice Hall, New Jersey. ISBN 0-13-262478-8
  4. J. Hopcroft, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, 3. Auflage 1994, 461 Seiten, kart., Addison Wesley, Bonn. ISBN 3-89319-744-3