Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Mastervorlesung

Ausgewählte Kapitel der Algorithmik

im Wintersemester 2018/2019



.
Veranstalter:Jun.-Prof. Dr. Maike Buchin
Termine: VorlesungMontag, 10-12 UhrOH14-304ab: 8.10.2018
ÜbungMontag, 12-14 UhrOH14-304ab: 15.10.2018
Beginn: 8.10.2018


[Aktuelles] [Inhalt] [Vorlesung] [Übungsblätter] [Literatur]


Aktuelles




Inhalt

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.


Vorlesung

Datum Themen Kapitel in der Literatur
8.10.2018 Closest Pair [H] 1.1,1.2
15.10.2018 k-enclosing disk [H] 1.3,1.4
22.10.2018 Quadtrees [H] 2.1,2.2.1
29.10.2018 Komprimierte Quadtrees, WSPD [H] 2.2, 3.1
5.11.2018 WSPD mit Anwendungen [H] 3.1, 3.2
12.11.2018 Clustering [H] 4
19.11.2018 VC Dimension [H] 5.1
26.11.2018 epsilon-samples und -nets [H] 5.3
3.12.2018 Geometric Set Cover [H] 6.3
10.12.2018 Trapezzerlegung [H] 8.1,(8.2)
17.12.2018 Approximation der Tiefe [H] 10.1, 10.2
7.1.2019 Zufällige Partitionen [H] 11.1, (11.3)
21.1.2019 Fat Triangulations [H] 12
28.1.2019 Euklidischer TSP [H] 13


Übungsblätter

Übungsblatt Besprechung
Übungsblatt 01 15.10.2018
Übungsblatt 02 22.10.2018
Übungsblatt 03 29.10.2018
Übungsblatt 04 5.11.2018
Übungsblatt 05 12.11.2018
Übungsblatt 06 19.11.2018
Übungsblatt 07 26.11.2018
Übungsblatt 08 3.12.2018
Übungsblatt 09 10.12.2018
Übungsblatt 10 17.12.2018
Übungsblatt 11 7.1.2019
Übungsblatt 12 21.1.2019


Literatur



Letzte Änderung am 28.1.2019 von M. Buchin