Dozent: Mathias Schacht
Termine
Beginn der Vorlesung: 17.10.2006.| 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'307) M. Bodirsky |
| Mittwoch | 09:00 - 11:00 | (RUD 26, 1'306) G. Grunert | |
| Mittwoch | 13:00 - 15:00 | (RUD 26, 1'307) M. Killat | |
| Donnerstag | 11:00 - 13:00 | (RUD 26, 1'307) M. Bodirsky | |
| Freitag | 09:00 - 11:00 | (RUD 26, 1'306) W. Kössler | |
| Freitag | 11:00 - 13:00 | (RUD 26, 1'306) W. Kössler |
Klausurtermine
- Montag, 26.02.2007, 9:00 Uhr, RUD 26, 0'115
- Nachklausur: Donnerstag, 12.04.2007, 9:00 Uhr, RUD 26, 0'115
Klausurergebnisse
Die Ergebnisse der Klausur vom 26.02.2007 liegen vor. Die Klausureinsicht findet am 09.03.2007 von 14:30 bis 16:00 Uhr in Raum 3.321, RUD 25 statt. Zur Klausureinsicht ist in jedem Fall der Personalausweis vorzuzeigen.
Die Ergebnisse der Nachklausur vom 12.04.2007 liegen vor. Die Klausureinsicht findet am 18.04.2007 von 17:00 bis 18:00 Uhr in Raum 3.321, RUD 25 statt. Zur Klausureinsicht ist in jedem Fall der Personalausweis vorzuzeigen.
Zuordnung
- Grundstudium, 3. Semester
Inhalte und Lernziele
Teil I: Automatentheorie und Formale Sprachen
- Chomsky-Hierarchie
- Reguläre Sprachen und endliche Automaten
- Kontextfreie Sprachen und Kellerautomaten
- Kontextsensitive Sprachen
Teil II: Berechenbarkeit
- Turingmaschinen
- Halteproblem
- Satz von Rice
Teil III: Komplexitätstheorie
- Die Klassen P und NP
- 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
Kompletter Satz: druckerfreundliche Version und Vorlesungsversion (Stand 18.02.07)- VL 17.10.2006 (Einführung, Mathematische Grundlagen)
Teil I: Automatentheorie und Formale Sprachen
- VL 19.10.2006 (Grammatiken)
- VL 24.10.2006 - 31.10.2006 (Reguläre Sprachen)
- VL 02.11.2006 - 14.11.2006 (Kontextfreie Sprachen)
- VL 16.11.2006 - 23.11.2006 (Kontextsensitive/Typ 0 Sprachen)
Teil II: Berechenbarkeitstheorie
- VL 23.11.2006 - 05.12.2006 (Churchsche These, Berechenbarkeitsmodelle)
- VL 05.12.2006 - 09.01.2007 (Entscheidbarkeit, Halteproblem, Satz von Rice, PCP, Programme s.c und self2.c, Rekursionssatz, Fixpunktsatz von Kleene)
Teil III: Komplexitätstheorie
- VL 11.01.2007 - 18.01.2007 (Klassen P und NP)
- VL 18.01.2007 - 01.02.2007 (P-Reduktion, NP-Vollständigkeit, Satz von Cook & Levin, Erfüllbarkeitsproblem, NP-vollständige Probleme)
- VL 06.02.2007 - 15.02.2007 (Platzkomplexität, PSPACE, L, NL, NL-Vollständigkeit, NL=coNL)
Ü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:25 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 31.10.2006, 9:25 Uhr)
- Serie 2 (Abgabe bis 07.11.2006, 9:25 Uhr)
- Serie 3 (Abgabe bis 14.11.2006, 9:25 Uhr)
- Serie 4' (Abgabe bis 21.11.2006, 9:25 Uhr)
- Serie 5 (Abgabe bis 28.11.2006, 9:25 Uhr)
- Serie 6 (Abgabe bis 05.12.2006, 9:25 Uhr)
- Serie 7 (Abgabe bis 12.12.2006, 9:25 Uhr)
- Serie 8 (Abgabe bis 19.12.2006, 9:25 Uhr)
- Serie 9 (Abgabe bis 09.01.2007, 9:25 Uhr)
- Serie 10 (Abgabe bis 23.01.2007, 9:25 Uhr)
- Serie 11 (Abgabe bis 30.01.2007, 9:25 Uhr)
- Serie 12 (Abgabe bis 06.02.2007, 9:25 Uhr)
- Bonusserie (Abgabe bis 13.02.2007, 9:25 Uhr)
Literatur
- , Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 1979
- , Theoretische Informatik II, Vorlesungsskript, Berlin 2000
- , Computational Complexity, Addison Wesley, 1994
- , Theoretische Informatik - kurzgefasst, Spektrum Akademischer Verlag, 2001
- , Introduction to the Theory of Computation, Course Technology, 2005
- , Theoretische Informatik, Teubner Verlag, 1993
English