Randomized Algorithms - Einzelansicht

Randomisierte Algorithmen

Für viele Probleme stellen randomisierte Algorithmen die einzigen bekannten effizienten Lösungsverfahren dar. Für manches andere Problem erhalten wir mit einem solchen Verfahren Algorithmen, die um vieles einfacher und verständlicher sind als alle bekannten deterministischen Verfahren. Es ist daher nicht verwunderlich, dass wir randomisierte Algorithmen in viele Anwendungsgebieten finden, wie z.B. in

-      Datenstrukturen,

-      Graphenalgorithmen,

-      parallelen und verteilen Systemen,

-      Online-Algorithmen,

-      Zahlentheorie und

-      geometrische Algorithmen.

In der Vorlesung Randomisierte Algorithmen werden wir Verfahren aus einigen dieser Gebiete und grundlegende Techniken für randomisierte Algorithmen vorstellen und analysieren.

Darüber hinaus werden grundlegende probabilistische Methoden zur Analyse von Algorithmen vorgestellt.

Randomized Algorithms

For many problems randomized algorithms are the only known efficient solution method. For some other problem we can find randomized algorithms that are much simpler and more understandable than any known deterministic method. It is therefore not surprising that we find randomized algorithms in many areas, such as in

-      data structures,

-      graph algorithms,

-      parallel and distributed systems,

-      on-line algorithms,

-      number theory, and

-      geometric algorithms.

In the lecture Randomized Algorithms, we will present and analyze randomized algorithms and basic methods from some of these areas. Furthermore, basic probabilistic methods for the analysis of algorithms are presented.

Michael Mitzenmacher, Eli Upfal

Probability and Computing Randomized Algorithms and Probabilistic Analysis

CAMBRIDGE UNIVERSITY  PRESS, 2005

Bsc in a relevant study field

oral examination

M.Sc. Medieninformatik / Computer Science and Media / Computer Science for Digital Media / Human-Computer Interaction