|
Dozent:
Prof. Dr. Angelika Steger
|
|
|
Bereich:
4+2 SWS Vorlesung im
Bereich Informatik III (Theoretische Informatik)
Vertiefende Vorlesung
im Gebiet Algorithmen
|
|
|
Zeit und Ort:
Di 14h c.t. - 16:00, Hörsaal S0143
Mi 10h c.t. - 12:00, Hörsaal 2710
Beginn: 24. April
|
|
|
Übung:
2 SWS Übung zur Vorlesung
Di 16h c.t. - 18:00, Raum N1124
Übungsleitung: Ingo Rohloff
Übungsschein: Einen Schein erhält, wer
mindestens 40% der Punkte zu den Hausaufgaben erreicht und
erfolgreich an der Semestralklausur teilnimmt.
|
|
|
Hörerkreis:
Studierende im Hauptstudium der Informatik
Studierende mit Nebenfach Informatik
|
|
|
Voraussetzungen:
Stoff des Informatik Grundstudiums
Vorlesung Effiziente Algorithmen und Datenstrukturen I vorteilhaft, aber nicht notwendig.
|
|
|
Empfehlenswert für:
Grundkenntnisse im Bereich Algorithmen
|
|
|
Inhalt:
Für viele Probleme wurden in den letzten Jahren effiziente
randomisierte Algorithmen gefunden, die deterministischen
Verfahren in Bezug auf Laufzeit und/oder benötigte
Hardwareressourcen weit überlegen sind. Oft sind
randomisierte Algorithmen zudem auch viel einfacher zu
analysieren und zu implementieren.
In der Vorlesung werden wir verschiedene Grundprinzipien
randomisierter Algorithmen an Hand von Beispielen
vorstellen. Dabei werden wir uns eng an das Buch
Randomized Algorithms von Motwani und Raghavan
halten.
|
|
|
Weiterführende bzw. verwandte Vorlesungen:
Effiziente Algorithmen und Datenstrukturen I
|
|
|
Skript:
Folien zur Vorlesung:
|
|
|
Literatur:
-
R. Motwani, P. Raghavan:
-
Randomized Algorithms
Cambridge University Press, 1995
|
|
|
Sprechstunde:
siehe hier
|
