1.18 Average-Case Analyse

Inhalt:

Average-Case Analyse ist eine Vorlesung, die zwischen der algorithmischen Informatik und angewandten Mathematik anzusiedeln ist; insbesondere spielen Optimierung und Wahrscheinlichkeitsrechnung eine zentrale Rolle.

Unter einem Algorithmus versteht man ein Verfahren um informatisch-mathematische Aufgaben zu lösen. Die klassische Worst-Case Sicht fragt, wie der Name schon sagt, nach dem Verhalten von Algorithmen im schlechtesten Fall. Im Gegensatz dazu beschäftigt sich die Average-Case Analyse mit deren Verhalten bei „typischen“ Eingaben; was auch immer konkret unter „typisch“ zu verstehen ist.

Verdeutlichen wir die Situation mit einem Beispiel. Eine grundlegende Grösse zur Bewertung von Algorithmen ist deren Laufzeit, d.h., die Zeit die der Algorithmus zur Bestimmung einer Lösung benötigt. Betrachten wir die Aufgabe ein Feld von n Zahlen aufsteigend zu sortieren. Einer der bekanntesten Algorithmen dafür ist Quicksort. Im schlechtesten Fall benötigt Quicksort n² Vergleiche, was unbefriedigend ist, da n log n best-möglich ist. In der Praxis beobachtet man jedoch, dass Quicksort tatsächlich meist nur n log n Vergleiche braucht. Der Ansatz der Average-Case Analyse ist es, eine (natürliche) Wahrscheinlichkeitsverteilung der Eingaben anzunehmen und den Algorithmus darauf zu analysieren. Im Beispiel Quicksort kann man zeigen, dass der Algorithmus ein zufällig gewähltes Feld mit hoher Wahrscheinlichkeit in n log n Vergleichen sortiert.

Eines der Ziele der Average-Case Analyse ist es, Lücken, die zwischen Worst-Case Ergebnissen und Beobachtungen in der Praxis bestehen, zu schliessen, was unter anderem für Quicksort gelungen ist.

Highlights aus dem Inhalt:

• Laufzeitanalyse von Quicksort
• Rucksackproblem in erwartet polynomieller Laufzeit
• Typische Performance von Speicherzugriffsstrategien
• Produktionsplanung unter unvollständigem Wissen

Literatur:

1. Mitzenmacher, Upfal: Probability and Computing. Randomized Algorithms and Probabilistic Analysis
2. Motwani, Raghavan: Randomized Algorithms
3. Weitere Literatur wird angegeben