Randomisierte Algorithmen

Worum geht's

Du lernst Grundlagen und Techniken randomisierter Algorithmen kennen und wie man deren Laufzeit und Korrektheit mit probabilistischen Methoden abschätzt. Am Ende kannst du klassische randomisierte Algorithmen (z. B. randomisierter Quicksort, Min-Cut, Treaps) verstehen und analysieren sowie Werkzeuge wie Markov-, Chebyshev- und Chernoff-Ungleichungen anwenden.

Was du danach kannst

• Verständnis von Las-Vegas- und Monte-Carlo-Algorithmen
• Kenntnis wichtiger randomisierter Algorithmen (z. B. Quicksort, Min-Cut, Treaps)
• Vertrautheit mit probabilistischen Analysewerkzeugen (Momente, Markov, Chebyshev, Chernoff)
• Anwendung der probabilistischen Methode auf kombinatorische Probleme
• Einsatz spieltheoretischer Techniken wie Yaos Minimax-Prinzip
• Verständnis von universellem und perfektem Hashing

Aus was das Modul besteht

• VorlesungVermittlung der Inhalte durch Vortrag und Präsentation
• ÜbungBearbeitung und Besprechung von Übungsblättern; individuelle Rückmeldung durch Korrektur

Lehrmethode

• Vortrag / PräsentationEinführung und Erklärung der Theorie und Algorithmen
• Übungsblätter und ÜbungsbesprechungPraktische Anwendung des Gelernten und individuelles Feedback durch Korrekturen