Differences

This shows you the differences between two versions of the page.

Link to this comparison view

teaching:seminarae-ss2015 [2016-01-08 17:31] (current)
Line 1: Line 1:
 +====== Seminar Algorithm Engineering (SoSe 2015) ======
 +
 +| Veranstalterin | [[staff:​mutzel|Prof. Dr. Petra Mutzel]] |
 +| Modul          | Diplom, Master [[http://​www.cs.tu-dortmund.de/​nps/​de/​Studium/​Ordnungen_Handbuecher_Beschluesse/​Modulhandbuecher/​Master_Inf/​Pflichtveranstaltungen/​INF-MSc-102.pdf|INF-MSc-102 (Informatik,​ Angewandte Informatik)]] | 
 +| Veranstaltungsart ​   | Seminar ​                    |
 +| Veranstaltungsnummer | [[https://​www.lsf.tu-dortmund.de/​qisserver/​rds?​state=verpublish&​status=init&​vmfile=no&​publishid=154833&​moduleCall=webInfo&​publishConfFile=webInfo&​publishSubDir=veranstaltung|041405]] |
 +| 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 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
 +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 realistische 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 =====
 +
 +^ ^ Titel ^ Autoren ^ Konferenz ^ Teilnehmer ^ Betreuer ^
 +| 1. | [[http://​dx.doi.org/​10.1007/​s00453-007-9008-7|Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection]] | Hüffner, Wernicke, Zichner | Algorithmica 52:2 | Sebastian Opriel | [[staff:​kriege|Nils Kriege]] |
 +| 2. | [[http://​dx.doi.org/​10.1137/​1.9781611972931.4|Polynomial-time construction of contraction hierarchies for multi-criteria objectives]] | Funke, Storandt | ALENEX 2013 | Mark Schröder | [[staff:​kurz|Denis Kurz]] |
 +| 3. | [[http://​dx.doi.org/​10.1137/​1.9781611973198.14|Fast Shortest-path Distance Queries on Road Networks by Pruned Highway Labeling]] | Akiba, Iwata, Kawarabayashi,​ Kawata ​ | ALENEX 2014 | Pia Wierzoch | [[staff:​droschinsky|Andre Droschinsky]] |
 +| 4. | [[http://​dx.doi.org/​10.1137/​1.9781611973198.15|Flow-Based Guidebook Routing]] ​ | Bast, Storandt | ALENEX 2014 | Daniel Friesel | [[staff:​mutzel|Petra Mutzel]] |
 +| 5. | [[http://​arxiv.org/​abs/​1404.4465|PReaCH:​ A Fast Lightweight Reachability Index using Pruning and Contraction Hierarchies]] | Merz, Sanders | ESA (Track B) 2014 | Ole Bergenholtz | [[staff:​droschinsky|Andre Droschinsky]] |
 +| 6. | [[http://​dx.doi.org/​10.1007/​978-3-662-44777-2_27|Robust Distance Queries on Massive Networks]] | Delling, Goldberg, Pajor, Werneck | ESA (Track B) 2014 | Jan Stallmann | [[staff:​mutzel|Petra Mutzel]] |
 +| 7. | [[http://​dx.doi.org/​10.1109/​ICDM.2013.157|Subgraph Enumeration in Dynamic Graphs]] | Adiga, Vullikanti, Wiggins | ICDM 2013 | Tobias Heinlein | [[staff:​kriege|Nils Kriege]] |
 +| 8. | [[http://​dx.doi.org/​10.1109/​ICDM.2013.39|Active Density-based Clustering]] | Mai, He, Hubig, Plant, Böhm | ICDM 2013 | Patrick Brandt | [[staff:​schaefer|Till Schäfer]] |
 +| 9.| [[http://​dx.doi.org/​10.1002/​net.21552|Finding k Shortest Paths in Directed Graphs: A Node Classification Algorithm]] | Feng | Networks 2014 | Raoul Lefmann | [[staff:​kurz|Denis Kurz]] |
 +| 10.| [[http://​www.aaai.org/​ocs/​index.php/​SOCS/​SOCS13/​paper/​view/​7238|Bidirectional preference-based search for multiobjective state space graph problems]] | Galand, Ismaili, Perny, Spanjaard | SoCS 2013 | Tobias Marquardt | [[staff:​boekler|Fritz Bökler]] |
 +
 +Auf alle Artikel kann aus dem Uni-Netzwerk (oder mittels VPN von zu Hause aus) zugegriffen werden.
 +
 +Die Vorträge werden vom 20.-21.07.2015 im Raum 202, OH14 gehalten.
 +
 +| ^  Montag, 20.07.2014 ​ ^  Dienstag, 21.07.2015 ​ ^
 +^   ​9:​00-10:​00 |  **Fast Shortest-path Distance Queries on Road \\ Networks by Pruned Highway Labeling** \\ //Pia Wierzoch// ​ |  **PReaCH: A Fast Lightweight Reachability Index \\ using Pruning and Contraction Hierarchies** \\ //Ole Bergenholtz// ​ |
 +^  10:00-11:00 |  **Polynomial-time construction of contraction \\ hierarchies for multi-criteria objectives** \\ //Mark Schröder// ​ |  **Algorithm Engineering for Color-Coding with \\ Applications to Signaling Pathway Detection** \\ //Sebastian Opriel// ​ |
 +^  11:00-12:00 |  **Bidirectional preference-based search for \\ multiobjective state space graph problems** \\ //Tobias Marquardt// ​ |  **Subgraph Enumeration in Dynamic Graphs** \\ //Tobias Heinlein// ​ |
 +^              |  (Pause bis 13:30 Uhr)  |  (Pause bis 14:00 Uhr)  |
 +^  13:30-14:30 |  **Flow-Based Guidebook Routing** \\ //Daniel Friesel// ​ |::: |
 +^  :::         |::: |  **Active Density-based Clustering** \\ //Patrick Brandt// ​ |
 +^  14:30-15:30 |  **Robust Distance Queries on Massive Networks** \\ //Jan Stallmann// ​ |::: |
 +^  :::         |::: |    |
 +^  15:30-16:30 |  **Finding k Shortest Paths in Directed Graphs: \\ A Node Classification Algorithm** \\ //Raoul Lefmann// ​ |::: |
 +
 +**Vorsicht:​** Der letzte Vortrag **am Dienstag** kann wegen einer parallel stattfindenden Klausur erst von **14:​00-15:​00** stattfinden.
 +
 +===== Anmeldung und Vorbesprechung =====
 +
 +Die Anmeldung erfolgt per E-Mail an [[staff:​kurz|Denis Kurz]] bis zum Montag, den **06.04.2015**.
 +Da die Teilnehmerzahl beschränkt ist, können nur die ersten 12 Anfragen berücksichtigt werden.
 +Eine erfolgreiche Anmeldung wird durch eine E-Mail 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 der Vorlesungszeit einen **45-minütigen** Vortrag über das festgelegte Thema.
 +Im Anschluss folgt eine ca. 15-minütige Diskussion über Thema und Vortrag.
 +Es herrscht Anwesenheitspflicht bei allen Vorträgen.
 +Bitte beachten Sie auch die [[http://​ls11-www.cs.tu-dortmund.de/​people/​chimani/​seminarfolien.html|Hinweise]] zur Foliengestaltung!
 +
 +Voraussetzung für den Vortrag ist die vorherige Abgabe einer schriftlichen **Ausarbeitung**,​ welche 15-20 Seiten umfasst und mit **LaTeX** erstellt wird.
 +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 Nicht-Bestehen des Seminars.
 +Auch nicht rechtzeitig abgegebene Ausarbeitungen können zum Nicht-Bestehen führen. ​
 +
 +Vorlage für die Ausarbeitung:​ {{:​teaching:​ausarbeitung-ae2013.zip|[.zip-Archiv]}}
 +
 +===== Termine =====
 + 
 +Vorbesprechung und Themenvergabe:​ **09.04.2015,​ 15:00 Uhr (s.t.)** (OH 14, Raum 202)
 +
 +Weitere Termine: ​
 +
 +| Abgabe des Ausarbeitungskonzepts ​               | ** 01.06.2015 ** |
 +| Abgabe der Ausarbeitung ​                        | ** 15.06.2015 ** |
 +| Abgabe der Ausarbeitung (Überarbeitete Version) | ** 29.06.2015 ** |
 +| Abgabe der Präsentationsfolien (Aufbau) ​        | ** 06.07.2015 ** |
 +| Abgabe der Präsentationsfolien (Final) ​         | ** 13.07.2015 ** |
 +| Vorträge ​                                       | Montag, **20.07.2015**\\ Dienstag, **21.07.2015** \\ OH 14, Raum 202 |
 +
 +===== Ansprechpartner =====
 +
 +Bei Fragen zu dieser Veranstaltung wenden Sie sich bitte an [[staff:​kurz|Denis Kurz]] oder [[staff:​mutzel|Petra Mutzel]].
  
 
Last modified: 2016-01-08 17:31 (external edit)
DokuWikiRSS-Feed