Modul Ausgewählte Kapitel der Algorithmik (WiSe 2021/22)

Veranstalter Prof. Dr. Kevin Buchin
Modul Diplom, Master INF-MSc-603 (Informatik, Angewandte Informatik)
Veranstaltungsart VO 2 + UE 2
Veranstaltungsnummer 042605
Moodle ab November

Inhalt und Themen

In der Vorlesung werden Approximationsalgorithmen für geometrische Probleme besprochen. Für manche geometrische Probleme haben bekannte exakte Algorithmen eine hohe Laufzeit, manche davon sind sogar NP-schwer. Für diese Probleme wollen wir uns stattdessen effizientere Approximationsalgorithmen anschauen. Dabei wollen wir uns sowohl Probleme auf Punktmengen (z.B. closest pair, clustering) sowie auf Graphen (z.B. spanning trees, Euclidean TSP) anschauen, und verschiedene Methoden zum Entwurf von Approximationsalgorithmen kennenlernen (z.B. grids, sampling, reweighing).

Als Vorkenntnisse wird die Vorlesung “Algorithmen und Datenstrukturen” oder vergleichbare Kenntnisse erwartet.

Ort und Zeit

  • Vorlesung + Übung:
    • Dienstag, 10:15-14:00 Uhr, Raum 304, Otto-Hahn-Str. 14
  • Beginn der Vorlesungen: Dienstag, 12. Oktober 2021

Prüfungen

  • Prüfungen (s. Modulbeschreibung sowie Folien der ersten Vorlesung):
    • mündlich
    • aktive Teilnahme (inkl. Präsentation eigener Lösungen)

Materialien

  • Vorlesungsfolien
  • Das Buch “Geometric Approximation Algorithms” von Sariel Har-Peled. Online verfügbar hier

Themen

Ansprechpartner

Bei Fragen zu dieser Veranstaltung wenden Sie sich bitte an Kevin Buchin (bis November über die kevin.buchin@cs E-Mail Adresse)

 
Last modified: 2021-11-23 09:01 by Kevin Buchin
DokuWikiRSS-Feed