====== Seminar Algorithm Engineering (WiSe 2010/11) ====== | Veranstalterin | [[staff:mutzel|Prof. Dr. Petra Mutzel]] | | Modul | Diplom, [[http://www.cs.tu-dortmund.de/nps/de/Studium/Ordnungen_Handbuecher_Beschluesse/Modulhandbuecher/Modulhandbuch_Master_Informatik/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=93251&moduleCall=webInfo&publishConfFile=webInfo&publishSubDir=veranstaltung|041404]] | | Forschungsbereich | Algorithmen und Komplexität | | SWS | 2 | | Max. Teilnehmer | 12 | ===== Inhalt und Themen ===== 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 Themen aus dem Bereich des Algorithm Engineerings, wie z.B. * Kürzeste-Wege Suche in Straßennetzwerken * Minimale Spannbäume * NP-schwere Optimierungsprobleme wie Vehicle Routing und TSP * Suffix-Arrays * Fehlertolerante Algorithmen ===== Anmeldung ===== Die Anmeldefrist ist bereits abgelaufen. ===== 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. Alle Teilnehmer halten gegen 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! Voraussetzung für den Vortrag ist die vorherige Abgabe einer schriftlichen **Ausarbeitung**, welche 15-20 Seiten umfasst und mit **LaTeX** erstellt wird. Mangelhafte Ausarbeitungen führen zum Nicht-Bestehen des Seminars. ===== Termine ===== | Vorbesprechung und Themenvergabe | 13.10.2010 | 10:15 Uhr | OH14, Raum 202 | {{:teaching:vorbesprechung-seminar-ae-2010.pdf|Folien der Vorbesprechung}} | | **Abgabe der Ausarbeitung** | **29.11.2010** | | | | Abgabe der Präsentationsfolien | eine Woche vor dem Vortrag | | | | Beginn der Vorträge | 05.01.2011 | 10:15 Uhr | OH14, Raum 202 | ==== Die Vorträge ==== ^ Nr. ^ Datum ^ Vortragender ^ Thema ^ Betreuer ^ | 1 | 05.01. | Dawid Kopetzki | [[http://dx.doi.org/10.1007/978-3-642-13193-6_5|Space-Efficient SHARC-Routing]] | [[staff/wong|Hoi-Ming Wong]] | | 2 | 05.01. | Finn Siebert | [[http://dx.doi.org/10.1007/978-3-642-13193-6_15|Time-Dependent Contraction Hierarchies and Approximation]] | [[staff/gutwenger|Dr. Carsten Gutwenger]] | | 3 | 12.01. | Henning Garus | [[http://dx.doi.org/10.1007/978-3-642-13193-6_9|Practical Compressed Suffix Trees]] | [[staff/klein|Karsten Klein]] | | 4 | 19.01. | Jan Kleemann | [[http://dx.doi.org/10.1007/978-3-642-13193-6_35|Experiments on Union-Find Algorithms for the Disjoint-Set Data Structure]] | [[staff/zey|Bernd Zey]] | | 5 | 19.01. | Georg von der Brüggen | [[http://dx.doi.org/10.1007/978-3-642-13193-6_41|Geometric Minimum Spanning Trees with GeoFilterKruskal]] | [[staff/gutwenger|Dr. Carsten Gutwenger]] | | 6 | 26.01. | Manuel Allhoff | [[http://dx.doi.org/10.1007/978-3-642-13193-6_10|Maximum Cliques in Protein Comparison]] | [[staff/kriege|Nils Kriege]] | | 7 | 26.01. | Daniel Noack | [[http://dx.doi.org/10.1007/978-3-642-13193-6_34|Data Structures Resilient to Memory Faults: An Experimental Study of Dictionaries]] | [[staff/mutzel|Prof. Dr. Petra Mutzel]] | ===== Ansprechpartner ===== Bei Fragen zu dieser Veranstaltung wenden Sie sich bitte an [[staff:gutwenger|Carsten Gutwenger]].