Es geht um effiziente parallele Algorithmen zur Behandlung von
kombinatorischen Optimierungsproblemen. Zum Entwurf und zur
Analyse werden überwiegend probabilistische Methoden verwendet.
-
Umgang mit (vollständig) unabhängigen und k-weise unabhängigen
Zufallsvariablen über endlichen Wahrscheinlichkeitsräumen.
-
Analyse einfacher randomisierter kombinatorischer Algorithmen.
-
Verständnis grundlegender Derandomisierungstechniken.
-
Verständnis des Zusammenhangs zwischen Unabhängigkeit der
verwendeten Zufallsbits und der Größe des Suchraumes, sowie der
damit verbundenen algorithmischen Möglichkeiten.
-
Verständnis von automatenbasierten Derandomisierungstechniken.
-
Überblick über die Anwendung auf kombinatorische
Optimierungsprobleme.
-
Einblicke in die Implementierung paralleler Algorithmen.
Einen zentralen Gegenstand bilden die Konzepte der Unabhängigkeit
und k-weisen Unabhängigkeit von Zufallsvariablen. Wir benötigen
dafür einige Theorie auf endlichen Wahrscheinlichkeitsräumen;
diese wird in der Vorlesung von Anfang an aufgebaut, so dass hier
keine Vorkenntnisse notwendig sind. Wir zeigen die Analyse
einfacher randomisierter kombinatorischer Algorithmen, wenden uns
dann aber schnell dem Ziel zu -- geleitet von der Idee der
Randomisierung -- deterministische kombinatorische Algorithmen zu
entwerfen und zu analysieren. Hierzu lernen wir zwei Techniken
kennen: Die Methode der bedingten Erwartungswerte (auch
aufzufassen als eine binäre Suche) und die erschöpfende Suche.
Wir diskutieren ihre Anwendbarkeit unter verschiedenen
Voraussetzungen. Eine erschöpfende Suche erscheint dabei
zunächst aussichtslos. Hier kommt die Theorie der k-weisen
Unabhängigkeit ins Spiel: Sie erlaubt uns unter