[TZI]  [Computer Science Department]  [University of Bremen] 

Vorlesungsfolien

Übungen

Cuda

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.), ...

Algorithm Engineering

Stefan Edelkamp (edelkamp@tzi.de)