Die Vorbesprechung und die Vergabe der Vorträge findet in der ersten Veranstaltung im WS 98/99 statt. Interessierte Studierende können sich bereits vor Beginn des Semesters bei den Veranstaltern informieren und in die geplanten Vortragsthemen Einblick nehmen.
Um die verschiedenen Aspekte derartiger Fragestellungen besser untersuchen zu können, wurden in der Literatur verschiedene Modelle vorgestellt. Die bekanntesten unter ihnen sind unter den Schlagworten
zu finden. In der Vorlesung "Komplexität und Spiele" sollen diese Modelle vorgestellt und einige auf ihnen basierende Komplexitätsklassen anhand von Beispielen (wie z.B. Go oder das verallgemeinerte Geographiespiel) diskutiert werden.
Graph-Algorithmen:
Ein Standardproblem bei der
Planung von Netzwerken ist die Berechnung eines minimal erzeugenden
Baumes (minimal spanning tree) für gewichtete Graphen. Durch Randomisierung
kann dieses Problem auf einfache Weise gelöst werden. ([MR95], Kapitel
10.3)
Ein weiteres Thema sind Irrfahrten
(random walks) in Graphen, bei denen durch eine zufällige Auswahl
von Kanten ein unbekannter Graph möglichst schnell durchsucht werden
soll. Eine Erweiterung in Richtung auf schnell mischende Markov-Ketten,
eine elegante Technik um große Zustandsräume zu untersuchen,
ist möglich. ([MR95], Kapitel 6)
Online-Algorithmen:
Beim Paging-Problem
geht es darum, Datenblöcke so in der Speicherhierarchie eines Prozessors
abzulegen, daß er möglichst schnell auf sie zugreifen kann.
Wir betrachten den Fall eines großen Hauptspeichers mit langsamem
Zugriff kombiniert mit einem schnellen Cache, der allerdings nur Platz
für höchstens k Blöcke bietet. Eine Caching-Strategie
legt fest, welche Datenblöcke zu jedem Zeitpunkt im Cache gehalten
werden. Dabei unterscheidet man zwischen off-line-Verfahren, die
die gesamte Datenzugriffssequenz vorab benötigen, und on-line-Verfahren,
die jeweils auf eine neue Datenanfrage hin entscheiden, was im Cache gehalten
wird, ohne nachfolgende Anfragen zu kennen. Für den on-line Fall gibt
es keine deterministischen Paging-Strategien mit einem guten worst-case
Verhalten. Randomisiert kann man dieses Problem jedoch nachweisbar besser
lösen. ([MR95], Kapitel 13.1-3)
(II) Je nach Teilnehmerzahl und Interesse können noch weitere Aspekte und Beispiele von Algorithmen und Randomisierung behandelt werden, etwa die Frage, wie sich Lösungen bestimmter Optimierungsprobleme verhalten, wenn die Eingabedaten zufällig sind. Ein Beispiel ist das
Bin Packing-Problem:
Gegeben sei eine Menge gleicher Behälter mit einer gewissen Kapazität
und eine Menge von n Elementen mit Volumen X1,
X2, ..., Xn. Aufgabe ist es, diese
Elemente in möglichst wenigen Behältern unterzubringen. Die exakte
Berechnung der Minimalzahl L ist NP-schwierig, aber es gibt verschiedene
Approximationsalgorithmen (offline und online), welche eine Einteilung
in L' Gruppen liefern, so daß der Quotient L'/L bestimmte
Schranken nicht überschreitet. ([H97], Kapitel 2.1-2)
Schließlich betrachten
wir die Zahlen L und L' im Falle von zufälligen und
unabhängigen Eingabedaten Xi. Mithilfe einer
sehr eleganten Methode von M. Talagrand kann man zeigen, daß L/n
und L'/n bei großem n nahezu konstant sind. Talagrands
Methode kann man auf viele Probleme der kombinatorischen Optimierung anwenden.
([H97], Kapitel 2.3; [S97], Kapitel 6; [D96]).
[MR95] R. Motwani, P. Raghavan. Randomized Algorithms.
Cambridge University Press, 1995
[H97] D. Hochbaum (Ed.). Approximation Algorithms for NP-Hard
Problems. PWS Publishing Company, 1997
[S97] M. Steele. Probability Theory and Combinatorial Optimization.
SIAM, 1997
[D96] L. Dümbgen. Isoperimetrie und Konzentrationsungleichungen
für Wahrscheinlichkeitsmaße. Manuskript, 1996
sowie verschiedene Zeitschriftenartikel.
Freitags, 10-12 Uhr, Hörsaal 1 der Seefahrtschule
Nähere Informationen können sind vorab erhältlich bei Schindelhauer.
