Next: Das Component Commonality Problem
Up: Kombinatorische Optimierung
Previous: Das Maximum-Traveling-Salesman-Problem
Im letzten Jahrzehnt haben randomisierte Algorithmen enorm an
Bedeutung gewonnen. Während dieser Periode sind sie von
einem Werkzeug aus der Zahlentheorie zu einem
der bedeutensten algorithmischen Konzepte mit weitreichenden Anwendungen
in verschiedenen Gebieten geworden.
Randomisierte Algorithmen sind dabei Algorithmen, die sich im Gegensatz
zu deterministischen Algorithmen den Zufall zunutze machen.
Zwei Vorteile gehen in der Regel mit randomisierten Algorithmen einher,
Einfachheit und Geschwindigkeit. Für viele Anwendungen sind die
randomisierten Algorithmen entweder die einfachsten, die schnellsten
oder vereinen beide Vorteile.
Unsere Forschung, in Kooperation mit Ravi Kannan (Department of
Computer Science, Yale University) und
Leen Stougie (Department of Computer Science, Eindhoven University)
konzentrierte sich auf drei Anwendungen von
randomisierten Algorithmen:
Webmaster<www@zpr.uni-koeln.de>
1999-07-28