Lehrstuhl für Algorithm Engineering

LS11

Lehrgebietsvorstellung 29. Juni 2007

Karsten Klein

Die Professoren…

Günter Rudolph Petra Mutzel Jan Vahrenhold

Dezember 2004: Lehrstuhl für Algorithm Engineering(Nachfolge des Lehrstuhls für Systemanalyse, Prof. Schwefel)

• Design,• theoretische Analyse,• Implementierung, und• experimentelle Evaluationvon Algorithmen und Datenstrukturen

Algorithm Engineering

anwendungs-orientiert

Forschungsinteressen

• Algorithmen und Datenstrukturen• Graphenalgorithmen• Kombinatorische Optimierung

Traditionelle Algorithmik

• Entwurf für einfache Problem- und Maschinenmodelle• Hauptergebnis: beweisbare Leistungsgarantien für alle

möglichen Eingaben• → Elegante, zeitlose, an viele konkreten Anwendungen

anpassbare Lösungen• → Zuverlässig hohe Effizienz auch für zur Implementie-

rungszeit unbekannte Typen von Eingaben

Große Lücke zwischen Theorie und Praxis!

Vorstellung: Anwender greifen Ergebnisse auf, Implementierung, Einbau in Anwendungen

Klappt meist nicht!

Traditionelle Algorithmik

Abstrakte Modelle

Entwurf

Analyse

Leistungsgarantien

Implementierung

Anwendungen

Alg

orith

men

theo

rie

Beweisbare Leistungsgarantie? • Asympt. Worst-Case• Teilweise SEHR hohe versteckte Konstanten• Systemcharakteristika beeinflussen Performance• Eingabecharakteristika beeinflussen Performance

Praktisches Verhalten so schwer beschreibbar• Simplex-Algorithmus: Theoretisch exponentiell, praktisch

„gutmütig“• Auch „Crossover Point“ für Algorithmen

Traditionelle Algorithmik

70er/80er Jahre: Häufig gar keine Implementierung, Gefahr der Veröffentlichung inkorrekter Algorithmen

CPU CacheInternerSpeicher

(MainMemory)

Extern-speicher

Secondary Memory

Faktor 100 schneller als

Faktor 1000-106 schneller als

Hierarchisches Speichermodell moderner Computer

Problem ist aktueller denn je, denn

• Geschwindigkeit der Prozessoren verbessert sich zwischen 30%-50% im Jahr;

• Geschwindigkeit des Speichers nur um 7%-10% pro Jahr

• „One of the few resources increasing faster than the speed of computer hardware is the amount of data to be processed.“

• Einfluss von System- und Eingabecharakteristika evaluieren und in Entwurf berücksichtigen

• Praktisch schnelle Algorithmen entwerfen

• Algorithmen und Datenstrukturen für Praxis vereinfachen

Algorithm Engineering

Algorithm EngineeringRealistische

Modelle

Entwurf

Analyse

Leistungsgarantien

Implementierung

Alg.-Bibliotheken

Experimente

RealeEingaben

1

2

3 4

5

Anw

endungen

Anwendungsorientierung?

Anwendungsbereiche

• Automatisches Zeichnen von Graphen:Übersichtliche Darstellung von Informationen

• Netzwerkdesign: Aufwandsoptimierung und Versorgungssicherheit in Kommunikation oder Energieversorgung

• Routenplanung: Speditionen

• Bioinformatik: Schnelle/optimale Algorithmen und Visualisierung

Anwendungsbereiche

• Automatisches Zeichnen von Graphen– Kreuzungsminimierung– Planare Zeichenverfahren

Viele Probleme sind NP-schwer

Diplomarbeit (MPII)

Ein Layoutverfahren für biologische Netzwerke

Der chemische Strukturraum: PG 504

Anwendungsbereiche• Automatisches Zeichnen von Graphen

– Kreuzungsminimierung– Planare Zeichenverfahren

• Molekulare Bioinformatik– Sequenzanalyse (Sequenzenalignierung)– Proteinanalyse (Suffix Arrays, Graphprobleme)

Anwendungsbereiche• Automatisches Zeichnen von Graphen

– Kreuzungsminimierung– Planare Zeichenverfahren

• Molekulare Bioinformatik– Sequenzanalyse (Sequenzenalignierung)– Proteinanalyse (Suffix Arrays, Graphprobleme)

• Netzwerkdesign

Ausbau eines Fernwärmesystems

Anwendungsbereiche• Automatisches Zeichnen von Graphen

– Kreuzungsminimierung– Planare Zeichenverfahren

• Molekulare Bioinformatik– Sequenzanalyse (Sequenzenalignierung)– Proteinanalyse (Suffix Arrays, Graphprobleme)

• Netzwerkdesign

Diplomarbeitsthemen

• Routenplanung

• Externspeicheralgorithmen: PG 503 Xaver: Algorithm Engineering XXL(Auch: Vahrenhold)

• Algorithmische Geometrie (Vahrenhold)

Weitere Themen

Algorithmische Geometrie & Externspeicher

Simulation von Flussnetzwerken auf hochauflösenden dig. Geländemodellen zur Überschwemmungsvorhersage

• Seminar Algorithm Engineering:Vorbesprechung Mittwoch 11.07, 14Uhr

LVAs im WS 07/08

• Vorlesung Automatisches Zeichnen von Graphen

• VO Mo, Di 12-14, 4VO+2Ü

• PG 512 Smart Cell: Clevere Algorithmen für den Cell-Prozessor

Weitere Vorlesungen…

• Algorithmische Geometrie• Algorithm Engineering• Graphenalgorithmen• …

Schwerpunktgebiete:• Algorithmen und Komplexität (4)• Computational Intelligence (6)• Intelligente Systeme (7)

Vielen Dank! Bis Bald!