http://www.tu-ilmenau.de

Logo TU Ilmenau


Ihre Position

INHALTE

Ausgewählte Kapitel der Komplexitätstheorie/ Algorithmik

Mitteilungen

Termine

Vorlesungen Univ.-Prof. M. Dietzfelbinger :

Dienstag, 17:00 - 18:30 Uhr, Sr K 2016

Donnerstag, 9:00 - 10:30 Uhr, Sr H 1518

Materialien

0. Kapitel: Einführung und Beispiele

Druckversion

Blätterversion

2. Kapitel: Pseudozahlen nach Chor/Goldreich und nach Nisan

Druckversion

Inhalt

Moderne Hashverfahren

Hashfunktionen bilden Schlüssel auf eine Indexmenge [m]={0,...,m-1} ab.

Aus dieser Grundsituation ergeben sich viele Anwendungen und Fragestellungen.

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

- Dynamische Mengen (Einfügen, Löschen, 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

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.

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

Tabulation Hashing und Varianten

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

Literatur:

M. Mitzenmacher, E. Upfal, Probability and Computing, Cambridge University Press, 2005. Neue Auflage: 2017.

R. Motwani und P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.

Originalliteratur, wird in der Vorlesung genannt.