Spezialvorlesung/Aufbaumodul
SS 2010: Algorithm Engineering
Dozent
Stefan Edelkamp
Am Fallturm 1, Raum 2.62
D-28357 Universität Bremen
Übung
Peter Kissmann
Am Fallturm 1, Raum 1.57
D-28357 Universität Bremen
Termine
Mi. 10-12 Uhr (V) Do. 12-14 (Ü), Raum 1.50 (TZI Fallturm 1)
Modul
602 (Algorithmen- und Komplexitätstheorie), 2+2 SWS, 6 ECTS
Thema
Im Mittelpunkt von Algorithm Engineering steht ein von
falsifizierbaren Hypothesen getriebener Kreislauf
aus Entwurf, Analyse, Implementierung, und experimenteller Bewertung
von praktikablen Algorithmen.
Realistische Modelle, für
Algorithmenbibliotheken und Sammlungen
realer Eingabeinstanzen erlauben eine zustzliche Kopplung an Anwendungen.
Auf den ersten Blick gleichen die Themen dieser Vorlesung denen einer
"kanonischen"
Algorithmenvorlesung. Allerdings geht es hier nicht um die Vermittlung
der Grundideen, sondern um größtmögliche
praktische Effizienz. Erstaunlicherweise ist das immer
noch ein aktuelles
Forschungsthema. Dafür gibt es zwei wichtige Gründe:
-
Reale Maschinen haben sich weit vom einfachen von Neumann-Modell
entfernt. Insbesondere
Speicherhierarchien und parallele Befehlsausführung machen das bloße
Zählen von Befehlen ungenau.
- Die Algorithmentheorie hat faszinierende Techniken erfunden, die
z.T. als nicht implementierbar gelten.
Durch die Weiterentwicklung dieser Techniken lassen sich solche
Lücke zwischen Theorie und Praxis
manchmal überwinden.
Die Vorlesung ist ausgerichtet auf Algorithmen für
moderne PC-Architekturen mit mehreren Berechnungseinheiten,
hierarchisch organisiertem Prozessorcaches und
und externe Medien, wie riesige Festplatten und
Flashspeicher.
Inhalt
- Algorithm Engineering: Ansatz, grundlegende Methodologie
- Schnelles Sortieren mit Quick- und Weak-Heapsort
- Cache- und Worst-Case Effiziente Prioritätslisten
- Perfekte Hash-Funktionen zur Kompression von Daten
- Strings: Konstruktion von Suffix Bumen und Arrays
- Begrenzter Hauptspeicher: Festplattenalgorithmen
- Externe Such- und Spannbume, Graphsuche
- Flashspeicheralgorithmen: Schnelles Lesen auf der Solid-State-Disk
- GPU-Algorithmen: Parallele Graphsuche auf der Grafikkarte
Literatur
Aktuelle Veröffentlichung in Konferenzbänden und Zeitschriften der KI, der Verifikation und des Algorithmen Engineerings.
Protagonisten der Szene: Ulrich Meyer (Univ. Frankfurt), Peter Sanders (Univ. Karlsruhe), Lars Arge (Univ. Aarhus), Kurt Mehlhorn (MPI Saarbrücken), Eric Demaine (MIT), Lubos Brim (Brno), Eric Hansen (Missisippi State Univ.), ...