Donnerstag, 11:00 - 12:30 Uhr, H1510

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

Beginn: Donnerstag, den 2. Juni 2005

Inhalt:

Behandelt werden Algorithmen für zwei grundlegende Problemstellungen: Scheduling und Bin Packing. Beim Scheduling (Ablaufplanung) geht es um die Zuweisung von Jobs (Aufgaben) an Betriebsmittel (etwa Prozessoren), die diese Jobs möglichst schnell bearbeiten sollen. In Mehrprozessorensystemen erweist sich dieses Problem schon für einfache Fälle als NP- schwer. Das gleiche gilt für das verwandte Bin Packing Problem. Eine Lösung bieten daher Approximationsalgorithmen.

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.