[IRA] - [2022Sommer] - [en] - [Randomisierte Algorithmen]


Randomisierte Algorithmen [2022/23 WiSe]
Code
IRA
Name
Randomisierte Algorithmen
CP
6
Duration
ein Semester
Offered
mindst. jedes 4. Semester
Format
Vorlesung 3 SW + Übung 1 SWS
Workload
180 h; davon
60 h Präsenzstudium
40 h Prüfungsvorbereitung
80 h Selbststudium und Bearbeitung der Übungsaufgaben (eventuell in Gruppen)
Availability
B.Sc. Angewandte Informatik
B.Sc. Informatik
M.Sc. Angewandte Informatik
M.Sc. Scientific Computing
Language
Deutsch
Lecturer(s)
Wolfgang Merkle
Examination scheme
1+1
Learning objectives Auf der Grundlage der behandelten Anwendungsbeispiele aus verschiedenen Teilgebieten der Informatik können die Studierenden die probabilistische Betrachtungs- und Vorgehensweise anwenden
bei der Konstruktion und Analyse von probabilistischen und deterministischen Algorithmen,
auf kombinatorische Fragestellungen,
um spieltheoretische Situationen zu analysieren,
auf kryptographische Fragestellungen.
Learning content Elementare Wahrscheinlichkeitsrechnung
Das Tenure-Spiel
Derandomisierungstechniken
Die probabilistische Methode
Byzantinische Übereinkunft
Stabile Heiraten und der Gale-Shapley-Algorithmus
Das Minimax-Prinzip von Yao
Komplexitätsanalyse des randomisierten Sortierens
Randomisierte Fehlersuche und -korrektur
Das Local-Lemma von Lovasz
PAC-Lernen und VC-Dimension
Wahrscheinlichkeitsverstärkung und Fehlerschranken
Lokale Suche für k-SAT
Kryptographische Protokolle
Requirements for participation empfohlen sind: elementare Grundkenntnisse in Algorithmen wie sie z.B. im Modul Algorithmen und Datenstrukturen (IAD) vermittelt werden.
Requirements for the assignment of credits and final grade Das Modul wird mit einer benoteten mündlichen oder schriftlichen Prüfung abgeschlossen. Die Modulendnote wird durch die Note der Prüfung festgelegt. Für die Vergabe der LP gilt die Regelung aus dem Kapitel Prüfungsmodalitäten.
Useful literature R. Motwani und P. Raghavan, Randomized Algorithms, Cambridge University Press 1995.
M. Mitzenmacher und E. Upfal, Probability and Computing, Cambridge University Press, 1995.
N. Alon und J. H. Spencer, The Probabilistic Method,
John Wiley and Sons, 2008.