الخطوط العريضة للقسم

  • عام

    طي الكل توسيع الكل
    Umfang: 5 ECTS, 2+2 SWS [T:2,P:0]
    Vorlesung: mittwochs, 10:15–11:45 Uhr, HS 2 (Nat.wiss. HS-Bau) 
    Übungen: (1) freitags, 08:30–10:00 Uhr, SE I (Informatikgebäude)
    (2) freitags, 10:15–11:45 Uhr, SE 8 (Physikgebäude)
    (3) freitags, 12:15–13:45 Uhr, SE I (Informatikgebäude)

    Sowohl die Vorlesung als auch die Übung finden wieder in Präsenzform statt. Darüber hinaus stehen für Ankündigungen und Diskussionen das Forum auf WueCampus und Kanäle im Chat der Uni Würzburg zur Verfügung (Einladungslink: https://chat.uni-wuerzburg.de/invite/Lwn6JY). (Die entsprechenden Links finden Sie im pdf zu allgemeinen Informationen weiter unten.)
    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: Felix Klesen
    Tutoren: Thanh Mai Pham, Martin Hesse, Jan Krause
    Klausuren:

    Mo, 24. Juli 2023, 12–14 Uhr, Turing- und Zuse-Hörsaal
    Mi, 11. Oktober 2023, 10–13 Uhr, Zuse-Hörsaal.
    Als Hilfsmittel ist nur ein einseitig handbeschriebenes Blatt (A4) zulässig.

    • Nachrichtenforum منتدى
    • Diskussionsforum منتدى

  • 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 ملف

  • 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).

    • 01. Vorlesung (19.04.2023): Einführung ملف
    • 01. Vorlesung (19.04.2023): Druckversion (Einführung) ملف
    • 01. Vorlesung (19.04.2023): Video (Einführung, 12') ملف
    • 01. Vorlesung (19.04.2023): Rundreiseprobleme I: Eulerkreise ملف
    • 01. Vorlesung (19.04.2023): Druckversion (Eulerkreise) ملف
    • 01. Vorlesung (19.04.2023): Video (Eulerkreise, 13') ملف
    • 01. Vorlesung (19.04.2023): Rundreiseprobleme II: Hamiltonkreise ملف
    • 01. Vorlesung (19.04.2023): Druckversion (Hamiltonkreise) ملف
    • 01. Vorlesung (19.04.2023): Video (Hamiltonkreise, 14') ملف
    • 02. Vorlesung (26.04.2023): Lineare Programmierung ملف
    • 02. Vorlesung (26.04.2023): Druckversion ملف
    • 02. Vorlesung (26.04.2023): Video (30') صفحة
    • 03. Vorlesung (03.05.2023): Problem des Handlungsreisenden (TSP) ملف
    • 03. Vorlesung (03.05.2023): Druckversion ملف
    • 03. Vorlesung (03.05.2023): Video (TSP Teil I – Exakte Algorithmen, 28') صفحة
    • 03. Vorlesung (03.05.2023): Video (TSP Teil II – Komplexität und Approximation, 12') ملف
    • 04. Vorlesung (10.05.2023): Max-Flow-Min-Cut-Theorem und Flussalgorithmen [14.05.: kleine Korrektur auf S. 21/22] ملف
    • 04. Vorlesung (10.05.2023): Druckversion ملف
    • 04. Vorlesung (10.05.2023): Video (Teil I – 22 Min.) ملف
    • 04. Vorlesung (10.05.2023): Video (Teil II – 15 Min.) ملف
    • 04. Vorlesung (10.05.2023): Video (Teil III – 22 Min.) ملف
    • 05. Vorlesung (17.05.2023): Paarungen (Matchings) ملف
    • 05. Vorlesung (17.05.2023): Druckversion ملف
    • 05. Vorlesung (17.05.2023): Video (Teil I – Satz von Menger und größte Matchings in bipartiten Graphen, 18 Min.) ملف
    • 05. Vorlesung (17.05.2023): Video (Teil II – Heiratssatz, 8 Min.) ملف
    • 06. Vorlesung (24.05.2023): Matchings II: kombinatorischer Algorithmus, Christofides' Algorithmus, LP-Runden ملف
    • 06. Vorlesung (24.05.2023): Druckversion ملف
    • 06. Vorlesung (24.05.2023): Video (Teil I – Größte Matchings in bipartiten Graphen, 8 Min.) ملف
    • 06. Vorlesung (24.05.2023): Video (Teil II – Algorithmus von Christofides, 13 Min.) ملف
    • 06. Vorlesung (24.05.2023): Video (Teil III – Kostenminimale perfekte Matchings in bipartiten Graphen, 13 Min.) ملف
    • 06. Vorlesung (24.05.2023): Bonustrack – Beispiel für LP-Runden (kostenminimales perfektes Matching) ملف
    • 07. Vorlesung (31.05.2023): Minimale Wurzelspannbäume ملف
    • 07. Vorlesung (31.05.2023): Druckversion ملف
    • 07. Vorlesung (31.05.2023): Video (Teil I – Edmonds' Algorithmus, 18 Min.) ملف
    • 07. Vorlesung (31.05.2023): Video (Teil II – Laufzeit und Korrektheit von Edmonds' Algorithmus, 12 Min.) ملف
    • 07. Vorlesung (31.05.2023): Bonustrack – Beispiel für Edmonds' Algorithmus ملف
    • 08. Vorlesung (07.06.2023): Randomisierte Algorithmen für MinCut ملف
    • 08. Vorlesung (07.06.2023): Druckversion ملف
    • 08. Vorlesung (07.06.2023): Video (45 Min.) صفحة
    • Der Stoer-Wagner-Algorithmus, ein einfacher deterministischer Algorithmus für MinCut
    • 08. Vorlesung (07.06.2023): Bonustrack – Min-Cut-Algorithmus von Stoer und Wagner mit Beispiel ملف
    • 09. Vorlesung (14.06.2023): Färbungen, Cliquen und unabhängige Mengen [14.06.: kleine Änderungen, u.a. Kreis C -> K] ملف
    • 09. Vorlesung (14.06.2023): Druckversion ملف
    • 09. Vorlesung (14.06.2023): Video (31 Min.) صفحة
    • 10. Vorlesung (21.06.2023): Fest-Parameter-Berechenbarkeit – u.a. der Grad-3-Suchbaum-Algorithmus für Vertex Cover ملف
    • 10. Vorlesung (21.06.2023): Druckversion ملف
    • 10. Vorlesung (21.06.2023): Bonustrack – Beispiel für den Grad-3-Suchbaum-Algorithmus ملف
    • 10. Vorlesung (21.06.2023): Video (42 Min.) – passt nicht mehr genau zu den Folien! صفحة
    • 11. Vorlesung (28.06.2023): Planare Graphen ملف
    • 11. Vorlesung (28.06.2023): Druckversion ملف
    • 11. Vorlesung (28.06.2023): Video (Teil 1, 35 Min.) صفحة
    • 11. Vorlesung (28.06.2023): Video (Teil 2, 21 Min.) ملف
    • 12. Vorlesung (05.07.2023): Färben planarer Graphen und Planaritätstest [05.07.: kosmetische Änderungen] ملف
    • 12. Vorlesung (05.07.2023): Druckversion ملف
    • 12. Vorlesung (05.07.2023): Video (Teil I – Färben planarer Graphen, 18 Min.) ملف
    • 12. Vorlesung (05.07.2023): Video (Teil II – Planaritätstest, 26 Min.) ملف
    • 12. Vorlesung (05.07.2023): Bonustrack – Beispiel für den Planaritätstest von Auslander & Parter ملف
    • 12. Vorlesung (05.07.2023): Bonustrack – Beispiel für Thomassens Algorithmus zum 5-Listenfärben ملف
    • 13. Vorlesung (12.07.2023): PageRank und Power-Methode ملف
    • 13. Vorlesung (12.07.2023): Druckversion ملف
    • 13. Vorlesung (12.07.2023): Video (11 Min.) ملف
    • 13. Vorlesung (12.07.2023): The Mathematics of Google Search (von Raluca Tanase und Remus Radu) رابط الكتروني
    • 13. Vorlesung (12.07.2023): Dynamische Programmierung und das Rucksackproblem ملف
    • 13. Vorlesung (12.07.2023): Bonustrack – ILP-Formulierungen von Rucksack- und Graphfärbeproblem ملف
    • 13. Vorlesung (12.07.2023): Druckversion ملف
    • 13. Vorlesung (12.07.2023): spannendes Video von Thomas van Dijk zu praktischen Aspekten von Algorithmen für das Rucksackproblem (33') رابط الكتروني

  • Ü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 Fotografien von Abgaben. Der Abgabetermin ist dienstags um 13:00 Uhr.

  • Quizzes