English website

Hörerkreis:
Masterstudiengänge Informatik, IT-Engineering

Arbeitsaufwand: 5 ECTS-Punkte

Vorlesungstermin:

   Mi 12:30 - 15:15 Uhr, HS 1 mit einer 15-minütigen Pause dazwischen

Erster Termin: Mi der 1. Vorlesungswoche

Sprache: Englisch. Die Klausur kann aber auch auf Deutsch beantwortet werden.

Information wegen der Corona-Vorsichtsmaßnahmen:

Die auf dieser Webseite gegebene Information geht davon aus, dass die Vorlesung als Präsenzvorlesung beginnt und fortgeführt wird, also wie in normalen Zeiten.

Es ist allerdings noch nicht klar, wann wir starten dürfen, d.h. wann die 1. Vorlesungswoche sein wird. Die FH Wedel unterliegt denselben Regelungen wie alle Hochschulen in Deutschland bzw. Schleswig-Holstein (falls es eine bundeslandspezifische Verordnung gibt). Nach derzeitigem Stand soll die 1. Vorlesungswoche am 20.04. starten. Vermutlich wird das noch nach hinten geschoben werden. Falls wir später als am 02.05. starten dürfen, werden wir auch einen online-Betrieb durchführen. Dieser wird hier dann näher erläutert werden, sobald wir wissen, wie er abläuft.

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.

Das theoretische Fundament zur Algorithmik wird in der Vorlesung Berechenbarkeit und Komplexität gelegt. Diese ist aber keine Voraussetzung für Algorithmik, weswegen die notwendigsten Grundlagen aus Berechenbarkeit und Komplexität auch in Algorithmik behandelt werden. Wegen der größeren Anschaulichkeit wird empfohlen, die Algorithmik möglichst zu Beginn des Studiums und damit vor der Berechenbarkeit und Komplexität zu belegen. Aber auch die umgekehrte Reihenfolge ist möglich, falls Studierende im Wintersemester anfangen und das Studium in 3 Semestern abschließen wollen.

Die meisten Forschungsgruppen der Theoretischen Informatik weltweit beschäftigen sich mit Algorithmik oder Spezifikation und Verifikation. Daher bieten sich in diesen Gebieten auch viele Promotionsthemen (und davon abgeleitet Masterthemen) an. Ein Beispiel ist die vom WHB ausgezeichnete Masterarbeit von Nicolas Mönch (s.u.). 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 diesen Seminaren 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.

Der größte Teil dieser Vorlesung richtet sich nach einem von Studenten ausformulierten deutschsprachigen Skript für eine Vorlesung, die Prof. Dr. Helmut Alt (mein Doktorvater) an der FU Berlin im WS 2006/2007 gehalten hat. Eine von mir kommentierte Version seines Skripts können Sie hier herunterladen. Da die Vorlesung auf Englisch gehalten wird, wird das Skript nicht direkt eingesetzt, sondern stattdessen die unten angegebenen Folien, welche durch Erklärungen an der Tafel ergänzt werden. Skript und Folien orientieren sich im Aufbau größtenteils am Lehrbuch von Cormen et al. (s.u.).

Prof. Alt hielt diese Vorlesung auch nach meiner Revision seines Skripts. Mitschriften seiner Studenten Naja von Schmude aus dem WS 2008/2009 und Pascal-Nicolas Becker aus dem WS 2010/2011 finden Sie ebenfalls 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 in der Vorlesung 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 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. Auch wenn die Überschriften hier auf Deutsch wiedergegeben sind, ist das gesamte Material auf Englisch.

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
     3.3 Andere Methoden für den schlechtesten Fall in Suchbäumen (aktualisiert am 27.05.2020)
     3.4 Optimale binäre Suchbäume (Bellman)

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

5. String-Matching (aktualisiert am 01.07.2020)

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) (aktualisiert am 15.07.2020)

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.

Die etwas älteren Bücher von Preparata und Edelsbrunner behandeln viele Grundlagen und Algorithmen, welche aber in dieser Vorlesung nicht direkt thematisiert 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

Herbert Edelsbrunner: Algorithms in Combinatorial Geometry, Springer 1987, ISBN 3-540-13722-X

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

Nicolas Mönch: Kürzeste Wege in dynamischen Graphen, Masterarbeit FH Wedel WS 2015/16, download

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

Franco Preparata / Michael Shamos: Computational Geometry - An Introduction, Springer 1988 (2. Auflage), ISBN 3-540-96131-3

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)