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.

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.

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!

• 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)