Algorithmen und Datenstrukturen (WS 2020/2021)

Veranstalter	Dr. Bernd Zey
Modul	Modulhandbuch INF-MSc-241 (Master Informatik / Angewandte Informatik)
Schwerpunktgebiet	4, 6, 7 (Diplom Informatik / Angewandte Informatik)
SWS	4
Veranstaltungsnummer:	041237
Moodle	Moodle

Organisation

Vorlesung
- Prinzip des inverted classroom
- Vorlesungsvideos im Moodle
- Regelmäßig FAQ-Termine (werden im Moodle bekannt gegeben)
- Beginn der Vorlesungen: in der 44. KW, 02.11.-06.11.
Wichtig Melden Sie sich im Moodle zu dieser Veranstaltung an
- Im Moodle sind alle Materialien
- Nur dadurch bietet sich die Möglichkeit, alle Studierende der Veranstaltung per eMail zu erreichen
Informationen zu den Übungen:
- Wöchentlich
- 2 mögliche Termine:
  - Dienstag 16:15 Uhr
  - Mittwoch 10:15 Uhr

Prüfungen

Klausur, 90 Minuten
Stoff der Vorlesung und Übung
Die 2 Termine lauten wie folgt:
- Donnerstag, 18.02.2021, 15:30-17:00 Uhr
- Montag, 22.03.2021 14:30-16:00

Inhalte

Diese Vorlesung mit der begleitenden Übung gibt einerseits die Grundlagen für die meisten weiterführenden Spezialvorlesungen im Bereich algorithmische und formale Grundlagen, zum anderen behandelt sie weiterführende und komplexere Algorithmen und Datenstrukturen. Sie kann als Weiterführung von “DAP2” und “Effiziente Algorithmen” gesehen werden. Zum Teil kann es zu einzelnen Überschneidungen der Themen kommen. Im Einzelnen werden die folgenden Themen behandelt:

Komplexe Datenstrukturen und deren Analyse, wie z.B. Fibonacci-Heaps
Lineare Programmierung: Modellierung, Dualität, Simplexalgorithmus
Ganzzahlige Lineare Programmierung, z.B. Modellierung von Problemen
Kombinatorische Optimierung, z.B. primal-duale Algorithmen, Branch-and-Cut
Approximationsalgorithmen, z.B. Set Cover, Steiner Tree
Graphenalgorithmen: z.B. dynamische kürzeste Wege, Steiner Tree
Geometrische Datenstrukturen: z.B. Quadtree, kd-tree
Analysemethoden, wie z.B. amortisierte Analyse
Fixed-Parameter-Tractable, z.B: Treewidth, Kernelization