| Randomisierte Algorithmen [2024 SoSe] | ||
|---|---|---|
| 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. |
|