Differences
This shows you the differences between two versions of the page.
— |
teaching:seminarae-ws2017 [2018-02-04 13:59] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== Seminar Algorithm Engineering (WiSe 2017/2018) ====== | ||
+ | | 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=163110&moduleCall=webInfo&publishConfFile=webInfo&publishSubDir=veranstaltung|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. | ||
+ | |||
+ | ===== Themenliste ===== | ||
+ | |||
+ | ^ ^ (verlinkter) Titel ^ Autoren ^ Konferenz/Journal ^ Vortrags-Zeit ^ Teilnehmer/in^ Betreuer/in ^ | ||
+ | | 1. | [[http://pubsonline.informs.org/doi/abs/10.1287/ijoc.1120.0525?journalCode=ijoc|Exact Approaches to Multilevel Vertical Orderings]] | Chimani, Hungerländer | INFORMS2013 | Di 10-11:00 | JJ | [[:staff:jabrayilov|Adalat Jabrayilov]] | | ||
+ | | 2. | [[http://www.sciencedirect.com/science/article/pii/S157252861000054X|An exact approach for the Vertex Coloring Problem]] | E. Malaguti, M. Monaci, P. Toth | DO2011 | Di 11-12:00 | JS | [[:staff:jabrayilov|Adalat Jabrayilov]] | | ||
+ | | 3. | [[http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=6798|Bipartite Matching with Linear Edge Weights]] | Nevzat Onur Domanic, Chi-Kit Lam, C. Gregory Plaxton | ISAAC 2016 | Di 12-13:00 | RH | [[:staff:droschinsky|Andre Droschinsky]] | | ||
+ | | 4. | [[https://link.springer.com/content/pdf/10.1007%2Fs00454-016-9842-y.pdf|Upper and Lower Bounds for Online Routing on Delauney Triangulations]] | Bonichon, Bose, Carufel, Perković, Renssen | ESA 2015 | Di 14-15:00 | CD | [[:staff:droschinsky|Andre Droschinsky]] | | ||
+ | | 5. | [[https://link.springer.com/chapter/10.1007/978-3-319-22177-9_26|On the Power of Color Refinement | ||
+ | ]] | V. Arvind, J. Köbler, G. Rattan, O. Verbitsky | FCT 2015 | Di 15-16:00 | FL | [[:staff:morris|Christopher Morris]] | | ||
+ | | 6. | [[http://epubs.siam.org/doi/abs/10.1137/120867834?journalCode=smjcat|Sherali--Adams Relaxations and Indistinguishability in Counting Logics]] | A. Atserias and E. Maneva | SIAM J. Comput. | | MR | [[:staff:morris|Christopher Morris]] | | ||
+ | | 7. | [[http://www.jmlr.org/papers/volume17/mirzasoleiman16a/mirzasoleiman16a.pdf|Distributed Submodular Maximization]] |Mirzasoleiman, B.; Karbasi, A.; Sarkar, R. & Krause, A. | JMLR2016 | Di 16-17:00 | FH | [[:staff:schaefer|Till Schäfer]] | | ||
+ | | 8. | [[http://ieeexplore.ieee.org/document/6816705/?reload=true|Large-scale frequent subgraph mining in MapReduce]] |Lin, W.; Xiao, X. & Ghinita, G.| ICDE2014 | Mi 10-11:00 | PD | [[:staff:schaefer|Till Schäfer]] | | ||
+ | | 9. | [[http://rtsys.informatik.uni-kiel.de/~biblio/downloads/papers/gd15.pdf | Size- and Port-Aware Horizontal Node Coordinate Assignment]] | Ulf Rüegg, Christoph Daniel Schulze, John Julian Carstens, Reinhard von Hanxleden | GD 2015 | Mi 11-12:00 | BW | [[:staff:spisla|Christiane Spisla]] | | ||
+ | | 10. | [[http://drops.dagstuhl.de/opus/volltexte/2016/6783/pdf/LIPIcs-ISAAC-2016-8.pdf | Finding k Simple Shortest Paths and Cycles]] | Udit Agarwal, Vijaya Ramachandran| ISAAC 2016 | | DT | [[:staff:spisla|Christiane Spisla]] | | ||
+ | | 11. | [[https://www.researchgate.net/publication/318828055_Decomposition_methods_for_the_two-stage_stochastic_Steiner_tree_problem|Decomposition methods for the two-stage stochastic Steiner tree problem]] | Markus Leitner, Martin Luipersbeck, Markus Sinnl, Ivana Ljubic | TR2017 | | t | [[:staff:zey|Bernd Zey]] | | ||
+ | | 12. | [[http://drops.dagstuhl.de/opus/volltexte/2017/7816/pdf/LIPIcs-ESA-2017-59.pdf|Subexponential parameterized algorithms for graphs of polynomial growth]] | Dániel Marx and Marcin Pilipczuk | ESA2017 | | t | [[:staff:mutzel|Petra Mutzel]] | | ||
+ | | 13. | [[http://drops.dagstuhl.de/opus/volltexte/2017/7875/pdf/LIPIcs-ESA-2017-50.pdf|Contracting a Planar Graph Efficiently]] | Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki, Eva Rotenberg and Piotr Sankowski. | ESA2017 | | FB | [[:staff:zey|Bernd Zey]] | | ||
+ | | 14. | [[http://drops.dagstuhl.de/opus/volltexte/2017/7849/pdf/LIPIcs-ESA-2017-29.pdf|Streaming Algorithms for Matching Size Estimation in Sparse Graphs]] | Graham Cormode, Hossein Jowhari, Morteza Monemizadeh and S Muthukrishnan | ESA2017 | | t | [[:staff:mutzel|Petra Mutzel]] | | ||
+ | | 15. | [[http://drops.dagstuhl.de/opus/volltexte/2017/7868/pdf/LIPIcs-ESA-2017-6.pdf|Randomized Contractions for Multiobjective Minimum Cuts]] | Aissi Hassene, A. Ridha Mahjoub and R. Ravi | ESA2017 | Mi 12-13:00 | SA | [[:staff:mutzel|Petra Mutzel]] | | ||
+ | | 16. | [[http://drops.dagstuhl.de/opus/volltexte/2017/7867/pdf/LIPIcs-ESA-2017-11.pdf|Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles]] | Moritz Baum, Julian Dibbelt, Dorothea Wagner and Tobias Zündorf | ESA2017 | Mi 14-15:00 | SB | [[:staff:zey|Bernd Zey]] | | ||
+ | | 17. | [[http://drops.dagstuhl.de/opus/volltexte/2017/7848/pdf/LIPIcs-ESA-2017-58.pdf|Dynamic Space Efficient Hashing]] | Tobias Maier and Peter Sanders | ESA2017 | Mi 15-16:00 | TT | [[:staff:mutzel|Petra Mutzel]] | | ||
+ | ===== Anmeldung und Vorbesprechung ===== | ||
+ | <del> | ||
+ | Die Anmeldung erfolgt unter Angabe von **Name, Email (TU Dortmund), Matrikelnummer und der Nummer von drei Themen (nach Priorität gereiht)** per E-Mail an [[staff:jabrayilov|Adalat Jabrayilov]] (s. [[#Termine]]). | ||
+ | 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]]). | ||
+ | </del> | ||
+ | <color #ed1c24>Die Anmeldung ist abgeschlossen.</color> | ||
+ | ===== 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 ===== | ||
+ | **Anmeldung:** bis zum **10.10.2017** | ||
+ | |||
+ | **Vorbesprechung und Themenvergabe:** Mittwoch, **11.10.2017, 12:00 Uhr (s.t.)** (OH14, Raum 202) | ||
+ | |||
+ | Weitere Termine: | ||
+ | |||
+ | ^ Ereignis ^ Termin ^ | ||
+ | | Abgabe des Ausarbeitungskonzepts | ** 13.11.2017 ** | | ||
+ | | Abgabe der Ausarbeitung | ** 13.12.2017 ** | | ||
+ | | Abgabe der Ausarbeitung (Final) | ** 10.01.2018 ** | | ||
+ | | Abgabe der Präsentationsfolien (Aufbau) | ** 17.01.2018 ** | | ||
+ | | Abgabe der Präsentationsfolien (Final) | ** 24.01.2018 ** | | ||
+ | | Vorträge | Dienstag, **6.02.2018**\\ Mittwoch, **7.02.2018** \\ OH 14, Raum 202 | | ||
+ | |||
+ | ** Hinweis: Die Vorträge finden Dienstag ab 10 Uhr und Mittwoch ab 10 Uhr statt ** | ||
+ | |||
+ | |||
+ | ===== 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 | ||
+ | |||
+ | ===== 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:jabrayilov|Adalat Jabrayilov]] oder [[staff:mutzel|Petra Mutzel]]. |