Differences

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

Link to this comparison view

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]].
 
Last modified: 2016-07-19 15:12 (external edit)
DokuWikiRSS-Feed