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
    • Der Einschreibeschlüssel lautet AuD2021
  • Informationen zu den Übungen:
    • Wöchentlich
    • 2 mögliche Termine:
      • Dienstag 16:15 Uhr
      • Mittwoch 10:15 Uhr

Prüfungen

  • Es wird eine Klausur angeboten, Zeitumfang 90 Minuten.
  • Die vorläufige Planung sieht folgende Kalenderwochen für die 2 Termine vor:
    • 07. KW: 15.-20.02.2021
    • 12. KW: 22.-27.03.2021

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-10-25 17:53 by Bernd Zey
DokuWikiRSS-Feed