Randomisierte Algorithmik
- Type: Vorlesung / Übung (VÜ)
-
Chair:
KIT-Fakultäten - KIT-Fakultät für Informatik - Institut für Theoretische Informatik - ITI Bläsius
KIT-Fakultäten - KIT-Fakultät für Informatik - Institut für Theoretische Informatik - ITI Wagner - Semester: WS 23/24
-
Time:
Di 24.10.2023
08:00 - 09:30
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Do 26.10.2023
11:30 - 13:00, wöchentlich
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Do 02.11.2023
11:30 - 13:00, wöchentlich
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Di 07.11.2023
08:00 - 09:30
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Do 09.11.2023
11:30 - 13:00, wöchentlich
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Do 16.11.2023
11:30 - 13:00, wöchentlich
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Di 21.11.2023
08:00 - 09:30
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Do 23.11.2023
11:30 - 13:00, wöchentlich
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Do 30.11.2023
11:30 - 13:00, wöchentlich
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Di 05.12.2023
08:00 - 09:30
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Do 07.12.2023
11:30 - 13:00, wöchentlich
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Do 14.12.2023
11:30 - 13:00, wöchentlich
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Di 19.12.2023
08:00 - 09:30
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Do 21.12.2023
11:30 - 13:00, wöchentlich
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Do 11.01.2024
11:30 - 13:00, wöchentlich
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Di 16.01.2024
08:00 - 09:30
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Do 18.01.2024
11:30 - 13:00, wöchentlich
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Do 25.01.2024
11:30 - 13:00, wöchentlich
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Di 30.01.2024
08:00 - 09:30
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Do 01.02.2024
11:30 - 13:00, wöchentlich
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Do 08.02.2024
11:30 - 13:00, wöchentlich
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Di 13.02.2024
08:00 - 09:30
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
Do 15.02.2024
11:30 - 13:00, wöchentlich
50.34 Raum 236
50.34 INFORMATIK, Kollegiengebäude am Fasanengarten (2. Obergeschoss)
-
Lecturer:
TT-Prof. Dr. Thomas Bläsius
Maximilian Katzmann
Dr. Stefan Walzer
Prof. Dr. Peter Sanders
Hans-Peter Lehmann - SWS: 3
- Lv-No.: 2400153
- Information: Präsenz
Diese Vorlesung wird in Kooperation mit der Gruppe von TT-Prof. Dr. Thomas Bläsius gehalten. Die Website zur Vorlesung befindet sich auf der Website der Gruppe Bläsius.
Inhalt |
Randomisierte Algorithmen und Datenstrukturen machen ihr Vorgehen von Zufallsexperimenten abhängig. Während der Entwurf deterministischer Algorithmen oft von einer pessimistischen Sicht auf Worst-Case Verhalten getrieben ist, greifen randomisierte Algorithmen auf Ansätze zurück, die zwar gelegentlich versagen aber meistens wesentlich besser abschneiden. Die Laufzeit solcher Algorithmen sowie die Lösungsqualität (im Falle von Optimierungsproblemen) und manchmal auch die Korrektheit (im Falle von Berechnungsproblemen) sind dann dem Zufall unterworfen. Eine formale Analyse nimmt daher Erwartungswerte und Erfolgswahrscheinlichkeiten in den Blick. Wir werden uns sowohl klassischen Beispielen als auch aktuellen Forschungsthemen aus dem Bereich Hashing und der Graphentheorie widmen. Hierbei kommen spezifische Entwurfsmethoden (wie Probability Amplification) und fortgeschrittene Analysewerkzeuge der Wahrscheinlichkeitstheorie (etwa Coupling, Poissonisierung und Konzentrationsschranken) zur Anwendung. Oft wird sich zeigen, dass randomisierte Ansätze effizienter oder einfacher sind als alle (oder zumindest alle bekannten) deterministischen Ansätze. Kurz werden wir zudem auf theoretischer Seite betrachten, wie sich randomisierte Komplexitätsklassen zu bekannten Klassen wie P und NP verhalten, und auf praktischer Seite klären, wie man randomisierte Algorithmen auf gängigen (im Wesentlichen deterministisch arbeitenden) Computern mit Pseudozufall implementieren kann. Lernziele: Die Studierenden - verstehen, wann und warum Randomisierung zur Lösung eines algorithmischen Problems nützlich oder notwendig ist, - können zentrale Entwurfsmethoden und Analysewerkzeuge der randomisierten Algorithmik erklären, - können einfache randomisierte Algorithmen und Datenstrukturen zur Lösung eines Problems entwerfen und erklären, - können entscheiden, welche Werkzeuge sich für die Analyse gegebener randomisierter Algorithmen und Datenstrukturen eignen und diese anwenden. Arbeitsaufwand: Vorlesung mit Übung mit 3 SWS, 5 LP
ca. 30h Prüfungsvorbereitung Empfehlungen: Grundkenntnisse über Algorithmen und Datenstrukturen (z.B. aus den Vorlesungen Algorithmen 1 + 2) sowie Grundlagen aus der Wahrscheinlichkeitstheorie (bspw. aus der Vorlesung Einführung in die Stochastik) sind hilfreich. |
Vortragssprache | Deutsch/Englisch |