Fakultät für Informatik - Technische Universität München Lehrstuhl für Effiziente Algorithmen

Randomisierte Algorithmen (WS 06/07)

• Dozent:
  Prof. Dr. Christian Scheideler

• Bereich:
  4+2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
  Wahlpflichtvorlesung im Gebiet Algorithmen

• Zeit und Ort:
  Montag 12:30 - 14:00, Hörsaal MI HS 2
  Freitag 12:00 - 13:30, Hörsaal MI HS 1

• Übung:
  2 SWS Übung zur Vorlesung
  Dienstag 12:15 - 13:45, Hörsaal 00.13.009A
  Übungsleitung: Johannes Nowak
  Übungsschein: Einen Schein erhält, wer am Ende der Vorlesung die mündliche Prüfung erfolgreich besteht.

• Klausur:
  

• Hörerkreis:
  Studierende im Hauptstudium der Informatik
  Studierende mit Nebenfach Informatik

• Voraussetzungen:
  Stoff des Informatik Grundstudiums
  Vorlesung Effiziente Algorithmen und Datenstrukturen I vorteilhaft, aber nicht notwendig.

• Empfehlenswert für:
  Grundkenntnisse im Bereich Algorithmen

• Inhalt:
  
  • Einführung in die Wahrscheinlichkeitstheorie
    (aus Kapitel 3 von "Probabilistic Methods for Coordination Problems")
  • Einführung in randomisierte Algorithmen
    (aus Kapitel 1 vom Hofmeister-Skript)
  • Sortieren und Suchen mit Randomisierung
    (aus Kapitel 3 vom Sohler-Skript)
  • Randomisiert inkrementelle Methoden
    (aus Kapitel 4 vom Sohler-Skript)
  • Das Minimax-Prinzip
    (aus Kapitel 2 vom Hofmeister-Skript)
  • Monte Carlo Algorithmen
    (aus Kapitel 5 vom Sohler-Skript)
  • Markov-Ketten und Random Walks
    (aus Kapitel 6 vom Sohler-Skript)
  • Techniken für randomisierte Approximationsalgorithmen
    (aus einem Kapitel des Wanka-Skripts)
  • Quantencomputing I - Grundlagen
  • Quantencomputing II - Algorithmen
  • Universelle Routingprotokolle

• Weiterführende bzw. verwandte Vorlesungen:
  Effiziente Algorithmen und Datenstrukturen I und II

• Skript:Die Vorlesung wird sich im wesentlichen an zwei Skripten orientieren:
  • Randomisierte Algorithmen von Christian Sohler (Universität Paderborn)
  • Randomisierte Algorithmen von Thomas Hofmeister (Universität Dortmund)
  Zusätzliche Ressourcen sind
  • Kleinster umschließender Kreis (von Emo Welzl)
  • Techniken für randomisierte Approximationsalgorithmen (aus einem Skript von Rolf Wanka)
  • Quantumcomputing I (in ps und pdf Format)
  • Quantumcomputing II (in ps und pdf Format)
  • Universal Routing Protocols (in ps und pdf Format)

• Literatur:
  

  R. Motwani, P. Raghavan:

  Randomized Algorithms
  Cambridge University Press, 1995.

  C. Scheideler:

  Probabilistic Methods for Coordination Problems
  HNI-Verlagsschriftenreihe, Band 78, 2000.

• Sprechstunde:
  siehe hier