Differences

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

@@ Line 1: / Line 1: @@
+====== Seminar Algorithm Engineering (SoSe 2017) ======
+| 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/Journal ^ Teilnehmer/in^ Betreuer/in  ^ Vortrags-Zeit ^
+| 1. | [[http://download.springer.com/static/pdf/826/art%253A10.1007%252Fs12532-016-0102-1.pdf?originUrl=http%3A%2F%2Flink.springer.com%2Farticle%2F10.1007%2Fs12532-016-0102-1&token2=exp=1487687713~acl=%2Fstatic%2Fpdf%2F826%2Fart%25253A10.1007%25252Fs12532-016-0102-1.pdf%3ForiginUrl%3Dhttp%253A%252F%252Flink.springer.com%252Farticle%252F10.1007%252Fs12532-016-0102-1*~hmac=bce35c55d1d8d3e98976206cfbeb4e8c812da01f8899960fcaa5e160817ef59b|A node-based layered graph approach for the Steiner tree problem with revenues, budget and hop-constraints]] |Markus Sinnl, Ivana Ljubić | MPC 2015 | Jonas Charfreitag   | [[:staff:jabrayilov|Adalat Jabrayilov]]  |Di 9-10:00 |
+| 3. | [[http://epubs.siam.org/doi/10.1137/1.9781611974768.3|Engineering a direct k-way Hypergraph Partitioning Algorithm]] | Yaroslav Akhremtsev, Tobias Heuer, Peter Sanders, Sebastian Schlag | ALENEX 2017 | Lara Waltermann | [[:staff:kurz|Denis Kurz]] |Di 10-11:00 |
+| 4. | [[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 | Oliver Georg Zietek | [[:staff:droschinsky|Andre Droschinsky]]   |
+| 16. | [[https://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0ahUKEwjEi9bvrYrTAhUB8RQKHVlUDz4QFggcMAA&url=https%3A%2F%2Fpublikationen.bibliothek.kit.edu%2F1000052742%2F3801174&usg=AFQjCNE629Rnni47O9Fdmsgc8tjRMsPqKw&sig2=w10f1_hrfrpYVPJWF2tv1A|Faster Incremental All-Pairs-Shortest-Paths]] | Slobbe, Bergamini, Meyerhenke | Karlsruhe Reports in Informatics 2016| Till Schallau | [[:staff:mutzel|Petra Mutzel]]  |Di 11-12:00 |
+| 7. | [[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 |Hasan Simsek | [[:staff:morris|Christopher Morris]]   |
+| 8. | [[http://ieeexplore.ieee.org/abstract/document/7837861/|A Scalable and Generic Framework to Mine Top-k Representative Subgraph Patterns]] | Dheepikaa Natarajan, Sayan Ranu | ICDM 2016 |Florian Priebe | [[:staff:schaefer|Till Schäfer]]  |Di 13-14:00 |
+| 9. | [[https://link.springer.com/chapter/10.1007/978-3-319-31753-3_23|Significant Pattern Mining with Confounding Variables]] | Aika Terada, David duVerle, and Koji Tsuda | PAKDD 2016 |Dennis Duman | [[:staff:schaefer|Till Schäfer]]   |
+| 10. | [[http://dx.doi.org/10.1016/j.jsc.2013.09.003|Practical graph isomorphism, II]] | Brendan D. McKaya, Adolfo Piperno | J. Symb. Comput. 60, 2014 |Christopher Osthues | [[:staff:kriege|Nils Kriege]]   |Di 14-15:00 |
+| 11. | [[http://jgaa.info/getPaper?id=263|Inapproximability of Orthogonal Compaction]] | Michael J. Bannister, David Eppstein, and Joseph A. Simons  | JGAA, 2012 |Jonas Schmidt  | [[:staff:spisla|Christiane Spisla]]   |Di 15-16:00 |
+| 12. | [[http://link.springer.com/article/10.1007/s10107-016-1013-7|Nash equilibria in the two-player kidney exchange game]] |Margarida Carvalho, Andrea Lodi, João Pedro Pedroso, Ana Viana | MP, 161, 2017|Alexander Müller | [[:staff:spisla|Christiane Spisla]]  |Mi 10-11:00 |
+| 14. | [[https://arxiv.org/abs/1701.02989|A General Approximation Method for Bicriteria Minimization Problems]] | Halffmann, Ruzika, Thielen, Willems |arXiv.org 2017 | Mikel Jedrusiak  | [[:staff:boekler|Fritz Bökler]]  |Mi 11-12:00 |
+| 15. | [[http://epubs.siam.org/doi/abs/10.1137/080724514?journalCode=smjcat|Small Approximate Pareto-Sets for Bi-Objective Shortest Paths and Other Problems]] | Diakonikolas, Yannakakis | SIAM J. Comput. 39(4) 1340-1371, 2009|Johannes Neumann| [[:staff:boekler|Fritz Bökler]]  |Mi 13-14:00 |
+| 6. | [[http://dx.doi.org/10.1137/1.9781611973402.115|Bicriteria data compression]] | Andrea Farruggia, Paolo Ferragina, Antonio Frangioni, Rossano Venturini | SODA 2014 | Jonas Ellert | [[:staff:koeppl|Dominik Köppl]]  |Mi 14-15:00 |
+Die Vorträge werden vom 1-2.08.2017 im Raum 202, OH14 gehalten
+^ ^   Di, 1.08.2017  ^ Mi, 2.08.2017  ^ |
+===== Anmeldung und Vorbesprechung =====
+<del>Die Anmeldung erfolgt per E-Mail an [[staff:jabrayilov|Adalat Jabrayilov]] bis zum Montag, den **17.04.2017**.
+Die Themenverteilung erfolgt bei der Vorbesprechung 18.04.2017 (s. unten). </del>
+===== 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: **18.04.2017, 12:00 Uhr (s.t.)** (OH 14, Raum 202)
+Weitere Termine:
+| Abgabe des Ausarbeitungskonzepts                | ** 25.05.2017 ** |
+| Abgabe der Ausarbeitung                         | ** 26.06.2017 ** |
+| Abgabe der Ausarbeitung (Überarbeitete Version) | ** 10.07.2017 ** |
+| Abgabe der Präsentationsfolien (Aufbau)         | ** 17.07.2017 ** |
+| Abgabe der Präsentationsfolien (Final)          | ** 24.07.2017 ** |
+| Vorträge                                        | Dienstag ** 1.08.2017 ab 9:00 Uhr **\\  Mittwoch, ** 2.08.2017  ab 10:00 Uhr **\\ OH 14, Raum 202 |
+===== 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]].

Chair 11

Teaching

Research Groups

Differences