Course: SS20: Exakte Algorithmen

Topic outline

General

Collapse all Expand all
- Announcements Forum

Kursdaten

Module:	Ausgewählte Kapitel der Algorithmik / Theorie / Informatik
Kursumfang:	5 ECTS (2 SWS)
Zeit & Ort:	– Vorlesungen dienstags, 14:15–15:45, ~~ÜR I~~ – Übungen donnerstags, 14:15–15:45, ~~Besprechungszimmer 00.001 im neuen Gebäude~~ M4 Bis auf weiteres finden zu den obengenannten Zeiten Online-Sprechstunden auf ifiChat statt. Zur Teilnahme muss man sich ggf. erst bei der Benutzerverwaltung der IT des Instituts ein Benutzerkonto einrichten ("New account" klicken). Die beiden Kanäle exakt-vorlesung und exakt-uebung sind jetzt privat. Wenn Sie den Diskussionen folgen oder sich beteiligen möchten, schicken Sie uns eine Email, damit wir Sie hinzufügen können.
Zielgruppe:	Master Informatik, Master Mathematik, Master Computational Mathematics
Lecturers:	Alexander Wolff (Vorlesungen) Felix Klesen (Übungen)
Prüfung:	mündlich (genaues Datum wird noch festgelegt) Anmeldung unter WueStudy unbedingt erforderlich!
Voraussetzung:	Algorithmische Graphentheorie (nachdrücklich empfohlen)
Sprache:	Englisch oder Deutsch (abhängig von den TeilnehmerInnen)

Kursbeschreibung
Inhalt
Für viele wichtige Probleme in der Informatik ist derzeit kein effizienter (d.h. polynomieller) Algorithmus bekannt. Ein prominentes Beispiel ist das Problem des Handlungsreisenden, bei dem es darum geht eine kürzeste Rundreise zu finden, die eine vorgegebene Menge von Stationen besucht. In dieser Vorlesung beschäftigen wir uns mit Entwurfs- und Analysetechniken für Algorithmen, die zwar im schlechtesten Fall exponentielle Laufzeit besitzen können, aber dennoch nachweisbar schneller als naheliegende Brute-Force-Ansätze sind.
Schlüsselwörter: Exakte Exponentialzeit-Algorithmen; parameterisierte Algorithmen.
Lernziele
Am Ende dieses Kurses sollen die Teilnehmer in der Lage sein, einfache exakte Algorithmen zu entwickeln oder zu analysieren. Außerdem sollen sie grundlegende Entwurfstechniken, wie beispielsweise Branching, dynamische Programmierung, Inclusion-Exclusion, Measure & Conquer, Kernelisierung und Suchbäume mit begrenzter Tiefe verstehen und anwenden können.
Prüfung
Die Note wird durch eine mündliche Pfüfung am Ende des Semesters bestimmt. Wer bei den Übungen mindestens 50% der Punkte erreicht, bekommt bei einer bestandenen Prüfung einen Notenbonus von 0,3 Notenpunkten.

Literatur

Parameterized Algorithms.
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh. Springer International Publishing 2015.
https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf
Exact Exponential Algorithms.
Fedor V. Fomin and Dieter Kratsch. Springer-Verlag Berlin Heidelberg 2010.
http://www.ii.uib.no/~fomin/BookEA/BookEA.pdf
Vorlesungsfolien
- 01. Vorlesung (21.04.2020): Einleitung und zwei Beispiele: TSP und MIS [Update 21.04., 10:13 auf den Stand des Videos] File
- 01. Vorlesung (21.04.2020): Druckversion File
- 01. Vorlesung (21.04.2020): Video Page
  
  Not available unless: Your ID number is not empty
- 02. Vorlesung (28.04.2020): Verzweigungsalgorithmus für k-SAT File
- 02. Vorlesung (28.04.2020): Druckversion File
- 02. Vorlesung (28.04.2020): Video Page
  
  Not available unless: Your ID number is not empty
- 03. Vorlesung (05.05.2020): Minimum Dominating Set File
- 03. Vorlesung (05.05.2020): Druckversion File
- 03. Vorlesung (05.05.2020): Video File
  
  Not available unless: Your ID number is not empty
- 04. Vorlesung (12.05.2020): Measure & Conquer [15.5.: kleine Ergänzungen dank AE] File
- 04. Vorlesung (12.05.2020): Druckversion File
- 04. Vorlesung (12.05.2020): Video (Teil I – M & C für MIS) File
  
  Not available unless: Your ID number is not empty
- 04. Vorlesung (12.05.2020): Video (Teil II – M & C für Set Cover) File
  
  Not available unless: Your ID number is not empty
- 05. Vorlesung (19.05.2020): Inclusion–Exclusion [22.05.: N_0 ≠ N(∅) – Danke, FE!] File
- 05. Vorlesung (19.05.2020): Druckversion File
- 05. Vorlesung (19.05.2020): Video (24 Min.) File
  
  Not available unless: Your ID number is not empty
- 06. Vorlesung (26.06.2020): Graphfärben File
- 06. Vorlesung (26.06.2020): Druckversion File
- 06. Vorlesung (26.05.2020): Video (Teil I – Algorithmen von Lawler und Byskov, 25 Min.) File
  
  Not available unless: Your ID number is not empty
- 06. Vorlesung (26.06.2020): Video (Teil II – Bestimmung der chromatischen Zahl, 16 Min.) File
  
  Not available unless: Your ID number is not empty
- 07. Vorlesung (09.06.2020): Allgemeine Inclusion–Exclusion, angewandt auf Färbung File
- 07. Vorlesung (09.06.2020): Druckversion File
- 07. Vorlesung (09.06.2020): Video Page
  
  Not available unless: Your ID number is not empty
- 08. Vorlesung (16.06.2020): Teilbaumprobleme und Zerlegungsprobleme [Laufzeit DP gefixt] File
- 08. Vorlesung (16.06.2020): Druckversion File
- 08. Vorlesung (16.06.2020): Video (Teil I – Teilbaumprobleme, 20 Min.) File
  
  Not available unless: Your ID number is not empty
- 08. Vorlesung (16.06.2020): Video (Teil II – Zerlegungsprobleme, 6 Min.) File
  
  Not available unless: Your ID number is not empty
- 09. Vorlesung (23.06.2020): Teil I: Fest-Parameter-Berechenbarkeit (Wiederholung AGT) File
- 09. Vorlesung (23.06.2020): Druckversion File
- 09. Vorlesung (23.06.2020): Video (FPT, 42 Min.) Page
  
  Not available unless: Your ID number is not empty
- 09. Vorlesung (23.06.2020): Teil II: Reduktionen und die W-Hierarchie File
- 09. Vorlesung (23.06.2020): Druckversion File
- 10. Vorlesung (30.06.2020): Kernbildung [30.6.: Bildchen für Regeln 3 und 4 hinzugefügt] File
- 10. Vorlesung (30.06.2020): Druckversion File
- 10. Vorlesung (30.06.2020): Video (36 Min.) Page
  
  Not available unless: Your ID number is not empty
- 11. Vorlesung (07.07.2020): Alternative Parameterisierungen; Baumzerlegung [07.07., 15:50: kleine Änderungen] File
- 11. Vorlesung (07.07.2020): Druckversion File
- 11. Vorlesung (07.07.2020): Video (Teil I – Unabhängige Menge auf Bäumen und serienparallelen Graphen, 12 Min.) File
  
  Not available unless: Your ID number is not empty
- 11. Vorlesung (07.07.2020) Video (Teil II – Nette Baumzerlegungen, 22 Min.) File
  
  Not available unless: Your ID number is not empty
- 12. Vorlesung (13.07.2020): Iterative Kompression File
- 12. Vorlesung (13.07.2020): Druckversion File
- 12. Vorlesung (14.07.2020): Video (Teil I – Iterative Kompression für Vertex Cover, 9 Min.) File
  
  Not available unless: Your ID number is not empty
- 12. Vorlesung (14.07.2020): Video (Teil II – Iterative Kompression für Feedback Vertex Set in Turnieren, 20 Min.) File
  
  Not available unless: Your ID number is not empty
Zusätzliche Materialien
- Lecture 2: Solving SAT by branching (source paper) URL
  
  This is the original paper giving the two branching algorithms for satisfiability as discussed in the lecture.
- Lecture 4 supplemental: Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms (by D. Eppstein) URL
- Lecture 6: Independent Sets by Byskov URL
- Lecture 7: Source paper for the (R,F,O) formulation URL
- Lecture 7: Counting 2-Sat solutions --- Fürer & Kasiviswanathan article URL
- Lecture 8: Subtrees Problems Source Paper URL
- Lecture 9: source paper -- W[1]-completeness of Indep. Set URL
- Lecture 11: Channel Assignment, NP-completeness on bounded treewidth graphs URL
- Exercise Sheet 13: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization URL
- Lecture 14: Bern's Article on Steiner Trees in Planar graphs URL

Topic outline

General

Kursdaten

Kursbeschreibung

Vorlesungsfolien

Zusätzliche Materialien