Algorithm Engineering
- Typ:
- Lehrstuhl: Lehrstuhl Prof. Sanders
- Ort: SR 236
- Zeit: Mi 15.45 - 17.15 Uhr
- Beginn: 26.04.2006
- Dozent: P. Sanders
- SWS: 2
- LVNr.: 24624
- Prüfung: Prüfbar
-
Hinweis:
Voraussetzung: Vordiplom, Algorithmentechnik.
Vertiefungsgebiete: Algorithmentechnik
Algorithm Engineering für grundlegende Datenstrukturen und Algorithmen
Auf den ersten Blick gleichen die Themen dieser Vorlesung denen einer
"kanonischen" Algorithmenvorlesung. Allerdings geht es hier nicht um
die Vermittlung der Grundideen, sondern darum was man wirklich
tut um größtmögliche Effizienz zu erreichen. 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 Weiterentwicklung dieser Techniken lassen sich solche Lücken zwischen Theorie und Praxis aber manchmal überwinden.
Ergebnis der Vorlesungsevaluation.
Themenliste
- Algorithm Engineering: Was ist das, grundlegende Methodologie
- Repräsentation von Folgen: Felder, verkettete Listen und das war's?
- Sortieren: cache-effizient, befehlsparallel, extern
- Prioritätslisten: cache-effizient, Ausnutzung ganzzahliger Schlüssel
- Suchbäume: cache-oblivious, Ausnutzung ganzzahliger Schlüssel
- Graphen
- kürzeste Wege
- minimale Spannbäume
- Strings: Konstruktion von Suffix Arrays
Folien
- Kurzfassung aus einem Sommerkurs im Jahre 2004.
- Folien aus der Vorlesung WS 2004/2005.
- Intro Folien
- Listen, Arrays. Sortieren: Quick sort, sample sort, multiway merge sort, parallele Platten,... Folien
- Datenstrukturen: Prioritätslisten, Suchbäume, Hashtabellen. Folien
- Beschleunigungstechniken für Routenplanung: Überblick , Highway Hierarchies
- Minimale Spannbäume, Daten darstellen,...
- String- und Suffix-Sortierung
Weitere Unterlagen
- Ein Buchmanuskript.
- Manuskript und Papier zu super scalar sample sort
- Externes Sortieren: Papier zu asynchronous parallel disk sorting
- Priority Queues und Speicherhierarchien
- Adressable Priority Queues (Manuskript), Integer Search Trees
- String- und Suffix-Sortierung Folien. Der DC3 Algorithmus (Abschnitte 1-3). Externe Implementierung.