Hauptstudiumsschwerpunktvorlesung im SoSe 2003
18.214 Algorithmische Graphentheorie

   Matthias Jantzen

2st. Do 10 - 12 C-221
Lernziel:
In dieser Hauptstudiums-Veranstaltung soll das theoretische Wissen über geometrische Probleme und ihre algorithmische Lösung bekanntgemacht oder vertieft werden. Grundlegende Verfahren der Algorithmischen Graphentheorie (Computational Geometry) werden studiert, und deren effizientesten Varianten hinsichtlich Laufzeit, Speicherplatz, wie auch Verständlichkeit und den günstigsten Datenstrukturen betrachtet.
Die Teilnehmer(innen) sollen in die Lage versetzt werden, ähnliche oder neue Probleme aus den verschiedensten Anwendungsbereichen als Probleme über Graphen zu formulieren, um die an den Beispielen verdeutlichten Methoden ihrer Lösung einsetzen zu können. Die Veranstaltung will weder einen vollständigen Überblick aller einsetzbaren Verfahren geben, noch eine Anleitung zum sofortigen Programmieren.
Inhalt:
Algorithmischen Graphentheorie beschäftigt sich mit Lösungen geometrischer Probleme, wie sie oft in realen Anwendungen, also in vielen Bereichen der Informatik, auftreten: Computer Graphics, geographische Informationssysteme, Robotics, Bildanalyse, VLSI-Design, CAD/CAM und vielen anderen. Die algorithmischen Lösungen mit den - nicht immer offensichtlichen - deterministischen Verfahren sind in der Regel zu langsam, schwer verständlich und umständlich zu implementieren. Trotzdem kann man nicht immer auf andere Verfahren, wie randomisierte, approximative, evolutionäre, oder genetische Algorithmen ausweichen. Der Schwerpunkt liegt hier auf den deterministischen Verfahren, die es vor der Wahl von Alternativen zu verstehen gilt. Es werden bekannte Algorithmen und (deren Zusammenhang mit realen Problemen) behandelt. Unter anderen sind enthalten:
  • kürzeste Wege und andere Pfadprobleme (viele Anwendungen)
  • Konvexe Hüllen (Durchschnitte und Sichtbarkeit in Polygonen, Statistik),
  • Durchschnitte von Geradensegmenten (Überlagerung von Landkarten und Bewegungsplanung),
  • Polygon Triangulation (Aufstellung von Überwachungskameras),
  • Sichtbarkeitsgraphen (Robotorbewegungen)
  • Voronoi Diagramme (Dichteste Punkte in der Ebene, Platzierung von Rettungsmeldern),
  • Delaunay Triagulation (Berechnung des Voronoi Diagramms).
Stell. im Studienplan:
Hauptstudium, Vertiefungsgebiete A1, A3, P7, T1, T2; Schwerpunkte BV, ES, IM
Voraussetzungen:
Grundstudium, (Vorlesung AUK dazu/davor ist hilfreich)
Vorgehen:
Vorlesung (Stofferarbeitung mit Beispielen)
Literatur:
Anstelle eines vorlesungsbegleitenden Skripts:
  1. R. Klein: Algorithmische Geometrie (Addison Weslay, 1997)
  2. M. de Berg/van Kreveld/Overmars/Schwarzkopf: Computational Geometry (Springer 1997)
  3. V. Turau: Algorithmische Graphentheorie (Addison Weslay, 1996)
Als Grundlagen, z.B.:
  1. Brassard/Bratley: Fundamentals of Algorithms (Prentice Hall, 1996),
  2. Gritzmann/Brandenberg: Das Geheimnis des kürzesten Weges (Springer, 2002),
  3. bekannte Bücher zur Diskreten Mathematik.
Weitere Literaturhinweise werden in der Veranstaltung gegeben.
Eignung:
Bedingt geeignet für Lehramtsstudierende, Nebenfachstudierende, Bioinformatikstudierende, Wirtschaftsinformatikstudierende.
Stichworte:
Datenstrukturen, Graph, Analyse, Polygon, Triangulation, Entwurf, Komplexität von Algorithmen.