Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Algorithmen und Datenstrukturen

im Wintersemester 2017/2018


Veranstalter:Jun.-Prof. Dr. Maike Buchin
Termine: Dienstag12:15-13:45 Uhr HG1-HS5 (Südcampus)
Donnerstag12:15-13:45 UhrSRG1-2.008
Beginn: Dienstag, 10.10.2017


[Aktuelles] [Inhalt] [Übungen] [Prüfung] [Vorkenntnisse] [Literatur] [Moodle]


Aktuelles

19.02.2018: Die mündlichen Prüfungen finden im Raum OH14-307 statt.

26.01.2018: Termine für die mündlichen Prüfungen werden in der kommenden Woche in den Vorlesungen (30.01. und 01.02.) und am Mittwoch (31.01) zwischen 9:30 und 12:00 Uhr in OH14-307 vergeben, sowie anschließend per Mail an Maike Buchin.

18.01.2018: Eine Liste der möglichen Prüfungsfragen ist in Moodle angeboten.

12.12.2017: Als Literatur für das Thema Kombinatorische Optimierung wurde ein Teil des Skripts von Prof. Dr. P. Mutzel in Moodle zur Verfügung gestellt.

12.12.2017: Die Vorlesung am 12.12. (Dienstag) fällt krankheitsbedingt aus.

06.12.2017: Für das Thema "Ganzzahlige lineare Programmierung" gibt es als Zusatzmaterial eine Skript vom Imperial College London.

30.10.2017: Am Donnerstag, den 02.11.2017 wird statt der Vorlesung ein Repetitorium über das Thema "Konvexe Hülle" gegeben (SRG1-2.008, 12:15 Uhr). Die Übungen am Donnerstag, den 02.11.2017 fallen aus.

30.10.2017: Für einige Vorlesungsthemen werden die Folien in Moodle angeboten. Bitte laden Sie aus Moodle die Folien über konvexen Hüllen herunter.

26.10.2017: Raumänderung Ab 02.11.2017 wird die Vorlesung donnerstags in SRG1-2.008 stattfinden. Die Vorlesung dienstags bleibt am Campus-Süd.

26.10.2017: Die kurze Zusammenfassungen der Vorlesungen 1 bis 6 wurden in Moodle hochgeladen. Diese Datei wird nach jeder Vorlesung aktualisiert.

19.10.2017: Die Folien über Fibonacci Heaps (aus Cambridge University) wurden als Zusatzmaterial angeboten.

18.10.2017: Die Zusammenfassung der Vorlesung über Binomial Heaps wurde in Moodle hochgeladen. Es wurden als Zusatzmaterial die Folien von R. Chowdhury von Stony Brook University angeboten.

12.10.2017: Die Übungsblätter werden in Moodle zur Verfügung gestellt. Der Zugang zur Moodle-Veranstaltung ist mit Uni-Account frei. Das erste Blatt wurde am 12.10.2017 hochgeladen.

10.10.2017: Wegen höher Teilnehmeranzahl wird eine dritte Übungsgruppe angeboten. Sie wird donnerstags, 8-10 Uhr stattfinden.

10.10.2017: Die Anmeldung für die Übungen wird ab Dienstag, den 10.10.2017 um 20:00 Uhr (auf Anfrage der Studierenden für Abend verschoben) bis Sonntag, den 15.10.2017 um 23:59 Uhr in ASSESS freigeschaltet. Bei Probleme wenden Sie sich per Email an Amer Krivošija.


Inhalt

Die Veranstaltung behandelt fortgeschrittene Entwurfs- und Analysemethoden für Algorithmen und Datenstrukturen. Sie kann als Weiterführung von "Datenstrukturen, Algorithmen und Programmierung" und als Grundlage für die entsprechenden Vertiefungsmodule gesehen werden.

Themen

  • Heaps und die amortisierte Analyse
  • Geometrische Algorithmen
  • Lineare Programmierung
  • Kombinatorische Optimierung
  • Geometrische Datenstrukturen
  • Approximationsalgorithmen

Vorlesungen

Datum Themen Kapitel in der Literatur Hilfreiche Links Zusatzmaterial
10.10.2017 Organisatorisches, Wdhl. Dijkstra Algorithmus, Wdhl. Binäre Heaps CLRS: 24.3, 6
12.10.2017 Amortisierte Analyse CLRS: 17
17.10.2017 Binomial Heaps CLRS: 19 CLRS-2.Ed. Ch.19 Folien SBU
19.10.2017 Fibonacci Heaps CLRS: 19 (2. Ausg: 20) Folien 1 Folien 2
24.10.2017 Konvexe Hülle: Eingenschaften, Langsamer Algorithmus, Untere Schranke CLRS: 33.3; Mt: 3
26.10.2017 Konvexe Hülle: Algorithmen von Graham, Jarvis und Chan dBCvKO: 1; Mt: 4 Folien Konvexe Hülle
07.11.2017 Streckenschnitte CLRS: 33.2; dBCvKO: 2; Mt: 5 Folien Streckenschnitte
09.11.2017 Lineare Programmierung in 2D dBCvKO: 4.3-4.4; Mt: 8 Folien LP in 2D
14.11.2017 Lineare Programmierung in 2D (fort.) dBCvKO: 4.5; Mt: 8; V1: 1.1 Folien LP in 2D
16.11.2017 Lineare Programmierung: das Simplexverfahren V1: 2.1-2.2 Manuskript V1 Folien RWTH
21.11.2017 Lineare Programmierung: das Simplexverfahren (fort.) V1: 2.2
23.11.2017 Lineare Programmierung: das Simplexverfahren (fort.) V1: 2.3-2.5
28.11.2017 Dualität in der Linearen Programmierung V1: 4
30.11.2017 Aspekte der Ganzzahligkeit V1: 5
05.12.2017 Ganzzahlige LPs und Branch and Bound CLRS: 29.2; V1: 4.3 Skript Imp.Coll.
07.12.2017 Kombinatorische Optimierung Mutz: 4.1.1, 4.2.2, 4.3 Skript P. Mutzel (teil)
14.12.2017 Approximationsalgorithmen V2: 1.1, 1.2, 1.3 Manuskript V2 Folien M. de Berg
19.12.2017 Approximationsalgorithmen (insb. Set Cover) V2: 1.4
21.12.2017 Approximationsalgorithmen (insb. TSP) V2: 2; CLRS: 35
09.01.2018 Approximationsalgorithmen (insb. Scheduling I) V2: 3
11.01.2018 Approximationsalgorithmen (insb. Scheduling II) V2: 3.2
16.01.2018 Approximationsalgorithmen (insb. Scheduling III) V2: 4
18.01.2018 Geometrische Bereichsabfragen (kd-Bäume) dBCvKO: 5.1, 5.2; Mt: 31 Folien KD Bäume
23.01.2018 Geometrische Bereichsabfragen (Range Trees) dBCvKO: 5.3, 5.6; Mt: 32 Folien Range Trees
25.01.2018 Geometrische Bereichsabfragen (Range Trees) dBCvKO: 10.1, 10.3; Mt: 33, 34 Folien Fensterabfragen
30.01.2018 Voronoi Diagramme dBCvKO: 7; Mt: 11 Folien Voronoi-Diagramme
01.02.2018 Delaunay-Triangulierungen dBCvKO: 9; Mt: 12, 13 Folien Delaunay-Triangulierungen



Übungen

Veranstalter:Amer Krivošija
Termine: Donnerstag08:15-09:45 UhrOH14-104
Donnerstag10:15-11:45 UhrOH14-104
Donnerstag14:15-15:45 UhrOH14-104
Beginn: Donnerstag 19.10.2017


In den Übungen werden Aufgaben gemeinsam gelöst und besprochen. Es soll in Gruppen zusammengearbeitet werden. Die Übungsblätter werden in Moodle zur Verfügung gestellt. Der Zugang zur Moodle-Veranstaltung ist mit Uni-Account frei.


Prüfung

Die Veranstaltung wird mündlich geprüft. Prüfungen finden in der vorlesungsfreien Zeit statt.


Vorkenntnisse

Sie sollten vertraut sein mit grundlegenden Techniken der Analyse von Algorithmen, den Algorithmenparadigmen Teile und Herrsche, gierige Algorithmen und dynamisches Programmieren, sowie balancierten Suchbäumen. Diese werden in der Regel in Büchern zu Algorithmen und Datenstrukturen beschrieben, wie zum Beispiel dem Buch von Cormen, Leiserson, Rivest und Stein.



Literatur und nützliche Links

  • [CLRS] Cormen, Leiserson, Rivest, Stein: "Introduction to Algorithms", MIT Press / McGraw-Hill, 3rd ed., ISBN: 978-0-262-03384-8
    deutsche Ausgabe: Cormen, Leiserson, Rivest, Stein: "Algorithmen - eine Einführung", Oldenbourg, 3. Auflage, ISBN: 978-3-486-59002-9
  • [dBCvKO] M. de Berg, O. Cheong, M. van Kreveld, M. Overmars: "Computational Geometry. Algorithms and Application.", Springer, 3rd ed., ISBN: 978-3-540-77973-5
  • [dBvKOS] (erste Ausgabe von [dBCvKO]) M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: "Computational Geometry. Algorithms and Application.", Springer, 1st ed.
  • [Mt] D. Mount: Computational Geometry - Lecture Notes Fall 2016
  • [Mutz] P. Mutzel: Skript zur Vorlesung Algorithmen und Datenstrukturen in Moodle
  • [V1] B. Vöcking: Lineare Programmierung. Manuskript und Folien.
  • [V2] B. Vöcking: Approximationsalgorithmen. Manuskript.


Letzte Änderung am 19.02.2018 von A. Krivošija