Teaching

Algorithmische Diskrete Mathematik

Sommersemester 2019
03-M-WP-18, 6 CP (+3 CP bei optionaler Zusatzleistung)


Inhalt

  • Einführung in Graphentheorie, kombinatorische und lineare Optimierung
  • Graphentheorie: Grundbegriffe, Wege in Graphen, Euler- und Hamiltonkreise, Bäume
  • Algorithmische Grundlagen (Kodierungslänge, Laufzeit, Polynomialzeitalgorithmen)
  • Spannbäume, Matchings, Netzwerkflüsse und -schnitte (kombinatorische Algorithmen)
  • Einblick in lineare Optimierung: Modellierung und Struktur linearer Programme, Polyeder, Optimalitätskriterien, Dualität, Simplex-Algorithmus
  • Elemente der Komplexitätstheorie

Dozentin:
Assistent:
Prof. Dr. Nicole Megow (Email)
Lukas Nölke (Email)
Zeit & Raum:


Do 10-12 Uhr in Raum MZH 6210 (Vorlesung)
Mi 10-12 Uhr in Raum MZH 6340 (Übung)
Start:
Donnerstag, 4. April 2019
Datum Thema Unterlagen Übung (Abgabe)
4. April Einführung Folien, Notizen Blatt 1 (10.4.)
11. April Bäume, Minimale aufspannende Bäume (Prim, Kruskal), Clustering Folien Blatt 2 (24.4.)
25. April Grundlagen Algorithmen, Korrektheit und Laufzeit, Breitensuche Folien, Notizen Blatt 3 (2.5.)
2. Mai Kürzeste Wege, Dijkstra's Algorithmus Folien, Notizen Blatt 4 (8.5.)
9. Mai Kürzeste Wege II (Bellman-Ford, Floyd-Warshall), Dynamische Programmierung, Knapsack Problem Folien, Notizen, [KV] 17.2 Blatt 5 (15.5.)
16. Mai Netzwerkflüsse, Max Fluss/Min Schnitt Theorem Folien, Notizen Blatt 6 (22.5.), Netzwerk
23. Mai Matchings, Satz von König, Satz von Hall Notizen Blatt 7 (29.5.)
29. Mai Hungarische Methode - Selbststudium Notizen Blatt 8 (12.6.)
13. Juni Matchings, Satz von Berge, stabile Matchings Notizen, Handout Blatt 9 (19.6.)
20. Juni Einblick in Komplexitätstheorie (P, NP, polynomielle Reduktion, NP-schwer/vollständig, Beispiele) Handout, Notizen Blatt 10 (26.6.)
27. Juni Approximationsalgorithmen, Metrisches TSP, Christofides, Inapproximierbarkeit Buchkapitel Vazirani Kap. 3 Blatt 11 (3.7.)
4. Juli Einblick in Lineare Optimierung Handout, Notizen
11. Juli Einblick in Online Optimierung, Zusammenfassung/Überblick Notizen

Geben Sie bitte bei Abgabe der Übungsblätter die Namen und Matrikelnummern aller Mitwirkenden ab.

Literatur:

  • [KV] Korte, Vygen: Kombinatorische Optimierung: Theorie und Algorithmen, Springer, 2012.
  • [KN] Krumke, Noltemeier: Graphentheoretische Konzepte und Algorithmen, Springer-Vieweg, 2012.
  • [CLRS] Corman, Leiserson, Rivest, Stein: Introduction to Algorithms, 3rd edition, MIT Press, 2009.
  • [KT] Kleinberg, Tardos: Algorithm Design, Pearson, 2006.
  • [AMO] Ahuja, Magnanti, Orlin: Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, 1993.
  • [BT] Bertsimas, Tsitsiklis: Introduction to Linear Optimization, Athena Scientific, 1997.
  • [GKT] Guenin, Könemann, Tuncel: A Gentle Introduction to Optimization, Cambridge University Press, 2014.

ADM Zusatzseminar - 17.9.19, MZH 1110

08:30 - 09:15   Angelina Matis: Minimum Bounded Degree Spanning Trees (deutsch)
09:25 - 10:10   Gideon Klaila: Expander graphs and their applications
10:30 - 11:15   Nele Schriefer: Approximation Algorithms for distance-constrained vehicle routing
11:25 - 12:10   Arndt Kathmann: Introduction to algorithmic game theory: Routing games

13:15 - 14:00   Oliver Link: Maintaining Matchings Online (deutsch)