Randomisierte Algorithmen (Sommersemester 2021 und 2022)

Kapitel 1 - Einführung und Beispiele

Dokumente

Videos

Kapitel1, Teil 1
Kapitel1, Teil 2
Kapitel1, Teil 3
Kapitel1, Teil 4
Kapitel1, Teil 5
Kapitel1, Teil 6

Kapitel 2 - Wahrscheinlichkeitsrechnung

Dokumente

Videos

Kapitel 2.1
Kapitel 2.2
Kapitel 2.3
Kapitel 2.4
Kapitel 2.5
Kapitel 2.6, Teil 1
Kapitel 2.6, Teil 2
Kapitel 2.7
Kapitel 2.8, Teil 1
Kapitel 2.8, Teil 2
Kapitel 2.8, Teil 3

Korrektur:

Kapitel 2.8, Teil 3: Fehler bei Minute 18:15: "x=1", nicht "x=0".

Kapitel 3 - Modellierung und Transformation

Dokumente

Videos

Kapitel 3, Teil 1
Kapitel 3, Teil 2
Kapitel 3, Teil 3
Kapitel 3, Teil 4
Kapitel 3, Teil 5
Kapitel 3, Teil 6

Kapitel 4 - Randomisierte Suche

Dokumente

Videos

Kapitel 4, Teil 1
Kapitel 4, Teil 2
Kapitel 4, Teil 3
Kapitel 4, Teil 4
Kapitel 4, Teil 5

Kapitel 5 - Randomisierte Algorithmen für Probleme aus der Zahlentheorie

Dokumente

Videos

Kapitel 5.1, Teil 1
Kapitel 5.1, Teil 2
Kapitel 5.1, Teil 3
Kapitel 5.1, Teil 4
Kapitel 5.1, Teil 5
Kapitel 5.2, Teil 1
Kapitel 5.2, Teil 2
Kapitel 5.2, Teil 3
Kapitel 5.2, Teil 4
Kapitel 5.2, Teil 5
Kapitel 5.3
Kapitel 5.4, Teil 1
Kapitel 5.4, Teil 2

Hinweise:

Die Videos zu Abschnitt 5.2 (Miller-Rabin-Test, sehr lang) und 5.3 (Primzahlerzeugung). Diese Videos stammen aus der Kryptographievorlesung.
Sie finden die Zuordnung leicht auf der Basis der Abschnittsüberschriften.

4. Fehlerschranke des Miller-Rabin-Tests Achtung: Das Video sagt, dieser Abschnitt sei nicht prüfungsrelevant.
Für die Vorlesung "Randomisierte Algorithmen" ist es Teil des Stoffs (aber sehr fortgeschritten, also nicht unbedingt jenes, welches Sie zuerst anschauen sollten.

Kapitel 6 - Algebraische Methoden

Dokumente

Videos

Kapitel 6, Teil 1
Kapitel 6, Teil 2
Kapitel 6, Teil 3