Seminar Algorithm Engineering (WiSe 2014/15)

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

Inhalt

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 aktuellen Veröffentlichungen aus dem Bereich des Algorithm Engineerings, die auf internationalen Konferenzen oder in Zeitschriften erschienen sind.

Themenliste

Nr. Thema Konferenz / Journal Teilnehmer Betreuer Termin
1. Maximum common induced subgraph parameterized by vertex cover
Faisal N. Abu-Khzam
Inf. Proc. Letters 114(3), 2014 Elena Erdmann Nils Kriege 9:30 Uhr
2. Mining Graph Patterns Efficiently via Randomized Summaries
Chen Chen, Cindy X. Lin, Matt Fredrikson, Mihai Christodorescu, Xifeng Yan, Jiawei Han
VLDB 2009 Maren Geske Till Schäfer 10:30 Uhr
3. Triangle Listing Algorithms: Back from the Diversion
Mark Ortmann, Ulrik Brandes
ALENEX 2014 Henning Funke Petra Mutzel 11:30 Uhr
4. Connection Scan Accelerated
Ben Strasser, Dorothea Wagner
ALENEX 2014 Benjamin Kramer Till Schäfer 13:30 Uhr
5. Finding the k Shortest Paths
David Eppstein
SIAM J. Comput. 28(2), 1998 Julian Kürby Denis Kurz 14:30 Uhr
6. GRASP. Extending Graph Separators for the Single-Source Shortest-Path Problem
Alexandros Efentakis, Dieter Pfoser
ESA (Track B) 2014 Jaouad Zarouali Fritz Bökler 15:30 Uhr

Auf die Artikel kann aus dem Uni-Netzwerk (oder mittels VPN von zu Hause aus) zugegriffen werden.

Die Reihenfolge und die Zeiten der Termine sind vorläufig.

Anmeldung und Vorbesprechung

Die Anmeldung erfolgt per Email bei Carsten Gutwenger bis zum Montag, dem 06.10.2014. Da die Teilnehmerzahl beschränkt ist, können nur die erste 12 Anfragen berücksichtigt werden. Eine erfolgreiche Anmeldung wird durch eine Email bestätigt. 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. Die Ausarbeitung wird vom Betreuer bewertet und es besteht anschließend einmalig die Gelegenheit, die Ausarbeitung zu überarbeiten. Mangelhafte Ausarbeitungen und 1:1-Übersetzungen 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: 09.10.2014, 14:00 Uhr (OH 14, Raum 202)

Weitere Termine:

Abgabe des Ausarbeitungskonzepts 15.12.2014
Abgabe der Ausarbeitung 12.01.2015
Abgabe der Ausarbeitung (Überarbeitete Version) 19.01.2015
Abgabe der Präsentationsfolien (Aufbau) 26.01.2015
Abgabe der Präsentationsfolien (Final) 02.02.2015
Vorträge Dienstag, 10.02.2015
9:30-12:30 und 13:30-16:30
(Raum 202, OH14)

Ansprechpartner

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

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