Berechenbarkeit und Komplexität

Semester:	Wintersemester 2011/12
Veranstalter:	Prof. Vöcking
Bemerkungen:	Seite der Veranstaltung Seite im CAMPUS Die Titel entsprechen den Titeln der Vorlesungsfolien.

Videos

- Motivation, Übersicht und Organisatorisches
- Di, 11.10.2011, 08:15 Uhr
- Modellierung von Problemen, Einführung der Turingmaschine
- Fr, 14.10.2011, 11:45 Uhr
- Mehrband-Turingmaschinen und die universelle Turingmaschine
- Di, 18.10.2011, 08:15 Uhr
- Registermaschine (RAM), Church-Turing-These
- Fr, 21.10.2011, 11:45 Uhr
- Unentscheidbare Probleme: Diagonalisierung
- Di, 25.10.2011, 08:15 Uhr
- Unentscheidbarkeit des Halteproblems: Unterprogrammtechnik
- Fr, 28.10.2011, 11:45 Uhr
- Der Satz von Rice
- Fr, 04.11.2011, 11:45 Uhr
- Rekursive Aufzählbarkeit, Reduktion
- Di, 08.11.2011, 08:15 Uhr
- Wiederholung, Beispiele für Reduktion
- Gehalten von Sascha Geulen
- Fr, 11.11.2011, 11:45 Uhr
- Allgemeines Halteproblem, Hilberts 10. Problem
- Di, 15.11.2011, 08:15 Uhr
- Das Postsche Korrespondenzproblem
- Fr, 18.11.2011, 11:45 Uhr
- Mächtigkeit von WHILE-Programmen
- Di, 22.11.2011, 08:15 Uhr
- Mächtigkeit von LOOP-Programmen
- Fr, 25.11.2011, 11:45 Uhr
- Es fehlen die ersten paar Minuten des Videos, Ton wird ab Min. 21 besser
- Die Komplexitätsklassen P und NP
- Di, 29.11.2011, 08:15 Uhr
- Die Klasse NP und die polynomielle Reduktion
- Di, 06.12.2011, 08:15 Uhr
- NP-Vollständigkeit und der Satz von Cook und Levin
- Fr, 09.12.2011, 11:45 Uhr
- NP-Vollständigkeit
- Di, 13.12.2011, 08:15 Uhr
- NP-Vollständigkeit ausgewählter Graphprobleme
- Fr, 16.12.2011, 11:45 Uhr
- NP-Vollständigkeit einiger Zahlprobleme
- Di, 20.12.2011, 08:15 Uhr
- 1. Globalübung
- Gehalten von Oliver Göbel
- Di, 24.01.2012, 08:15 Uhr
- Aufgaben (Aufgabe 6 nicht vorgerechnet)
- 2. Globalübung
- Gehalten von Melanie Winkler
- Di, 31.01.2012, 08:15 Uhr
- Aufgaben