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