Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Randomisierte Algorithmen

Wintersemester 2016/2017

Veranstalter:Dr. Matthias Westermann
Termine: Mittwoch16:00-17:30 UhrOH 14 304
Beginn: Mittwoch 19.10.

Inhalt

Randomisierte Algorithmen sind nicht deterministisch. Ihr Verhalten hängt von dem Ausgang von Zufallsexperimenten ab. Häufig sind randomisierte Algorithmen effizienter und einfacher zu implementieren als deterministische Algorithmen. Zudem können die Wahrscheinlichkeiten von unerwünschten Ereignissen, wie zu lange Rechenzeiten oder die Berechnung falscher Ergebnisse, oft gering gehalten werden. Die Veranstaltung behandelt den Entwurf und die Analyse randomisierter Algorithmen und stellt grundlegende Techniken und Konzepte dieses Gebietes der Algorithmik vor.

Themen

  • Fingerprinting
  • Routing im Hypercube
  • Spieltheorie
  • Random Walks
  • Paging
  • Datenmanagement in Netzwerken

Stand der Vorlesung

  • 19.10.2016: Übersicht
  • 26.10.2016: Fingerprinting: Produkt von Matrizen
  • 02.11.2016: Fingerprinting: Vergleich von Wörtern; Routing im Hypercube: Deterministische untere Schranke
  • 09.11.2016: Routing im Hypercube: Nützliche Ungleichungen
  • 16.11.2016: Routing im Hypercube: Randomisierter Algorithmus
  • 23.11.2016: Routing im Hypercube: Wieviel Zufall ist notwendig?
  • 30.11.2016: Lehrveranstaltungsfrei wegen Fachschaftsvollversammlung
  • 07.12.2016: Spieltheorie: Und-Oder-Bäume
  • 14.12.2016: Paging: Deterministisch
  • 21.12.2016: Paging: Unwissender Widersacher I
  • 11.01.2017: Paging: Unwissender Widersacher II, amortisierte Analyse, adaptiver Widersacher I
  • 18.01.2017: Paging: Adaptiver Widersacher II
  • 25.01.2017: Datenmanagement in Netzwerken: Bäume I
  • 01.02.2017: Datenmanagement in Netzwerken: Bäume II, Approximation von Metriken I
  • 08.02.2017: Datenmanagement in Netzwerken: Approximation von Metriken II

Übungen

Veranstalter:Dr. Matthias Westermann
Termine: Mittwoch17:30-19:00 UhrOH 14 304
Beginn: Dienstag 26.10.

In den Übungen werden Aufgaben gemeinsam gelöst und besprochen. Es soll in Gruppen zusammengearbeitet werden.

Die Studienleistung wird durch regelmäßige und aktive Teilnahme an den Übungen erbracht.


Prüfung

Die Veranstaltung wird mündlich geprüft. Prüfungen finden typischerweise in der vorlesungsfreien Zeit alle zwei Wochen jeweils Dienstags statt.

Die Studienleistung ist Voraussetzung für die Teilnahme an der Prüfung.


Literatur

Auf ergänzende Literatur wird in den Manuskripten verwiesen.