Seminar Algorithm Engineering (SoSe 2018)

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

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 Parallelisierung, 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 vielversprechende 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 praxisrelevante 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.

Vorträge

Die Vorträge werden in der Otto-Hahn-Straße 12 im Raum 3.031 gehalten.

Dienstag

Uhrzeit Betreuer/in Teilnehmer/in Autor/innen Titel Quelle
09:30 Bernd Zey Daniel Kurowski Paul, Freund, Ferber, Shmoys, Williamson Prize-Collecting TSP with a Budget Constraint ESA 2017
10:30 Adalat Jabrayilov Uriel Elias Wieblitz Costa, Cordeau, Laporte Models and branch-and-cut algorithms for the Steiner tree problem with revenues, budget and hop constraints Networks 53 (2), 2009
11:30 Nils Kriege Artur Ljulin Engler, El-Kebir, Mulder, Mark, Geerke, Klau Enumerating common molecular substructures PeerJ Preprints 2017
12:30 Mittagspause
13:30 Christiane Spisla Scarlett Gebski Aulbach, Fink, Schuhmann, Wolff Drawing Graphs within Restricted Area GD 2014
14:30 Christine Dahn Jens Zentgraf Holm, Italiano, Karczmarz, Łącki, Rotenberg, Sankowski Contracting a Planar Graph Efficiently ESA 2017
15:30 Christine Dahn Cedric Schinner Nocaj, Ortmann, Brandes Untangling Hairballs - From 3 to 14 Degrees of Separation GD 2014

Mittwoch

Uhrzeit Betreuer/in Teilnehmer/in Autor/innen Titel Quelle
09:30 Denis Kurz Philipp Kramer Wagner, Zündorf Public Transit Routing with Unrestricted Walking ATMOS 2017
10:30 Denis Kurz Fabian Smolinski Delling, Dibbelt, Pajor, Zündorf Faster Transit Routing by Hyper Partitioning ATMOS 2017
11:30 Lutz Oettershagen Hermann Foot Strehler, Merting, Schwan Energy-efficient shortest routes for electric and hybrid vehicles Transportation Research Part B: Methodological 103, 2017
12:30 Mittagspause
13:30 Lutz Oettershagen Julius Adamek Wu, Cheng, Huang, Ke, Lu, Xu Path Problems in Temporal Graphs VLDB 2014
14:30 Andre Droschinsky Dennis Misera Hansen, Kaplan, Tarjan, Zwick Hollow Heaps ICALP 2015
15:30 Till Schäfer Christian Bohr Badanidiyuru, Mirzasoleiman, Karbasi, Krause Streaming Submodular Maximization: Massive Data Summarization on the Fly SIGKDD 2014

Anmeldung und Vorbesprechung

Die Anmeldung erfolgt ab dem 26.03.18 unter Angabe von Name, Email (TU Dortmund), Matrikelnummer per E-Mail an Denis Kurz (s. Termine) ist abgeschlossen. Da die Teilnehmerzahl beschränkt ist, können nur die ersten 14 Anfragen berücksichtigt werden. Eine erfolgreiche Anmeldung wird durch eine E-Mail bestätigt. Die Themenverteilung erfolgt bei der Vorbesprechung (s. Termine).

Ablauf des Seminars

Die Themenverteilung erfolgt während der Vorbesprechung. Im weiteren Verlauf des Semesters haben die TeilnehmerInnen Zeit, eine Ausarbeitung zu schreiben und einen Vortrag vorzubereiten. In dieser Zeit wird es keine regelmäßigen Treffen in der Gruppe geben. Die SeminarteilnehmerInnen sollen sich bei organisatorischen und inhaltlichen Fragen jederzeit an den zugeordneten Betreuer wenden.

Es soll zunächst ein Ausarbeitungskonzept von ca. 1-2 Seiten erstellt und mit dem Betreuer besprochen werden. Dieses Konzept sollte eine Gliederung der späteren Ausarbeitung umfassen sowie Stichpunkte, welche Themen in den einzelnen Abschnitten behandelt und welche weiteren Quellen verwendet werden. Das Konzept wird besprochen, bevor mit der Ausarbeitung begonnen wird; spätestens zum unten angegebenen Termin.

Die schriftlichen Ausarbeitung (Vorlage) umfasst 15-20 Seiten und muss mit LaTeX erstellt werden. Dazu muss eventuell eine Stoffauswahl getroffen werden, falls das zu bearbeitende Paper zu umfangreich ist. Die Ausarbeitung sollte inhaltlich mit dem späteren Vortrag übereinstimmen. Falls zur Bearbeitung weitere Quellen nötig sind, sollen diese im nötigen Umfang ebenfalls in der Ausarbeitung aufgearbeitet werden. Eine kritische Auseinandersetzung mit allen verwendeten Quellen, vor allem aber dem zugeordneten Artikel, ist ausdrücklich gewünscht. Die Ausarbeitung ist Voraussetzung für den Vortrag.

Nach der Abgabe der Ausarbeitung besteht einmalig die Gelegenheit, die Ausarbeitung auf Grundlage des Feedbacks des Betreuers zu überarbeiten. Mangelhafte Ausarbeitungen und 1:1-Übersetzungen sowie mangelhafte Vorträge führen zum Nichtbestehen des Seminars. Auch nicht rechtzeitig abgegebene Ausarbeitungen führen zum Nicht-Bestehen.

Alle Teilnehmer halten im Rahmen eines Blockseminars kurz nach Ende der Vorlesungszeit einen 45-minütigen Vortrag über das festgelegte Thema. Im Anschluss an jeden Vortrag folgt eine ca. 15-minütige Diskussion über Thema und Vortrag. Es herrscht Anwesenheitspflicht bei allen Vorträgen. Bitte beachten Sie auch die Hinweise zur Foliengestaltung!

Termine

Ereignis Vorlesungswoche Termin
Anmeldebeginn (-2) 26.03.2018
Anmeldeschluss 1 oder 2 10.04.2018
Vorbesprechung und Themenvergabe 1 oder 2 11.04.2018 ab 11:00 Uhr (s.t.)
im Raum OH14, R. 202
Abgabe des Ausarbeitungskonzepts 6 16.05.2018
Abgabe der Ausarbeitung 11 20.06.2018
Abgabe der Ausarbeitung (Final) 13 04.07.2018
Abgabe der Präsentationsfolien (Aufbau) 14 11.07.2018
Abgabe der Präsentationsfolien (Final) 15 23.07.2018
(ursprünglich 18.07.2018)
Vorträge 15 + 2 31.07. – 01.08.2018

Benotungskriterien

Kriterien der schriftlichen Ausarbeitung:

  • Darstellung/Formales: Struktur, Literaturangaben (adäquat und sind im korrekten Format), Abbildungen/Tabellen, Form (Formatierung, Erscheinungsbild), frei von grammatikalischen Fehlern, von Zeichensetzung- und Tippfehlern.
  • Stil/Aufbau/Struktur: Schreibstil (Fachbegriffe werden korrekt definiert und verwendet, flüssig geschrieben, gut lesbar), gut strukturiert, Inhalt ist prägnant dargestellt, Verwendung von Latex-Theorem-Umgebungen wie “Definition”, “Lemma”, etc.
  • Inhalt: adäquate Stoffauswahl, evtl. über die Seminarliteratur hinausgehende Quellen, keine inhaltlichen Fehler, eigenständige Aufbereitung des Stoffs, z.B. durch selbst erstellte Beispiele, eigene Formulierungen etc., kritische Auseinandersetzung mit dem Thema
  • Selbstständigkeit in der Vorbereitung: Fragen in Vorbesprechung geklärt, angemessene Schwerpunktsetzung, eigenes eingebracht (Achtung: Fragen an und Diskussionen mit den Betreuern führen nicht zur Abwertung, sondern in der Regel durch die dadurch folgenden qualitativ bessere Abgaben zu besseren Noten; viel eher ist damit gemeint, dass nicht jeder dritte Satz der Ausarbeitung korrigiert werden muss)

Kriterien des Vortrags:

  • Inhalt: Aufbau, adäquater Umfang und Auswahl, Korrektheit, Einbringen eigener Überlegungen (z.B. Beispiele, Graphiken, eigene kritische Anmerkungen), Verständlichkeit (z.B. Definition von Fachbegriffen), Veranschaulichung durch Bilder, eigene Bewertung/Diskussion
  • Präsentation: Vortragsstil (frei, flüssig, Wortwahl, gut verständlich), Folien sinnvoll eingesetzt und sinnvoll gestaltet, Zeitplanung

Ansprechpartner

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

 
Last modified: 2018-07-30 10:24 by Denis Kurz
DokuWikiRSS-Feed