====== Algorithm Engineering (SoSe 2010) ====== | Veranstalter | **[[staff:gutwenger|Carsten Gutwenger]]** | | Modul | **[[http://www.cs.tu-dortmund.de/nps/de/Studium/Ordnungen_Handbuecher_Beschluesse/Modulhandbuecher/Modulhandbuch_Master_Informatik/Vertiefungsmodule/Forschungsbereich_Algorithmen_und_Komplexitaet/INF-MSc-601.pdf|INF-Msc-601]]** (Master Informatik / Angewandte Informatik) | | Veranstaltungsnummer: | **[[https://www.lsf.tu-dortmund.de/qisserver/rds?state=verpublish&status=init&vmfile=no&publishid=87929&moduleCall=webInfo&publishConfFile=webInfo&publishSubDir=veranstaltung|042601]]** | | EWS | [[https://ews.tu-dortmund.de/cseGui/MainBrowser.jsp?-Main=PersonalDesktop&PRTLT_ACT=Main&SelAct=1&Lect=lsf-87929|Algorithm Engineering Arbeitsraum]] | | Forschungsbereich | Algorithmen und Komplexität | | Schwerpunktgebiete | Algorithmen, Komplexität und formale Modelle | | | Computational Intelligence and Natural Computing | | | Intelligente Systeme | | SWS | 2 | Siehe auch: Webseite zur [[staff:gutwenger:ae-ueb-2010|Übung zu Algorithm Engineering]] ===== Zeit und Ort ===== * **Vorlesung:** Dienstag, 14:15-15:45 Uhr, OH14, Raum 104 * **[[staff:gutwenger:ae-ueb-2010|Übung:]]** Mittwoch, 10:15-11:45 Uhr, OH14, Raum 304 ===== Inhalt der Vorlesung ===== 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 dieser Vorlesung wird eine Einführung in die Thematik des Algorithm Engineering gegeben und die dabei verwendeten Techniken vorgestellt. An besonders gelungenen Beispielen wird der typische Kreislauf des Algorithm Engineering dargestellt. Diese beinhalten u.a. Cache-effiziente Externspeicheralgorithmen, sowie Algorithmen für Mehrkernprozessoren und NP-schwierige kombinatorische Optimierungsprobleme. ==== Themen ==== * Einführung in die Grundlagen des Algorithm Engineering * Externspeicheralgorithmen * Cache-effiziente Algorithmen * Multicore-Algorithmen * Algorithm Engineering für NP-schwere kombinatorische Optimierungsprobleme * Anwendungsfall: Kürzeste Wege Suche in Straßennetzwerken * Anwendungsfall: Graph Drawing für große Graphen ==== Zugangsvoraussetzungen ==== * Kenntnisse der Inhalte des Basismoduls //[[http://www.cs.tu-dortmund.de/nps/de/Studium/Ordnungen_Handbuecher_Beschluesse/Modulhandbuecher/Modulhandbuch_Master_Angewandte_Informatik/Basismodule/Forschungsbereich_Algorithmen_und_Komplexitaet/Modul-INF-MA-241-Algorithmen-und-Datenstrukturen.pdf|Algorithmen und Datenstrukturen]]// (Master-Studiengang) * Vordiplom (Diplom-Studiengang) ===== Prüfungsmodalitäten, Leistungsnachweise ===== ==== Diplomstudiengang ==== * Mündliche Fachprüfung * über 2VO + 2 UE, 6LP * mündliche Prüfung über den Stoff der Vorlesung __und__ Übung * Leistungsnachweis * über 2VO + 2UE, 6LP * regelmäßige, aktive Teilnahme an den Übungen ==== Masterstudiengang ==== * Modulprüfung * über 2VO + 2UE, 6LP * regelmäßige, aktive Teilnahme an den Übungen * mündliche Prüfung über den Stoff der Vorlesung __und__ Übung ===== Materialien zur Vorlesung ===== * Die Vorlesungsfolien und weitere Materialien zur Vorlesung werden im **[[https://ews.tu-dortmund.de/cseGui/MainBrowser.jsp?-Main=Lectures&PRTLT_ACT=Main&SelAct=1&Lect=lsf-87929|EWS-Arbeitsraum der Vorlesung]]** zur Verfügung gestellt. Um diesen zu nutzen, müsst ihr euch über [[https://ews.tu-dortmund.de/cseGui/MainBrowser.jsp|EWS]] anmelden. Bei Fragen bzw. Problemen bitte bei mir melden! * **[[ae-2010-ov|Überblick]]** über die einzelnen Vorlesungen mit Links auf relevante Literatur und Webseiten ===== Literatur und Links ===== ==== Allgemeine Literatur zu Algorithm Engineering ==== * [[http://dx.doi.org/10.1007/3-540-36574-5|Algorithms for Memory Hierarchies]]\\ //Ulrich Meyer, Peter Sanders, Jop Sibeyn//\\ Lecture Notes in Computer Science 2625, Springer-Verlag, 2003 * [[http://dx.doi.org/10.1007/978-3-540-77978-0| Algorithms and Data Structures: The Basic Toolbox]]\\ //Kurt Mehlhorn, Peter Sanders//\\ Springer Verlag, 2008 * [[http://dx.doi.org/10.1007/3-540-36383-1_1|Algorithm Engineering for Parallel Computation]]\\ //David A. Bader, Bernard M. E. Moret and Peter Sanders//\\ In: Lecture Notes in Computer Science 2547, Springer-Verlag, 2002, 1-23 ==== Konferenzen ==== Links und weiterführende Informationen zu Algorithm Engineering Konferenzen findet man [[staff:gutwenger:ae|hier]].