Personen: Timo Kötzing
Links: Lehrveranstaltungen IT-Systems Engineering, Algorithm Engineering Moodle

In diesem Kurs wird auf Wissen aus dem Kurs "Radomiserte Algorithmen" aufgebaut und weiter vertieft. Insbesondere werden wir die folgenden Themen behandeln.

• Vertiefende arithmetische Ungleichungen (Jensen's Ungleichung,...).
• Yao's Minimax Prinzip für untere Schranken.
• Analyse endlicher Markovketten.
• Drifttheoreme (Variabler Drift, Konzentration,...).
• Drifttheoreme für untere Schranken (Negativer Drift, unterer multiplikativer Drift,...).
• Analyse randomisierte Suchheuristiken (Evolutionäre Algorithmen, Schwarmintelligenz,...).
• Zufallsgraphen.

Weiterhin können Themen nach Wunsch der Studierenden hinzugefügt werden.

Vorausgesetzt wird das Verständnis aller Inhalte des Kurses Randomiserte Algorithmen. Insbesondere umfasst dies die folgenden Themen.

• Einfache Arithmetische Ungleichungen (Bernoulli,...).
• Probabilistische Ungleichungen (Markov, Chebycheff, Chernoff,...).
• Einfache randomisierte Algorithmen und ihre Analyse (QuickSelect, Karger-Stein,...).
• Modelle für zufällige Graphen (Erdős–Rényi, Torusmodell).
• Zufallsprozesse und Random Walks.
• Einfache Markov-Prozesse auf endlichen Graphen.
• Analyse einfacher randomiserter Suchheuristiken.

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

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 mündlich.

Wir treffen uns wöchentlich am Dienstag um 17:00 in A-2.2 und Mittwochs um 11:00 in A-1.1. Der erste Termin ist in der ersten Vorlesungswoche, am 18.10.