Modulcode:	MS1404
Englische Bezeichnung:	Parallel Algorithms via Probabilistic Methods
Modulverantwortliche(r):	Prof. Dr. Anand Srivastav
Turnus:	unregelmäßig (WS09/10 WS10/11 SS12)
Präsenzzeiten:	2V 2Ü
ECTS:	6
Workload:	180 Std.
Dauer:	ein Semester
Modulkategorien:	MSc Math (Export) TG (MSc Inf)
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

Es geht um effiziente parallele Algorithmen zur Behandlung von kombinatorischen Optimierungsproblemen. Zum Entwurf und zur Analyse werden überwiegend probabilistische Methoden verwendet.

Lernziele:

• 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.

Lehrinhalte:

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 Umständen, den Suchraum drastisch zu reduzieren. Unter bestimmten Voraussetzungen wird eine erschöpfende Suche durchführbar. Indem wir die Reduktion des Suchraums mit der Methode der bedingten Erwartungswerte kombinieren, können wir aber noch größere Klassen von Problemen lösen. Die Algorithmen laufen nicht nur in Polynomialzeit, sondern in logarithmischer Zeit unter Ausnutzung polynomiell vieler Prozessoren (sogenannte NC-Algorithmen). Wir stellen NC-Algorithmen zur Berechnung von Niedrigdiskrepanzfärbungen in Hypergraphen und - darauf aufbauend

• zur Berechnung guter Gitterapproximationen vor. Wir wenden

diese erweiterte Methode der bedingten Erwartungswerte auch auf multidimensionales Bin-Packing an.

Dann lernen wir noch eine weitere Technik kennen, die letztlich wieder auf eine erschöpfende Suche hinausläuft. Vorher sind aber einige Vorbereitungen zu treffen. Wir betrachten dazu genauer, was bei der Ausführung von randomisierten Algorithmen passiert. Zu einer festen Eingabe stellt ein randomisierter Algorithmus ein Zuffalsexperiment dar, und wir können dieses mit einem Wahrscheinlichkeitsraum modellieren. Dafür ist die Darstellung des Algorithmus als Automat hilfreich. Eine erschöpfende Suche in diesem Wahrscheinlichkeitsraum deckt alle möglichen Abläufe des Algorithmus ab. Wenn der Algorithmus mit positiver Wahrscheinlichkeit ein gutes Ergebnis liefert, so ist dieses also auf diesem Wege zu finden. Es genügt sogar, die Suche auf den Träger zu beschränken; das sind jene Stichproben, die positives Maß haben. Nur hat man selbst mit dieser Beschränkung oft eine zu große Anzahl an Stichproben zu prüfen. Unter Umständen lässt sich aber das zugehörige Wahrscheinlichkeitsmaß so abändern, dass man sich einerseits nicht weit von den Eigenschaften des Algorithmus entfernt, andererseits den Träger aber drastisch reduziert. Der Algorithmus, der diese Reduktion vornimmt, benutzt als wichtigen Baustein den vorher entwickelten Algorithmus für Gitterapproximationen. Zum Abschluss lernen wir eine Anwendung dieser Methode auf allgemeine Packungsprobleme kennen.

Neben den theoretischen Ergebnissen wird während der gesamten Vorlesung auch immer wieder die Frage nach der praktischen Umsetzbarkeit aufgeworfen. Praktische Übungsaufgaben bieten Anregungen, sich damit zu beschäftigen. Eine Anleitung zum Umgang mit Softwarebibliotheken zur Parallelisierung (z.B. OpenMP oder MPI) kann punktuell geboten werden.

Weitere Voraussetzungen:

Grundkenntnisse in kombinatorischer Optimierung oder Komplexitätstheorie sind wünschenswert, aber nicht notwendig. Bei Bedarf werden fehlende Grundlagen hier durch kurze Einschübe in der Vorlesung aufgeholt.

Vorkenntnisse in Wahrscheinlichkeitstheorie sind hilfreich, aber auch nicht notwendig, da die relevante Theorie in der Vorlesung von Grund auf vorgestellt wird.

Prüfungsleistung:

Abschließende mündliche Prüfung.

Lehr- und Lernmethoden:

Vorlesung mit Beamer und Tafel. Es wird empfohlen, die relevanten Kapitel im Skript vor der jeweiligen Vorlesungstunde zu lesen. Das Skript und die Beamer-Präsentationen sind englischsprachig, die Vorlesung selbst wird aber auf deutsch gehalten.

Übungsaufgaben werden gestellt und bei Bedarf besprochen. Lösungen zu den meisten Übungsaufgaben sind im Skript zu finden.

Verwendbarkeit:

Master Mathematik und Informatik

Literatur:

Die Vorlesung basiert zum Großteil auf dem Handbuchartikel: L. Kliemann und A. Srivastav, Parallel Algorithms via the Probabilistic Method, In S. Rajasekaran und J.H. Reif, Parallel Computing: Models, Algorithms, and Applications, Chapman \& Hall/CRC, 18-1--18-61, 2008.

Es gibt zu der Vorlesung auch ein ausführliches Skript in englischer Sprache. Dieses wird als PDF allen Teilnehmern zur Verfügung gestellt. Interessierte Studierende sind eingeladen, an der weiteren Ausgestaltung und Durchsicht des Skriptes mitzuwirken.

Verweise:

Kommentar: