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

Die Vorlesung beginnt am Donnerstag, den 20. Oktober, um 11:30.

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
    Die Vorlesung am Montag, den 21. Dezember, entfällt.

Ü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
  • randomisiertes Approximieren
  • schnell mischende Markov-Ketten
  • Hashing
  • randomisierte Online-Algorithmen
  • 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 [[skript-2015.pdf]Pdf-Datei]] (Fassung vom Wintersemester 2015/2016).

Nachfolgend werden im Laufe des Semesters Vorlesungsfolien, Skript, Aufgaben und vielleicht auch 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      

Author: Thomas Worsch

Created: 2016-11-17 Thu 10:10

Validate