Section outline

  • Общее

    Свернуть всё Развернуть всё

  • 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

  • Vorlesungsfolien

    • 01. Vorlesung (21.04.2020): Einleitung und zwei Beispiele: TSP und MIS [Update 21.04., 10:13 auf den Stand des Videos] Файл
    • 01. Vorlesung (21.04.2020): Druckversion Файл
    • 01. Vorlesung (21.04.2020): Video Страница
    • 02. Vorlesung (28.04.2020): Verzweigungsalgorithmus für k-SAT Файл
    • 02. Vorlesung (28.04.2020): Druckversion Файл
    • 02. Vorlesung (28.04.2020): Video Страница
    • 03. Vorlesung (05.05.2020): Minimum Dominating Set Файл
    • 03. Vorlesung (05.05.2020): Druckversion Файл
    • 03. Vorlesung (05.05.2020): Video Файл
    • 04. Vorlesung (12.05.2020): Measure & Conquer [15.5.: kleine Ergänzungen dank AE] Файл
    • 04. Vorlesung (12.05.2020): Druckversion Файл
    • 04. Vorlesung (12.05.2020): Video (Teil I – M & C für MIS) Файл
    • 04. Vorlesung (12.05.2020): Video (Teil II – M & C für Set Cover) Файл
    • 05. Vorlesung (19.05.2020): Inclusion–Exclusion [22.05.: N_0 ≠ N(∅) – Danke, FE!] Файл
    • 05. Vorlesung (19.05.2020): Druckversion Файл
    • 05. Vorlesung (19.05.2020): Video (24 Min.) Файл
    • 06. Vorlesung (26.06.2020): Graphfärben Файл
    • 06. Vorlesung (26.06.2020): Druckversion Файл
    • 06. Vorlesung (26.05.2020): Video (Teil I – Algorithmen von Lawler und Byskov, 25 Min.) Файл
    • 06. Vorlesung (26.06.2020): Video (Teil II – Bestimmung der chromatischen Zahl, 16 Min.) Файл
    • 07. Vorlesung (09.06.2020): Allgemeine Inclusion–Exclusion, angewandt auf Färbung Файл
    • 07. Vorlesung (09.06.2020): Druckversion Файл
    • 07. Vorlesung (09.06.2020): Video Страница
    • 08. Vorlesung (16.06.2020): Teilbaumprobleme und Zerlegungsprobleme [Laufzeit DP gefixt] Файл
    • 08. Vorlesung (16.06.2020): Druckversion Файл
    • 08. Vorlesung (16.06.2020): Video (Teil I – Teilbaumprobleme, 20 Min.) Файл
    • 08. Vorlesung (16.06.2020): Video (Teil II – Zerlegungsprobleme, 6 Min.) Файл
    • 09. Vorlesung (23.06.2020): Teil I: Fest-Parameter-Berechenbarkeit (Wiederholung AGT) Файл
    • 09. Vorlesung (23.06.2020): Druckversion Файл
    • 09. Vorlesung (23.06.2020): Video (FPT, 42 Min.) Страница
    • 09. Vorlesung (23.06.2020): Teil II: Reduktionen und die W-Hierarchie Файл
    • 09. Vorlesung (23.06.2020): Druckversion Файл
    • 10. Vorlesung (30.06.2020): Kernbildung [30.6.: Bildchen für Regeln 3 und 4 hinzugefügt] Файл
    • 10. Vorlesung (30.06.2020): Druckversion Файл
    • 10. Vorlesung (30.06.2020): Video (36 Min.) Страница
    • 11. Vorlesung (07.07.2020): Alternative Parameterisierungen; Baumzerlegung [07.07., 15:50: kleine Änderungen] Файл
    • 11. Vorlesung (07.07.2020): Druckversion Файл
    • 11. Vorlesung (07.07.2020): Video (Teil I – Unabhängige Menge auf Bäumen und serienparallelen Graphen, 12 Min.) Файл
    • 11. Vorlesung (07.07.2020) Video (Teil II – Nette Baumzerlegungen, 22 Min.) Файл
    • 12. Vorlesung (13.07.2020): Iterative Kompression Файл
    • 12. Vorlesung (13.07.2020): Druckversion Файл
    • 12. Vorlesung (14.07.2020): Video (Teil I – Iterative Kompression für Vertex Cover, 9 Min.) Файл
    • 12. Vorlesung (14.07.2020): Video (Teil II – Iterative Kompression für Feedback Vertex Set in Turnieren, 20 Min.) Файл

  • Zusätzliche Materialien