Effiziente Algorithmen (SoSe 2019)

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

Die Veranstaltung entspricht auch 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, 12:15-13:45 Uhr, OH14 E23
- Donnerstag 12:15-13:45 Uhr, OH14 E23
Beginn der Vorlesungen: Dienstag, 2.04.2019
Übungen: siehe begleitende Übungen

Prüfungen

Für die Bachelor-Studierenden der Informatik und der Angewandten Informatik findet die Klausur statt am:
- Donnerstag, dem 11. Juli 2019 um 18:30 Uhr im SRG 1, H.001

Die Wiederholungsklausur findet statt am:
Dienstag, dem 17. September 2019 um 11:00 Uhr im HG 2, HS 5

Studierende anderer Fachrichtungen haben entweder mündliche Prüfungen oder auch Klausur. Die genauen Konditionen werden in der Vorlesung bekannt gegeben (s. Folien). Im Falle einer Klausur findet diese zeitgleich mit den obigen Klausuren statt. Bitte beachten Sie die Anmeldefristen für die Prüfungen beim Prüfungsamt, die für Klausuren sehr früh sind.

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 Moodle-Arbeitsraum.
Sie können oben den Arbeitsraum aufrufen, falls Sie für diesen Raum eingeschrieben sind.
Dazu müssen Sie sich anmelden. Hierzu benötigen Sie ein Password, das Sie in der ersten Vorlesungsstunde erhalten. Falls Sie dort verhindert sein sollten, dann erhalten Sie es in der zweiten Stunde. Bitte vor Freitag 5.4. nicht per Email nach dem Password fragen.