Wintersemester 2008/2009
Prof. Dr. (USA) M. Dietzfelbinger

[Mitteilungen] [Inhalte] [Termine] [Scheinerhalt] [Literatur] [Materialien]

Mitteilungen

Beginn:

Hörer: Informatik-Studierende im Hauptstudium, die eine Vertiefung im Bereich "Algorithmik" (insbesondere Randomisierte Algorithmen) anstreben.Die Vorlesung dient auch der Vorbereitung auf Studien- und Diplomarbeiten im Fachgebiet.

Vorkenntnisse: Algorithmen, Grundlagen der Stochastik/Wahrscheinlichkeitsrechnung

Inhalte

(Ausgewählte Kapitel der Algorithmik)
Randomisierte Hashverfahren: Entwurf, Analyse, Anwendungen

"Hashing" oder "Schlüsseltransformation": Aus einem Schlüssel x, einem Namen, der etwa einen Datensatz oder eine Speicherzelle identifiziert, wird ein Index h(x) berechnet. Idealerweise ist h(x) ein "zufälliger" Wert.
In der Vorlesung werden verschiedene Konstruktionen beschrieben, die dieser Annahme der Zufälligkeit nahe kommen und es werden Konsequenzen aus verschiedenen Graden der Zufälligkeit hergeleitet. Weiter werden Anwendungen von Hashfunktionen beschrieben, von Realisierung der klassischen Datentypen "Menge" und "Wörterbuch" über "Bloom-Filter" (approximative Darstellung von Mengen - wichtig in Netz-Anwendungen) bis hin zu Techniken für die Verbesserung von "schlechten" Zufallszahlen.

Die Themen im einzelnen:

1. Universelle Hashklassen - Zweifache Unabhängigkeit: Entwurf, Analysemethoden, Einfache Anwendungen
2. Universelle Hashklassen - d-fache Unabhängigkeit: Polynomielle Hashklassen, Matrixbasierte Konstruktionen
3. High-Performance Hashklassen - (fast) zufälliges Verhalten
4. Perfektes Hashing: Konstruktion von injektiven Funktionen mit konstanter Auswertezeit und mit geringem Platzbedarf
5. Analyse von idealem (vollständig zufälligem) Hashing: Verteilung der Fachgrößen
6. Cuckoo-Hashing: konstante Zugriffszeit im schlechtesten Fall
7. Verallgemeinerungen von Cuckoo-Hashing: d-äres Cuckoo Hashing und das Two-Choice-Paradigma
8. Bloom-Filter: platzsparendes Speichern von Mengen
9. Anwendungen (Komplexitätstheorie): Pseudozufallszahlen-Generatoren
10. Anwendungen (Algorithmische Geometrie): Finden von nächsten Nachbarn in Punktmengen im mehrdimensionalen Raum
11. Extractors: Wie man aus ungleichemäßig zufälligen Bitfolgen besser zufällige extrahiert.
    

Termine

• Vorlesung
• Donnerstag, 9:00-10:30 Uhr, Sr Bi 13
  

Kriterien für den Scheinerhalt

Scheinerwerb: Fachgespräch

Prüfungsrelevanz: SK oder EK "Komplexitätstheorie und Effiziente Algorithmen" in der Vertiefungsgebietsprüfung.

Literatur und Links

Materialien und Übungsblätter