Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Randomisierte Algorithmen

MSc Lecture - Summer 2017

Beschreibung

Diese Vorlesung wird in Teilen auf Englisch gehalten.

Im ersten Teil wird es eine generelle Einführung zum Thema Wahrscheinlichkeitstheorie geben. Wir werden uns mit Konzentrationsschranken (wie zum Beispiel Chernoffschranken) und generellen Techniken zur Abschätzung von Wahrscheinlichkeiten (zum Beispiel Bernoulli's Ungleichung) anschauen.

Danach geht es um das Konzept des Zufalls speziell in der Algorithmik: zum einen können Algorithmen Zufall nutzen, um Entscheidungen zu treffen; zum anderen können Algorithmen mit einer zufälligen Eingabe konfrontiert sein. Es wird darum gehen einerseits Zufall gewinnbringend in Algorithmen einzusetzen und andererseits zufällige Strukturen zu analysieren.

Voraussetzungen

Vorausgesetzt wird ein Interesse am Knobeln und Kniffeln sowie ein grundlegendes Verständnis von mathematischer Notation und Sprache. Insbesondere wird Sicherheit im Umgang mit Landau-Notation (O-Notation) vorausgesetzt, sowie grundlegende Fähigkeiten im Algorithmendesign und -Analyse. Es sind keine speziellen Kenntnisse im Bereich der Wahrscheinlichkeitsrechnung vorausgesetzt, diese wird komplett in der Vorlesung eingeführt.

Lern- und Lehrformen

In diesem Kurs werden wir problemorientiert lernen. Zu einem gegebenen Problem werden dabei Lösungen gesucht und gemeinsam von Studierenden und dem Dozenten entwickelt. Dabei werden Elemente der traditionellen Lehrformen "Vorlesung", "Übung" sowie "Sprechstunde" vermischt. Daher gibt es bei den beiden Terminen auch keine Unterscheidung zwischen Vorlesung und Übung. Da Lehrelemente mit einseitigem Informationsfluss keine Treffen von Studierenden mit dem Dozenten benötigen, werden alle solche Elemente in Heimarbeit erledigt (vom Dozenten vorbereitet und den Studierenden konsumiert).

Leistungserfassung

Es werden wöchentliche Hausaufgaben gestellt, deren erfolgreiche Bearbeitung Zulassungsvoraussetzung für die Endklausur ist. 100% der Note ergeben sich aus der Punktzahl bei der Endklausur (plus Bonuspunkte aus den Übungen). Die Endklausur ist eine take-home Klausur mit mündlicher Überprüfung.

Termine

  • Vorlesung: Dienstag 09:15, A-1.2
  • Vorlesung: Mittwoch 09:15, H 2.57