01.07.2009

Mittwoch, 1. Juli 2009, 17:00 Uhr, Zuse-Hörsaal

Prof. Dr. Markus Nebel (TU Kaiserslautern)

"Maximum-Likelihood Analyse von Algorithmen"

Im Vorwort zu A=B von Petkovsek, Wilf und Zeilberger schreibt Donald Knuth:

"Science is what we understand well enough to explain to a computer. Art is everything else we do".

In diesem Vortrag werden wir sehen, dass unsere sog. Maximum-Likelihood Analyse von Algorithmen aus der Kunst der Average-Case Analyse tatsächlich etwas macht, das ein Computer (nahezu) eigenständig erledigen kann.

Im Vortrag werden wir am Beispiel des Quick- und des Heap-Sort die Ideen hinter unserer Analysetechnik vorstellen und ihre Vor- und Nachteile diskutieren. Wir werden sehen, dass es nahezu automatisiert gelingt, die bekannten Ergebnisse zur erwarteten Laufzeit dieser Algorithmen wiederzufinden aber auch Resultate zeigen, die auf nicht-uniformen Modellen beruhen, für die es bisher keinen Zugang auf klassischem Wege gibt.