Zufallsgesteuerte Algorithmen

Kurzame
Zufallsgest. Algorithmen
Modulnummer
TI5008
Modulverantwortlicher
  • Hellwig Geisse
Dozent
  • 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.