Home  | Impressum | Sitemap | KIT

Algorithm Engineering

Algorithm Engineering
Typ: Vorlesung
Lehrstuhl: Prof. Dr. Peter Sanders
Ort: SR 236, Geb. 50.34
Zeit:

Dienstag 11.30 bis 13.00 Uhr
Donnerstag 15.45 bis 17.15 Uhr

Beginn: 17.04.2007
Dozent: P. Sanders, R. Dementiev
SWS: 3
LVNr.: 24624
Prüfung:

ja

Hinweis: Voraussetzung: Vordiplom, Algorithmentechnik. Vertiefungsgebiete: Algorithmentechnik

Ankündigung

Achtung: die Vorlesung am Dienstag 8. Mai fällt aus.

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.

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
  • Algorithmen und Datenstrukturen für große Datenmengen
    • Stacks, Queues, Listen
    • Sortieren
    • Prioritätslisten
    • Suchbäume (B-Trees, buffer trees)
    • minimale Spannbäume
    • Breitensuche
    • Graphenfärbung
    • Konstruktion von Suffix Arrays
  • Algorithmen-Bibliotheken