Dozent: PD Dr. R. Neininger
Zeit: Di 14:15 - 15:45
Ort: 711 (klein)
Thema
Bei der "Stochastischen Analyse von Algorithmen'' werden grundlegende algorithmische Probleme der Mathematischen Informatik, etwa das Auswählen oder Suchen in Datenmengen, das Sortieren von Daten, Probleme der kombinatorischen Optimierung oder die Effizienz von Datenstrukturen unter probabilistischen Modellannahmen untersucht. Dabei kann ein Algorithmus deterministisch sein, die Eingabe aber als zufällig angenommen werden, oder der Algorithmus selbst zufällig sein (randomisierter Algorithmus). Untersucht werden Laufzeit, Speicherplatzbedarf oder die Anzahl elementarer Operationen (Schlüsselvergleiche, rekursive Aufrufe), die der Algorithmus benötigt. Das asymptotische Verhalten von Erwartungswerten, Varianzen und Verteilungen dieser Größen ist dann zentral, um Algorithmen auf quantitativer Grundlage beurteilen zu können.
In der Vorlesung werden eine Reihe einfacher stochastischer Sachverhalte erarbeitet (z.B. zum Verhalten von Galton-Watson Bäumen, von einfachen Irrfahrten, Spiegelungsprinzip, Eigenschaften der Entropie, first/second moments method), die für sich bereits interessant sind, dann aber auch gewinnbringend bei der Analyse von Algorithmen eingesetzt werden.
Scheinerwerb
Schicken
Sie mir bitte gegebenenfalls Ihre für den Schein relevanten Daten
(Name, Matrikelnummer, Geburtstag) per E-mail zusammen mit möglichen
Terminen.
Fragen zum Scheinerwerb
Drei der 13 Fragen werden zufällig zum Gespräch ausgewählt
(mit dem Statistikpaket R mit dem Befehl "sample(13,3);").
Termine
Skript zur Vorlesung
Abschnitt 1, Teil 1 [1.9 MB]
Abschnitt 1, Teil 2 [2.1 MB]
Abschnitt 2, Teil 1 [1.9 MB]
Abschnitt 2, Teil 2 [1.8 MB]
Abschnitt 3 [2.7 MB]
Abschnitt 4 [2.4 MB]
Abschnitt 5 [0.3 MB] OO Beweis der Existenz und Form optimaler Couplings
Ralph Neininger