Uni Dortmund, Informatik 2: Vorlesung EA

Effiziente Algorithmen

Stammvorlesung 4V + 2 Ü, Sommersemester 2000

Susanne Albers

[Termine] [Zusammenfassung] [Skript] [Übungen]

Termine

	Wann?	Wo?	Wer?
Vorlesungen:	Mo 10 - 12	HG II, HS 4	Susanne Albers
	Do 16 - 18	HG II, HS 5	Susanne Albers
Übungen:	Mo 8 - 10	GB IV, 318	Thomas Jansen
	Mo 12 - 14	GB V, 420	Hubert Wagner
	Mo 14 - 16	GB IV, 113	Thomas Jansen
	Do 10 - 12	ZB C, links	Hubert Wagner

Effiziente Algorithmen werden in fast allen Bereichen der Informatik benötigt. Leider gibt es kein Patentrezept, wie man ein gegebenes Problem schnell und gut lösen kann. Zentrales Ziel dieser Vorlesung über effiziente Algorithmen ist es, Techniken zum Entwurf effizienter Algorithmen vorzustellen und das Verhalten dieser Algorithmen zu analysieren. Dieses geschieht anhand von ausgewählten Beispielproblemen, an denen man typische Methoden des Algorithmenentwurfs aufzeigen kann. Genauso wichtig wie der Algorithmenentwurf sind natürlich auch Korrektheitsbeweise der Algorithmen und Laufzeitanalysen.

Natürlich kann nicht erwartet werden, dass in der beruflichen Praxis exakt genau die Probleme auftreten werden, die in der Vorlesung behandelt werden sollen. Wer jedoch über das entsprechende Handwerkszeug verfügt und genügend ähnliche Probleme und deren Lösung gesehen hat, wird diese praktischen Probleme mit großer Erfolgsaussicht bearbeiten könen. Behandelt werden sollen in dieser Vorlesung insbesondere Algorithmen für Probleme auf Graphen wie Zusammenhangsprobleme, kürzeste Wege, minimale Spannbäme, Flüsse in Netzwerken und die Berechnung maximaler Matchings.

Weitere Probleme von praktischer Relevanz sind Hashing, die Berechnung von Potenzen, Primzahltests für sehr große Zahlen sowie Probleme aus der algorithmischen Geometrie, um nur einige zu nennen. Für andere Probleme, wie das Rucksackproblem und das Traveling Salesman Problem, die vermutlich nicht effizient lösbar sind, werden Approximationsverfahren vorgestellt.

Literatur:
Zur Vorlesung wird ein Skript verfügbar sein. Darüberhinaus empfehlen wir die folgenden Bücher als vertiefende Lektüre.

R.K. Ahuja, T.L. Magnanti, J.B. Orlin. Network Flows: Theory, Algorithms and Applications, Prentice Hall, 1993.
T.H. Cormen, C.E. Leiserson, R.L. Rivest. Introduction to Algorithms, MIT Press, 1990.
T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, BI, 1990.

Skript

Grundlage der Vorlesung ist ein Vorlesungsskript, das am 13.04.2000 in der Vorlesung erworben werden konnte. Wer auf diese Art nicht zu einem Skript gekommen ist, kann sich ein Exemplar mittels lprdoc ausdrucken. Der Dokumentname ist alg-ss00.

Übungen

In der Vorlesung wurde jeweils am Montag ein Übungsblatt ausgegeben. Bearbeitungen der Übungsaufgaben waren bis zum folgenden Montag, 16 Uhr, abzugeben.