Prof. Dr. M. Kunde

Vorlesung (1 SWS)

In der zweiten Semesterhälfte wird die Vorlesung wöchentlich 2-stündig gelesen.

Beginn: Donnerstag, den 1. Juni 2006
17:00 - 18:30 Uhr, H1520b

Inhalt:

Behandelt werden Algorithmen für die grundlegende Problemstellung des Schedulings. Beim Scheduling (Ablaufplanung) geht es um die Zuweisung von Jobs (Aufgaben) an Betriebsmittel (etwa Prozessoren), die diese Jobs möglichst schnell bearbeiten sollen. Die Minimierung der Gesamtausführzeit in Mehrprozessorensystemen erweist sich schon für einfache Fälle als NP-schwer. Eine Lösung bieten daher Approximationsalgorithmen. Neben der Gesamtausführzeit werden weitere Optimierungskriterien (wie Verspätung usw.) in verschiedenen Parallelrechnerarchitekturen angesprochen.

Anmerkung:

Die Vorlesung ist als Ergänzung zu den Vorlesungen "Effiziente Algorithmen" oder " Approximationsalgorithmen" gedacht, kann aber auch ohne Kenntnis dieser Vorlesungen verstanden werden.

Die Vorlesung wird als Studienleistung in den Schwerpunkt- und Ergänzungskomplexen für das Gebiet "Automaten und Formale Sprachen" anerkannt.