Differences
This shows you the differences between two versions of the page.
— |
teaching:seminarae-ss2016 [2016-07-19 15:12] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== 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]]. |