Zufallsgesteuerte Algorithmen

Modulnummer
TI5008
Modulverantwortliche
Hellwig Geisse
Dozenten
Hellwig Geisse
Kurzbeschreibung
Der Kurs zeigt die systematische Nutzung von Zufall beim Design von Algorithmen, deren deterministische Varianten unvernünftig lange Laufzeiten haben.
Qualifikations- und Lernziele

Die Teilnehmer wissen, wie zufallsgesteuerte Algorithmen arbeiten, nach welchen Prinzipien sie entworfen werden und wie ihre Eigenschaften nachgewiesen werden können. Sie verteidigen eigene Beweise in den Übungen.

Lerninhalte
  • Grundlagen
  • Überlisten des Gegners
  • Die Methode der Fingerabdrücke
  • Wahrscheinlichkeitsverstärkung durch Wiederholungen und die Stichprobenmethode
  • Die Methode der häufigen Zeugen
  • Optimierung und zufälliges Runden
Moduldauer (Semester)
1
Unterrichtssprache
Deutsch
Gesamtaufwand
6 CrP; 180 Stunden, davon etwa 60 Stunden Präsenzzeit.
Semesterwochenstunden
4
Lernformen

Vorlesung 2 SWS, Übung 2 SWS

Geprüfte Leistung

Prüfungsleistung: Übungsaufgaben, Vortrag (zusammen 100%)

(Anzahl der Übungsaufgaben wird den Studierenden zu Semesterbeginn rechtzeitig und auf geeignete Art und Weise bekannt gegeben)

Bewertungsstandard

Bewertung der Prüfungsleistung nach § 9 der Prüfungsordnung (Teil l)

Häufigkeit des Angebots
Nach Bedarf
Literatur
  • J. Hromkovic: Randomisierte Algorithmen Teubner
  • R. Motwani: Randomized Algorithms Cambridge University Press
Voraussetzungen

Teilnehmer sollten keine Scheu vor Mathematik und Beweisen haben.