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.

Unsere Webseite verwendet Cookies. Diese haben zwei Funktionen: Zum einen sind sie erforderlich für die grundlegende Funktionalität unserer Website. Zum anderen können wir mit Hilfe der Cookies unsere Inhalte für Sie immer weiter verbessern. Hierzu werden pseudonymisierte Daten von Website-Besuchern gesammelt und ausgewertet. Das Einverständnis in die Verwendung der technisch nicht notwendigen Cookies können Sie jeder Zeit wiederrufen. Weitere Informationen erhalten Sie auf unseren Seiten zum Datenschutz.

Erforderlich

Diese Cookies werden für eine reibungslose Funktion unserer Website benötigt.

Statistik

Für den Zweck der Statistik betreiben wir die Plattform Matomo, auf der mittels pseudonymisierter Daten von Websitenutzern der Nutzerfluss analysiert und beurteilt werden kann. Dies gibt uns die Möglichkeit Websiteinhalte zu optimieren.

Name Zweck Ablauf Typ Anbieter
_pk_id Wird verwendet, um ein paar Details über den Benutzer wie die eindeutige Besucher-ID zu speichern. 13 Monate HTML Matomo
_pk_ref Wird benutzt, um die Informationen der Herkunftswebsite des Benutzers zu speichern. 6 Monate HTML Matomo
_pk_ses Kurzzeitiges Cookie, um vorübergehende Daten des Besuchs zu speichern. 30 Minuten HTML Matomo