Vorlesung Randomisierte Algorithmen (WS 2016/2017)

Informatik-Vorlesung für das Diplom-Haupt- und Masterstudium im Wintersemester. Sie ist prüfbar im Rahmen der Vertiefungsgebiete Parallelverarbeitung und Algorithmentechnik, aber auch für Mathematiker etc.

Diese Vorlesung wird mit Übung angeboten und es sind 5 Leistungspunkte zu erwerben.

Eine strenge Trennung nach Vorlesung und Übung hat sich nicht besonders bewährt. Es wird immer gerade gemacht, was passt.

Aktuell

Wir sind etwas vorzeitig mit dem Stoff durch. Die Vorlesung ist beendet.

Termine im Wintersemester 2016/2017

Die Termine sind

  • donnerstags, 11:30 - 13:00 im Raum 236 (Geb. 50.34).
    Beginn ist am 20. Oktober 2015.
  • montags, 11:30 - 13:00 im Hörsaal -101 (Geb. 50.34) vierzehntätig

Überblick über den Inhalt

Randomisierte Algorithmen sind nicht deterministisch. Ihr Verhalten hängt vom Ausgang von Zufallsexperimenten ab. Diese Idee wurde erstmals von Rabin durch einen randomisierten Primzahltest bekannt. Inzwischen gibt es für eine Vielzahl von Problemen randomisierte Algorithmen, die (in dem einen oder anderen Sinne) schneller sind als deterministische Verfahren. Außerdem sind randomisierte Algorithmen mitunter einfacher zu verstehen und zu implementieren als "normale" (deterministische) Algorithmen.

Im Rahmen der Vorlesung werden nicht nur verschiedene "Arten" randomisierter Algorithmen (Las Vegas, Monte Carlo, …) vorgestellt, sondern auch die für die Analyse ihrer Laufzeit notwendigen wahrscheinlichkeitstheoretischen Grundlagen weitgehend erarbeitet und grundlegende Konzepte wie Markov-Ketten behandelt. Da stochastische Methoden in immer mehr Informatikbereichen von Bedeutung sind, ist diese Vorlesung daher auch über das eigentliche Thema hinaus von Nutzen.

Hier ein kurzer Überblick über den voraussichtlich in der Vorlesung behandelten Stoff.

  • Einleitung
  • Erste Beispiele
  • probabilistische Komplexitätsklassen
  • Routing in Hyperwürfeln
  • zwei spieltheoretische Aspekte
  • randomisierte Graph-Algorithmen
  • Random Walks
  • Markov-Ketten
  • schnell mischende Markov-Ketten
  • randomisiertes Approximieren
  • randomisierte Online-Algorithmen
  • Hashing
  • Erzeugung von Pseudozufallszahlen

Elektronische Kurswaren

Skript und Folien werden im Laufe des Semesters an dieser Stelle zur Verfügung gestellt.

Es gibt alle Kapitel zusammen in einer Pdf-Datei (Fassung vom Wintersemester 2015/2016).

Nachfolgend werden im Laufe des Semesters Vorlesungsfolien, Skript, Aufgaben und (verzögert) Lösungen dazu in Pdf-Format veröffentlicht.

Kap. 1 Kap. 2 Kap. 3 Kap. 4 Kap. 5 Kap. 6 Kap. 7
Folien Folien Folien Folien Folien Folien Folien
Skript Skript Skript Skript Skript Skript Skript
Aufgaben Aufgaben Aufgaben Aufgaben Aufgaben Aufgaben Aufgaben
Lösungen Lösungen Lösungen Lösungen Lösungen Lösungen Lösungen
Kap. 8 Kap. 9 Kap.10 Kap.11 Kap.12 Kap.13 Anhang
Folien Folien Folien Folien Folien Folien  
Skript Skript Skript Skript Skript Skript Skript
Aufgaben Aufgaben Aufgaben Aufgaben --- ---  
Lösungen Lösungen Lösungen Lösungen --- ---  
  Extra          

Author: Thomas Worsch

Created: 2017-01-30 Mon 11:21

Validate