English website

Hörerkreis:
Masterstudiengänge Informatik und IT-Sicherheit

Arbeitsaufwand: 5 ECTS-Punkte

Vorlesungstermin:

   Di 08:00 - 10:45 Uhr mit einer Pause, HS 3
   1. Termin: 21.04.

In diesem Semester wird diese Vorlesung letztmalig auf Deutsch gelesen. Wegen der Integration in den neuen englischsprachigen Studiengang IT-Engineering wird diese Vorlesung künftig immer auf Englisch gelesen. Die Klausur kann aber auch künftig auf Deutsch beantwortet werden.

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 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 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 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. 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 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 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 wird bereits komplett auf Englisch angeboten, aber auf Deutsch in der Vorlesung vorgestellt.

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
     3.4 Optimale binäre Suchbäume (Bellman) (entfällt in diesem Semester)

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)
     4.4 Matchings in Graphen

5. String-Matching

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)

Zusammenfassung mit Klausurabgrenzung (durchgestrichene Teile sind nicht klausurrelevant)

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)