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.5., 25.5. und 6.7.)
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
Fragestunde 10:00 - 11:00 AVZ III / HS 2 Mo. 25. Juli 2016
1. Klausurtermin 14:30 - 16:00
Einlass 14:15
Hauptgebäude
HS X + I
Do. 28. Juli 2016
2. Klausurtermin 15:30 - 17:00
Einlass 15:15
Hauptgebäude
HS X
Mo. 26. September 2016

Prüfungen & Fragestunde

Klausureinsicht

Die Klausureinsicht zur zweiten Klausur fand am Freitag, den 7.10., zwischen 08:00 und 10:00 im Raum E.08 im Landesbehördenhaus in der Friedrich-Ebert-Allee 144 statt.

Bitte wenden Sie sich bei Fragen zu dieser Klausur nun an das Prüfungsamt.

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.

Eine kleine Übersicht über die in Vorlesung und Übung behandelten Berechnungsmodelle gibt es hier.

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
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.)
  • Übungszettel 8 (Abgabe bis Mittwoch, 22.06., 09:00 im Postkasten in der Römerstraße, Besprechung 28.06. - 01.07.)
  • Übungszettel 9 (Abgabe bis Mittwoch, 29.06., 09:00 im Postkasten in der Römerstraße, Besprechung 05.07. - 08.07.)
  • Übungszettel 10 (keine Abgabe, Besprechung 12.07. - 15.07.)
  • Übungszettel 11 (keine Abgabe, Besprechung 19.07. - 22.07.)
  • Übungszettel 12 (keine Abgabe, keine Besprechung, Lösungsskizzen im Aufschrieb zur Fragestunde)
lehre/ss16/vl-algo-ii.txt · Zuletzt geändert: 2016/10/11 10:43 von kuebel

Benutzer-Werkzeuge