SS16:Algorithmische Graphentheorie

Topic outline

• 

  General

  Vorlesung Algorithmische Graphentheorie

  Umfang:	5 ECTS, 2+2 SWS [T:2,P:0]
  Vorlesung:	dienstags, 10:15–11:45 Uhr, HS 2
  Übungen:	1) freitags, 08:30–10:00 Uhr, SE III 2) freitags, 10:15–11:45 Uhr, SE III 3) freitags, 12:15–13:45 Uhr, SE III
  Voraussetzung:	Vorlesung Algorithmen und Datenstrukturen (dringend empfohlen)
  Zielgruppe:	Bachelor Informatik ab 2. Semester
  Anmeldung:	Einschreibung hier in den Wuecampus-Kurs. Die Anmeldung zur Klausur erfolgt über SB@Home (siehe unten).
  Dozent:	Alexander Wolff
  Übung:	Fabian Lipp Jan Bartsch Julian Behringer Norbert Fischer

  • 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 Exakte Algorithmen (jedes gerade SS)
  • Vorlesung Visualisierung von Graphen (jedes SS)
  • Seminar Visualisierung von Graphen (jedes WS)

  Siehe auch unsere Veranstaltungsübersicht
• 

  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 (12.04.2016): Einführung File
  • 01. Vorlesung (12.04.2016): Druckversion File
  • 01. Vorlesung (12.04.2016): Rundreiseprobleme File
  • 01. Vorlesung (12.04.2016): Druckversion File
  • 02. Vorlesung (19.04.2016): Problem des Handlungsreisenden (TSP) File
  • 02. Vorlesung (19.04.2016): Druckversion File
  • 03. Vorlesung (26.04.2016): Lineare Programmierung, Flüsse und Flussalgorithmen File
  • 03. Vorlesung (26.04.2016): Druckversion File
  • 04. Vorlesung (03.05.2016): Paarungen (Matchings) File
  • 04. Vorlesung (03.05.2016): Druckversion File
  • 05. Vorlesung (10.05.2016): Matchings (II) und Christofides' Algorithmus File
  • 05. Vorlesung (10.05.2016): Druckversion File
  • 06. Vorlesung (24.05.2016): Wurzelspannbäume File
  • 06. Vorlesung (24.05.2016): Druckversion File
  • 07. Vorlesung (31.05.2016): Randomisierte Algorithmen für MinCut File
  • 07. Vorlesung (31.05.2016): Druckversion File
  • 07. Vorlesung (31.05.2016): Ein einfacher (deterministischer) Algorithmus für MinCut
  • 08. Vorlesung (07.06.2016): Färbungen, Cliquen und unabhängige Mengen File
  • 08. Vorlesung (07.06.2016): Druckversion File
  • 09. Vorlesung (14.06.2016): Planare Graphen File
  • 09. Vorlesung (14.06.2016): Druckversion File
  • 10. Vorlesung (21.06.2016): Planaritätstest File
  • 10. Vorlesung (21.06.2016): Druckversion File
  • 11. Vorlesung (28.06.2016): Festparameter-Berechenbarkeit File
  • 11. Vorlesung (28.06.2016): Druckversion File
  • 12. Vorlesung (05.07.2016): PageRank und Power-Methode File
  • 12. Vorlesung (05.07.2016): Druckversion File
  • The Mathematics of Google Search (von Raluca Tanase und Remus Radu) URL
  • 13. Vorlesung (12.07.2016): Planare Graphen aufs Gitter zeichnen (Schnyder) File
  • 13. Vorlesung (12.07.2016): Druckversion File
  • Schnyders Artikel "Embedding planar graphs on the grid" (SODA 1990) URL
• 

  Übung

  Es wird insgesamt 12 bewertete Übungsblätter geben, auf denen jeweils bis zu 20 Punkte erreicht werden können. Sie dürfen maximal in 2er-Gruppen abgeben. Bitte geben Sie Namen und Übungsgruppen aller Mitarbeiter an. Idealerweise sollten Sie mit einem Partner in der selben Übungsgruppe abgeben. Falls das nicht möglich ist, geben Sie bitte auf dem Blatt an, in welcher Gruppe es zurückgegeben werden soll. Sie müssen sich dann selbst darum kümmern es an Ihren Übungspartner weiterzugeben. Sie sollten Ihre Lösung in der Übung vorliegen haben.
  

  Bitte geben Sie Ihre Lösungen zu Beginn der Vorlesung oder im Briefkasten im Informatikgebäude (unterster Briefkasten in der ersten Spalte) ab. Der Abgabetermin ist in der Regel dienstags um 10:15 Uhr.

  • Wiederholung von wichtigen Graphalgorithmen aus der ADS-Vorlesung File
  • Einführung in OPL, Teil 1 File
  • 0. Übungblatt (keine Abgabe, Besprechung in der Übung am 15.04.2016) File
  • 1. Übungsblatt (Abgabe bis 19.04.2016) Assignment

    [PDF-Download]
    

  • 2. Übungsblatt (Abgabe bis 26.04.2016) Assignment

    [PDF-Download]

    Bitte laden Sie den Quelltext zu Aufgabe 4 hier in Wuecampus hoch. Die übrigen Lösungen geben Sie bitte wie üblich in der Vorlesung oder im Briefkasten ab.
    

  • 3. Übungsblatt (Abgabe bis 03.05.2016) Assignment

    [PDF-Download]

    Bitte laden Sie den Quelltext zu Aufgabe 1c und 1d hier in Wuecampus hoch. Die übrigen Lösungen geben Sie bitte wie üblich in der Vorlesung oder im Briefkasten ab.
    

  • OPL-Quelltext zur Lösung von Aufgabe 1c und 1d auf dem 3. Übungsblatt Page
  • 4. Übungsblatt (Abgabe bis 10.05.2016) Assignment

    [PDF-Download]
    

  • 5. Übungsblatt (Abgabe bis 24.05.2016) Assignment

    [PDF-Download]
    

  • 6. Übungsblatt (Abgabe bis 31.05.2016) Assignment

    [PDF-Download]
    

  • 7. Übungsblatt (Abgabe bis 07.06.2016) Assignment

    [PDF-Download]
    

  • 8. Übungsblatt (Abgabe bis 14.06.2016) Assignment

    [PDF-Download]
    

  • 9. Übungsblatt (Abgabe bis 21.06.2016) Assignment

    [PDF-Download]
    

  • 10. Übungsblatt (Abgabe bis 28.06.2016) [Update am 22.06.2016: Aufgabe 4] Assignment

    [PDF-Download]
    

  • 11. Übungsblatt (Abgabe bis 05.07.2016) Assignment

    [PDF-Download]
    

  • 12. Übungsblatt (Abgabe bis 12.07.2016) [Update am 05.07.2016: Konkretisierung der Aufgabenstellung in Aufgabe 1] Assignment

    [PDF-Download]
    

• 

  Klausur

  Die Modalitäten für die Klausur unterscheiden sich, je nachdem nach welcher Prüfungsordnung Sie studieren. Für Studenten im Bachelor Informatik gelten die folgenden Bestimmungen. Studenten in anderen Studiengängen finden in ihren fachspezifischen Bestimmungen jeweils die Version der Informatik-Prüfungsordnung, aus der das Modul entnommen ist. Die hier angegebenen Bestimmungen gelten dann entsprechend.
  

  • Prüfungsordnung 2015-WS: Algorithmische Graphentheorie (10-I-AGT) ist für Sie eine Pflichtvorlesung im Unterbereich Mathematik. Sie müssen nicht an den Übungen teilnehmen. Wenn Sie 50% der Übungspunkte erreichen, können Sie sich allerdings einen Bonus für die Note der Klausur erarbeiten. Dieser Bonus gilt nur für die Klausur im SS 2016.
    
  • Prüfungsordnung 2014-SS: Algorithmische Graphentheorie (10-I-AGT) ist für Sie eine Pflichtvorlesung im Unterbereich Mathematik. Sie müssen nicht an den Übungen teilnehmen. Sie können ohne Voraussetzungen an der Klausur teilnehmen.
  • Prüfungsordnung 2010-WS: Algorithmische Graphentheorie (10-I-GT) ist für Sie eine Wahlpflichtvorlesung im Unterbereich Informatik. Voraussetzung für die Teilnahme an der Klausur ist das Erreichen von 50% der Übungspunkte.

  Unabhängig davon, ob ihre Prüfungsordnung Sie zur Teilnahme an den Übungen verpflichtet, empfehlen wir Ihnen dringend Übungblätter abzugeben und die Übungen zu besuchen, da dies erfahrungsgemäß die Klausurergebnisse deutlich verbessert.

  Sie können sich zwischen 1. April und 30. Juni über SB@Home zur Klausur an- bzw. wieder abmelden. Diese Frist ist vom Prüfungsamt vorgegeben. Ohne fristgerechte Anmeldung können Sie nicht an der Klausur teilnehmen.
  

  Die Klausur wird 60 Minuten dauern. Als Hilfsmittel ist ein von Ihnen selbst handschriftlich einseitig beschriebenes DIN A4-Blatt erlaubt.

  • Klausurtermine

    • Sommersemester: Dienstag, 19.07.2016, 14:00-16:00, Turing-HS (Anmeldung: 01.04.2016 bis 30.06.2016)
      
    • Wintersemester: Dienstag, 11.10.2016, 10:00-12:00, Turing-HS (Anmeldung: 01.09.2016 bis 30.09.2016)