Vorlesung Randomisierte Algorithmen (WS 2018/2019)

Vorlesung für das Masterstudium Informatik 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

Die Vorlesung beginnt am Donnerstag, den 18. Oktober in Raum 236 (im Infobau am Fasanengarten).

Termine im Wintersemester 2018/2019

Die Termine sind

  • wöchentlich donnerstags, 11:30 - 13:00 im Raum 236 (Geb. 50.34).
    Beginn ist am 19. Oktober 2017.
  • vierzehntägig montags, 11:30 - 13:00 im Hörsaal -101 (Geb. 50.34)
    erstmals am 22. Oktober 2017

Ü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 2017/2018).

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          
Skript Skript Skript          
Aufgaben Aufgaben Aufgaben          
Lösungen              
Kap. 8 Kap. 9 Kap.10 Kap.11 Kap.12 Kap.13 Kap. 14 Anhang
Folien             Folien (unvollständig)
Skript             Skript (unvollständig)
Aufgaben              
Lösungen              
               

Author: Thomas Worsch

Created: 2018-10-18 Thu 10:09

Validate