|
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 8:30 - 10:00, Hörsaal 1400
Do 8:30 - 10:00, Hörsaal 1400
Beginn: 4. November
|
|
|
Übung:
2 SWS Übung zur Vorlesung
Di 14h c.t. - 16:00, Raum S2225
Beginn: 14. November
Übungsleitung: Ulrich Voll
Ü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:
Kein Skript.
|
|
|
Literatur:
-
R. Motwani, P. Raghavan:
-
Randomized Algorithms
Cambridge University Press, 1995
|
|
|
Sprechstunde:
siehe hier
|
