Mi, 28.05., 09:00 Uhr - 14:30 Uhr, HS 5
Do, 05.06., 09:00 Uhr - 14:30 Uhr, HS 5
Di, 17.06., 15:00 Uhr - 19:00 Uhr, HS 5

Dieses Seminar richtet sich an Bachelor- und Diplomstudierende aller Informatikstudiengänge.

Der Entwurf und die Analyse von Algorithmen gehören zur Kernkompetenz eines Informatikers. Es sollen klassische Algorithmen behandelt werden, die im normalen Vorlesungsbetrieb des Bachelorstudiums gar nicht oder nur am Rande unterkommen. Der Schwerpunkt liegt in der Vorstellung des Algorthmenentwurfs. Die Analyse darf informell erfolgen. Für eine exakte Analyse (Verifikation und Laufzeitabschätzung) gibt es die Vorlesung Algorithmik im Masterstudium.

Die Algorithmen sollen in einer neuartigen Systematik vorgestellt werden, die im unten angegeben Buch von Levitin vorgegeben ist. Daher richtet sich die Themeneinteilung nach der Systematik dieses Buches. Das Buch ist in unser Bibliothek zweifach vorhanden (davon ein nicht ausleihbares in meiner Lehrbuchsammlung).

Das bedeutet aber nicht zwingend, dass Vortragende ausschließlich die Inhalte dieses Buches vortragen sollen, im Gegenteil: Eigene Recherchen und selbständige Literaturauswahl zum besseren Verständnis bzw. zur Vertiefung des Vortragsstoffs wird ausdrücklich willkommen geheißen und auch in der Abschlussnote honoriert. Die Darstellung der Algorithmen selbst soll aber im Vordergrund stehen.

Außerdem gehört zu jedem Vortrag die Implementierung mindestens eines Algorithmus in einer algorithmischen Programmiersprache Ihrer Wahl: Pascal, C. Java oder eine andere Sprache, deren Syntax für Informatiker auch ohne Vorkenntnisse darin klar verständlich ist. Die Implementierung soll im Vortrag vorgeführt werden. Der Programmcode muss mit der Ausarbeitung und den Präsentationsunterlagen mit abgegeben werden. Die Testumgebung darf rudimentär sein (gerne auch zeilenorientiert).

Die im Folgenden verlinkten Ausarbeitungen und Vortragsunterlagen sind im Original dargestellt und ausschließlich von den Verfassern bearbeitet worden. Daher kann der Lehrveranstalter keine Gewähr für die Qualität und Richtigkeit geben.

Es gibt außerdem noch einen Bereich für dieses Seminar auf dem Handout-Server, der nur für Studierende der FH-Wedel zugänglich ist. Dort sind alle Implementierungen der Referenten zugänglich, die unter Windows mit Java 1.5 erfolgreich getestet werden konnten.

In Klammern hinter dem Thema finden Sie die Kapitel des Buches von Levitin, in denen das Pflichtmaterial enthalten ist.

Thema 1: Brute Force (3.2, 3.3., 3.4)
String Matching, Closest Pair, Convex Hull (jeweils mit Implementierung)
Traveling Salesman, Knapsack, Job Assignment
Vortragender: Robert Schilling
28.05., 9:00 Uhr - 10:15 Uhr
Vortrag    Ausarbeitung

Thema 2: Divide + Conquer (4.5, 4.6)
Matrixmultiplikation (Strassen) mit Implementierung
Closest Pair, Convex Hull
Vortragender: Janno Rothfos
28.05., 10:15 Uhr - 11:30 Uhr
Vortrag    Ausarbeitung

Thema 3: Decrease + Conquer (5.1, 5.3, 5.4, 5.6)
InsertionSort, Topologisches Sortieren, Permutationsgenerierung (Johnsen-Trotter)
Mediansuche, Interpolationssuche (beide mit Inplementierung)
Vortragende: Theresa Brandt von Fakh
28.05., 12:00 Uhr - 13:15 Uhr
Vortrag    Ausarbeitung

Thema 4: Transform + Conquer I (6.3, 6.4)
Balancierte Bäume: AVL, 2-3-Bäume (letzteres mit Implementierung des Wörtbuchproblems)
Heapsort
Vortragender: Alexander Sittig
28.05., 13:15 Uhr - 14:30 Uhr
Vortrag    Ausarbeitung

Thema 5: Transform + Conquer II (6.5, 6.6)
Hornerschema und binäre Potenzierung (mit Implementierung)
Lineares Programmieren mit Anwendung Knapsack
Vortragender: Serkan Kaya
05.06., 9:00 Uhr - 10:15 Uhr
Vortrag    Ausarbeitung

Thema 6: Zeit vs. Platz I (7.1, 7.2)
Comparison Counting, Distribution Counting
String Matching: Horspool, Boyer-Moore (letzterer mit Implementierung)
Vortragender: Marco Brakmann
05.06., 10:15 Uhr - 11:30 Uhr
Vortrag    Ausarbeitung

Thema 7: Zeit vs. Platz II (7.3)
Hashing (mit Implementierung)
Vortragender: Claas Casper
05.06., 12:00 Uhr - 13:15 Uhr
Vortrag    Ausarbeitung

Thema 8: Zeit vs. Platz III (7.4)
B-Bäume (mit Implementierung des Wörterbuchproblems)
Vortragender: Sebastian Barzyk,
05.06., 13:15 Uhr - 14:30 Uhr
Vortrag    Ausarbeitung

Thema 9: Dynamisches Programmieren I (8.2)
Algorithmen von Warshall und Floyd (letzterer mit Implementierung)
Vortragender: Moritz Eilering
17.06., 15:00 Uhr - 16:15 Uhr
Vortrag    Ausarbeitung

Thema 10: Dynamisches Programmieren II (8.3, 8.4)
Optimale Binärsuchbäume (mit Implementierung)
Knapsack mit Memory Functions
Vortragender: Malte Matthias
17.06., 16:15 Uhr - 17:30 Uhr
Vortrag    Ausarbeitung

Thema 11: Greedy (9.1, 9.2)
Algorithmen von Prim und Kruskal (letzterer mit Implementierung)
Vortragender: John Freytag
17.06., 17:45 Uhr - 19:00 Uhr
Vortrag    Ausarbeitung