Effiziente Algorithmen (SoSe 2015)

Veranstalterin Petra Mutzel
Modul INF-BSc-221 (Bachelor Informatik / Angewandte Informatik)
Veranstaltungsnummer 040221
EWS EWS-Anmeldung
SWS 4 VO + 2 UE

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.

Ort und Zeit

  • Vorlesung:
    • Dienstag, 10:15-11:45 Uhr, OH12 E003
    • Donnerstag 12:15-13:45 Uhr, OH14 E23
  • Beginn der Vorlesungen: Dienstag, 07.04.2015 (KW15)
  • Übungen: siehe begleitende Übungen

Prüfungen

  • Für die Bachelor-Studierenden der Informatik und der Angewandten Informatik findet die Klausur statt am:
    • Dienstag, dem 21. Juli 2015 von 12-14 Uhr statt
  • Die Wiederholungsklausur findet am
    • Dienstag, dem 22. September 2015 von 10-12 Uhr statt
  • Studierende anderer Fachrichtungen haben entweder mündliche Prüfungen (wie z.B. Diplom-Informatik) oder auch Klausur. Die genauen Konditionen wurden in der Vorlesung bekannt gegeben (s. Folien). Im Falle einer Klausur findet diese zeitgleich mit den obigen Klausuren statt.

Zusammenfassung

  • 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.

Materialien

Die Vorlesungsfolien und begleitende Materialien finden Sie im EWS-Arbeitsraum. Sie können sich oben für den Arbeitsraum anmelden.

 
Last modified: 2016-03-16 20:03 by Petra Mutzel
DokuWikiRSS-Feed