Fakultät für Informatik
Lehrstuhl für Algorithm Engineering (Ls11)
Home Kontakt Deutsch English
Algorithm Engineering

Algorithm Engineering

(Spezialvorlesung 042323)

Sommersemester 2007

Prof. Dr. Petra Mutzel

Termin:   
Dienstag12:15 - 14:00OH14, E23 (bis 03.05.), Raum 304 (ab 08.05.)
Donnerstag14:15 - 16:00OH14, E23 (bis 03.05.), Raum 304 (ab 08.05.)
Beginn:03.04.2007

Siehe auch: Übungen zu Algorithm Engineering

Zugangsvoraussetzungen

Vordiplom

Kommentar

Algorithm Engineering beinhaltet das Design von Algorithmen, ihre theoretische Analyse sowie ihre experimentelle Analyse am Rechner. Dabei liegt der Schwerpunkt auf der praktischen Seite.

Die klassische Algorithmik beschränkte sich lange Zeit auf die Theorie. Viele Publikationen beschreiben die Algorithmen und Datenstrukturen unter idealen Voraussetzungen, die jedoch in der Praxis häufig nicht gegeben sind. Auch wurden zunehmend hochkomplexe Datenstrukturen verwendet, die allgemein als praktisch nicht implementierbar galten. Mit der zunehmenden Anwendung der theoretischen Ergebnisse in der Praxis merkte man, dass eine große Lücke zwischen Theorie und Praxis existiert. Das Gebiet des Algorithm Engineering soll dem entgegenwirken, indem es Algorithmen für die Praxis entwirft und analysiert, evaluiert und darauf aufbauend verbessert.

Nach einer Einführung werden spezielle ausgewählte Themen behandelt. Anhand Kürzeste-Wege-Probleme wird der typische Algorithm Engineering Kreislauf dargestellt. Einen wichtigen Themenaspekt bilden die Externspeicheralgorithmen inkl. cache-effizienter Algorithmen, denn die realen Rechenmaschinen entfernen sich zunehmend vom idealisierten von Neumann-Modell. Hierzu betrachten wir einige grundlegende Datenstrukturen sowie einfache Algorithmen für grundlegende Probleme wie z.B. Sortieren. Weitere Themen beinhalten Algorithmen für NP-schwierige kombinatorische Optimierungsprobleme aus dem Netzwerk-Design, der Bioinformatik und dem Graphenlayout. Ein Kapitel widmet sich auch dem Design von experimentellen Analysen von Algorithmen.

Schwerpunktgebiete

  • Algorithmen, Komplexitšt und formale Modelle
  • Computational Intelligence and Natural Computing
  • Intelligente Systeme

Literatur

Es gibt noch kein Buch zu diesem Thema. Zu den jeweiligen Themengebieten wird die Literatur in der Vorlesung bekannt gegeben.

Skriptausschnitte zu einigen Vorlesungen:

Folien und Vorlesungsmitschriften

Die Folien zur Vorlesung gibt es jeweils in zwei Versionen: mit 1 Folie pro Seite (zum Anschauen) und mit 6 Folien pro Seite (zum Ausdrucken).

Einführung in AE (03.04.): [1 Folie/Blatt] [6 Folien/Blatt]
Kreuzungszählen (05.04.): [1 Folie/Blatt] [6 Folien/Blatt]
Kreuzungsminimierung (10.04.): [1 Folie/Blatt] [6 Folien/Blatt]
Kombinatorische Optimierungsprobleme (12./17.04.): [1 Folie/Blatt] [6 Folien/Blatt]
Branch and Cut (19.04.): [1 Folie/Blatt] [6 Folien/Blatt]
Das Handlungsreisendenproblem (TSP) (24.04.): [1 Folie/Blatt] [6 Folien/Blatt]
Das Handlungsreisendenproblem (TSP) (Teil 2) (26.04.): [1 Folie/Blatt] [6 Folien/Blatt]
Engineering Lin-Kernighan (03.05.): [1 Folie/Blatt] [6 Folien/Blatt]
Suffix Arrays (08.05.): [1 Folie/Blatt] [6 Folien/Blatt]
Anwendung von Suffix Arrays (10.05.): [1 Folie/Blatt] [6 Folien/Blatt]
Dynamic Shortest Path (SSSP) (15.05. und 22.05): [1 Folie/Blatt] [6 Folien/Blatt]
Dynamic Shortest Path (APSP) (Teil 1) (24.05.): [1 Folie/Blatt] [6 Folien/Blatt]
Dynamic Shortest Path (APSP) (Teil 2) (29.05-05.06.): [1 Folie/Blatt] [6 Folien/Blatt]
Dynamic Shortest Path: Experimentelle Analyse (12.06.): [1 Folie/Blatt] [6 Folien/Blatt]
Sequenzen-Alignierung (Teil 1) (14.06.): [1 Folie/Blatt] [6 Folien/Blatt]
Sequenzen-Alignierung (Teil 2) (19.06.): [1 Folie/Blatt] [6 Folien/Blatt]
Sequenzen-Alignierung (Teil 3) (21.06.): [1 Folie/Blatt] [6 Folien/Blatt]
Externspeicheralgorithmen (26.06.): [1 Folie/Blatt] [6 Folien/Blatt]
Externe Array-Heaps (28.06. und 03.07.): [1 Folie/Blatt] [6 Folien/Blatt]
SPQR-Bäume (05.07.): [1 Folie/Blatt] [6 Folien/Blatt]
Non-planar Core Reduction (10.07.): [1 Folie/Blatt] [6 Folien/Blatt]
Letzte Vorlseung (12.07.): [1 Folie/Blatt] [6 Folien/Blatt]
<webmaster  ls11.cs.tu-dortmund.de>
Die Universität übernimmt keine Haftung für den Inhalt verlinkter externer Internetseiten