Effiziente Algorithmen (SoSe 2014)

Die Veranstaltung entspricht auch der auslaufenden Vorlesung “Effiziente Algorithmen und Komplexitätstheorie” im Diplomstudiengang Informatik / Angewandte Informatik als Wahlpflichtveranstaltung sowie dem Modul MD V “Effiziente Algorithmen” im Master Datenwissenschaften. Die begleitende Übung ist für das Verständnis des Stoffes sehr wichtig.

• Vorlesung:
  • Dienstag, 10:15-11:45 Uhr, SRG1 1.001
  • Donnerstag 12:15-13:45 Uhr, OH14 E23
• Beginn der Vorlesungen: Dienstag, 08.04.2013 (KW15)
• Übungen: siehe begleitende Übungen
• Übungsklausur: 3. Juli (Donnerstag, im Rahmen der Vorlesung)

• Achtung: Für alle Prüfungen gilt:
  • rechtzeitige Anmeldung bei Ihren Prüfungsämtern notwendig
  • Ausweise mitbringen (Immatrikulationsnachweis und ID oder Pass)
  • keine Hilfsmittel erlaubt

• Bachelor Informatik / Angewandte Informatik / Master Datenwissenschaften
  • Klausur, 90 Minuten, keine Hilfsmittel
  • Klausurtermin: Mo 21.07.2014 (11:00-12:30), EF50 HS3
    • Klausurergebnisse: Download (PDF)
    • Klausureinsicht: Mi 10.09.2014 von 10:00 bis 11:00 Uhr in OH14 Raum 202
  • Wiederholungstermin: Mo 15.09.2014 (08:00-09:30), EF50 HS2
    • Klausurergebnisse: Download (PDF)
    • Klausureinsicht: Mo 03.11.2014 von 10:00 bis 11:00 Uhr in OH14 Raum 202
  • Stoff der Vorlesung und der Übungen

• Diplom Informatik / Angewandte Informatik
  • mündliche Prüfung, 20 Minuten
  • Stoff der Vorlesung und der Übungen

• Lehramt
  • mündliche Prüfung oder Klausur, 20 oder 45 Minuten, je nach Prüfungsordnung und Prüfungsanmeldung
  • Stoff der Vorlesung und der Übungen

• Sonstige Studiengänge / Nebenfächer auf Anfrage

• Die in DAP 2 eingeführten Basistechniken werden vertieft und auf komplexere Probleme angewendet, hinzu kommen ausgewählte Probleme mit großen Anwendungsbereichen, weitergehende Aspekte wie Approximation und weitergehende Entwurfsmethoden wie primal-duale Ansätze. Themen, u.a.:
• Graphenalgorithmen, wie z.B. starker Zusammenhang in Graphen, Maximale Matchings, Netzwerkflussprobleme, Schnittprobleme (Min Cut vs. Max Cut), Travelling Salesman Problem, Vertex Cover, MaxSAT
• Analysetechniken, wie z.B. Amortisierte Analyse von Algorithmen, Analyse randomisierter Algorithmen
• Optimierungstechniken, wie z.B. Lineare Programmierung, Approximationsgüte und -schemata
• Hashing Verfahren, Skiplisten, String Matching

Weitere Informationen: s. Modulbeschreibung.

Die Vorlesung ist wie folgt in Kapitel und Abschnitte gegliedert (die Gliederung wird synchron zur Vorlesung ergänzt):

1. Einführung (VO 1)
2. Tiefensuche und 2-Zusammenhang (VO 2)
   1. Tiefensuche (Wdh. aus DAP 2)
   2. Zweizusammenhang
3. Starke Zusammenhangskomponenten (VO 3)
   1. Tiefensuche in gerichteten Graphen
   2. Starker Zusammenhang
4. Maximale Matchings in Graphen (VO 4-5)
   1. Matchings in bipartiten Graphen
   2. Matchings in allgemeinen Graphen
5. Flüsse in Graphen (VO 6-10)
   1. Das Flussproblem
   2. Der Algorithmus von Ford und Fulkerson
   3. Das Max-Flow / Min-Cut Theorem
   4. Der Algorithmus von Dinic
   5. Der Algorithmus von Malhotra et al.
   6. Der Goldberg-Tarjan Algorithmus
6. Amortisierte Analyse (VO 11-12)
   1. Potenzialmethode
   2. Kostenverteilung
   3. Kontenmethode
   4. Union/Find mit Pfadkompression
7. String Matching (VO 12-16)
   1. Einleitung und naiver Algorithmus
   2. String Matching mit DEAs
   3. Algorithmus von Knuth, Morris, Pratt
8. Approximationsalgorithmen (VO 17)
   1. Grundbegriffe
   2. FPTAS für das Rucksackproblem
9. Das Traveling Salesman Problem (VO 18)
   1. Motivation & Grundlagen
   2. Approximationen für das metrische TSP
10. Analyse randomisierter Algorithmen für Erfüllbarkeitsprobleme (VO 19-20)
    1. Randomisierte Algorithmen
    2. Approximation für MAX-k-SAT
    3. Randomisiertes Runden
11. Schnittprobleme (VO 21-22)
    1. Max Cut
    2. Ein randomisierter Min-Cut Algorithmus
    3. Fast Min-Cut
12. Hashing (VO 23-24)
    1. Universelles Hashing
    2. Statisches perfektes Hashing
    3. Cuckoo Hashing
13. Skiplisten (VO 25)
    1. Perfekte Skiplisten
    2. Randomisierte Skiplisten