Randomisierte Algorithmen
- Dozent: Prof. Dr. Susanne Albers
- Modul: IN2160, TUMonline
-
Bereich:
4+2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Wahlpflichtvorlesung im Gebiet Algorithmen -
Zeit und Ort:
Montag, 10:00 – 12:00, 00.13.009A
Mittwoch, 8:00 – 10:00, 00.13.009A -
Übung:
2 SWS Übung zur Vorlesung
Date: TBA -
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.