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
 
Last modified: 2020-12-17 17:05 by berndzey
DokuWikiRSS-Feed