Technische Universität Ilmenau

Ausgewählte Kapitel der Komplexitätstheorie/Algorithmik - Modultafeln der TU Ilmenau

Die Modultafeln sind ein Informationsangebot zu den Studiengängen der TU Ilmenau.

Die rechtsverbindlichen Studienpläne entnehmen Sie bitte den jeweiligen Studien- und Prüfungsordnungen (Anlage Studienplan).

Alle Angaben zu geplanten Lehrveranstaltungen finden Sie im elektronischen Vorlesungsverzeichnis.

Informationen und Handreichungen zur Pflege von Modulbeschreibungen durch die Modulverantwortlichen finden Sie unter Modulpflege.

Hinweise zu fehlenden oder fehlerhaften Modulbeschreibungen senden Sie bitte direkt an modulkatalog@tu-ilmenau.de.

Modulinformationen zu Ausgewählte Kapitel der Komplexitätstheorie/Algorithmik im Studiengang Master Informatik 2013
Modulnummer200075
Prüfungsnummer2200729
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 2242 (Komplexitätstheorie und Effiziente Algorithmen)
Modulverantwortliche(r)Prof. Dr. Martin Dietzfelbinger
Turnusganzjährig
SpracheDeutsch
Leistungspunkte5
Präsenzstudium (h)67
Selbststudium (h)83
VerpflichtungWahlmodul
Abschlussmündliche Prüfungsleistung, 30 Minuten
Details zum Abschluss
Alternative Abschlussform aufgrund verordneter Corona-Maßnahmen inkl. technischer Voraussetzungen
Anmeldemodalitäten für alternative PL oder SL
max. Teilnehmerzahl
Vorkenntnisse

 

Berechenbarkeit und Komplexitätstheorie

Effiziente Algorithmen

Stochastik;  günstig: "Randomisierte Algorithmen"

Lernergebnisse und erworbene Kompetenzen

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.

Inhalt

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

 

Medienformen und technische Anforderungen bei Lehr- und Abschlussleistungen in elektronischer Form

hauptsächlich Tafelvortrag, teilweise Folien

Literatur

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

Lehrevaluation