http://www.tu-ilmenau.de

Logo TU Ilmenau


INHALTE

Ausgewählte Kapitel der Komplexitätstheorie/Algorithmik

Aktuelle Informationen

Die Ankündigung zu den mündlichen Prüfungsterminen finden Sie hier.

Termine

Vorlesung:

Dienstag, 17:00 - 18:30 Uhr, Sr HU 210, Univ.-Prof. M. Dietzfelbinger

Übungen:

Montag (G), 17:00 - 18:30 Uhr, Sr H 1520b, M. Dietzfelbinger

Materialien

Vorlesung

Übung

Inhalt

Hashing: Algorithmen- und Analysetechniken

Hashfunktionen bilden Schlüssel auf eine Indexmenge {1,...,m} ab.

Aus dieser Grundsituation ergeben sich viele Anwendungen und Fragestellungen.

Verschiedene Funktionalitäten, die in der Vorlesung diskutiert werden, sind:

Dynamische Mengen (member-Test)
Wörterbücher (dynamische Abbildungen mit member-Test)
Retrieval (dynamische Abbildungen ohne member-Test)
Approximative Mengen (Bloom-Filter-Funktionalität)
(Minimale) Perfekte Hashfunktionen Analyse von Datenströmen

 Konkrete Themen: Universelles Hashing, Konstruktion universeller Klassen, Anwendungen universeller Klassen: O(1)-Suche und perfekte Hashfunktionen, Momentanalyse bei Datenströmen mit 4-facher Unabhängigkeit, Lineares Sondieren und 5-fache Unabhängigkeit, High-Performance-Hashklassen und ihre Analyse, Verhalten von voll zufälligen Funktionen (Negative Korrelation, Poisson-Approximation, größte Buckets), Simulation von voll zufälligen Funktionen: „Split-and-Share“, das Mehrfunktionen-Paradigma (Bloom-Filter, Cuckoo-Hashing, verallgemeinertes Cuckoo-Hashing), zufällige Hypergraphen, bipartite Graphen, Matrizen, „Retrieval“: Werte ohne Membership-Test, neuere Konstruktionen perfekter Hashfunktionen

In der Vorlesung werden klassische und neue Algorithmen und ihre Analysen besprochen. Die hierfür nötigen Techniken aus der Wahrscheinlichkeitsrechnung, der (Hyper-)Graphentheorie und der Linearen Algebra werden bereitgestellt. - Die Vorlesung bereitet auch auf weiterführende Arbeiten in dem Gebiet vor.