Vorlesung
Lernziele: Die Teilnehmer beherrschen wichtige theoretische Grundlagen der Informatik und können Probleme in Kategorien einordnen wie entscheidbar/unentscheidbar oder effizient lösbar (durch deterministische/nichtdeterministische Berechnungen).
Inhalt: Gleichwertigkeit der verschiedenden Konkretisierungen des Algorithmenbegriffs, Churchsche These, Grenzen zwischen Entscheidbarbkeit und Unentscheidbarkeit. Turing-Berechenbarkeit, Halteproblem, Satz von Rice. Wichtige Komplexitätsklassen, P-NP-Problem, NP-Vollständigkeit, Satz von Cook.
Hinweise
- Um an der Modulprüfung “Berechenbarkeit und Komplexität” teilzunehmen, benötigen Sie den Übungsschein dieser Veranstaltung. Ein Übungsschein des Moduls aus einem früheren Jahr wird dabei auch akzeptiert.
- Falls Sie einen benoteten Schein benötigen (z.B. Lehramt oder Nebenfach), melden Sie sich bitte beim Übungsleiter.
- Die Scheinklausur des Vorjahres zum Üben gibt es hier.
- Prüfungsklausuren früherer Jahrgänge (teilweise mit Lösungsvorschlägen). Diese sind jedoch hauptsächlich aus den Diplomstudiengängen und daher nur begrenzt relevant.
- Voraussichtlicher Prüfungstermin: 15.03.2013 (stand 30.01)
- Für die Teilnahme an der Prüfung wird ein Übungsschein aus diesem oder einem frühreren Semester benötigt.
- Die Ergebnisse der Modulprüfung BuK hängen am Brett des FMI aus.
- Die Einsicht ist am 8.04.2013 zwischen 12:30 Uhr und 13:30 Uhr in Raum 1.168.
Termine
Zeit | Raum | Termine | |
---|---|---|---|
Mo 15:45–17:15 | V38.04 | wöchtl. ab 15.10.12 bis 28.1.13 | |
Mi 15:45–17:15 | V38.04 | wöchtl. ab 24.10.12 bis 23.1.13 | außer am 14.11.12, 5.12.12 und 19.12.12 |
Vorlesungsplan und Folien
Die nächste Vorlesung ist stets grün unterlegt. Die Folien mit den in der Vorlesung eingetragenen Ergänzungen werden jeweils nach der Vorlesung hier eingefügt.
Vorl. | Datum | Folien | Inhalt |
---|---|---|---|
1 | 15.10. | Algorithmenbegriff, Churchsche These, Turing-Berechenbarkeit | |
17.10. | -- keine Vorlesung -- | ||
2 | 22.10. | Mehrband-Turingmaschinen, spezielle Maschinenkonstruktionen | |
3 | 24.10. | LOOP-, WHILE- und GOTO-Berechenbarkeit | |
4 | 29.10. | Normalform-Theorem, Turing=GOTO, Primitive Rekursion | |
5 | 31.10. | Primitiv rekursiv = LOOP-berechenbar, μ-Rekursion | |
6 | 5.11. | Satz von Kleene, Ackermann-Funktion | |
7 | 7.11. | Unentscheidbarkeit, rekursive Aufzählbarkeit | |
8 | 12.11. | Unentscheidbare Probleme, insbesondere Halteproblem | |
14.11. | -- keine Vorlesung -- | ||
9 | 19.11. | Satz von Rice, Postsches Korrespondenzproblem | |
10 |
21.11. | Unentscheidbare Grammatikprobleme | |
11 | 26.11. | Der Gödelsche Satz, arithmetische Repräsentierbarkeit | |
12 | 28.11. | Beweissysteme, Unvollständigkeitssatz | |
13 | 3.12. | Komplexitätsklassen, P und NP, NP-Vollständigkeit | |
5.12. | -- keine Vorlesung -- | ||
14 | 10.12. | Der Satz von Cook | |
15 | 12.12. | Weitere NP-vollständige Probleme | |
16 | 17.12. | Zeit- und Platzklassen, Varianten algorithmischer Probleme | |
19.12. | -- keine Vorlesung -- | ||
17 | 7.01. | Grapherreichbarkeit und der Satz von Savitch | |
18 | 9.01. | Hierarchiesätze und Satz von Borodin | |
19 | 14.01. | Noch einmal Immerman und Szelepcsenyi | |
20 | 16.01. | Translationssatz, Anwendungen | |
21 | 21.01. | NL-vollständige Probleme | |
23.01. | -- keine Vorlesung -- | ||
22 | 28.01. | P-vollständige Probleme | |
30.01. | -- keine Vorlesung -- | ||
23 | 4.02. | PSPACE-vollständige Probleme | |
6.02. | -- Ersatztermin -- |
Ergänzungen
Webseite der Ergänzungen ( Jürn Laun )
Übungen
Die Besprechung der Übungsaufgaben erfolgt 14-tägig in Raum 0.124.
Der unbenotete Übungsschein ist notwendige Vorleistung für die Modulprüfung “Berechenbarkeit und Komplexität”. Einen Übungsschein erhält, wer mindestens 50% der Punkte aus Hausaufgaben und mindestens 50% der Votierpunkte von Blatt 1 bis 6 erreicht.
Falls Sie gesondert einen benoteten Schein benötigen, treten Sie bitte vor dem 8. Februar mit dem Übungsleiter in Kontakt.
Übungsblätter und Besprechungstermine
Blatt 0 | Blatt 1 | Blatt 2 | Blatt 3 | Blatt 4 | Blatt 5 | Blatt 6 | |||
---|---|---|---|---|---|---|---|---|---|
Ausgabe | 15.10. | 29.10. | 12.11. | 26.11. | 10.12. | 7.01. | 21.01. | ||
Abgabe | -- | 2.11. | 16.11. | 30.11. | 14.12. | 11.01. | 25.01. | ||
Gruppe | Zeit | Tutor | Besprechung | ||||||
1 | DI 15:45–17:15 | Wächter | 23.10. | 6.11. | 20.11. | 4.12. | 18.12. | 15.01. | 29.01. |
2 | Di 15:45–17:15 | Wächter | 30.10. | 13.11. | 27.11. | 11.12. | 08.01. | 22.01. | 5.02. |
3 | Mi 11:30–13:00 | Hartmann | 24.10. | 7.11. | 21.11. | 5.12. | 19.12. | 16.01. | 30.01. |
4 | Mi 11:30–13:00 | Hartmann | 31.10. | 14.11. | 28.11. | 12.12. | 09.01. | 23.01. | 6.02. |
5 | Do 15:45–17:15 | Seybold | 25.10. | 8.11. | 22.11. | 6.12. | 20.12. | 17.01. | 31.01. |
Literatur
Die Inhalte der Vorlesung entstammen im ersten Teil im Wesentlichen dem Buch von Uwe Schöning. Der zweite Teil stützt sich hauptsächlich auf das Skript der früheren Vorlesung Komplexitätstheorie:
- Uwe Schöning: Theoretische Informatik – kurzgefasst, 5. Auflage, Spektrum, 2008.
- Volker Diekert: Komplexitätstheorie, Skript, Universität Stuttgart, 10.12.2007