Informatik-Logo
Fakultät für Informatik - Technische Universität München

Lehrstuhl für Effiziente Algorithmen

TUM-Logo

Hauptseminar im WS 2004/05:
Dynamische Graphenalgorithmen

Blockseminar am
16. Februar 2005, 9:00 Uhr bis 14:00 Uhr, Seminarraum MI 03.11.018
17. Februar 2005, 9:00 Uhr bis 12:00 Uhr, Seminarraum MI 03.11.018


[Themen & Literatur] [Programm] [Zusammenfassung] [Hinweise]

Zusammenfassung

Die Fragen, die in den klassischen Graphenalgorithmen betrachtet werden, entsprechen nicht immer der konkreten Anwendungssituation. Bei den üblicherweise studierten statischen Graphenproblemen ist eine Aufgabe (z.B. Berechnung der Zusammenhangskomponenten, Bestimmung eines minimalen Spannbaumes) auf einem durch die Eingabe festgelegten Graphen zu lösen.

Bei einem dynamischen Graphenproblem verändert sich der Graph - Kanten und Knoten können eingefügt oder gelöscht werden, und die Gewichte können sich ändern. Die Aufgabe besteht hier nun darin, das Problem für den veränderten Graphen zu lösen, ohne die Lösung nach jeder Veränderung vollkommen neu berechnen zu müssen. Die gerade erwähnten diskreten Änderungen an einem Graphen tauchen in vielen Anwednungsgebieten auf (Internet und sonstige Computernetzwerke, World-Wide Web, Computergrafik, VLSI-Design). Deshalb haben sich dynamische Graphenalgorithmen zu einem sehr aktiven Forschungsgebiet entwickelt.

Im Hauptseminar werden wir häfig vorkommende dynamische Probleme (kürzeste Wege, minimale Spannbäme, Zusammenhang), wichtige dynamische Datenstrukturen (dynamische Bäme), Techniken wie Sparsifikation und sampling sowie die Transformation eines eingeschränkt dynamischen Algorithmus zu einem voll dynamischen Algorithmus kennenlernen.

Voraussetzung für die Teilnahme am Hauptseminar sind neben mathematischem Verständnis auch Englischkenntnisse, die zumindest ausreichend für die Bearbeitung der ausschließlich englischsprachigen Literatur sind.

Programm

Mittwoch, 16. Februar 2005
09:00-09:05 Begrüßung
09:05-09:50 Stephen Marius Lauschke
Thema: Single-Source-Shortest-Path-Probleme
Betreuer: Stefan Pfingstl
10:00-10:45 Rossen Stefanov
Thema: All-Pairs-Shortest-Paths-Probleme
Betreuer: Moritz G. Maaß
11:00-11:45 Immanuel Scheerer
Thema: Dynamische Bäume
Betreuer: Hanjo Täubig
Mittagspause
12:30-13:15 Tan Liang
Thema: Topologische Bäume mit kleinem Durchmesser
Betreuer: Peter Ullrich
Donnerstag, 17. Februar 2005
09:00-09:45 Yin Yixin
Thema: Gewurzelte Bäume
Betreuer: Sven Kosub
10:00-10:45 Sergius Schneider
Thema: Planaritätstests
Betreuer: Johannes Nowak
11:00-11:45 Benjamin Hummel
Thema: Transformation dekrementeller in dynamische Algorithmen
Betreuer: Stefan Eckhardt

Hinweise

Ein Schein für die erfolgreiche Teilnahme am Hauptseminar wird vergeben, wenn folgende Leistungen erbracht worden sind (die Gesamtnote setzt sich aus gewichteten Einzelnoten zusammen):

Probevortrag (ohne Bewertung) Der Probevortrag erfolgt spätestens zum angegebenen Termin beim Betreuer. Vorzulegen sind dabei die fertig ausgearbeiteten Folien oder ähnliche Präsentationshilfsmittel und die Erstfassung der Seminarbeit.
Vereinbaren Sie für den Probevortrag rechtzeitig einen Termin beim Betreuer (spätestens eine Woche vor dem anvisierten Termin).
Seminarvortrag (in mindestens zufriedenstellender Qualität) Der Seminarvortrag ist zum festgelegten Termin zu halten und dauert 45 (+/-5) Minuten. Tafelvorträge werden nicht akzeptiert. Nach dem Vortrag muss auf Fragen aus dem Publikum eingegangen werden.
Seminararbeit (in mindestens zufriedenstellender Qualität) Die Endfassung der Seminarbeit muss zum Zeitpunkt des Vortrags als TeX-Datei und Postscript-Datei abgegeben worden sein. Der Umfang der Seminararbeit beträgt 5 (+/- 1) Seiten (ohne Literaturverzeichnis) im LNCS-Style (Springer-Verlag) unter LaTeX (Hinweise siehe unten).

Ablauf der Vorbereitung

Der Vortrag und die Ausarbeitung müssen mit dem Betreuer abgesprochen werden. Hierzu sind nachfolgende Terminvorgaben bindend (soweit nicht anders mit dem Betreuer abgestimmt). Werden die Termine nicht eingehalten, führt dies zur Streichung des Vortrags und zum Nichtbestehen des Seminars:

bis 4 Wochen vor dem Vortragerstes Treffen mit dem Betreuer (vor dem Treffen ist die Literatur bereits zu lesen); die genauen Vortragstermine werden noch bekannt gegeben;
bis 2 Wochen vor dem VortragGliederung des Vortrags und der Ausarbeitung mit dem Betreuer besprechen;
bis 1 Woche vor dem VortragProbevortrag vor den Betreuer; fertige Folien und vollständige erste Version der Ausarbeitung mit dem Betreuer abstimmen;

Hinweise zur Anfertigung einer Seminararbeit

* Die Seminararbeiten werden nach der letzten Seminarveranstaltung gemeinsam in einem Seminarband zur Verfügung gestellt. Damit eine einheitliche Form erzielt wird, müssen alle Ausarbeitungen mit dem Textsatzsystem LaTeX erstellt werden. Hierzu sind folgende Richtlinien zu beachten:
  • Es ist der LNCS-Style (die Datei llncs.cls) des Springer-Verlages zu verwenden.
  • Der folgende Rahmen ist zu verwenden (seminararbeit.tex). Dabei dürfen die Seitengröße und der Font nicht verändert werden.
  • Ein Beispiel kann in der Datei example.tex gefunden werden (das Bild example.eps wird eingebunden)
  • Die Ausarbeitung soll auf die verwendete Literatur verweisen, diese Literatur ist mit BibTeX zu verwalten und in einer eigenen Datei zu speichern (hier die zum Beispiel gehörende Datei: example.bib).
* Bei Fragen zu LaTeX sei einerseits auf die folgenden Links hingewiesen, ferner kann auch der Betreuer um Hilfestellungen bzw. Literaturangaben gebeten werden:
* Eine weitere Anleitung zur Erstellung von Ausarbeitungen finden sie hier.
* Informationen zur Installation von LaTeX unter Windows finden Sie hier.

Hinweise zur Gestaltung der Seminarvorträge

* Merkblatt zur Gestaltung eines Seminarvortrags. (Die Tipps auf diesem Merkblatt sind keine offiziellen Anforderungen oder Bewertungskriterien der TU München, sondern aus der Praxis eines Seminarleiters heraus entstandene Ratschläge.)
* Tipps zur Erstellung von Folien mit LaTeX (einschließlich Rahmen-Datei als Vorlage)

Weitere Auskünfte bei Sven Kosub.
Sven Kosub, July/8/2004.