Effiziente Algorithmen (WS 2016/17)
Die Vorläufigen Noten sollten im Campus Office sichtbar sein
Die Einsicht für die Wiederholungsklausur findet am 05.04. von 13:00–14:00 im Raum 5052 im Informatikzentrum statt.Übungsbetrieb
Es gibt keine von uns überprüfte Klausurzulassungsbeschränkung. Die Hausaufgaben koennen auf freiwilliger Basis abgegeben werden, sie werden aber nicht korrigiert. An der Klausur teilnehmen darf jeder, der an Hand der Musterloesungen nach eigenem Ermessen mindestens 50% der Punkte bei den Hausaufgaben erreicht hat.Voraussetzungen
Stoff der ersten Semester des Informatikstudiums und der zugehörigen Mathematikvorlesungen.Inhalt
Die Vorlesung gibt einen Überblick über verschiedene Gebiete der Algorithmik. Im Zentrum der Vorlesung steht die theoretische Analyse der vorgestellten Algorithmen bezüglich ihrer Korrektheit, Laufzeit und Güte. Die Themenauswahl berücksichtigt insbesondere die praktische Relevanz der vorgestellten algorithmischen Konzepte. Im Einzelnen widmen wir uns den folgenden Themen.- Flüsse und Matchings
- Lineare Programmierung
- Algorithmische Geometrie
- Randomisierte Algorithmen
- Approximationsalgorithmen
- Online-Algorithmen
Vorlesungsfolien
- 21. Oktober 2016: Wiederholung von Flüssen
- 27. Oktober 2016: Edmond-Karp-Algorithmus; Bipartite Matchings
- 28. Oktober 2016: Der Preflow-Push-Algorithmus
- 4. November 2016: Flüsse mit minimalen Kosten
- 9. November 2016: Matchings mit maximalem Gewicht; Matchings in allgemeinen Graphen
- 16. November 2016: Matchings in allgemeinen Graphen; Einführung in Lineare Programme
- 18. November 2016: Geometrie des Linearen Programmierens
- 23. November 2016: Der Simplex-Algorithmus
- 25. November 2016: Entartete Basen, Dualität
- 30. November 2016: Dualität
- 2. Dezember 2016: Interior Point-Verfahren, Integer Linear Programs
- 9. Dezember 2016: NP-schwere Probleme, Backtracking
- 16. Dezember 2016: Satisfiability, Branch and Bound
- 21. Dezember 2016: Branch and Bound, Scheduling
- 11. Januar 2017: Approximationsalgorithmen
- 13. Januar 2017: Approximationsschemata, PTAS
- 18. Januar 2017: PTAS für Scheduling
- 25. Januar 2017: FPTAS für Scheduling, Nichtapproximierbarkeit
- 1. Februar 2017: Online-Algorithmen
- 3. Februar 2017: Randomisierte Online-Algorithmen, Randomisierte Algorithmen I
- 8. Februar 2017: Randomisierte Algorithmen II
Übungen
- Übung 01 (Lösungsvorschlag)
- Übung 02 (Lösungsvorschlag)
- Übung 03 (Lösungsvorschlag)
- Übung 04 (Lösungsvorschlag)
- Übung 05 (Lösungsvorschlag)
- Übung 06 (Lösungsvorschlag)
- Übung 07 (Lösungsvorschlag)
- Übung 08 (Lösungsvorschlag)
- Übung 09, Spezifikation H17 (Lösungsvorschlag)
- Übung 10 (Lösungsvorschlag)
- Übung 11 (Lösungsvorschlag)
- Übung 12 (Lösungsvorschlag)
- Übung 13 (Lösungsvorschlag)
- Eine alte Klausur
Literatur
|
Introduction to Algorithms. |
|
The Art of Computer Programming. |