Algorithmen und Komplexität - Hauptseite Algorithmen und Komplexität

Vorlesung: Graphen und Algorithmen 1

Dozent: Dr. Stefan Hougardy

Termine

Beginn der Vorlesung: 17.10.2001
Beginn der Übung: Mittwoch, 20.10.1999
VL Montag 11:00 - 13:00 (RUD 25, 3.101)
Mittwoch 11:00 - 13:00 (RUD 25, 3.101)
UE Mittwoch 13:00 - 15:00 (RUD 25, 3.101) Dr. C. Gröpl
PR n.V. Dr. C. Gröpl
Im Sommersemester 2002 folgt "Graphen und Algorithmen 2". Zu dieser Vorlesung gibt es ein Skript.

Zuordnung

  • Hauptstudium, 1. Teil eines Kurses
  • Theoretische Informatik

Voraussetzungen

  • Grundstudium
  • Graphen und Algorithmen

Inhalte und Lernziele

Ein Graph besteht aus einer Menge von Knoten, von denen einige durch Kanten verbunden sind. Hier sind Beispiele für Graphen:

Der "Petersen Graph" Ein Baum Der "Heawood Graph"

Mit Hilfe dieser relativ einfachen Struktur lassen sich viele fundamentale Probleme modellieren und mittels geeigneter Graphenalgorithmen auch effizient lösen, wie beispielsweise

  • was ist die kürzeste/schnellste Verbindung von einem Ort zu einem anderen (Routenplaner)?
  • wie packt man 3 Millionen Transistoren so auf einen Chip, daß die Gesamtleitungslänge möglichst gering bleibt ( Chipdesign)?
  • wieviele Telefongespräche können gleichzeitig über super24 von Berlin nach Bonn geführt werden?
  • was ist die effizienteste Art multicasting im Internet durchzuführen?
  • lassen sich die Länder einer Landkarte so mit 4 Farben färben, daß benachbarte Länder nie die gleiche Farbe erhalten ( 4-Farben-Satz)?
  • ...

Besonders interessant ist die Art und Weise, in der algorithmische Probleme strukturelle Fragen über Graphen aufwerfen, deren Beantwortung dann zu verbesserten Algorithmen führt.

Folgende Themen sollen im Wintersemester behandelt werden:
  • Grundlagen
  • Zusammenhang
  • Flüsse
  • Matchings
  • Eulersche/Hamiltonsche Graphen
  • Das Traveling-Salesman-Problem
  • Färbungen
  • Planarität
  • Steinerbäume

Übungen

Begleitend zur Vorlesung wird wöchentlich eine Übungsstunde angeboten, in der die gestellten Aufgaben besprochen werden.
Die Übungen sollten in Zweier- oder Dreiergruppen bearbeitet werden. Die Abgabe erfolgt zu Beginn jeder Übungsstunde.

Programmierpraktikum

praufg2001.ps , praufg2001.pdf Daten

Empfohlene Literatur

zuletzt geändert am 20.02.2006 (alkox-www)