Algorithmen und Berechnungskomplexität II und III

Termine

Art Wann Wo Beginn Dozent
V4
Montag 12:30 - 14:00
Mittwoch 12:30 - 14:00
AVZ III / HS 1
AVZ III / HS 1
4. April 2011 Röglin
Ü2 Termine 12. April 2011 Brunsch, Gödde, Liß, Röglin, Vößing

Inhalt

Nachdem wir uns im ersten Teil der Vorlesung im Wintersemester mit grundlegenden Datenstrukturen und Techniken zum Entwurf von Algorithmen beschäftigt haben, werden wir im zweiten Teil der Vorlesung die Grenzen der Algorithmik beleuchten. Es wird diskutiert, welche Probleme überhaupt berechenbar sind und welche Probleme effizient gelöst werden können. Im dritten Teil der Vorlesung lernen wir wichtige Techniken zum Entwurf von Algorithmen kennen. Außerdem werden wir uns mit Approximations- und Online-Algorithmen beschäftigen.

Unten folgt eine genaue Inhaltsangabe der einzelnen Vorlesungstermine:

Algorithmen und Berechnungskomplexität II

Datum Inhalt Literatur
4. April
Organisatorisches, Ausblick
1 Einführung
1.1 Modellierung von Problemen
1.2 Computermodelle
1.2.1 Die Turingmaschine
[Vö]
6. April
1.2.1 Die Turingmaschine (Fortsetzung)
[Vö]
11. April
1.2.1 Die Turingmaschine (Fortsetzung)
1.2.2 Die Registermaschine (kurz)
1.2.3 Vergleich der beiden Computermodelle (kurz)
2 Berechenbarkeit
2.1 Die Church-Turing-These
2.2 Nicht rekursive Probleme
2.2.1 Existenz unentscheidbarer Probleme
[Vö]
13. April
2.2.2 Unentscheidbarkeit der Diagonalsprache
2.2.3 Unentscheidbarkeit des Halteproblems
2.2.4 Die Unterprogrammtechnik (Turing Reduktion)
[Vö]
18. April
2.2.5 Der Satz von Rice
2.3 Semi-Entscheidbarkeit und Rekursive Aufzählbarkeit
2.4 Eigenschaften rekursiver und rekursiv aufzählbarer Sprachen
[Vö]
20. April
2.5 Die Technik der Reduktion
2.6 Klassische Probleme aus der Rekursionstheorie
2.6.1 Hilberts zehntes Problem
[Vö]
25. April
Keine Vorlesung (Ostermontag)
27. April
2.6.2 Das Postsche Korrespondenzproblem
[Vö]
2. Mai
2.7 Mächtigkeit von Programmiersprachen
2.7.1 WHILE-Programme
2.7.2 LOOP-Programme
[Vö]
4. Mai
2.7.2 LOOP-Programme (Fortsetzung)
3 Komplexität
3.1 Die Komplexitätsklasse P
3.1.1 Motivation und Definition
3.1.2 Beispiele für Probleme in P
[Vö]
9. Mai
3.2 Die Komplexitätsklasse NP
3.2.1 Definition und Erläuterung
3.2.2 Alternative Charakterisierung der Klasse NP
[Vö]
11. Mai
3.2.3 Beispiele für Probleme in NP
3.3 P versus NP
[Vö]
16. Mai
3.4 NP-Vollständigkeit
3.4.1 Polynomielle Reduktionen
3.4.2 Beispiel einer polynomiellen Reduktion
3.4.3 Definitionen von NP-Härte und NP-Vollständigkeit
3.5 Der Satz von Cook und Levin
[Vö]
18. Mai
3.5 Der Satz von Cook und Levin (Fortsetzung)
3.6 NP-Vollständigkeit von 3SAT und CLIQUE
[Vö]
23. Mai
3.7 NP-Vollständigkeit des Hamiltonkreisproblems (kurz)
3.8 NP-Vollständigkeit einiger Zahlprobleme
3.8.1 NP-Vollständigkeit von SUBSET-SUM
3.8.2 NP-Vollständigkeit von PARTITION (kurz)
3.8.3 Konsequenzen für KP und BPP
[Vö]
25. Mai Keine Vorlesung (Dies Academicus)

Algorithmen und Berechnungskomplexität III

Datum Inhalt Literatur
30. Mai
1 Approximationsalgorithmen
1.1 Vertex Cover und Set Cover
1.1.1 Vertex Cover
1.1.2 Set Cover
1. Juni
1.1.3 Greedy-Algorithmen
1.2 Rucksackproblem
1.2.1 Greedy-Algorithmus
1.2.2 Pseudopolynomieller Algorithmus
6. Juni
1.2.3 Polynomielles Approximationsschema
8. Juni
1.3 Traveling Salesperson Problem
1.3.1 Nichtapproximierbarkeit und starke NP-Härte
1.3.2 Metrisches TSP
20. Juni
1.3.3 Christofides-Algorithmus
2 Online-Algorithmen
22. Juni
2.1 Paging
2.1.1 Optimaler Offline-Algorithmus
2.1.2 Markierungsalgorithmen
27. Juni
2.1.2 Markierungsalgorithmen (Fortsetzung)
2.1.3 Untere Schranken
29. Juni
2.2 Scheduling
2.2.1 Identische Maschinen
2.2.2 Maschinen mit Geschwindigkeiten
4. Juli
2.2.2 Maschinen mit Geschwindigkeiten (Fortsetzung)
3 Lineare Programmierung
6. Juli
3.1 Grundlagen
3.1.2 Geometrische Interpretation
11. Juli
3.1.3 Algebraische Interpretation
13. Juli
3.2 Simplex-Algorithmus
3.3 Komplexität von linearer Programmierung

Informationen zur Änderung der Bachelorprüfungsordnung

Gemäß der Änderung der Bachelorprüfungsordnung handelt es sich bei "Algorithmen und Berechnungskomplexität II" um eine (V2 + Ü2)-Vorlesung mit 6 Leistungspunkten. Für Studierende im Diplomstudiengang ist die Vorlesung "Informatik IV" jedoch weiterhin vierstündig. Um dieser speziellen Situation in diesem Semester gerecht zu werden, hat der Prüfungsausschuss die folgende Regelung beschlossen:

Übungen

Algorithmen und Berechnungskomplexität II

Algorithmen und Berechnungskomplexität III

Wann Wo Tutor
1 Dienstag, 10:15 - 11:45 AVZ III / A7a Tobias Brunsch
2 Mittwoch, 10:15 - 11:45 AVZ III / A7a Heiko Röglin
3 Donnerstag, 10:15 - 11:45 AVZ III / A301 Florian Liß
4 Donnerstag, 12:15 - 13:45 AVZ III / A301 Johannes Vößing
5 Donnerstag, 14:15 - 15:45 AVZ III / A301 Johannes Vößing
6 Freitag, 8:15 - 9:45 AVZ III / A7a Kai Gödde
7 Freitag, 10:15 - 11:45 AVZ III / A301 Florian Liß
8 Freitag, 12:15 - 13:45 AVZ III / A7a Kai Gödde

Literatur

Zur Vorlesung "Algorithmen und Berechnungskomplexität III" gibt es ein Skript.

Die Vorlesung "Algorithmen und Berechnungskomplexität II" basiert in wesentlichen Teilen auf dem folgenden Skript: Weiterführende Literatur: