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	<html><!–	1	Dienstag 8:15 - 9:45	AVZ III / A301	2	Dienstag 8:15 - 9:45	AVZ III / A7a
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	<html><!–	13	Freitag 10:15 - 11:45	AVZ III / A301
8	Freitag 12:00 - 13:30	AVZ III / A7a	Martin Kretschmer
9	~~Dienstag 16:30 - 18:00~~	~~AVZ III / A6b~~	~~David Kübel~~
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.)