Fakultät für Informatik - Technische Universität München Lehrstuhl für Effiziente Algorithmen

Zusammenfassung

Algorithm Engineering hat sich in jüngster Zeit als eigenständiges Teilgebiet der Algorithmik etabliert. Die klassische Algorithmik konzentriert sich hauptsächlich auf theoretische Analysen unter oft stark vereinfachenden, unrealistischen Voraussetzungen. Im Algorithm Engineering versucht man dagegen praxisrelevante Aspekte soweit wie möglich bei dem Entwurf, der Implementierung und der Analyse von Algorithmen zu berücksichtigen. QuickSort ist zum Beispiel in der Praxis häufig effizienter als seine asymptotisch besseren Konkurrenten. Man will nun einerseits verstehen, warum bestimmte Algorithmen in der Praxis besonders gut sind, andererseits aber auch die Erkenntnisse in den Entwurf von praktisch guten Algorithmen einfließen lassen. Dabei werden Algorithmen stets nicht nur theoretisch analysiert, sondern auch durch Experimente auf ihr Praxisverhalten untersucht. Wichtige Aspekte im Algorithm Engineering sind dabei zum Beispiel:

• Verwendung von realistischeren Maschinenmodellen bei der Analyse von Algorithmen, z.B. Speicherhierarchien im Gegensatz zur einfachen RAM
• Experimentelle Analyse von Algorithmen
• Algorithmendesign unter praktischen Gesichtspunkten (Flexibilität, Robustheit, Einfachheit, usw.)
• Analyse von Algorithmen unter realistischen Eingabemodellen

Im Hauptseminar sollen die Konzepte des Algorithm Engineering am Beispiel von grundlegenden Algorithmen und Datenstrukturen wie z.B. Sortieren, einfachen Graphenalgorithmen oder Priority Queues erarbeitet werden. Da es noch kein Buch zu diesem Thema gibt, basieren die einzelnen Themen in der Regel auf aktuellen Forschungsarbeiten. Wegen der interessanten Kombination aus Theorie und Praxis bieten sich einige der Themen auch als Anknüpfungspunkt für Bachelor- oder Diplomarbeiten an.

Themenliste:

Themenliste[pdf]

• External Memory Algorithms
  Einführung External-Memory-Modelle, Breitensuche mit sublinearem I/O
  [Vit01], [MM02]
• External Memory Graph Algorithms
  Überblick, SSSP, MST
  [KM02], [MZ03]
• Cache-Aware and Cache-Oblivious Algorithms
  Cache-sensitive Algorithmen, vergleichende Studie von Cache-Aware und Cache-Oblivious Suchbäumen
  [Kum02], [LFN00]
• Engineering Priority Queues
  Priority Queues in der Praxis
  [San99], [DKMS04]
• Distributed Algorithm Engineering
  Verteilte Algorithmen, Beispiel Sortieren
  [SZ00], [CC05]
• Engineering Sorting Algorithms
  Cache-Effizientes und Externes Sortieren
  [SW04]
• Engineering String Algorithms
  Suffix Arrays, Linearzeitkonstruktion von Suffix Arrays, Indizierung von DNA Sequenenzen
  [KS03], [HLS+04]
• Experimental Analysis of Algorithms
  Design, Auswertung und Aufbereitung von experimentellen Algorithmenanalysen
  [Joh02], [San00]
• Dynamic Graph Algorithms
  Dynamische Graph-Algorithmen, Implementierungen und Evaluation
  [Zar00], [ACI97]
• Shortest Path Computations in Road Networks
  Varianten von Shortest-Path-Problemen mit praktischer Relevanz, Design, Analyse und experimentelle Evaluation
  [GW05], [Shi99]
• Parameterized Complexity
  Parmeterisierte Komplexitätsanalyse und praktische Aspekte
  [Fel02]
• Smoothed Analysis of Algorithms
  Einführung in die Smoothed Analysis
  [ST02]

Anmeldung

• Name, Vorname
• Studiengang und Studienfach
• Semester
• E-Mail (nur Adressen @in.tum.de)
• bevorzugtes Thema

Vorbesprechung

Termine und Betreuer

Hinweise

Ein Schein für die erfolgreiche Teilnahme am Proseminar wird vergeben, wenn folgende Leistungen erbracht worden sind (die Gesamtnote setzt sich aus gewichteten Einzelnoten zusammen):

Ablauf der Vorbereitung

Der Vortrag und die Ausarbeitung müssen mit dem Betreuer abgesprochen werden. Hierzu sind nachfolgende Terminvorgaben bindend (soweit nicht anders mit dem Betreuer abgestimmt). Werden die Termine nicht eingehalten, führt dies zur Streichung des Vortrags und zum Nichtbestehen des Seminars:

Hinweise zur Anfertigung einer Seminararbeit

	Die Seminararbeiten werden nach der letzten Seminarveranstaltung online zur Verfügung gestellt. Damit eine einheitliche Form erzielt wird, müssen alle Ausarbeitungen mit dem Textsatzsystem LaTeX erstellt werden. Hierzu sind folgende Richtlinien zu beachten:
	Es ist der LNCS-Style (die Datei llncs.cls) des Springer-Verlages zu verwenden. Der folgende Rahmen ist zu verwenden (seminararbeit.tex). Dabei dürfen die Seitengröße und der Font nicht verändert werden. Ein Beispiel kann in der Datei example.tex gefunden werden (das Bild example.eps wird eingebunden) Die Ausarbeitung soll auf die verwendete Literatur verweisen, diese Literatur ist mit BibTeX zu verwalten und in einer eigenen Datei zu speichern (hier die zum Beispiel gehörende Datei: example.bib).
	Bei Fragen zu LaTeX sei einerseits auf die folgenden Links hingewiesen, ferner kann auch der Betreuer um Hilfestellungen bzw. Literaturangaben gebeten werden:
	LaTeX Kochbuch RBG-Seite zu LaTeX
	Eine weitere Anleitung zur Erstellung von Ausarbeitungen finden sie hier.
	Informationen zur Installation von LaTeX unter Windows finden Sie hier.

Hinweise zur Gestaltung der Vorträge

	Wer seine Folien mit LaTeX erstellen möchte findet hier einige Hinweise (einschließlich Rahmen-Datei als Vorlage)

Literatur