Differences

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

Link to this comparison view

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]].
 
Last modified: 2018-02-04 13:59 (external edit)
DokuWikiRSS-Feed