English English

Termine

Art
Termin / Ort
Beginn
Dozent
V4
 Di, 17:00h - 18:30h / AH V
Fr, 10:00h - 11:30h / AH III 		8.4.08
 Vöcking
Ü2
Mo, 10:00h - 11:30h / 5056
Di, 10:00h - 11:30h / AH6
Do, 10:00h - 11:30h / 5056 		14.4.08
15.4.08
10.4.08 		Ackermann

Für Bachelorstudenten wird diese Vorlesung im Format 3SWS angeboten, d.h. es gibt 21 statt 28 Vorlesungstermine. An den Vorlesungsterminen 20. Mai und 24. Juni sind Präsenzübungen vorgesehen, somit ergeben sich 23 Termine. Die Anzahl der anderen Übungstermine wird entsprechend gekürzt. Nach diesen 23 Terminen wird die Vorlesung mit zusätzlichem Stoff nur für Diplomstudierende fortgesetzt. Im Detail bedeutet dies

  • Am Dienstag, den 20.05.08 findet die erste Präsenzübung statt.
  • Am Dienstag, den 24.06.08 findet die zweite Präsenzübung statt.
  • Am Dienstag, den 1.07.08 endet die Vorlesung für Bachelorstudierende.
  • Am Freitag, den 18.07.08 endet die Vorlesung für Diplomstudierende.
  • In der Pfingstwoche vom 12. - 18.05.08 findet keine Vorlesung statt.

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.

  • Lineare Programmierung
  • Flüsse und Matchings
  • Approximationsalgorithmen
  • Online-Algorithmen
  • Algorithmische Geometrie
  • Randomisierte Algorithmen

Prüfungs- und Scheinkriterien

Credit Workload Selbststudium
Vorlesung 4 75h
Übung 2 30h
  • Bachelorstudierende melden sich bitte bis zum 25.4.08 23:55h im Campus Office zur Vorlesung an.
  • Bachelorstudierende benötigen 50% der Punkte in den Präsenzübungen und müssen die Lösung einer Aufgabe vortragen, um zur Prüfung zugelassen zu werden. Die Prüfungen für Bachelorstudierende finden voraussichtlich am 24./25. Juli statt.
  • Andere Studierende (insbesondere Lehramtsstudierende) erhalten für 50% der Punkte in den Präsenzübungen und das Vortragen der Lösung einer Aufgabe einen Übungsschein.
  • Eine Anmeldung zu einer Übungsgruppe ist nicht erforderlich.

Skript
  • Flussalgorithmen [PS] [PDF verkleinert] [PS verkleinert]
    Änderungen in der überarbeiteten Version des Skriptes vom 23.4.
    • S.13: Detailänderungen, verbesserter Aufschrieb
    • S.29: Detailänderungen, verbesserter Aufschrieb
    • S. 32: Fehler in der Laufzeitabschlätzung korrigiert, verbesserter Aufschrieb
    • S. 34: Detailänderungen, verbesserter Aufschrieb
    • S.39-41: (jetzt S. 39-42) ausführlichere Erklärungen, sowie Berücksichtigung der Korrektur von S. 32
    Beispiele
    • Beispiel Ford-Fulkerson 1 [PS] [PDF]
    • Beispiel Ford-Fulkerson 2 [PS] [PDF]
    • Beispiel Dinic [PS] [PDF]
    • Beispiel Cycle Cancelling [PS] [PDF]
  • Maximum Matchings [PS] [PDF]
    • Beispiel Hopcroft-Karp [PS] [PDF]
    • Hinweis: Die Beweise der Lemmata 9 und 10 sind nicht prüfungsrelevant.
  • Stabile Paarungen [PS] [PDF]
  • Lineare Programmierung
    • Folien zu Simplex- und Ellipsoidmethode [PS] [PDF]
    • Skript mit Detail- und Hintergrundinformationen [PS] [PDF]
    • Prüfungsrelevant ist der Inhalt der Folien sowie Kapitel 4 des Skriptes zum Thema Dualität.
  • Approximationsalgorithmen [PS] [PDF]
  • Onlinealgorithmen [PS] [PDF]
  • Randomisierte Algorithmen [PS] [PDF]
    Hinweis: Dieser Teil ist nicht prüfungsrelevant für Bachelor-Studenten.
Übungsblätter

  • Ausgabe: Dienstags im Verlauf des Nachmittags.
  • Abgabe: Dienstags bis 17:00h.
  • aktualisierte Terminplanung Übung [PDF]

Kontakt