Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Randomisierte Algorithmen

MSc Lecture - Summer 2016

Beschreibung

Das Konzept des Zufalls begegnet uns in der Algorithmik auf zwei Wegen: zum einen können Algorithmen Zufall nutzen, um Entscheidungen zu treffen; zum anderen können Algorithmen mit einer zufälligen Eingabe konfrontiert sein. In diesem Kurs wollen wir uns zuerst generell mit dem Konzept des Zufalls und seiner Formalisierung (Wahrscheinlichkeitstheorie) vertraut machen. Danach wird es 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

Wöchentlich dienstags um 9:15 und donnerstags um 13:00 im Raum A-1.2. Beginn in der ersten Vorlesungswoche.