Mitarbeiter
Organisatorisches
Hörerkreis:
Masterstudiengang Informatik
Laut Studienplan ist diese Vorlesung nur für das 2. oder 3. Semester ausgewiesen. Studienanfänger im SS 2010 können diese Veranstaltung aber auch schon im 1. statt im 3. Semester belegen, wenn ihnen das besser in die zeitliche Planung passt.
Vorlesungstermin: Mi 08:00 Uhr - 09:15 Uhr, HS5 + Do 08:00 Uhr - 09:15 Uhr, HS 1
Vorlesungsinhalte
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) durchgeführt.
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.
Vorlesungsunterlagen
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.
Prof. Alt wird uns in diesem Semester mit einem Kolloquiumsvortrag beehren und auch als Gast eine Algorithmik-Vorlesung übernehmen. Nutzen Sie die Chance, ein Mitglied der internationalen Spitzenforschung in diesem Gebiet im Original kennenzulernen.
Eine von mir kommentierte Version seines 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 aktuelle Zusammenfassung der Inhalte steht unten. Diese wird im Laufe der Vorlesung an die aktuell behandelten Inhalte angepasst.
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.
Die Vorlesungsfolien sind ab Kap. 3.4 in englischer Sprache, weil die Vorlesung im letzten Jahr auf Englisch gehalten wurde. Es ist geplant, das gesamte Vorlesungsmaterial auf Englisch umzustellen, damit die gesamte Vorlesung auf Englisch gehalten werden kann (falls es wieder internationale Gaststudenten gibt). Die Klausur wird aber für jedes Kapitel auf Deutsch gestellt.
1. Einführung in die formale Behandlung von Algorithmen
1.1 Vergleich von grundlegenden Sortiertechniken (Algorithmenbeschreibungen dazu)
1.2 Einführung in Komplexitätsmaße für Algorithmen
1.3 Untere Schranken für vergleichsbasierte Algorithmen
2. Weitere Such- und Sortieralgorithmen
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 (12.05.: aktualisiert, die Hausaufgabe soll bis zum 20.05. bearbeitet werden)
3.3 Andere Methoden mit Suchbäumen
3.4 Optimale binäre Suchbäume (Bellman) (07.06.: geringfügig korrigiert)
4. Graphenalgorithmen
4.1 Minimale spannende Bäume als Motivation für Basisalgorithmen
4.2 Kürzeste Wege (Dijkstra, Floyd-Warshall, Strassen)
4.3 Maximale Flüsse in q/s-Netzwerken (Ford-Fulkerson, Edmonds-Karp, Dinic) (07.06.: geringfügig korrigiert)
4.4 Matchings in Graphen (bipartit, Edmonds)
6. Grundlagen der Algorithmischen Geometrie
6.1 Grundlegende Aufgaben und die Anwendung von Voronoi-Diagrammen für ihre Lösung
6.2 Sweep-Techniken (inkl. Berechnung von Voronoi-Diagrammen) (08.07.: Folie 5 geringfügig geändert)
Zusammenfassung für die Klausur
Literatur
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-0262032933Rolf 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-0Anany 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)