Selected Topics in Complexity / Algorithmics - Interactive curriculae of TU Ilmenau

Berechenbarkeit und Komplexitätstheorie

Effiziente Algorithmen

Stochastik;  günstig: "Randomisierte Algorithmen"

Moderne Hashverfahren

Fachkompetenz:  Die Studierenden kennen die in der Vorlesung vorgestellten Konstruktionen und Beweise im Gebiet moderner Hashverfahren. Sie kennen die notwendigen Grundlagen aus der linearen Algebra und der Wahrscheinlichkeitsrechnung.

Methodenkompetenz: Die Studierenden können die Konstruktionsmethoden beschreiben, ihre Eigenschaften (insbesondere Zuverlässigkeitsaussagen) präzise benennen und die wesentlichen Beweise nachvollziehen und wiedergeben. Sie können Konstruktionen variieren und einschätzen, ob dadurch die Gültigkeit der Beweise eingeschränkt wird. Sie können die Praktikabilität der Verfahren einschätzen.

Sozialkompetenz: Selbst in der Vorlesung ist Interaktion stets möglich, ja erwünscht, damit sind die Studierenden vertraut. Die Studierenden haben die Erfahrung gemacht, dass Fragen unmittelbar geklärt werden, dass Diskussionen auf Augenhöhe stattfinden und Beiträge wertschätzend aufgenommen werden. In der Übung waren die Studierenden zu Präsentationen aufgerufen. Sie konnten wertvolle Erfahrung in der Rolle des Präsentierenden sammeln. Die Teilnahme erforderte und trainierte ein hohes Maß an Selbstorganisation.

Moderne Hashverfahren

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
  

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, 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

hauptsächlich Tafelvortrag, teilweise Folien

Version 1: Moderne Hashverfahren

• M. Mitzenmacher, E. Upfal, Probability and Computing, Cambridge University Press, 2005
  

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

• Originalliteratur, wird in der Vorlesung genannt