Technische Universität Ilmenau

Selected Topics in Complexity Theory / 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 Theory / Algorithmics in degree program Master Informatik 2009
module number232
examination number2200226
departmentDepartment of Computer Science and Automation
ID of group 2242 (Complexity Theory and Efficient Algorithms)
module leaderProf. Dr. Martin Dietzfelbinger
term (unknown)
languageDeutsch
credit points5
on-campus program (h)90
self-study (h)60
obligationelective module
examoral examination performance, 30 minutes
details of the certificate

Findet statt im:  WS 2016/2017, WS 2018/19, SS 2021

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

Für Version 1: Stochastik;  günstig: „Randomisierte Algorithmen“

Für Version 2: „Integrierte Hard- und Softwaresysteme 1“

learning outcome

Version 1: 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. 

Version 2: Boolesche Funktionen: Algorithmen und Komplexität

Fachkompetenz: Die Studierenden kennen die in der Vorlesung vorgestellten Darstellungsformen für Boolesche Funktionen, ihre algorithmischen Eigenschaften sowie die komplexitätstheoretische Einordnung der zugeordneten Berechnungsprobleme. Sie kennen die Konstruktionsalgorithmen für Schaltkreise und die Verfahren zur Manipulation von OBDDS mit ihren Performanzparametern.

Methodenkompetenz: Die Studierenden können die Darstellungen, Konstruktionsmethoden und Algorithmen beschreiben. Sie überblicken die Darstellungsform „OBDD“ mit ihren Vorteilen und Problemen, können somit Systeme, die diese Darstellungsform einsetzen, in ihrem Verhalten besser beurteilen. Sie können die Eigenschaften von Darstellungsformen, Konstruktionsmethoden und Algorithmen präzise benennen und die wesentlichen Beweise nachvollziehen und darstellen. Sie können Konstruktionen variieren und einschätzen, ob dadurch die Gültigkeit der Beweise eingeschränkt wird.

content

Version 1: 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

Version 2: Boolesche Funktionen: Algorithmen und Komplexität

Die Realisierung von Schaltungen für strukturierte oder unstrukturierte Boolesche Funktionen ist die Basis der Konstruktion digitaler Rechner. Diese Veranstaltung bespricht - aus theoretischer Sicht  - Verfahren zur Konstruktion und Manipulation von Darstellungen Boolescher Funktionen und komplexitätstheoretische Grenzen solcher Konstruktionen.
Konkrete Themen:

  • Boolesche Funktionen und Boolesche Formeln
  • Schaltkreise und Straight-Line-Programme
  • Komplexitätsklassen für Boolesche Funktionen
  • Minimierung zweistufiger Schaltkreise (Ermittlung der Primimplikanten,
    Aufbau eines Minimalpolynoms)
  • Konstruktion von Additionsschaltkreisen (Fischer-Ladner)
  • Konstruktion von Multiplikationsschaltkreisen (Karatsuba)
  • Konstruktion von Divisionsschaltkreisen
  • Schaltkreise für die (diskrete) schnelle Fouriertransformation
  • Ordered Binary Decision Diagrams: Datenstruktur für Boolesche Funktionen
  • Minimierung und Reduktion
  • OBDD-Synthese
  • Beispiele für minimierte OBDDs: Addition, Speicheradressierung, Multiplikation u.a.
  • Schaltkreisverifikation mit OBDDs
  • Analyse sequentieller Systeme (Schaltwerke) mit OBDDs
media of instruction and technical requirements for education and examination in case of online participation

zum Moodle-Kurs

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.

 

Version 2: Boolesche Funktionen: Algorithmen und Komplexität

 I.Wegener, Branching Programs and Binary Decision Diagrams -Theory and Applications, SIAM, 2000
C. Meinel, T. Theobald, Algorithmen und Datenstrukturen im VLSI-Design, Springer Verlag, 1988
Originalliteratur, wird in der Vorlesung genannt.

evaluation of teaching

Pflichtevaluation:

Freiwillige Evaluation:

SS 2010 (Vorlesung)

Hospitation: