Differences

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

Link to this comparison view

teaching:seminarae-ss2013 [2015-09-11 13:41]
teaching:seminarae-ss2013 [2015-09-11 13:41] (current)
Line 1: Line 1:
 +====== Seminar Algorithm Engineering (SoSe 2013) ======
 +
 +| 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=125137&​moduleCall=webInfo&​publishConfFile=webInfo&​publishSubDir=veranstaltung|041406]] |
 +| 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 Parallelismus,​ 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
 +viel versprechende 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 realistischere 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 =====
 +^  Nr.  ^ Thema ^ Quelle ^ Teilnehmer ^ Termin ^ Betreuer ^ 
 +|  1  | [[http://​knowledgecenter.siam.org/​0238-000020/​|Practical Batch-Updatable External Hashing with Sorting]]\\ Hyeontaek Lim, David G. Andersen, Michael Kaminsky | ALENEX 2013 | Yuri Struszczynski | 22.07. | [[staff:​gutwenger| Carsten Gutwenger]] |
 +|  2  | [[http://​dx.doi.org/​10.1109/​TCBB.2008.99|Finding the Nearest Neighbors in Biological Databases Using Less Distance Computations]]\\ Jianjun Zhou, Jörg Sander, Zhipeng Cai, Lusheng Wang, and Guohui Lin | TCBB 7:4 | Markus Frohme | 22.07. | [[staff:​schaefer| Till Schäfer]] |
 +|  3  | [[http://​www.vldb.org/​pvldb/​vol6/​p133-han.pdf|An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases]]\\ Jinsoo Lee, Wook-Shin Han, Romans Kasperovics,​ Jeong-Hoon Lee | VLDB 2012 | Dominik Mohr | 22.07. | [[staff:​kriege| Nils Kriege]] |
 +|  4  | [[http://​dx.doi.org/​10.1007/​s10479-011-1019-8|Polyhedral study of the maximum common induced subgraph problem]]\\ Breno Piva, Cid Carvalho de Souza | Annals OR 199:1 | Samir Mahmalat | 22.07. | [[staff:​kriege| Nils Kriege]] |
 +|  5  | [[http://​dx.doi.org/​10.1002/​net.20077|Near-shortest and K-shortest simple paths]]\\ W. Matthew Carlyle, R. Kevin Wood | Networks 46:2 | Chris Apfelbeck | 22.07. | [[staff:​boekler| Fritz Bökler]] |
 +|  6  | [[http://​dx.doi.org/​10.1023/​A:​1008215702611|An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set of a Multiple Objective Linear Programming Problem]]\\ Harold P. Benson | J. Global Opt. 13:1 | Sebastian Witte | 22.07. | [[staff:​boekler| Fritz Bökler]] |
 +|     | | | | | |
 +|  7  | [[http://​dx.doi.org/​10.1145/​2432622.2432628|Steiner Tree Approximation via Iterative Randomized Rounding]]\\ Jarosław Byrka, Fabrizio Grandoni, Thomas Rothvoss, Laura Sanità | JACM 60:1 | Tilo Schulz | 23.07. | [[staff:​zey| Bernd Zey]] |
 +|  8  | [[http://​dx.doi.org/​10.1016/​j.ejor.2009.12.004|Two-stage stochastic matching and spanning tree problems: Polynomial instances and approximation]]\\ Bruno Escoffier, Laurent Gourvès, Jérôme Monnot | EJOR 205:1 | Lukas Pradel | 23.07. | [[staff:​zey| Bernd Zey]] |
 +|  9  | [[http://​dx.doi.org/​10.1287/​moor.1060.0237|LP Rounding Approximation Algorithms for Stochastic Network Design]]\\ Anupam Gupta, R. Ravi, Amitabh Sinha | MOR 32:2 | Florian Eckey | 23.07. | [[staff:​zey| Bernd Zey]] |
 +|  10  | [[http://​dx.doi.org/​10.4230/​OASIcs.ATMOS.2010.100|An Empirical Analysis of Robustness Concepts for Timetabling]]\\ Marc Goerigk, Anita Schöbel | ATMOS 2010 | Sebastian Buschjäger | 23.07. | [[staff:​kurz| Denis Kurz]] |
 +
 +Auf die Artikel kann in der Regel aus dem Netz der Universität zugegriffen werden; sollte dies bei einzelnen Artikeln nicht möglich sein, kann der zuständige Betreuer kontaktiert werden.
 +
 +===== Anmeldung und Vorbesprechung =====
 +
 +Die Anmeldung erfolgt per Email bei Petra Mutzel bis zum Dienstag, dem **09.04.2013**.
 +Dieser Email fügen Sie bitte eine 3er Prioritätenliste Ihrer gewünschten Vorträge (Auswahl s. oben) bei. 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 Teilnehmer Zeit die Ausarbeitung zu schreiben und den Vortrag vorzubereiten. In dieser Zeit wird es keine regelmäßigen Treffen in der Gruppe geben, die Seminarteilnehmer besprechen sich allerdings mit ihrem zugeordneten Betreuer.
 +
 +Es handelt sich um ein Blockseminar. Alle Teilnehmer halten kurz nach Ende des Semesters einen **45-minütigen** Vortrag über das festgelegte Thema; im Anschluss folgt eine ca. 15-minütige Diskussion über Thema und Vortrag. Bitte beachten Sie auch die [[http://​ls11-www.cs.tu-dortmund.de/​people/​chimani/​seminarfolien.html|Hinweise]] zur Foliengestaltung! Es herrscht Anwesenheitspflicht bei allen Vorträgen.
 +
 +Voraussetzung für den Vortrag ist die vorherige Abgabe einer schriftlichen **Ausarbeitung**,​ welche 15-20 Seiten umfasst und mit **LaTeX** erstellt wird. Die Ausarbeitung wird vom Betreuer bewertet und es besteht anschließend einmalig die Gelegenheit,​ die Ausarbeitung zu überarbeiten. Mangelhafte Ausarbeitungen und 1:​1-Übersetzungen sowie mangelhafte Vorträge führen zum Nicht-Bestehen des Seminars. Auch nicht rechtzeitig abgegebene Ausarbeitungen können zum Nicht-Bestehen führen. ​
 +
 +Vorlage für die Ausarbeitung:​ {{:​teaching:​ausarbeitung-ae2013.zip|[.zip-Archiv]}}
 +
 +===== Termine =====
 + 
 +Vorbesprechung und Themenvergabe:​ Mittwoch, der **10.04.2013** um 11:15 Uhr in OH14, Raum 202 (Seminarraum des LS11). ​
 +
 +Weitere Termine: ​
 +
 +| Abgabe des Ausarbeitungskonzepts ​               | **17.06.** |
 +| Abgabe der Ausarbeitung ​                        | **24.06.** |
 +| Abgabe der Ausarbeitung (Überarbeitete Version) | **01.07.** |
 +| Abgabe der Präsentationsfolien (Aufbau) ​        | **08.07.** |
 +| Abgabe der Präsentationsfolien (Final) ​         | **15.07.** |
 +| Vorträge ​                                       | **22./​23.07.** in Raum 202, OH14 |
 +
 +===== Ansprechpartner =====
 +
 +Bei Fragen zu dieser Veranstaltung wenden Sie sich bitte an [[staff:​mutzel|Petra Mutzel]].
  
 
Last modified: 2015-09-11 13:41 (external edit)
DokuWikiRSS-Feed