Section outline

  • Общее

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

    Vorlesung Algorithmische Graphentheorie

    Umfang: 5 ECTS, 2+2 SWS [T:2,P:0]
    Vorlesung: mittwochs, 10:30–11:30 Uhr, online
    Übungen: 1) freitags, 08:30–10:00 Uhr, online
    2) freitags, 10:15–11:45 Uhr, online
    3) freitags, 10:15–11:45 Uhr, online
    4) freitags, 12:15–13:45 Uhr, online

    Bis auf weiteres finden zu den obengenannten Zeiten Online-Sprechstunden statt. Wir nutzen hierfür Zoom der Uni Würzburg. Darüber hinaus stehen für Ankündigungen und Diskussionen Kanäle im Chat der Uni Würzburg zur Verfügung. Die entsprechenden Links für Zoom und den Uni-Chat finden Sie in der Sammlung von Links hierunter.
    Voraussetzung: Vorlesung Algorithmen und Datenstrukturen (dringend empfohlen)
    Zielgruppe: Bachelor Informatik ab 2. Semester
    Anmeldung:
    • Einschreibung hier in diesen Wuecampus-Kurs. (Klicken Sie dazu im Kursraum ganz oben links auf das Feld mit den weißen Zahnrädern auf blauem Grund und wählen Sie dann "Mich in diesem Kurs einschreiben" aus.) 
    • Die Anmeldung zur Klausur erfolgt über WueStudy (siehe auch das pdf zu allgemeinen Informationen weiter unten).
    Dozent: Alexander Wolff
    Übungen: Johannes Zink
    Tutoren: Diana Sieper, Vasil Alistarov, Tim Gerlach, Samuel Wolf
    Klausuren:

    Mo, 26.07., 10:00–12:00 (Turing, Z6) [Anmeldung bis 15.07.]
    Mi, 13.10., 09:00–11:00 (Turing, Zuse)
    Als Hilfsmittel ist nur ein einseitig handbeschriebenes Blatt (A4) zulässig.


    • Nachrichtenforum Форум
    • Diskussionsforum Форум
    • Links (Zoom & uw-Chat) zur Vorlesung und Übung Страница

  • Kursbeschreibung

    Inhalt

    Wir werden uns grob mit den folgenden Themengebieten der algorithmischen Graphentheorie auseinandersetzen:

    • kürzeste Wege,
    • Minimale Spannbäume,
    • Rundreiseprobleme (Euler- und Hamiltonkreise),
    • Flüsse,
    • Modellierung mittels (ganzzahliger) linearer Programmierung,
    • Matchings,
    • planare Graphen,
    • Färbbarkeit,
    • Approximation und Fest-Parameter-Berechenbarkeit.

    Lernziele

    Am Ende dieses Kurses sind HörerInnen in der Lage typische Probleme der Informatik als Graphenprobleme zu modellieren. Außerdem können TeilnehmerInnen entscheiden, welche Werkzeuge aus der Vorlesung dabei helfen ein gegebenes Graphenproblem algorithmisch zu lösen. Studierende lernen in diesem Kurs vertieft die Laufzeit von gegebenen Graphalgorithmen abzuschätzen.

    Weiterführende Veranstaltungen

    • Vorlesung Algorithmische Geometrie (jedes WS)
    • Vorlesung Approximationsalgorithmen (jedes WS)
    • Vorlesung Advanced Algorithms (jedes WS)
    • Vorlesung Visualisierung von Graphen (jedes SS)
    • Vorlesung Algorithmen für geographische Informationssysteme (jedes SS)
    • Vorlesung Exakte Algorithmen (jedes SS)
    • Seminar Visualisierung von Graphen (o.ä., jedes WS)
    • Seminar Algorithmen für Programmierwettbewerbe (derzeit jedes WS und SS)

    Siehe auch unsere Veranstaltungsübersicht

    • Allgemeine Informationen zur Vorlesung und Übung (Stand 03.08.2021) Файл

  • Materialien zur Vorlesung

    Die Vorlesung basiert auf dem Buch Graphentheoretische Konzepte und Algorithmen von Sven Oliver Krumke and Hartmut Noltemeier (Vieweg+Teubner, 2.­ Auflage, 2009), das man sich aus dem Hochschulnetz hier kapitelweise herunterladen kann.

    Außerdem setzt die Vorlesung einige Kapitel des Buchs Introduction to Algorithms (Algorithmen – eine Einführung) von Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein (MIT Press und McGraw-Hill, 3. Auflage, 2009 bzw. De Gruyter Oldenbourg, 4. Auflage, 2013) voraus (BFS, DFS, Algorithmus von Dijkstra, minimale Spannbäume).

    Sehr intuitiv geschrieben ist Algorithmic Graph Theory von Alan Gibbons (Cambridge University Press, 1985).

    Die Vorlesungsvideos sind nur sichtbar, wenn Sie in WueCampus eingeloggt sind.

    • 01. Vorlesung (14.04.2021): Einführung Файл
    • 01. Vorlesung (14.04.2021): Druckversion (Einführung) Файл
    • 01. Vorlesung (14.04.2021): Video (Einführung) Файл
    • 01. Vorlesung (14.04.2021): Rundreiseprobleme I: Eulerkreise [19.04.: Auf S. 4 Kante zu v0 durchgestrichen – danke, Vasil!] Файл
    • 01. Vorlesung (14.04.2021): Druckversion (Eulerkreise) Файл
    • 01. Vorlesung (14.04.2021): Video (Eulerkreise) Файл
    • 01. Vorlesung (14.04.2021): Rundreiseprobleme II: Hamiltonkreise Файл
    • 01. Vorlesung (14.04.2021): Druckversion (Hamiltonkreise) Файл
    • 01. Vorlesung (14.04.2021): Video (Hamiltonkreise) Файл
    • 02. Vorlesung (21.04.2021): Problem des Handlungsreisenden (TSP) Файл
    • 02. Vorlesung (21.04.2021): Druckversion Файл
    • 02. Vorlesung (21.04.2021): Video (TSP Teil I – Exakte Algorithmen) Страница
    • 02. Vorlesung (21.04.2021): Video (TSP Teil II – Komplexität) Файл
    • 02. Vorlesung (21.04.2021): Bonustrack – Dynamische Programmierung und das Rucksackproblem Файл
    • 02. Vorlesung (21.04.2021): Bonustrack – Druckversion Файл
    • 02. Vorlesung (21.04.2021): spannendes Video von Thomas van Dijk zu praktischen Aspekten von Algorithmen für das Rucksackproblem (33') Гиперссылка
    • 03. Vorlesung (28.04.2021): Lineare Programmierung Файл
    • 03. Vorlesung (28.04.2021): Druckversion Файл
    • 03. Vorlesung (28.04.2021): Video Страница
    • 03. Vorlesung (28.04.2021): Bonustrack – ILP-Formulierungen von Rucksack- und Graphfärbeproblem Файл
    • 04. Vorlesung (05.05.2021): Max-Flow-Min-Cut-Theorem und Flussalgorithmen Файл
    • 04. Vorlesung (05.05.2021): Druckversion Файл
    • 04. Vorlesung (05.05.2021): Video (Teil I – 22 Min.) Файл
    • 04. Vorlesung (05.05.2021): Video (Teil II – 15 Min.) Файл
    • 04. Vorlesung (05.05.2021): Video (Teil III – 22 Min.) Файл
    • 05. Vorlesung (12.05.2021): Paarungen (Matchings) Файл
    • 05. Vorlesung (12.05.2021): Druckversion Файл
    • 05. Vorlesung (12.05.2021): Video (Teil I – Satz von Menger und größte Matchings in bipartiten Graphen, 18 Min.) Файл
    • 05. Vorlesung (12.05.2021): Video (Teil II – Heiratssatz, 8 Min.) Файл
    • 05. Vorlesung (12.05.2021): Bonustrack – ILP-Formulierung für Größte Paarung Файл
    • 06. Vorlesung (19.05.2021): Matchings II: kombinatorischer Algorithmus, Christofides' Algorithmus, LP-Runden Файл
    • 06. Vorlesung (19.05.2021): Druckversion Файл
    • 06. Vorlesung (19.05.2021): Video (Teil I – Größte Matchings in bipartiten Graphen, 8 Min.) Файл
    • 06. Vorlesung (19.05.2021): Video (Teil II – Algorithmus von Christofides, 13 Min.) Файл
    • 06. Vorlesung (19.05.2021): Video (Teil III – Kostenminimale perfekte Matchings in bipartiten Graphen, 13 Min.) Файл
    • 06. Vorlesung (19.05.2021): Bonustrack – Beispiel für LP-Runden (kostenminimales perfektes Matching) Файл
    • 07. Vorlesung (26.05.2021): Minimale Wurzelspannbäume Файл
    • 07. Vorlesung (26.05.2021): Druckversion Файл
    • 07. Vorlesung (26.05.2021): Video (Teil I – Edmonds' Algorithmus, 18 Min.) Файл
    • 07. Vorlesung (26.05.2021): Video (Teil II – Laufzeit und Korrektheit von Edmonds' Algorithmus, 12 Min.) Файл
    • 07. Vorlesung (26.05.2021): Bonustrack – Beispiel für Edmonds' Algorithmus Файл
    • 08. Vorlesung (02.06.2021): Randomisierte Algorithmen für MinCut Файл
    • 08. Vorlesung (02.06.2021): Druckversion Файл
    • 08. Vorlesung (02.06.2021): Video (45 Min.) Страница
    • Der Stoer-Wagner-Algorithmus, ein einfacher deterministischer Algorithmus für MinCut
    • 08. Vorlesung (02.06.2021): Bonustrack – Min-Cut-Algorithmus von Stoer und Wagner mit Beispiel Файл
    • 09. Vorlesung (09.06.2021): Färbungen, Cliquen und unabhängige Mengen Файл
    • 09. Vorlesung (09.06.2021): Druckversion Файл
    • 09. Vorlesung (09.06.2021): Video (31 Min.) Страница
    • 10. Vorlesung (16.06.2021): Fest-Parameter-Berechenbarkeit (alte Folien, passen zum Video) Файл
    • 10. Vorlesung (16.06.2021): Druckversion Файл
    • 10. Vorlesung (16.06.2021): Der Grad-3-Algorithmus (einfacher als der Grad-4-Algorithmus). Файл
    • 10. Vorlesung (16.06.2021): Druckversion des Grad-3-Algorithmus Файл
    • 10. Vorlesung (16.06.2021): Bonustrack – Beispiel für den Grad-3-Algorithmus Файл
    • 10. Vorlesung (16.06.2021): Video (42 Min.) Страница
    • 11. Vorlesung (22.06.2021): Planare Graphen Файл
    • 11. Vorlesung (22.06.2021): Druckversion Файл
    • 11. Vorlesung (22.06.2021): Video (Teil 1, 35 Min.) Страница

    • 11. Vorlesung (22.06.2021): Teil 2 wird in der Zoom-Vorlesung "live" besprochen.

    • 11. Vorlesung (22.06.2021): Video (Teil 3, 21 Min.) Файл
    • 12. Vorlesung (30.06.2021): Färben planarer Graphen und Planaritätstest Файл
    • 12. Vorlesung (30.06.2021): Druckversion Файл
    • 12. Vorlesung (30.06.2021): Video (Teil I – Färben planarer Graphen, 18 Min.) Файл
    • 12. Vorlesung (30.06.2021): Video (Teil II – Planaritätstest, 26 Min.) Файл
    • 12. Vorlesung (30.06.2021): Bonustrack – Beispiel für den Planaritätstest von Auslander & Parter Файл
    • 13. Vorlesung (07.07.2021): Bonustrack – Beispiel für Thomassens Algorithmus zum 5-Listenfärben Файл
    • 13. Vorlesung (07.07.2021): PageRank und Power-Methode [kleine Änderungen am 7.7.] Файл
    • 13. Vorlesung (07.07.2021): Druckversion Файл
    • 13. Vorlesung (07.07.2021): Video (11 Min.) Файл

  • Übung

    Es wird voraussichtlich 12 Übungsblätter geben. Auf den bewerteten Blättern können jeweils bis zu 20 Punkte erreicht werden. Sie dürfen maximal in 2er-Gruppen abgeben. Bitte geben Sie die Namen aller an, die das Blatt mit Ihnen bearbeitet haben. Sie sollten Ihre Lösung während der Übung vorliegen haben.

    Pro Gruppe ist das Übungsblatt von einem Gruppenmitglied auf WueCampus hochzuladen. Bevorzugt werden Abgaben, die mit Latex erstellt wurden. Sie können hierfür gerne die Vorlage nutzen. Bitte vermeiden Sie Fotographien von Abgaben. Der Abgabetermin ist dienstags um 12:00 Uhr.