Effiziente Algorithmen (SoSe 2013)

Veranstalter	Petra Mutzel
Modul	INF-BSc-221 (Bachelor Informatik / Angewandte Informatik)
Veranstaltungsnummer	040221
EWS	EWS-Arbeitsraum
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, OH14 E23
- Donnerstag 12:15-13:45 Uhr, OH14 E23
Beginn der Vorlesungen: Dienstag, 09.04.2013 (KW15)
Übungen: siehe begleitende Übungen
Übungsklausur: 18.06.2013 (während der Vorlesungszeit)

Prüfungen

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: 23.07.2013 10-12 Uhr
  - Klausureinsicht: 20.08.2013 12-13 Uhr / OH14 R202
- Wiederholungstermin: 07.10.2013 12-14 Uhr
  - Klausureinsicht: 16.10.2013 14-15 Uhr / OH14 R202
- 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

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.