Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen

Randomisierte Algorithmen (WS 02/03)

• Dozent:
  Prof. Dr. Angelika Steger,
  Stefanie Gerke, Ph.D.

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

• Zeit und Ort:
  Mo 15h c.t. - 16:45, Hörsaal MW 1250
  Do 10h c.t. - 11:45, Hörsaal MW 0250
  Erster Vorlesungstermin am Do 17.10.02

• Übung:
  2 SWS Übung zur Vorlesung
  Di 16h c.t. - 17:45, Hörsaal MI 00.07.014
  Übungsleitung: Alexander Offtermatt-Souza
  Übungsschein: Einen Schein erhält, wer mindestens 40% der Punkte zu den Hausaufgaben erreicht und erfolgreich an der Semestralklausur teilnimmt.

• Aktuelles:
  Wegen des MVV-Streiks am Montag den 16.12.2002 können die Hausaufgaben auch am Dienstag den 17.12.2002 in der Übung oder am Donnerstag den 19.12.2002 in der Vorlesung abgegeben werden.
  Achtung! Fehler in Blatt 10 Aufgabe 3. Es gibt eine korrigierte Version!
  Achtung! Fehler in Blatt 11 Aufgabe 2. Es gibt eine korrigierte Version!
  Die Klausurergebnisse hängen im Schaukasten 03.09 aus. Der Termin für die Klausureinsicht wird in Kürze bekannt gegeben.

• Klausur:
  Die Semestralklausur findet am Donnerstag, den 6.2.2003 von 10:15-13:15h im Hörsaal MW 0250 statt.
  Bitte bringen Sie einen Lichtbildausweis und ihren Studentenausweis mit.
  An Hilfsmitteln sind beliebige Unterlagen (in Papierform) zugelassen.
  Die Arbeitszeit beträgt 180 Minuten.
  Viel Erfolg :)
  Matrikelnummern zugelassener Studenten: siehe Übungsseite.

• 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:
  Für viele Probleme wurden in den letzten Jahren effiziente randomisierte Algorithmen gefunden, die deterministischen Verfahren in Bezug auf Laufzeit und/oder benötigte Hardwareressourcen weit überlegen sind. Oft sind randomisierte Algorithmen zudem auch viel einfacher zu analysieren und zu implementieren.
  In der Vorlesung werden wir verschiedene Grundprinzipien randomisierter Algorithmen an Hand von Beispielen vorstellen. Dabei werden wir uns eng an das Buch Randomized Algorithms von Motwani und Raghavan halten.

  Die Übersichtsfolien vom 3. Februar finden Sie hier.

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

• Skript:
  Die Mitschrift von Max Pühler und Benjamin Helfmann finden Sie hier. Diese ist jedoch kein "offizielles" Skript.

• Literatur:
  

  R. Motwani, P. Raghavan:

  Randomized Algorithms
  Cambridge University Press, 1995

• Sprechstunde:
  siehe hier