Algorithmen und Komplexität - Hauptseite Algorithmen und Komplexität

Vorlesung: Theoretische Informatik 2

Dozent: Amin Coja-Oghlan

Termine

VL Dienstag 09:30 - 11:00 RUD 25, 3.001
Donnerstag 09:30 - 11:00 RUD 25, 3.001
UE Dienstag 11:00 - 13:00 (RUD 26, 1'305) M. Bodirsky
Mittwoch 09:00 - 11:00 (RUD 25, 4.112) M. Bodirsky
Mittwoch 13:00 - 15:00 (RUD 25, 4.112) M. Bodirsky
Donnerstag 11:00 - 13:00 (RUD 26, 1'305) M. Bodirsky
Freitag 09:00 - 11:00 (RUD 25, 4.112) M. Bodirsky
Freitag 11:00 - 13:00 (RUD 25, 4.112) M. Bodirsky

Zuordnung

  • Grundstudium, 3. Semester

Inhalte und Lernziele

Teil I: Automatentheorie und Formale Sprachen

  1. Chomsky-Hierarchie
  2. Reguläre Sprachen und endliche Automaten
  3. Kontextfreie Sprachen und Kellerautomaten
  4. Kontextsensitive Sprachen

Teil II: Berechenbarkeit

  1. Turingmaschinen
  2. Halteproblem
  3. Satz von Rice

Teil III: Komplexitätstheorie

  1. Die Klassen P und NP
  2. NP-Vollständigkeit

Lernziele: Grundkenntnisse in den Gebieten Formale Sprachen, Berechenbarkeit und Komplexitätstheorie; Heranführung an korrektes mathematisches Argumentieren.

Die Vorlesung ist angelehnt an das Buch Theoretische Informatik - kurzgefasst von Schöning.

Voraussetzungen

  • Theoretische Informatik 1

Folien

Teil I: Automatentheorie und Formale Sprachen

Teil II: Berechenbarkeit

Teil III: Komplexitätstheorie

Übungen

In den Übungen kann ein Übungsschein "Theoretische Informatik 2" erworben werden. Voraussetzung ist das Erreichen von mindestens 50% der möglichen Punkte in den Übungsaufgaben sowie die aktive Mitarbeit in der Übung. Der Übungsschein ist notwendig, um zur Klausur zugelassen zu werden.

Die neuen Übungsaufgaben erscheinen jeweils dienstags auf dieser Seite und in Goya und werden in der Vorlesung verteilt. Abgabe ist bis zum darauf folgenden Dienstag 9:30 Uhr im Sekretariat möglich. Die Abgabe erfolgt in Papierform, elektronische Abgabe per E-Mail oder Goya ist nicht erlaubt. Die Aufgaben dürfen in Zweiergruppen oder einzeln bearbeitet werden, wobei jedes Blatt der Abgabe Name(n) und Matrikelnummer(n) der beteiligten Studenten enthalten sollte. Bitte achten Sie auf nachvollziehbare Lösungswege!

Die korrigierten Lösungen erhält man in seiner Übungsgruppe oder dienstags und donnerstags 14-16 Uhr im Sekretariat. Zur Teilnahme an den Übungen ist es erforderlich, sich über Goya in einer der Übungsgruppen anzumelden. In den Übungen werden die Übungsaufgaben besprochen, Fragen dazu beantwortet und Lösungen diskutiert.

  • Serie 1 (Abgabe bis 25.10.2005, 9:30 Uhr)
  • Serie 2 (Abgabe bis 01.11.2005, 9:30 Uhr)
  • Serie 3 (Abgabe bis 08.11.2005, 9:30 Uhr)
  • Serie 4 (Abgabe bis 15.11.2005, 9:30 Uhr)
  • Serie 5 (Abgabe bis 22.11.2005, 9:30 Uhr)
  • Serie 6 (Abgabe bis 29.11.2005, 9:30 Uhr)
  • Serie 7 (Abgabe bis 06.12.2005, 9:30 Uhr)
  • Serie 8 (Abgabe bis 13.12.2005, 9:30 Uhr)
  • Serie 9 (Abgabe bis 03.01.2006, 9:30 Uhr)
  • Serie 10 (Abgabe bis 10.01.2006, 9:30 Uhr)
  • Serie 11 (Abgabe bis 17.01.2006, 9:30 Uhr)
  • Serie 12 / Probeklausur (Abgabe bis 24.01.2006, 9:30 Uhr)
  • Serie 13 (Abgabe bis 31.01.2006, 9:30 Uhr)

Ausgewählte Musterlösungen

Klausur

Die Klausurtermine sind

  • 27.02.2006, 10:00-12:00 Uhr (Einlass pünktlich um 9:30 Uhr), RUD 26, 0'115,
  • Nachklausur: 13.04.2006, 10:00-12:00 Uhr (Einlass 9:30 Uhr), RUD 26, 0'115.

Sowohl die Ergebnisse der Klausur vom 27.02.2006 als auch die Ergebnisse der Klausur vom 13.04.2006 liegen vor. Die Klausureinsicht für beide Klausuren findet am 28.4., 16:30 bis 17:00 in Raum 3.321, RUD 25 statt. Zur Klausureinsicht ist in jedem Fall der Personalausweis vorzuzeigen.

Literatur

  • Hopcroft, Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 1979
  • Köbler, Theoretische Informatik II, Vorlesungsskript, Berlin 2000
  • Papadimitriou, Computational Complexity, Addison Wesley, 1994
  • Schöning, Theoretische Informatik - kurzgefasst, Spektrum Akademischer Verlag, 2001
  • Wegener, Theoretische Informatik, Teubner Verlag, 1993
zuletzt geändert am 19.04.2006 (alkox-www)