Sidebar
Algorithmen und Berechnungskomplexität II
BA-INF041
Termine
| Art | Uhrzeit | Ort | Datum | LP | Dozent und Übungsleitung |
|---|---|---|---|---|---|
| V2 | Mittwoch 12:30 - 14:00 | AVZ III / HS 1 | 13. April - 20. Juli 2016 (ausser 18. und 25. Mai) | 2,5 | Prof. Rolf Klein, David Kübel |
| Ü2 | siehe Übungstermine | 19. April - 22. Juli 2016 (ausser 17. - 27. Mai) | 3,5 | Philipp Bruckschen, Martin Kretschmer, Pascal Mueller, Florian Nelles, Patrick Seume |
|
| 1. Klausurtermin | Nachmittag | HS X + I | Do. 28. Juli 2016 | ||
| 2. Klausurtermin | Nachmittag | HS X + IX | Mo. 26. September 2016 | ||
Inhalte
Grenzen der Berechenbarkeit, Unentscheidbarkeit, Rekursionstheorie, NP-schwere Probleme, Theorie der NP-Vollständigkeit (Satz von Cook), polynomielle Reduktionen, randomisierte Algorithmen, Approximationsalgorithmen, Approximationshärte
Die Vorlesung basiert auf einem Skript, welches im Laufe des Semesters aktualisiert und erweitert wird. Für Interessierte wird in folgendem Paper der Universität Paderborn gezeigt, warum Game of Life unentscheidbar ist.
Update Skript 11.05.: Diverse Korrekturen und Kapitel 2.4.
Update Skript 07.06.: Diverse Korrekturen und Kapitel 3.
Übungen
Wer die Übungen zu diesem Modul bereits in einem früheren Semester bestanden hat, erhält die Prüfungszulassung automatisch. Bitte überprüfen Sie selbst, ob dies in basis bereits eingetragen wurde und wenden Sie sich bei Problemen an David Kübel.
Wer aus früheren Semestern keinen Übungserfolg vorweisen kann, beachte:
- Voraussetzung für die Zulassung zur Prüfung ist ein Erreichen von mindestens 50% der Übungspunkte und das Vorrechnen zweier Übungsaufgaben im Tutorium.
- Die Anmeldung zu den Tutorien erfolgte über das Tutorienvergabesystem (TVS) und war bis So. 24.04.2016 möglich.
- Eine Abgabe der Übungsaufgaben ist in festen Gruppen von bis zu drei Studierenden möglich.
- Die Ausgabe des Übungsblattes erfolgt mittwochs. Die Lösungen müssen eine Woche später im entsprechenden Briefkasten in der Römerstraße 164 abgegeben sein.
- Die Abgabe muss auf dem ersten Blatt in der ersten Zeile die Namen der Studierenden und deutlich erkennbar die Nummer der Übungsgruppe enthalten. Eine Abgabe aus mehreren Blättern ist zu heften!
| Gruppe | Wann | Wo | Tutor |
|---|---|---|---|
| 1 | Dienstag 10:15 - 11:45 | AVZ III / A7a | Philipp Bruckschen |
| 2 | Dienstag 14:15 - 15:45 | AVZ III / A6a | Philipp Bruckschen |
| 3 | Mittwoch 14:15 - 15:45 | AVZ III / A6b | Pascal Müller |
| 4 | Mittwoch 16:00 - 17:30 | AVZ III / A6a | Pascal Müller |
| 5 | Donnerstag 12:15 - 13:45 | AVZ III / A7a | Florian Nelles |
| 6 | Donnerstag 14:15 - 15:45 | AVZ III / A301 | Florian Nelles |
| 7 | Freitag 10:15 - 11:45 | AVZ III / A7a | Martin Kretschmer |
| 8 | Freitag 12:00 - 13:30 | AVZ III / A7a | Martin Kretschmer |
| | | |
|
| 10 | Donnerstag 10:15 - 11:45 | AVZ III / A301 | Patrick Seume |
| 11 | Donnerstag 12:15 - 13:45 | AVZ III / A301 | Patrick Seume |
Übungszettel
- Präsenzzettel (keine Abgabe, Besprechung 18.-22.04.)
- Übungszettel 1 (Abgabe bis Mittwoch, 20.04., 08:00 im Postkasten in der Römerstraße, Besprechung 25.04. - 29.04.)
- Übungszettel 2 (Abgabe bis Mittwoch, 27.04., 09:00 im Postkasten in der Römerstraße, Besprechung 03.05. - 06.05.)
- Übungszettel 3 (Abgabe bis Mittwoch, 04.05., 09:00 im Postkasten in der Römerstraße, Besprechung 10.05. - 13.05.)
- Übungszettel 4 (Abgabe bis Mittwoch, 11.05., 09:00 im Postkasten in der Römerstraße, Besprechung 31.05. - 03.06.)
- Übungszettel 5 (Abgabe bis Mittwoch, 01.06., 09:00 im Postkasten in der Römerstraße, Besprechung 07.06. - 10.06.)
- Übungszettel 6 (Abgabe bis Mittwoch, 08.06., 09:00 im Postkasten in der Römerstraße, Besprechung 14.06. - 17.06.)
- Übungszettel 7 (Abgabe bis Mittwoch, 15.06., 09:00 im Postkasten in der Römerstraße, Besprechung 21.06. - 24.06.)