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
|
Skript |
| 1. Juni | 1.1.3 Greedy-Algorithmen
1.2 Rucksackproblem
1.2.1 Greedy-Algorithmus
1.2.2 Pseudopolynomieller Algorithmus
|
Skript |
| 6. Juni | 1.2.3 Polynomielles Approximationsschema
|
Skript |
| 8. Juni | 1.3 Traveling Salesperson Problem
1.3.1 Nichtapproximierbarkeit und starke NP-Härte
1.3.2 Metrisches TSP
|
Skript |
| 20. Juni | 1.3.3 Christofides-Algorithmus
2 Online-Algorithmen
|
Skript |
| 22. Juni | 2.1 Paging
2.1.1 Optimaler Offline-Algorithmus
2.1.2 Markierungsalgorithmen
|
Skript |
| 27. Juni | 2.1.2 Markierungsalgorithmen (Fortsetzung)
2.1.3 Untere Schranken
|
Skript |
| 29. Juni | 2.2 Scheduling
2.2.1 Identische Maschinen
2.2.2 Maschinen mit Geschwindigkeiten
|
Skript |
| 4. Juli | 2.2.2 Maschinen mit Geschwindigkeiten (Fortsetzung)
3 Lineare Programmierung |
Skript |
| 6. Juli | 3.1 Grundlagen
3.1.2 Geometrische Interpretation |
Skript |
| 11. Juli | 3.1.3 Algebraische Interpretation |
Skript |
| 13. Juli | 3.2 Simplex-Algorithmus
3.3 Komplexität von linearer Programmierung |
Skript |
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:- Die erste Hälfte des Semesters (Vorlesung bis einschließlich 23. Mai, Übungen bis einschließlich 3. Juni) entspricht der Pflichtveranstaltung "Algorithmen und Berechnungskomplexität II".
- Die zweite Hälfte des Semesters entspricht der neuen Wahlpflichtveranstaltung "Algorithmen und Berechnungskomplexität III", für die es ebenfalls 6 Leistungspunkte gibt.
- Für Studierende im Diplomstudiengang entspricht das komplette Semester der Pflichtvorlesung "Informatik IV".
Übungen
Algorithmen und Berechnungskomplexität II
- Präsenzblatt (Besprechung in KW 15, keine Abgabe)
- Übungsblatt 1 (Besprechung in KW 16, Abgabe am 13.04. in der Vorlesung)
- Übungsblatt 2 (Besprechung in KW 17, Abgabe am 20.04. in der Vorlesung)
- Übungsblatt 3 (Besprechung in KW 18, Abgabe am 27.04. in der Vorlesung)
- Übungsblatt 4 (Besprechung in KW 19, Abgabe am 04.05. in der Vorlesung)
- Übungsblatt 5 (Besprechung in KW 20, Abgabe am 11.05. in der Vorlesung)
- Übungsblatt 6 (Besprechung in KW 21, Abgabe am 18.05. in der Vorlesung)
- Übungsblatt 7 (Besprechung in KW 22, Abgabe in KW 21 in den Übungen)
- Probeklausur (Besprechung in KW 23, Abgabe am 01.06. in der Vorlesung oder in KW 22 in den Übungen)
Algorithmen und Berechnungskomplexität III
- Übungsblatt 1 (Besprechung in KW 25, Abgabe am 08.06. in der Vorlesung)
- Übungsblatt 2 (Besprechung in KW 26, Abgabe am 22.06. in der Vorlesung)
- Übungsblatt 3 (Besprechung in KW 27, Abgabe am 29.06. in der Vorlesung)
- Übungsblatt 4 (Besprechung in KW 28, Abgabe am 06.07. in der Vorlesung)
- Übungsblatt 5 (Besprechung im Ferientutorium, keine Abgabe)
- Probeklausur (Besprechung im Ferientutorium, keine Abgabe)
| 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" gab es ein Skript, welches nur noch auf Anfrage verfügbar ist.
Die Vorlesung "Algorithmen und Berechnungskomplexität II" basiert in wesentlichen Teilen auf dem folgenden Skript:- [Vö] Berthold Vöcking. Skript zur Vorlesung "Berechenbarkeit und Komplexität".Wintersemester 2009/10, RWTH Aachen.
- [Bl] Norbert Blum. Einführung in Formale Sprachen, Berechenbarkeit, Informations- und Lerntheorie.ISBN: 978-3486274332, Oldenbourg, 2006.
- [We] Ingo Wegener. Theoretische Informatik - eine algorithmenorientierte Einführung.ISBN: 978-3835100336, Teubner Verlag, 3. Auflage, 2005.
- [We2] Ingo Wegener. Kompendium Theoretische Informatik: Eine Ideensammlung.ISBN: 978-3519021452, Teubner Verlag, 1996.