Randomisierte Algorithmen (Sommersemester 2017)

Lecturer: Dr. Timo Kötzing (Algorithm Engineering) , Dr. Andreas Göbel (Algorithm Engineering)

General Information

• Weekly Hours: 4
• Credits: 6
• Graded: yes
• Enrolment Deadline: 28.04.2017
• Teaching Form: Lecture / Exercise
• Enrolment Type: Compulsory Elective Module
• Maximum number of participants: 30

Programs, Module Groups & Modules

Description

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.

Requirements

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.

Learning

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).

Examination

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.

Dates

TBA

Zurück