| Wann | Wo | Beginn | LP | Dozent |
|---|---|---|---|---|
| Mitwochs 12:30-14:00 | AVZ III / HS 1 | 09. April 2014 | 4,0 | Röglin |
| Die Termine der Tutorien sind weiter unten aufgelistet. | 14. April 2014 | 2,0 | Bruckschen, Heidemann, Kurnatowski, Loevenich, Omlor, Saljoki | |
In dieser Vorlesung werden wir uns mit der Berechenbarkeit und Komplexität von Problemen beschäftigen. Es gibt viele verschiedene Probleme. Wir werden formalisieren, was wir unter einem Problem verstehen und Rechnermodelle angeben, die bestimmen, was für Operationen wir zur Bestimmung von Lösungen benutzen dürfen. Wir haben im vergangenen Semester effiziente Algorithmen zur Lösung einer Vielzahl von Problemen entworfen. In dieser Vorlesung werden wir die Grenzen der Algorithmik kennenlernen und uns damit beschäftigen, für welche Probleme es keine effizienten Algorithmen gibt und welche überhaupt nicht algorithmisch gelöst werden können.
| Datum | Inhalt | Literatur |
|---|---|---|
| 9. April | 1 Einleitung 1.1 Probleme und Funktionen 1.2 Rechnermodelle 1.2.1 Turingmaschinen | Skript Folien |
| 16. April | 1.2.1 Turingmaschinen (Fortsetzung) 1.2.2 Registermaschinen | Skript Folien |
| 23. April | 1.2.2 Registermaschinen (Fortsetzung) 1.2.3 Die Church-Turing-These 2 Berechenbarkeitstheorie 2.1 Entwurf einer universellen Turingmaschine 2.2 Die Unentscheidbarkeit des Halteproblems | Skript |
| 30. April | 2.2 Die Unentscheidbarkeit des Halteproblems (Fortsetzung) 2.3 Turing- und Many-One-Reduktionen | Skript |
| 7. Mai | 2.3 Turing- und Many-One-Reduktionen (Fortsetzung) 2.4 Der Satz von Rice | Skript |
| 14. Mai | 2.5 Rekursiv aufzählbare Sprachen | Skript |
| 21. Mai | Keine Vorlesung wegen Dies Academicus | |
| 28. Mai | 2.6 Weitere nicht entscheidbare Probleme 3 Komplexitätstheorie 3.1 Die Klassen P und NP 3.1.1 Die Klasse P | Skript |
| 4. Juni | 3.1.2 Die Klasse NP 3.1.3 P versus NP | Skript |
| 18. Juni | 3.2 NP-Vollständigkeit | Skript |
| 25. Juni | 3.2 NP-Vollständigkeit (Fortsetzung) | Skript |
| 2. Juli | 3.3 Weitere NP-vollständige Probleme 3.4 Ausblick | Skript |
| 9. Juli | 4 Approximationsalgorithmen 4.1 Traveling Salesman Problem 4.1.1 Nichtapproximierbarkeit 4.1.2 Metrisches TSP | Skript |
| 17. Juli | 4.1.3 Christofides-Algorithmus | Skript |
Für den Erhalt des Übungsscheins müssen insgesamt mindestens 50% der zu erreichenden Punkte bei den Übungsaufgaben erreicht werden und Lösungen von zwei Aufgaben müssen im Laufe des Semesters erfolgreich in den Tutorien präsentiert werden. Eine Abgabe der Übungsaufgaben in Gruppen bis zu drei Studierenden ist möglich.
| Wann | Wo | Tutor |
|---|---|---|
| Di 8 (c.t.) - 10 | AVZ III / A301 | Vitali Kurnatowski |
| Di 8 (c.t.) - 10 | AVZ III / A7a | Mosadeq Saljoki |
| Di 10 (c.t.) - 12 | AVZ III / A7a | Philipp Bruckschen |
| Di 14 (c.t.) - 16 | AVZ III / A6a | Philipp Bruckschen |
| Di 16 (c.t.) - 18 | AVZ III / A6b | Philipp Bruckschen |
| Mi 14 (c.t.) - 16 | AVZ III / A6b | Vitali Kurnatowski |
| Do 10 (c.t.) - 12 | AVZ III / A301 | Philipp Bruckschen |
| Do 12 (c.t.) - 14 | AVZ III / A301 | Johannes Loevenich |
| Do 12 (c.t.) - 14 | AVZ III / A7a | Lukas Heidemann |
| Do 14 (c.t.) - 16 | AVZ III / A301 | Yvonne Omlor |
| Fr 10 (c.t.) - 12 | AVZ III / A7a | Yvonne Omlor |
| Fr 10 (c.t.) - 12 | AVZ III / A301 | Johannes Loevenich |
| Fr 12 (c.t.) - 14 | AVZ III / A7a | Lukas Heidemann |