Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage...
Begriffe und Strategien im Zusammenhang mit randomisierten Algorithmen zu erklären;
Randomisierte Algorithmen für verschiedene Problemstellungen intuitiv und formal zu beschreiben, mathematisch zu analysieren und ihre Eigenschaften zu beweisen;
Wahrscheinlichkeitsberechnungen anzuwenden um die Leistung von randomisierten Algorithmen zu analysieren;
Anwendungsbereiche randomisierter Algorithmen zu identifizieren und geeignete Algorithmen für die Lösung einer gegebenen Problemstellung auszuwählen;
Unbekannte Berechnungsprobleme zu analysieren und eigene randomisierte Lösungensverfahren zu entwerfen und analysieren.
Randomisierte Algorithmen sind Algorithmen, die während ihrer Ausführung Zufallsentscheidungen treffen. Solche Vorgehensweisen können die Berechnung deutlich vereinfachen oder beschleunigen. Man nimmt aber in Kauf, dass die Algorithmen mit einer bestimmten, beschränkten Wahrscheinlichkeit zu falschen Ergebnissen kommen, oder dass die Algorithmen nur mit bestimmter Wahrscheinlichkeit effizient sind. Diese Vorlesung behandelt grundlegende Prinzipien, Techniken und Anwendungen von randomisierten Algorithmen. Anhand von Beispielen wird ihre Entwicklung und Analyse studiert, insbesondere in Hinsicht darauf, die Fehlerwahrscheinlichkeit zu beschränken, und die Effizienz zu zeigen. Mögliche Themenblöcke:
Vorlesungen und Übungseinheiten
Die Gesamtnote setzt sich aus der Leistung in den Übungseinheiten und der mündlichen Prüfung zusammen.
