Technische Universität Ilmenau

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

Die Modultafeln sind ein Informationsangebot zu unseren Studiengängen. Rechtlich verbindliche Angaben zum Verlauf des Studiums entnehmen Sie bitte dem jeweiligen Studienplan (Anlage zur Studienordnung). Bitte beachten Sie diesen rechtlichen Hinweis. Angaben zum Raum und Zeitpunkt der einzelnen Lehrveranstaltungen entnehmen Sie bitte dem aktuellen Vorlesungsverzeichnis.

Fachinformationen zu Ausgewählte Kapitel der Komplexitätstheorie / Algorithmik im Studiengang Master Informatik 2009
Fachnummer232
Prüfungsnummer2200226
Fakultät
Fachgebietsnummer 2242 (Komplexitätstheorie und Effiziente Algorithmen)
Fachverantwortliche(r)Prof. Dr. Martin Dietzfelbinger
Turnusunbekannt
SpracheDeutsch
Leistungspunkte5
Präsenzstudium (h)90
Selbststudium (h)60
VerpflichtungWahlpflicht
Abschlussmündliche Prüfungsleistung, 30 Minuten
Details zum Abschluss

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

max. Teilnehmerzahl
Vorkenntnisse

Berechenbarkeit und Komplexitätstheorie, Effiziente Algorithmen

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

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

Lernergebnisse

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.

Inhalt

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
Medienformen

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.

 

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.

Lehrevaluation

Pflichtevaluation:

Freiwillige Evaluation:

SS 2010 (Vorlesung)

Hospitation:

Informationen und Handreichungen zur Pflege von Modul- und Fachbeschreibungen durch den Modul- oder Fachverantwortlichen finden Sie auf den Infoseiten zum Modulkatalog.