Randomisierte Algorithmen

Lernziele

Abrundung der Kenntnisse in einem zentralen Bereich der theoretischen Informatik; Erwerb der Fähigkeit, sich in aktuelle Bereiche der Forschung selbständig einzuarbeiten; Vertrautheit im Umgang mit den Methoden der theoretischen Informatik in thematisch fortgeschrittenen Gebieten.

Inhalt

Randomisierung ist eines der zentralen algorithmischen Konzepte, um Probleme effizient zu lösen. Hauptidee dabei ist es, bei Algorithmen Zufallsentscheidungen zuzulassen (Münzwurf), deren Ausgang den weiteren Lauf des Algorithmus beeinflussen können. Dies führt zu wesentlichen Änderungen bezüglich der Anforderungen, was ein Algorithmus leisten soll. Durch die Randomisierung liefert ein Algorithmus, der mehrfach auf derselben Eingabe ausgeführt wird, i.a. nicht mehr stets dasselbe Ergebnis. Daher werden Ergebnisse nur mit einer gewissen Wahrscheinlichkeit korrekt sein. Im Gegenzug hofft man, dass die Randomisierung Algorithmen effizienter macht. Die Vorlesung will dieses Konzept studieren und wesentliche Techniken beim Entwurf und der Analyse probabilistischer Verfahren vorstellen.

Behandelt werden u.a. voraussichtlich folgende Themen:

  • Las Vegas und Monte Carlo Algorithmen
  • Techniken aus der Spieltheorie
  • Markov und Chebychev Ungleichungen, Chernoff Bound
  • die probalistische Methode
  • Random walks, Markovketten
  • algebraische Techniken
  • Anwendungen: Graphenalgorithmen, Lineare Programmierung
  • Derandomisierung

Zielgruppe

  • Informatik M.Sc. und Diplom
    Komplex: Grundlagen der Informatik
    Niveaustufe 400 (4. Studienjahr)
  • Mathematik/Diplom
  • Modul 12457, 6 KP
    2 SWS VL, 2 SWS UE

Voraussetzungen

Die Kenntnis des Modells der Turingmaschine sowie der Begriffe Entscheidungsproblem und Berechenbarkeit wird empfohlen. Zu Beginn der Vorlesung werden diese kurz wiederholt.

Literatur

  • R. Motwani, P. Raghavan: Randomized Algorithms, Cambridge Univ. Press 1995. Klassisches Lehrbuch für randomisierte Algorithmen in der theor. Informatik.
  • J. Hromkovic: Randomisierte Algorithmen, Teubner 2004. Lehrbuch, das großen Wert auf Verständlichkeit legt, daher thematisch etwas weniger umfangreich als Motwani & Raghavan.
  • T. Müller-Gronbach, E. Novak, K. Ritter, Monte Carlo-Algorithmen, Springer 2012. Ein als Zusatzliteratur sehr empfehlenswertes Lehrbuch für diejenigen, die weitere Einsatzbereiche randomisierter Algorithmen kennenlernen möchten.