LEA

Randomisierte Algorithmen

  • Dozent: Prof. Dr. Susanne Albers
  • Modul: IN2160,
  • Bereich:
    4+2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
    Wahlpflichtvorlesung im Gebiet Algorithmen
  • Zeit und Ort:
    Montag, 14:00–16:00, 00.13.009A
    Mittwoch, 16:00–18:00, 00.13.009A
  • Übung:
    2 SWS Übung zur Vorlesung
    Mittwoch, 14:00–16:00, 03.11.018
    Übungsleitung: Dr. Dimitrios Letsios
  • Erfolgreiche Teilnahme:
  • Hörerkreis:
    Studierende im Hauptstudium der Informatik
    Studierende mit Nebenfach Informatik
  • Voraussetzungen:
    Stoff des Informatik Grundstudiums
    Vorlesung Effiziente Algorithmen und Datenstrukturen I vorteilhaft, aber nicht notwendig.
  • Empfehlenswert für:
    Erweiterte Kenntnisse im Bereich Algorithmen

Information

  • Da die Veranstaltang in Englisch gehalten wird, pflegen wir nur die englische Version dieser Web-Seite.

Inhalt

Über die letzten 25 Jahre ist die Entwicklung und Analyse von randomisierten Algorithmen, die während ihrer Ausführung Zufallsentscheidungen treffen, ein wesentlicher Bestandteil der Algorithmentheorie geworden. Für viele Probleme können überraschend elegante und schnelle randomisierte Algorithmen entwickelt werden. In dieser Vorlesung werden wir (a) grundlegende Konzepte aus der Wahrscheinlichkeitstheorie, die in probabilistischen Analysen benötigt werden, studieren und (b) randomisierte Algorithmen für eine Reihe von grundlegenden Problemen entwerfen.

Literatur

  • M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
  • R. Motwani, and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.