English website (for Algorithmics only)

Hörerkreis:
Masterstudiengang Informatik

Arbeitsaufwand: 8 ECTS-Punkte

Vorlesungstermin:

   Teil Berechenbarkeit: Fr 08:00 - 10:45 Uhr, HS 4 (ab 11.04.) (außer 23.05., s.u.)

Für beide Teile muss die Prüfung gemeinsam abgelegt werden und wird auch zu einer Note zusammengerechnet.

In diesem Semester wird der Teil Algorithmik wegen der Teilnahme eines Austauschstudenten einer Partnerhochschule auf Englisch gelesen. Die Klausur wird aber auf Deutsch gestellt. Der Teil Berechenbarkeit ist ganz auf Deutsch.

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

Der Vorlesungsteil Berechenbarkeit legt das theoretische Fundament zur Algorithmik und behandelt ebenfalls einige Algorithmen. Eine gewisse Redundanz zwischen den Vorlesungsteilen ist 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.

In der Vergangenheit gab es mehrere Seminare zu algorithmischen Themen. 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.

Auch in diesem Semester gibt es ein Seminar, in dem einige algorithmische Themen angesprochen werden. Die Vorträge sind am 04.06., 25.06. und 02.07.

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 besucht uns am 23.05. und wird die Vorlesung selbst übernehmen. Am 23.05. hält er außerdem einen Kolloquiumsvortrag um 12:30 Uhr zum Thema Packen und Stapeln geometrischer Objekte.

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

Prof. Alt hält diese Vorlesung alle 2 Jahre. Mitschriften seiner Studenten Naja von Schmude aus dem WS 2008/2009 und Pascal-Nicolas Becker aus dem WS 2010/2011 finden Sie auf dem Handout-Server (Korrektheit ohne Gewähr).

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 im Vorlesungsteil Berechenbarkeit ausführlich 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 jeder Woche werden auch Übungsaufgaben gestellt, welche dann in der nachfolgenden Vorlesung besprochen werden. Diese sind als Vorbereitung für die Klausur anzusehen. Die Übungsaufgaben sowie zusätzliche Materialien zur Vorlesung finden Sie auf dem Handout-Server (nur für Studierende der FH Wedel zugänglich).

Im Laufe der Vorlesung könnte das folgende Material noch überarbeitet werden. Das wird dann in rot gekennzeichnet. Das gegenwärtige Material ist bereits komplett auf Englisch umgestellt.

1. Einführung in die formale Behandlung von Algorithmen
     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
     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 und andere für das durchschnittliche Laufzeitverhalten konzipierte Verfahren
     3.2 2-3-Bäume als Beispiel für ein optimales Verhalten im schlechtesten Fall (Aktualisierung 07.05.) 
     3.3 Andere Methoden für den schlechtesten Fall in Suchbäumen (Aktualisierung 14.05.)
     3.4 Optimale binäre Suchbäume (Bellman)

4. Graphenalgorithmen
     4.1 Minimale spannende Bäume als Motivation für Basisalgorithmen (Aktualisierung 21.05.)
     4.2 Kürzeste Wege (Dijkstra, Floyd-Warshall, Strassen) (Aktualisierung 21.05.)
     4.3 Maximale Flüsse in q/s-Netzwerken (Ford-Fulkerson, Edmonds-Karp, Dinic) (Aktualisierung 11.06.)
     4.4 Matchings in Graphen (Aktualisierung 18.06.)

5. String-Matching (Aktualisierung 18.06.)

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) (Aktualisierung 02.07.)

Zusammenfassung (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 

Kurt Mehlhorn / Peter Sanders: Algorithms and Data Structures - The Basic Toolbox, Springer2008, ISBN 978-3-540-77977-3

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)