English website

Hörerkreis:
Masterstudiengang Informatik

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

Vorlesungstermin: Di 14:00 Uhr - 15:15 Uhr + 17:00 Uhr - 18:15 Uhr, HS3

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. Aber auch in der Vorlesung Algorithmik werden Korrektheitsbeweise geführt.

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.

Im SS 2008 gab es ein Seminar zu Algorithmen für Bachelorstudenten. In diesem Seminar sind ein paar interessante Lösungen zu algorithmischen Problemstellungen entstanden, die auch in dieser Vorlesung angesprochen werden. Diese Lösungen stehen zur Einsicht und Erprobung auf dem Handout-Server zur Verfügung.

Zusätzlich werden im SS 2009 Beispielimplementierungen durch einen ausländischen Praktikanten erstellt, der vom DAAD finanziert wird.

Der größte Teil dieser Vorlesung richtet sich nach einem von Studenten ausformulierten Skript für eine Vorlesung, die Prof. Dr. Helmut Alt (mein Doktorvater) an der FU Berlin im WS 2006/2007 gehalten hat. Eine vin mir kommentierte Version dieses Skripts können Sie hier herunterladen. Die Kommentare werden im Laufe der Vorlesung ergänzt. Bitte gehen Sie selbst auf die Suche nach Fehlern und Verbesserungsmöglichkeiten.

In jedem Fall ist das Skript 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.).

In der Vorlesung werden die meisten Teile der Kapitel 1 bis 4 des Skripts systematisch durchgearbeitet. Für Kapitel 4 gehen wir teilweise auch nach dem Buch von Turau (s.u.) vor. Das Kapitel 5 des Skripts (NP-Vollständigkeit) entfällt ganz, weil es in der Vorlesung Berechenbarkeit und Komplexität thematisiert wird. Unser Kapitel 5 (String-Matching) entspricht Kapitel 4.8 des Skripts.

Beim Thema Algorithmische Geometrie (Kap. 6), 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.

Die Vorlesung wird als seminaristischer Unterricht (also mit Eigenbeteiligung der Studierenden) gehalten. Als Unterrichtsmedium dient die Tafel. Studierende sollten sich daher einen Ordner für die Mitschriften anlegen. Eine Zusammenfassung der Inhalte wird jeweils nach der Vorlesung auf diese Webseite gestellt.

In unregelmäßigen Abständen werden auch Hausaufgaben gestellt, welche dann in der nachfolgenden Vorlesung besprochen werden. Diese sind als Vorbereitung für die Prüfung (in diesem Semester: Klausur) anzusehen.

Im Folgenden wird eine Übersicht über den Inhalt der Vorlesung vom SS 2008 gegeben. Dieser könnte sich noch im Laufe des SS 2009 geringfügig ändern.

Die Vorlesung wird ab Kap. 3.4 in englischer Sprache gehalten. Daher sind auch die Übersichtsfolien ab diesem Kapitel auf Englisch. Die Klausur wird aber für jedes Kapitel auf Deutsch gestellt.

1. Einführung in die formale Behandlung von Algorithmen (geändert: 21.04.)
     1.1 Vergleich von grundlegenden Sortiertechniken
     1.2 Einführung in Komplexitätsmaße für Algorithmen
     1.3 Untere Schranken für vergleichsbasierte Algorithmen

2. Weitere Such- und Sortieralgorithmen (geändert: 28.04.)
     2.1 Das Auswahlproblem (Order statistics)
     2.2 Suchen in sortierten Feldern
     2.3 Sortieren in endlichen Universen

3. Lösungen für das Wörterbuchproblem
     3.1 Hashing
     3.2 2-3-Bäume
     3.3 Andere Methoden mit Suchbäumen (korrigiert am 26.05.)
     3.4 Optimale binäre Suchbäume (Bellman) (ergänzt am 26.05.)

4. Graphenalgorithmen
     4.1 Minimale spannende Bäume als Motivation für Basisalgorithmen (ergänzt am 26.05.)
     4.2 Kürzeste Wege (Dijkstra, Floyd-Warshall, Strassen) Hausaufgabe zum 09.06.
     4.3 Maximale Flüsse in q/s-Netzwerken (Ford-Fulkerson, Edmonds-Karp, Dinic)
     4.4 Matchings in Graphen (bipartit, Edmonds) (geringfügig geändert: 23.06.)

5. String-Matching (aktualisiert am 01.07.)

6. Grundlagen der Algorithmischen Geometrie
     6.1 Grundlegende Aufgaben und die Anwendung von Voronoi-Diagrammen für ihre Lösung (aktualisiert am 01.07.)
     6.2 Sweep-Techniken (inkl. Berechnung von Voronoi-Diagrammen)

Zusammenfassung der Vorlesung mit Klausurabgrenzung

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 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.

Das Buch von Levitin ist Grundlage des Seminars vom SS 2008. Es richtet sich zwar an Bachelorstudenten, behandelt aber auch Algorithmen und zugehörige Beweistechniken, wie sie an der FH Wedel erst im Masterstudium behandelt werden.

Die beiden Bücher 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 auch neueste Resultate aus dem Gebiet Algorithmische Geometrie, die aber in dieser Vorlesung nicht behandelt werden. Es dient als englische Referenz für Kapitel 6.

Das Buch von Papadimitriou und Steiglitz behandelt Graphalgorithmen erheblich detaillierter als in dieser Vorlesung. Vor allem wird dort auch der Matching-Algorithmus von Edmonds für allgemeine Graphen beschrieben.

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 

Christos Papadimitriou / Kenneth Steiglitz: Combinatorial Optimization - Algorithms and Complexity, Dover 1998, ISBN 0-486-40258-4

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)