Algorithmen und Datenstrukturen
im Wintersemester 2017/2018
Veranstalter: | Jun.-Prof. Dr. Maike Buchin |
Termine: | Dienstag | 12:15-13:45 Uhr | HG1-HS5 (Südcampus) |
| Donnerstag | 12:15-13:45 Uhr | SRG1-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: | Donnerstag | 08:15-09:45 Uhr | OH14-104 |
| Donnerstag | 10:15-11:45 Uhr | OH14-104 |
| Donnerstag | 14:15-15:45 Uhr | OH14-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