====== Seminar Algorithm Engineering (SoSe 2016) ====== | 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=169057&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 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. ===== Themenliste ===== ^ ^ (verlinkter) Titel ^ Autoren ^ Konferenz ^ Teilnehmer ^ Betreuer ^ | 1. | [[http://ac.els-cdn.com/S0166218X05003094/1-s2.0-S0166218X05003094-main.pdf?_tid=cd899d82-fa5b-11e5-88e0-00000aab0f26&acdnat=1459770970_3ce4ca5424ecbfb1d1b596412bb70460|A Branch-and-Cut algorithm for graph coloring]] | Méndez-Díaz, Zabala | DAM 2005 | Manuel Barbi | [[:staff:jabrayilov|Adalat Jabrayilov]] | | 2. | [[http://arxiv.org/pdf/1409.8318v1.pdf|Strong Steiner Tree Approximations in Practice]] | Bayer, Chimani | CoRR 2014 | Sergei Harder | [[:staff:zey|Bernd Zey]] | | 3. | [[http://dl.acm.org/citation.cfm?id=1718537|A sketch-based distance oracle for web-scale graphs]] | Das Sarma, Gollapudi, Najork, Panigrahy | WSDM 2010 | Jan Möller | [[:staff:morris|Christopher Morris]] | | 4. | [[http://link.springer.com/chapter/10.1007%2F978-3-319-07959-2_10| Parallel Bi-objective Shortest Paths Using Weight-Balanced B-trees with Bulk Updates]] | Erb, Kobitzsch, Sanders | SEA 2014 | John Sarrazin | [[:staff:boekler|Fritz Bökler]] | | 5. | [[http://dx.doi.org/10.1007/978-3-642-40450-4_13|Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement]] | Berkholz, Bonsma, Grohe | ESA 2013 | Dennis Ciba | [[:staff:kriege|Nils Kriege]] | | 6. | [[http://dx.doi.org/10.1007/978-3-662-44777-2_42|Dimension Reduction via Colour Refinement]] | Grohe, Kersting, Mladenov, Selman | ESA 2014 | Mirko Bunse | [[:staff:mutzel|Petra Mutzel]] | Die Vorträge werden vom 25.-26.07.2016 im Raum 304, OH14 gehalten. ^ ^ Montag, 25.07.2016 ^ Dienstag, 26.07.2016 ^ | ^ 9:00-10:00 | **A Branch-and-Cut algorithm for graph coloring** \\ //Manuel Barbi// | ^ | ^ 10:00-11:00 | **Strong Steiner Tree Approximations in Practice** \\ //Sergei Harder// | **A sketch-based distance oracle for \\ web-scale graphs** \\ //Jan Möller// ^ 10:00-11:00 | ^ | | **Parallel Bi-objective Shortest Paths Using \\ Weight-Balanced B-trees with Bulk Updates** \\ //John Sarrazin// ^ 11:00-12:00 | ^ ::: | ::: | (Pause) ^ 12:00:13:30 | ^ ::: | ::: | **Tight Lower and Upper Bounds for the Complexity \\ of Canonical Colour Refinement** \\ //Dennis Ciba// ^ 13:30-14:30 | ^ ::: | ::: | **Dimension Reduction via Colour Refinement** \\ //Mirko Bunse// ^ 14:30-15:30 | ===== Anmeldung und Vorbesprechung ===== Die Anmeldung erfolgt per E-Mail an [[staff:kurz|Denis Kurz]] bis zum Montag, den **11.04.2016**. Da die Teilnehmerzahl begrenzt 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 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 können 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** (**{{:teaching:ausarbeitung-ae2013.zip|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 Paper 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 Nicht-Bestehen 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 [[http://ls11-www.cs.tu-dortmund.de/people/chimani/seminarfolien.html|Hinweise]] zur Foliengestaltung! ===== Termine ===== Vorbesprechung und Themenvergabe: **20.04.2016, 11:00 Uhr (s.t.)** (OH 14, Raum 304) Weitere Termine: | Abgabe des Ausarbeitungskonzepts | ** 18.05.2016 ** | | Abgabe der Ausarbeitung | ** 20.06.2016 ** | | Abgabe der Ausarbeitung (Überarbeitete Version) | ** 04.07.2016 ** | | Abgabe der Präsentationsfolien (Aufbau) | ** 11.07.2016 ** | | Abgabe der Präsentationsfolien (Final) | ** 18.07.2016 ** | | Vorträge | Montag, **25.07.2016**\\ Dienstag, **26.07.2016** \\ OH 14, Raum 304 | ===== Links ===== * Vorlage für die Ausarbeitung: {{:teaching:ausarbeitung-ae2013.zip|[.zip-Archiv]}} * [[http://ls11-www.cs.tu-dortmund.de/people/chimani/seminarfolien.html|Hinweise zur Foliengestaltung]] ===== Ansprechpartner ===== Bei Fragen zu dieser Veranstaltung wenden Sie sich bitte an [[staff:kurz|Denis Kurz]] oder [[staff:mutzel|Petra Mutzel]].