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

Randomisierte Algorithmen (WS 07/08)

• Dozent:
  Prof. Dr. Christian Scheideler

• Modul: IN2160

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

• Zeit und Ort:
  Mittwoch 12:15 - 13:45, Hörsaal MI HS 3
  Freitag 12:00 - 13:30, Hörsaal MI HS 1

  Die Vorlesung am Freitag, den 23. November findet in Raum 01.11.018 statt.
  
  

• Übung:
  2 SWS Übung zur Vorlesung
  Mi 16:00 - 18:00, Hörsaal MI 03.11.018
  Übungsleitung: Jonas Pfoh
  Ü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

• ECTS: 8 Punkte

• 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 Postscript und PDF)
  • Randomisierte Suchstrukturen I - Arrays und Bäume (in Postscript und PDF)
  • Randomisierte Suchstrukturen II - Hashing (in Postscript und PDF)
  • Kombinatorische Optimierung I - Randomisiertes Runden (in Postscript und PDF)
  • Kombinatorische Optimierung II - Clarksons Algorithmus (in Postscript und PDF)
  • Kombinatorische Optimierung III - Das Lovasz Local Lemma (in Postscript und PDF)
  • Approximationsalgorithmen (in Postscript und PDF)
  • Sublineare Algorithmen (als Skript und Vorträge 1 und 2 aus der "Randomisierte Algorithmen" Vorlesung von Christian Sohler)
  • Online Algorithmen (in Postscript und PDF)
  • Monte Carlo Algorithmen (in Postscript und PDF aus der "Randomisierte Algorithmen" Vorlesung von Christian Sohler)
  • Quantencomputing I - Grundlagen (in Postscript und PDF)
  • Quantencomputing II - Algorithmen (in Postscript und PDF)

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

• Skript: Für die Vorlesung wird es ein Skript geben, das kapitelweise erstellt wird.

• 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