Vorlesung
"Average-Case Analyse"
Wintersemester 2006/2007
Prof. Dr. Susanne Albers
Dr. Alexander Souza
VorlesungDie folgenden Formalitäten bilden den Rahmen für die Vorlesung.
|
Aktuelles31. Oktober 2006Wir haben einen neuen Vorlesungstermin: Dienstags von 13-15 Uhr im Raum 051-00-006, Gebäude 051 Diese Änderung gilt ab nächster Woche, d.h. ab (inclusive) 7. November 2006. |
Inhalt der VeranstaltungUnter 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. Es gibt einige Algorithmen (z.B. Quicksort) die im Prinzip sehr schlechtes Verhalten zeigen können, dieses in der Praxis aber nur sehr selten auftritt. Beispielsweise bei Quicksort ist es möglich, dass der Algorithmus n2 Vergleiche zum Sortieren eines n-elementigen Feldes benötigt - tatsächlich werden aber üblicherweise nur nlog n gebraucht. Eines der Ziele der Average-Case Analyse ist es, solche Lücken, die zwischen Worst-Case Ergebnissen und Beobachtungen in der Praxis bestehen, zu schliessen, was unter anderem für Quicksort gelungen ist. Weitere Highlights aus dem Inhalt:
Eine etwas umfangreichere Darstellung ist hier zu finden. Für eine erfolgreiche Teilnahme an der Vorlesung sind grundlegende Kenntnisse in den Bereichen Algorithmen, Optimierung und Wahrscheinlichkeitsrechnung hilfreich aber nicht Voraussetzung. |
LeistungsnachweisWird noch bekannt gegeben. Vermutlich individuelle, mündliche Prüfungen. KreditpunkteIn dieser Veranstaltung können 3 ECTS-Punkte erworben werden. |
Weiterführendes Material
Hier finden Sie Links zu Materialien, die in der sonstigen Literatur nicht oder nicht ausführlich genug behandelt werden.- Wichtige Wahrscheinlichkeitsverteilungen
- Zu Pseudo-Zufallszahlen: Knuth: The Art of Computer Programming - Volume 2 - Seminumerical Algorithms, Addison Wesley.
- Zu Simulation von Wahrscheinlichkeitsverteilungen: Ross: Introduction to Probability Models, Harcourt Academic Press.
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.