Allgemeine Informationen

ECTS: 6
Sprache: Deutsch
Campus: hier
Modul-
anmeldung:
über CampusOffice
Art Termin / Ort Beginn Dozent
V3 Di 14:15h - 15:45h / Eph
Do 16:15h - 17:45h / Eph
29.10.2013 Vöcking

Ü2 siehe unten TBA siehe unten


Aktuelles


Inhalt

Welche Probleme kann man mit Hilfe des Computers lösen? Und welche Probleme kann man effizient lösen? - Das sind die Fragestellungen, um die es in dieser Vorlesung geht. Wir versuchen diese Fragen mit mathematischen Methoden zu beantworten. Dazu müssen wir zunächst Begriffe wie Problem, Algorithmus und Effizienz modellieren. Anschließend werden wir verblüffend klare und weitgehende Aussagen über die (effiziente) Lösbarkeit von Problemen auf Rechnern machen können. Grundlage der Vorlesung sind mathematische Modelle und Methoden. Der Bezug zu praktischen Problemen und modernen Rechnern wird aber klar herausgearbeitet. Ein Highlight der Vorlesung ist die NP-Vollständigkeitstheorie, deren Auswirkung auf Theorie und Praxis wohl kaum überschätzt werden kann.


Vorlesungsmaterial

Skript zur Vorlesung

Einführung
29. Okt. Motivation, Übersicht und Organisatorisches [Folien]
31. Okt. Modellierung von Problemen, Einführung der Turingmaschine [Folien]
05. Nov. Mehrband-Turingmaschinen und die universelle Turingmaschine [Folien]
07. Nov. Registermaschine (RAM), Church-Turing-These [Folien]

Berechenbarkeit
19. Nov. Unentscheidbare Probleme: Diagonalisierung [Folien] [Anlage]
21. Nov. Unentscheidbarkeit des Halteproblems: Unterprogrammtechnik [Folien] [Notizen]
26. Nov. Der Satz von Rice [Folien]
28. Nov. Rekursive Aufzählbarkeit, Die Reduktion [Folien]
03. Dez. Allgemeines Halteproblem, Hilberts 10. Problem [Folien]
05. Dez. Das Postsche Korrespondenzproblem [Folien]
10. Dez. Mächtigkeit von WHILE-Programmen [Folien]
12. Dez. Mächtigkeit von LOOP-Programmen [Folien]

Komplexität
07. Jan. Die Komplexitätsklassen P und NP [Folien] [Notizen]
09. Jan. Die Klasse NP und die polynomielle Reduktion [Folien] [Notizen]
14. Jan. NP-Vollständigkeit des Erfüllbarkeitsproblems [Folien] [Notizen]
16. Jan. NP-Vollständigkeit einiger Zahlprobleme [Folien]
21. Jan. NP-Vollständigkeit ausgewählter Graphprobleme [Folien]
23. Jan. Überblick über die Komplexitätslandschaft [Folien]
30. Jan. Approximationsalgorithmen für NP-harte Optimierungsprobleme [Folien]

Globalübung
04. Feb. Präsenzübung [Musterlösung] und Fragenkatalog [Fragen]

Prüfungstermine
28. Feb. Bachelorklausur
27. Mrz. Wiederholungsklausur


Übungen

1 Mo 12:15 - 13:45, 2356|056 (5056) Janosch Fuchs
2 Mo 12:15 - 13:45, 4017 Philipp Nagel
3 Mo 14:00 - 15:30, 2356|056 (5056) Erwin Fang
4 Mo 16:00 - 17:30, 4017 Maximilian Gödicke
5 Di 12:00 - 13:30, 4017 Tobias Räderscheidt
6 Mi 12:00 - 13:30, 4017 Martin Ritzert
7 Mi 12:00 - 13:30, 2356|054 (5054) Tobias Ölschlägel
8 Mi 13:30 - 15:00, 2356|054 (5054) Malte Neuss
9 Mi 13:30 - 15:00, 4017 Tim Hartmann
10 Mi 14:15 - 15:45, 2356|052 (5052) Benjamin Hohlmann
11 Do 10:00 - 11:30, 4017 Russ Jukic
12 Do 12:15 - 13:45, 2356|056 (5056) Philipp Niemitz
13 Do 14:30 - 16:00, 4017 Niklas Gehlen
14 Fr 12:00 - 13:30, 4017 Richard Wilke
15 Fr 14:00 - 15:30, 4017 Johannes Lipp

Übungsblätter

Hinweise zu den Übungen


Prüfungszulassung (Bachelor Informatik/Mathematik) und Leistungsnachweis

Für die Zulassung zur Bachelor-Prüfung bzw. für einen Leistungsnachweis sind mindestens 50 Punkte zu sammeln. Hierzu gibt es folgende Möglichkeiten:

Weitere Literaturhinweise

Die folgenden Bücher eignen sich als zusätzliche Literatur und stehen in der Informatikbibliothek zur Verfügung.


Kontakt