Sidebar
Algorithmen und Berechnungskomplexität II
Termine
| Wann | Wo | Beginn | Dozent | |
|---|---|---|---|---|
| Vorlesung | Mitwoch 12:30-14:00 | AVZ III / HS 1 | 19. April 2017 | Röglin |
| Übungen | 24. April 2017 |
Inhalt
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 |
|---|---|---|
| 19. April | 1 Einleitung 1.1 Probleme und Funktionen 1.2 Rechnermodelle 1.2.1 Turingmaschinen | Folien |
| 26. April | 1.2.1 Turingmaschinen (Fortsetzung) 1.2.2 Registermaschinen | Folien |
| 3. Mai | 1.2.2 Registermaschinen (Fortsetzung) 1.2.3 Die Church-Turing-These 2 Berechenbarkeitstheorie 2.1 Entwurf einer universellen Turingmaschine | Folien |
| 10. Mai | 2.2 Die Unentscheidbarkeit des Halteproblems 2.3 Turing- und Many-One-Reduktionen | |
| 17. Mai | dies academicus (keine Vorlesung) | |
| 24. Mai | 2.3 Turing- und Many-One-Reduktionen (Fortsetzung) 2.4 Der Satz von Rice | |
| 31. Mai | 2.5 Rekursiv aufzählbare Sprachen | |
| 14. Juni | 2.6 Weitere nicht entscheidbare Probleme 3 Komplexitätstheorie 3.1 Die Klassen P und NP 3.1.1 Die Klasse P | |
| 21. Juni | 3.1.2 Die Klasse NP | |
| 28. Juni | 3.1.3 P versus NP 3.2 NP-Vollständigkeit | |
| 5. Juli | 3.2 NP-Vollständigkeit (Fortsetzung) | |
| 12. Juli | 3.3 Weitere NP-vollständige Probleme 3.4 Ausblick | |
| 19. Juli | 4 Approximationsalgorithmen 4.1 Traveling Salesman Problem 4.1.1 Nichtapproximierbarkeit 4.1.2 Metrisches TSP 4.1.3 Christofides-Algorithmus | |
| 26. Juli | Keine Vorlesung |
Übungen
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.
| Nr. | Wann | Wo | Tutor |
|---|---|---|---|
| 1 | Dienstag 10:15 - 11:45 | AVZ III / A7a | Torben Plitt |
| 2 | Dienstag 14:15 - 15:45 | AVZ III / A6a | Danny Rademacher |
| 3 | Dienstag 16:15 - 17:45 | AVZ III / A6b | Danny Rademacher |
| 4 | Mittwoch 14:15 - 15:45 | AVZ III / A6b | Florian Glässer |
| 5 | Mittwoch 16:15 - 17:45 | AVZ III / A6a | Florian Glässer |
| 6 | Donnerstag 10:15 - 11:45 | AVZ III / A301 | Florian Nelles |
| 7 | Donnerstag 12:15 - 13:45 | AVZ III / A301 | Florian Nelles |
| 8 | Freitag 10:15 - 11:45 | AVZ III / A7a | Jan Hoeckendorff |
| 9 | Freitag 12:15 - 13:45 | AVZ III / A7a | Jan Hoeckendorff |
- Präsenzblatt (Besprechung in KW 17, keine Abgabe)
- Übungsblatt 1 (Besprechung in KW 18, Abgabe bis 26.04., 12:30 Uhr, im Briefkasten in der Römerstraße)
- Übungsblatt 2 (Besprechung in KW 19, Abgabe bis 03.05., 12:30 Uhr, im Briefkasten in der Römerstraße)
- Übungsblatt 3 (Besprechung in KW 20, Abgabe bis 10.05., 12:30 Uhr, im Briefkasten in der Römerstraße)
- Übungsblatt 4 (Besprechung in KW 21, keine Abgabe)
- Übungsblatt 5 (Besprechung in KW 22, Abgabe bis 24.05., 12:30 Uhr, im Briefkasten in der Römerstraße)
- Übungsblatt 6 (Besprechung in KW 24, Abgabe bis 31.05., 12:30 Uhr, im Briefkasten in der Römerstraße)
- Übungsblatt 7 (Besprechung in KW 25, Abgabe bis 14.06., 12:30 Uhr, im Briefkasten in der Römerstraße)
- Übungsblatt 8 (Besprechung in KW 26, Abgabe bis 21.06., 12:30 Uhr, im Briefkasten in der Römerstraße)
- Übungsblatt 9 (Besprechung in KW 27, Abgabe bis 28.06., 12:30 Uhr, im Briefkasten in der Römerstraße)
- Übungsblatt 10 (Besprechung in KW 28, Abgabe bis 05.07., 12:30 Uhr, im Briefkasten in der Römerstraße)
- Übungsblatt 11 (Besprechung in KW 29, Abgabe bis 12.07., 12:30 Uhr, im Briefkasten in der Römerstraße)
- Probeklausur (Besprechung in KW 30, keine Abgabe)
Literatur
Die Inhalte der Vorlesung finden sich in diesem Skript.