English website

Hörerkreis:
Masterstudiengang Informatik (nach dem Bachelor)

Laut Studienplan ist diese Vorlesung nur für das 2. Semester ausgewiesen. Studienanfänger im SS 2008 können diese Veranstaltung aber auch schon jetzt statt im 3. Semester belegen, wenn ihnen das besser in die zeitliche Planung passt.

Vorlesungstermin: Do 09:30 Uhr - 12:15 Uhr, HS6 (Raum geändert!)

Algorithmik ist für das systematische Erstellen korrekter und effizienter Softwarelösungen eine wesentliche Grundlage. Algorithmen zu ausgewählten Problemstellungen wie Suchen, Sortieren und Graphenproblemen wurden bereits in verschiedenen Vorlesungen des Bachelorstudiums behandelt (Programmieren, Diskrete Mathematik, Grundlagen der Theoretischen Informatik, Algorithmen und Datenstrukturen in C). Dort standen aber eher realisierungstechnische Details im Vordergrund. Vereinzelt wurden auch schon Korrektheitsbeweise behandelt. Die Komplexität in Form von Laufzeit und Speicherplatzbedarf wurde zwar thematisiert, aber nicht systematisch bewiesen.

In dieser Veranstaltung wird ein vertiefter Einblick in die Welt der Algorithmik gegeben. Es wird von programmiertechnischen Details abstrahiert und dafür mehr Wert auf die Beweise von Korrektheit und Komplexität gelegt.  In der Algorithmik liegt der Schwerpunkt traditionell in der Untersuchung der Komplexität, insbesondere der asymptotischen Laufzeit. Für die Spezifikation und Verifikation gibt es eine eigene Vorlesung von Prof. Hoffmann.

Die Vorlesung Berechenbarkeit und Komplexität von Prof. Lang wird in vielen Büchern und Vorlesungen als Teil der Algorithmik behandelt. Daher komplementiert sie auch diese Vorlesung. Die beiden Vorlesungen sind so aufgebaut, dass sie in beliebiger Reihenfolge gehört werden können. Eine gewisse Redundanz ist daher unvermeidlich und dient der Festigung des Gelernten.

Die meisten Forschungsgruppen der Theoretischen Informatik weltweit beschäftigen sich entweder mit Algorithmik oder Spezifikation und Verifikation. Daher bieten sich in diesen Gebieten auch viele Promotionsthemen (und davon abgeleitet Masterthemen) an. Ich habe selbst meine Promotion in Algorithmik (genauer: Algorithmische Geometrie) erworben.

Inhaltlich werden wir aufbauend auf den Themen der angesprochenen Bachelorvorlesungen weitere Sortier- und Suchalgorithmen behandeln, ferner weitere Suchbaumtechniken und zahlreiche Graphenalgorithmen. Schließlich werden wir noch ausgewählte Themen aus der algorithmischen Geometrie behandeln, vor allem die effiziente Berechnung von Voronoi-Diagrammen und ihre Anwendung.

Ich biete in diesem Semester noch ein Seminar zu Algorithmen für Bachelorstudenten an, in dem einige der in dieser Vorlesung besprochenen Algorithmen, aber auch andere, thematisiert werden, wobei der Fokus in der Implementierung und Vorführung besteht. Außerdem wird eine neuartige Systematik der Methodik beim Algorithmenentwurf vorgestellt, welche in dieser Vorlesung keine Rolle spielt. Da der Inhalt dieses Seminars über die Standardinhalte des Bachelorstudiums an der FH Wedel bedeutend hinausgeht, ist der Besuch dieses Seminars auch für Masterstudenten, die die Vorlesung Algorithmik belegen, eine Bereicherung.

Der größte Teil dieser Vorlesung richtet sich nach einem ausformulierten Skript für eine Vorlesung, die Prof. Dr. Helmut Alt (mein Doktorvater) an der FU Berlin im WS 2006/2007 gehalten hat. Dieses Skript können Sie hier herunterladen. Es ist nur für den internen Gebrauch an der FH Wedel bestimmt. Das Skript orientiert sich im Aufbau am Lehrbuch von Cormen et al. (s.u.).

Wir werden das Skript in der Vorlesung systematisch durcharbeiten. Beweise und Beispiele werden an der Tafel nachvollzogen. Über das Skript hinausgehende Vortragsunterlagen wird es nicht geben. Die Lehrveranstaltung wird der geringen Zahl der Teilnehmer angepasst auch eher als seminaristischer Unterricht (also ein bisschen wie im Leistungskurs in der Schule) stattfinden und nicht als reine Vorlesung, in der nur der Dozent redet und alle anderen zuhören. Auf diese Weise sollen alle Teilnehmer aktiv einbezogen werden.

Einige Teile des Skripts, die bei uns bereits im Bachelorstudium behandelt wurden oder die ich als weniger wichtig empfinde, werden wir nur rudimentär oder gar nicht behandeln. Das Kapitel 5 (NP-Vollständigkeit) entfällt ganz, weil es in der Vorlesung Berechenbarkeit und Komplexität thematisiert wird.

Beim Thema Algorithmische Geometrie, welches im angegebenen Skript nicht mehr enthalten ist, gehen wir nach dem Buch von Klein (s.u.) vor. Hier werden wir vor allem die Kapitel 5 und 6 sowie die dafür benötigten Voraussetzungen behandeln. Zu diesem Thema relevantes Material wird unter Umständen auch dem Buch von deBerg et al. (s.u.) entnommen.

Im Folgenden wird eine Übersicht gegeben, die jeweils am Donnerstag nach der Vorlesung hier hineingestellt wird, um die Möglichkeit einer systematischen Nacharbeitung und Vertiefung des Vorlesungsstoffs zu ermöglichen:

Vorlesung 1 vom 10.04.

Vorlesung 2 vom 17.04.

Vorlesung 3 vom 24.04.

Vorlesung 4 vom 08.05. (Teil Hashing)
   (siehe auch das Lisp-Modul für 2-3-Bäume auf dem Handout-Server)

Vorlesung 5 vom 15.05.

Vorlesung 6 vom 22.05.

Vorlesung 7 vom 29.05.

Vorlesung 8 vom 12.06.
   (Ausarbeitung und Vortrag der Seminararbeit von Claudia Padberg)

Vorlesung 9 vom 19.06.

Vorlesung 10 vom 26.06. (inkl. Hausaufgaben zum 03.07.)

Vorlesung 11 vom 03.07.

Vorlesung 12 vom 10.07.

Zusammenfassung der Vorlesung (mit Prüfungsabgrenzung)

Die drei in dieser Vorlesung explizit verwendeten Bücher von Cormen et al., Klein und Turau finden Sie neben der allgemeinen Ausleihe auch in meiner Lehrbuchsammlung. Das Buch von Levitin wird im Seminar verwendet. Das in der Lehrbuchsammlung ebenfalls enthaltene Buch Algorithmik von Harel ist nicht für diese Vorlesung bestimmt, sondern Hintergrundliteratur für Grundlagen der Theoretischen Informatik. Es richtet sich an Erstsemester des Bachelorstudiums.

Die beiden Referenzen von Knuth und Sedgewick sind Standardwerke, die ebenfalls viele in dieser Vorlesung behandelte Themen enthalten und vertiefen. Das Buch von deBerg et al. erhält neueste Resultate aus dem Gebiet Algorithmische Geometrie, die aber in dieser Vorlesung nicht behandelt werden.

Mark de Berg / Otfried Cheong / Marc van Kreveld / Mark Overmars: Computational Geometry, Algorithms and Applications Springer 2008 (3. Aufl.), ISBN 978-3-540-77973-5

Thomas Cormen, Charles Leiserson / Ronald Rivest / Clifford Stein: Algorithmen - Eine Einführung, Oldenbourg 2007 (2. Aufl.), ISBN 978-3-486-58262-8
Englisches Original:
Thomas Cormen, Charles Leiserson / Ronald Rivest / Clifford Stein: Introduction to Algorithms, MIT Press 2001 (2nd ed.), ISBN 978-0262032933

Rolf Klein: Algorithmische Geometrie, Springer 2005 (2. Aufl.), ISBN 978-3-540-20956-0

Donald Knuth: The Art of Computer Programming, vol. 1,2,3,
Addison Wesley 1997, ISBN 0-201-89683-4,  0-201-89684-2, 0-201-89685-0

Anany Levitin: Introduction to the Design and Analysis of Algorithms, Addison-Wesley 2006, ISBN 0-321-36413-9

Robert Sedgewick: Algorithmen, Addison Wesley 1992 (2. Nachdr.), ISBN 3-89319-301-4
Das Buch ist im Original auf Englisch erschienen und existiert in mehreren Auflagen.
Neuere Auflagen sind spezifisch für Programmiersprachen (Algorithms in C, Algorithms in Java, etc.).

Volker Turau, Algorithmische Graphentheorie, Oldenbourg 2004 (2. Auflage), ISBN 3-486-20038-0
(in unserer Bibliothek: 1. Auflage, Addison-Wesley 1996)