Zur Startseite der Abteilung Theoretische Informatik

Berechenbarkeit und Komplexität (WS 2012/13)

Vorlesung

Prof. Dr. Ulrich Hertrampf

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/nichtdeterministischeBerechnungen).

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

ZeitRaumTermine

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.DatumFolienInhalt
1 15.10. pdf Algorithmenbegriff, Churchsche These, Turing-Berechenbarkeit
  17.10.     --  keine Vorlesung  --  
2 22.10. pdf Mehrband-Turingmaschinen, spezielle Maschinenkonstruktionen
3 24.10. pdf LOOP-, WHILE- und GOTO-Berechenbarkeit
4 29.10. pdf Normalform-Theorem, Turing=GOTO, Primitive Rekursion
5 31.10. pdf Primitiv rekursiv = LOOP-berechenbar, μ-Rekursion
6 5.11. pdf Satz von Kleene, Ackermann-Funktion
7 7.11. pdf Unentscheidbarkeit, rekursive Aufzählbarkeit
8 12.11. pdf Unentscheidbare Probleme, insbesondere Halteproblem
  14.11.     -- keine Vorlesung  --  
9 19.11. pdf Satz von Rice, Postsches Korrespondenzproblem

10

21.11. pdf Unentscheidbare Grammatikprobleme
11 26.11. pdf Der Gödelsche Satz, arithmetische Repräsentierbarkeit
12 28.11. pdf Beweissysteme, Unvollständigkeitssatz
13 3.12. pdf Komplexitätsklassen, P und NP, NP-Vollständigkeit
  5.12.     --  keine Vorlesung  --  
14 10.12. pdf Der Satz von Cook
15 12.12. pdf Weitere NP-vollständige Probleme
16 17.12. pdf Zeit- und Platzklassen, Varianten algorithmischer Probleme
  19.12.     --  keine Vorlesung  --  
17 7.01. pdf Grapherreichbarkeit und der Satz von Savitch
18 9.01. pdf Hierarchiesätze und Satz von Borodin
19 14.01. pdf Noch einmal Immerman und Szelepcsenyi
20 16.01. pdf Translationssatz, Anwendungen
21 21.01. pdf NL-vollständige Probleme
  23.01.     --  keine Vorlesung  --  
22 28.01. pdf P-vollständige Probleme
  30.01.     --  keine Vorlesung  --  
23 4.02. pdf PSPACE-vollständige Probleme  
  6.02.     --  Ersatztermin  --  

Übungen

Martin Seybold

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 0Blatt 1Blatt 2Blatt 3Blatt 4Blatt 5Blatt 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.
GruppeZeitTutorBesprechung
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