Uni-Logo
Algorithms and Complexity
 

Vorlesung
"Randomisierte Algorithmen und probabilistische Methoden"
Sommersemester 2007
Prof. Dr. Susanne Albers
Dr. Alexander Souza


Vorlesung

Die folgenden Formalitäten bilden den Rahmen der Veranstaltung: 3 + 1 SWS

Vorlesung

  • Zeit: Montags 11:00-12:30 und 13:15-14:00 Uhr
  • Ort: 051 - 00 - 006

Übung

  • Zeit: Mittwochs 13:15-14:00
  • Ort: 051 - 00 - 006

Leistungsnachweis

Individuelle mündliche Prüfungen.


Prüfung: Freitag, 19. Oktober

NameUhrzeit
10:00 - 10:30
Claudius Korzen10:30 - 11:00
Bente Luth11:00 - 11:30
11:30 - 12:00
13:00 - 13:30
13:30 - 14:00
14:00 - 14:30
Kamal Al-Bawani14:30 - 15:00

Kreditpunkte

In dieser Veranstaltung können 6 ECTS-Punkte erworben werden.
Bei Anregungen und Fragen wenden Sie sich bitte an Alexander Souza.

Aktuelles

16. April: Ein vorläufiges Inhaltsverzeichnis ist verfügbar: [PS]   [PDF]
16. April: Wir haben künftig den Raum 051-00-006. Die Übung findet ab nächster Woche Freitags 13-14 Uhr statt.
17. April: Es gab eine Anfrage, ob die Übung nicht zu einem anderen Termin stattfinden könne. Ich bin natürlich für Alternativen offen. Bitte mailt mir Eure Wunschtermine. Ich werde sehen was ich machen kann.
23. April: Die Übung ist auf Mittwoch 13-14 Uhr (Raum 051-00-006) verlegt worden und findet diese Woche das erste mal statt. Das erste Übungsblatt ist online (s.u.) und wird nächste Woche besprochen. Diese Woche gibt es einen kleinen Auffrischungskurs über Stochastik in der Übung.
30. April: Auf vielfachen Wunsch biete ich eine zusätzliche Vorlesungsstunde an, so dass die Veranstaltung mit 3+1 SWS jetzt 6 ECTS Punkte ergibt. Die neuen Vorlesungszeiten sind Montag 11:00-12:30 und 13:15-14:00 Uhr im 051-00-006.
25. Juni: Es gibt unten eine korrigierte Fassung des Übungsblattes 9.
16. Juli: Ein endgültiges Inhaltsverzeichnis ist verfügbar: [PS]   [PDF]
31. Juli: Die mündlichen Prüfungen finden am Freitag, 19. Oktober im Raum 079-00-09 statt. Stoff ist der gesamte Inhalt der Vorlesung sowie der Übungen. Prüfungszeit sind 30 Minuten. Bitte so bald wie möglich per email mit Name und Matrikelnummer bei mir anmelden.

Inhalt der Veranstaltung

Inhaltsverzeichnis [PS]   [PDF]

Ein randomisierter Algorithmus verwendet in Gegensatz zu einem deterministischen Algorithmus Zufallsbits um seinen Ablauf zu steuern. Es wird nicht verlangt, dass ein randomisierter Algorithmus immer effizient eine richtige Lösung findet. Randomisierte Algorithmen sind in vielen Fällen einfacher zu verstehen, einfacher zu implementieren und effizienter als deterministische Algorithmen für dasselbe Problem. Randomisierte Algorithmen, die nie ein falsches Ergebnis liefern, bezeichnet man auch als Las-Vegas-Algorithmen. Es gibt zwei Varianten von Las-Vegas-Algorithmen:

  • Algorithmen, die immer das richtige Ergebnis liefern, deren Rechenzeit aber (bei ungünstiger Wahl der Zufallsbits) sehr gross werden kann. In vielen Fällen ist der Algorithmus nur im Erwartungsfall schnell, nicht aber im schlimmsten Fall. Ein Beispiel ist die Variante von Quicksort, bei der das Pivotelement zufällig gewählt wird. Die erwartete Rechenzeit beträgt O(nlogn), bei ungünstiger Wahl der Zufallsbits werden dagegen O(n2) Schritte benötigt.
  • Algorithmen, die versagen dürfen (das heisst, dass sie "?" ausgeben dürfen), aber niemals ein falsches Ergebnis liefern dürfen. Die Qualität dieser Art von Algorithmen kann man durch eine obere Schranke für die Versagenswahrscheinlichkeit beschreiben.

Randomisierte Algorithmen, die auch ein falsches Ergebnis liefern dürfen, bezeichnet man auch als Monte-Carlo-Algorithmen. Die Qualität von Monte-Carlo-Algorithmen kann man durch eine obere Schranke für die Fehlerwahrscheinlichkeit beschreiben.

Von randomisierten Algorithmen spricht man, wenn man den Erwartungswert der Rechenzeit und/oder die Fehler- bzw. Versagenswahrscheinlichkeit abschätzen kann.

Einige Highlights aus dem Inhalt:

  • Laufzeitanalyse von randomisiertem Quicksort
  • Randomisierte Primzahltests
  • Erwartete Performance von Speicherzugriffsstrategien (Paging)
  • Randomisiertes Finden von erfüllenden Belegungen in Booleschen Formeln

Für eine erfolgreiche Teilnahme an der Vorlesung sind grundlegende Kenntnisse in den Bereichen Algorithmen, Optimierung und Wahrscheinlichkeitsrechnung hilfreich aber nicht Voraussetzung.

Übungsblätter

Abgabe der Übungsblätter in der Vorlesung. Rückgabe in der Übung.

Weiterführendes Material

Hier finden Sie Links zu Materialien, die in der sonstigen Literatur nicht oder nicht ausführlich genug behandelt werden.

Literatur

Die folgenden Literaturangaben dienen als Grundlage für die Vorlesung.
  • M. Mitzenmacher, E. Upfal: Probabilty and Computing, Cambridge University Press.
  • R. Motwani, P. Raghavan: Randomized Algorithms, Cambridge University Press.