Wintersemester 2006/2007

Prof. Dr.(USA) Martin Dietzfelbinger

Vorlesung: Dienstag, 11.00 - 12.30 Uhr , HU 117

(Ausgewählte Kapitel der Algorithmik)

Randomisierte Hashverfahren: Entwurf, Analyse, Anwendungen

Beginn: 17.10.2006

„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 Realisierungen 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.

Dabei finden verschiedene Bereiche der diskreten Mathematik Verwendung: Kombinatorik/Zählen, Wahrscheinlichkeitsrechnung, endliche Körper, Graphentheorie/Zufallsgraphen. Die notwendigen Werkzeuge werden in der Vorlesung bereitgestellt.

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.

Scheinerwerb: Fachgespräch

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

Literatur: Originalarbeiten.

Die Themen im einzelnen:

1. Universelle Hashklassen - Zweifache Unabhängigkeit:
   Entwurf, Analysemethoden
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
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. Anwendung: Simulation von gemeinsamem Speicher bei Parallelrechnern
10. Anwendung (Algorithmische Geometrie): Finden von nächsten Nachbarn in Punktmengen im mehrdimensionalen Raum.
11. Extractors: Wie man aus ungleichmäßig zufälligen Bitfolgen besser zufällige extrahiert.

Dokumente zur Vorlesung

Existenz von schwachen Expandern

Folien 06.02.2007