Technische Universität Ilmenau

Selected Topics in Complexity/Algorithmics - Modultafeln of TU Ilmenau

The module lists provide information on the degree programmes offered by the TU Ilmenau.

Please refer to the respective study and examination rules and regulations for the legally binding curricula (Annex Curriculum).

You can find all details on planned lectures and classes in the electronic university catalogue.

Information and guidance on the maintenance of module descriptions by the module officers are provided at Module maintenance.

Please send information on missing or incorrect module descriptions directly to modulkatalog@tu-ilmenau.de.

module properties Selected Topics in Complexity/Algorithmics in degree program Master Informatik 2013
module number200075
examination number2200729
departmentDepartment of Computer Science and Automation
ID of group 2242 (Complexity Theory and Efficient Algorithms)
module leaderProf. Dr. Martin Dietzfelbinger
term winter and summer term
languageDeutsch
credit points5
on-campus program (h)67
self-study (h)83
obligationelective module
examoral examination performance, 30 minutes
details of the certificate
alternative examination performance due to COVID-19 regulations incl. technical requirements
signup details for alternative examinations
maximum number of participants
previous knowledge and experience

 

Berechenbarkeit und Komplexitätstheorie

Effiziente Algorithmen

Stochastik;  günstig: "Randomisierte Algorithmen"

learning outcome

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.

content

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

 

media of instruction and technical requirements for education and examination in case of online participation

hauptsächlich Tafelvortrag, teilweise Folien

literature / references

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

evaluation of teaching