Die offizielle Themenvergabe war am Mi, 02.07. um 13 Uhr, SR 3. Es sind keine Vorträge mehr frei. Zu den unten aufgeführten kommen noch 2 Vorträge über ein Masterprojekt in Kooperation mit der FU Berlin.

Vortragstermine: Die Vorträge finden in 3 Blöcken statt am 19.11., 04.12. und 16.12. sowie als Abschlusskolloquium am 21.01.

Algorithmik ist ein weitreichendes Gebiet. Man kann es implementierungsnah betreiben, aber auch theoretisch konzeptionell. Für die Praxis ist auch von Relevanz, wie genau ein Problem gelöst werden soll. Algorithmik ist für Informatikern als Kernfach ihres Arbeitsgebiets von Interesse, aber auch für Anwender, die sich IT-Lösungen bedienen möchten.

In diesem Seminar werden 2 Schwerpunkte angeboten:

Der Schwerpunkt Randomisierung beschäftigt sich damit, wie man Problemstellungen umdefinieren kann, um sie leichter lösbar zu machen. Vor allem wird der Zufall eingebaut, um ein gutes Durchschnittsverhalten der Verfahren zu erreichen. Die dafür ausgewählten Vorträge richten sich an alle IT-Studiengänge (Thema 7 auch an Wirtschaftsingenieurwesen) und können sowohl von Bachelor- als auch von Masterstudierenden bearbeitet werden. Masterstudierende müssen das betreffende Thema vertiefter bearbeiten als Bachelorstudierende und mehr auf theoretische Grundlagen eingehen. Sprechen Sie mich zu den einzelnen Themen an, wenn Sie Fragen zum Umfang haben.

Der Schwerpunkt Logistik richtet sich nur an Bachelorstudierende der IT-Studiengänge (Thema 9 auch an Masterstudierende) sowie an alle Studierende des Wirtschaftsingenieurwesens (Bachelor und Master). Auch Studierende des eCommerce (beide Schwerpunkte) sollten sich hierfür besonders angesprochen fühlen.

Als Grundlage dient im Schwerpunkt Randomisierung das Buch von Hromkovic und im Schwerpunkt Logistik das Buch von Domschke, die aber - wie in jedem meiner Seminare - ausdrücklich nur als thematische Abgrenzung dienen und Sie nicht davon abhalten soll, andere Literatur zu benutzen. Gerne können Sie sich zunächst im Internet schlau machen, aber für den Vortrag reicht die ausschließliche Lektüre von Vorlesungsskripten und Lexika (z.B. Wikipedia) nicht aus. Nutzen Sie die Referenzen zu Lehrbüchern. Falls unsere Bibliothek ein noch nicht vorhandenes anschaffen sollte, sprechen Sie mich an!

Zusätzlich biete ich an, dass Themen, die in den vergangenen Seminaren nicht vergeben oder gar nicht angeboten wurden, in diesem Seminar aufgegriffen werden. Besonderes Interesse habe ich an der Bioinformatik, der algoithmischen Geometrie sowie jeglicher Aspekte der Verkehrsplanung und Verkehrsinformation. Gerne können Sie weitere Vorschläge machen. Generell dürfen nur Themen vorgestellt werden, die nicht in derselben Form schon einmal in einer Vorlesung oder in einem Seminar an der FH Wedel behandelt wurden.

Es wird von jedem Vortragenden erwartet, dass es deutlich vor dem Vortrag eine persönliche Absprache mit mir zur der genauen Ausgestaltung des Themas gibt. Diese sollte erst nach der Vergabe des Themas erfolgen, aber Sie dürfen mich auch gerne schon vorher darauf ansprechen.

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.

Schwerpunkt Randomisierung:

1) Online-Algorithmen (Hromkovic Kap. 3.4 und 3.5)

Hier soll auch erklärt werden, worum es bei Online-Algorithmen geht. Masterstudierende der Informatik sollen auch auf die deterministische Lösbarkeit von Online-Algorithmen eingehen.

Vortrag ausgefallen

Mi, 19.11., 09:00-10:00, HS 5

2) Die Methode der Fingerabdrücke in randomisierten Algorithmen (Hromkovic Kap. 4)

Es ist eine repräsentative Auswahl der in Hromkovic beschriebenen Problemstellungen vorzustellen. Alles im Detail ist in einem Vortrag nicht machbar. Mindestens ein Detail sollte aber gebracht werden.

Vortrag vergeben an Ole Groth

Mi, 19.11., 09:00-10:00, HS 5

Vortrag     Ausarbeitung

3) Ein randomisierter Algorithmus für das 3-SAT-Problem (Hromkovic Kap. 5.3)

Das 3-SAT-Problem ist eines der zentralen NP-vollständigen Probleme. Die Relevanz für Praktiker sollte unbedingt vorgetellt werden.

Vortrag vergeben an Nico Mönch

Mi, 19.11., 10:15-11:15, HS 5

Vortrag     Ausarbeitung

4) Ein randomisierter Algorithmus für die Generierung von nichtquadratischen Resten (Hromkovic 5.4)

Vortrag vergeben an Lara Vols

Mi, 19.11., 11:30-12:30, HS 5

Vortrag     Ausarbeitung

5) Randomisierte Algorithmen für Primzahltest und Primzahlgenerierung (Hromkovic Kap. 6)

Es soll die Methode von Solovay und Strassen vorgestellt werden. Von Masterstudierenden der Informatik wird erwartet, dass sie auch einen Vergleich zum Rabin-Miller-Verfahren anstellen.

Vortrag vergeben an Andrej Spady

Do, 04.12., 09:00-10:00, HS 5

Vortrag     Ausarbeitung

6) Relaxierung zur linearen Programmierung mit Anwendungen auf praxisrelevante Problemstellungen (Hromkovic Kap. 7)

Die Problemstellungen beziehen sich schon auf Inhalte des Operations Research und können daher auch von besonders informatikaffinen Wirtschaftsingenieuren bearbeitet werden. In erster Linie sehe ich aber IT-Studiengänge angesprochen.

Vortrag vergeben an Julia Müller

Do, 04.12., 10:15-11:15, HS 5

Vortrag     Ausarbeitung

Schwerpunkt Logistik:

7) Standortbestimmung in der Ebene (Domschke Standorte Kap. 5)

Es soll ein Beispiel ausgearbeitet werden, das die allgemeinen aber sehr knapp beschriebenen Verfahren aus Domschke illustriert.

Vortrag vergeben an Nadim Memic

Do, 04.12., 12:00-13:00, HS 5

Vortrag     Ausarbeitung

8) Quadratische Zuordnungsprobleme (Domschke Standorte Kap. 6, evtl. 7)

Es soll die allgemeine Problemstellung vorgestellt werden mit einem Lösungsansatz und wenigstens eine Anwendung. Dieses Thema kann auch von Masterstudierenden der Informatik bearbeitet werden.

Vortrag vergeben an Oliver Müller

Do, 04.12., 13:15-14:15, HS 5

Vortrag     Ausarbeitung

9) Minimale spannende Bäume und Wälder (Domschke Transport Kap. 3) 

Es sollen nicht die in Diskrete Mathematik behandelten Algorithmen von Kruskal und Dijkstra im Vordergrund stehen.

Vortrag vergeben an Hannes Schröder

Di, 16.12., 09:00-10:00, SR 11

Vortrag     Ausarbeitung

10) Kürzeste Wege in Graphen (Domschke Transport Kap. 4)

Es soll nicht der in Diskrete Mathematik behandelte Algorithmus von Dijkstra im Vordergrund stehen. Vor allem sollen auch Graphen mit negativen Zyklen behandelt werden.

Vortrag vergeben an Zümra Bilekkaya

Di, 16.12., 10:15-11:15, SR 11

Vortrag     Ausarbeitung

11) Primale Algorithmen für Umladeprobleme (Domschke Transport Kap. 6)

Vortrag vergeben an Jan Schulze

Di, 16.12., 11:30-12:30, SR 11

Vortrag     Ausarbeitung

Masterprojekt mit der FU Berlin:

12 + 13) Symmetrieerkennung in Theorie und Praxis

Vortrag vergeben an Timm Hoffmann und Marcus Riemer

Mi, 21.01., 16:00-18:15, HS 5

Vortrag     Ausarbeitung

Im Folgenden wird die Literatur aufgelistet, wie sie in unserer Bibliothek vorhanden ist:

W. Domschke / A. Trexl: Logistik: Standorte, Oldenbourg 1990 (3. Auflage), ISBN 3-486-21527-2

W. Domschke: Logistik: Transport, Oldenbourg 2007 (5. Auflage), ISBN 978-3-486-58290-1

J. Hromkovic: Randomisierte Algorithmen, Teubner 2004, ISBN 3-519-00470-4

Die Benutzung weiterer Literatur ist ausdrücklich willkommen.