Seminar Algorithm Engineering (WiSe 2011/12)

Veranstalterin Prof. Dr. Petra Mutzel
Modul Diplom, Master INF-MSc-102 (Informatik, Angewandte Informatik)
Veranstaltungsart Seminar
Veranstaltungsnummer 041404
Forschungsbereich Algorithmen und Komplexität
SWS 2
Max. Teilnehmer 12

Inhalt und Themen

Algorithmen und Datenstrukturen sind das Herz jeder Computeranwendung. Traditionell hat sich die Algorithmik der Methodik der Algorithmentheorie bedient: Algorithmen werden für einfache und abstrakte Problem- und Maschinenmodelle entworfen und Leistungsgarantien werden für alle möglichen Eingaben bewiesen (z.B. Worst-Case Analyse).

Bei wachsenden Anforderungen an innovative Algorithmen ergeben sich daraus wachsende Lücken zwischen Theorie und Praxis: Reale Hardware entwickelt sich durch Parallelismus, Speicherhierarchien Pipelining, etc. immer weiter weg von einfachen Maschinenmodellen und reale Anwendungen werden immer komplexer. Gleichzeitig entwickelt die Algorithmentheorie auch für einfache Anwendungen immer komplexere Algorithmen, die zwar in der Theorie wichtige Ideen und Resultate liefern, aber oft auch kaum implementierbar sind. Außerdem haben reale Eingaben oft wenig mit den Worst-Case Szenarien der theoretischen Analyse zu tun. Im schlimmsten Fall werden viel versprechende algorithmische Ansätze vernachlässigt, weil eine vollständige Analyse mathematisch zu schwierig wäre.

Seit Beginn der 1990er Jahre wird deshalb eine breitere Sichtweise der Algorithmik immer wichtiger, die als Algorithm Engineering bezeichnet wird. Dabei stehen der Entwurf, die Analyse, die Implementierung und die experimentelle Bewertung von Algorithmen gleichberechtigt nebeneinander. Der gegenüber der Algorithmentheorie größere Methodenapparat, die Einbeziehung realer Hard- und Software und der engere Bezug zu realen Anwendungen verspricht realistischere Algorithmen. Dadurch soll die Lücke zwischen Theorie und Praxis überbrückt und ein schnellerer Transfer von algorithmischem Wissen in Anwendungen gewährleistet werden.

In diesem Seminar beschäftigen wir uns mit ausgewählten Themen aus dem Bereich des Algorithm Engineerings, die auf der internationalen Konferenz Algorithm Engineering and Experiments (ALENEX 2011), dem European Symposium on Algorithms (ESA 2011), sowie dem International Symposium on Experimental Algorithms 2011 erschienen sind, sowie aktuellen Zeitschriftenartikeln aus dem ACM Journal on Experimental Algorithms.

Anmeldung und Vorbesprechung

Die Anmeldung erfolgt per Email bei Petra Mutzel bis zum Dienstag, 11. Oktober 2011. Dieser Email fügen Sie bitte eine 3er Prioritätenliste Ihrer gewünschten Vorträge (Auswahl s. oben) bei. Die Themenverteilung erfolgt bei der Vorbesprechung (Termin s. unten).

Ablauf des Seminars

Die Themenverteilung erfolgt während der Vorbesprechung. Im weiteren Verlauf des Semesters haben die Teilnehmer Zeit die Ausarbeitung zu schreiben und den Vortrag vorzubereiten. In dieser Zeit wird es keine regelmäßigen Treffen in der Gruppe geben, die Seminarteilnehmer besprechen sich allerdings mit ihrem zugeordneten Betreuer.

Es handelt sich um ein Blockseminar. Alle Teilnehmer halten kurz nach Ende des Semesters einen 45-minütigen Vortrag über das festgelegte Thema; im Anschluss folgt eine ca. 15-minütige Diskussion über Thema und Vortrag. Bitte beachten Sie auch die Hinweise zur Foliengestaltung! Es herrscht Anwesenheitspflicht bei allen Vorträgen.

Voraussetzung für den Vortrag ist die vorherige Abgabe einer schriftlichen Ausarbeitung, welche 15-20 Seiten umfasst und mit LaTeX erstellt wird. Mangelhafte Ausarbeitungen sowie mangelhafte Vorträge führen zum Nicht-Bestehen des Seminars. Auch nicht rechtzeitig abgegebene Ausarbeitungen können zum Nicht-Bestehen führen.

Vorlage für die Ausarbeitung: [.zip-Archiv]

Termine

Vorbesprechung und Themenvergabe: Mittwoch, der 12.10.2011 um 11:45 Uhr in OH14, Raum 202 (Seminarraum des LS11).

Abgabe des Ausarbeitungskonzepts 10.01.2012
Abgabe der Ausarbeitung 17.01.2012
Abgabe der Präsentationsfolien (Aufbau) 24.01.2012
Abgabe der Präsentationsfolien (Final) 31.01.2012
Vorträge 07.-08.02.2012 jeweils 11-16:15 Uhr

Vorträge

Autoren Thema Quelle Vortragender Termin
B. Katz, I. Rutter, B. Strasser, D. Wagner Speed Dating: An Algorithmic Case Study Involving Matching and Scheduling SEA 2011 Michael Jugovac 7.2.2012
Th. Gellert, F. König Heuristic 1D Vehicle Scheduling with Conflicts ALENEX 2011 Philipp Lewe 7.2.2012
G. Blelloch, J. Shun A Simple Parallel Cartesian Tree Algorithm and its Application to Suffix Tree Construction ALENEX 2011 Till Schäfer 7.2.2011
P.M.M. de Castro, O. Devillers Simple and Efficient Distribution-Sensitive Point Location in Triangulations ALENEX 2012 Johann Kexel 7.2.2012
A. Berger, C. Blaar, A. Gebhardt, M. Müller-Hannemann, M. Schnee Passenger Flow-Oriented Train Disposition ESA 2011 Mirijam Koch 8.2.2012
R. Geisberger, C. Vetter Efficient Routing in Road Networks with Turn Costs SEA 2011 Viktor Mucha 8.2.2012
S. Meinert and D. Wagner Generating Time Dependencies in Road Networks SEA 2011 entfällt 8.2.2012
N. Chen, X. Deng, J. Zhang How Profitable are Strategic Behaviors in a Market ESA 2011 entfällt 8.2.2012

Ansprechpartner

Bei Fragen zu dieser Veranstaltung wenden Sie sich bitte an Petra Mutzel.

 
Last modified: 2015-09-11 13:22 (external edit)
DokuWikiRSS-Feed