This site is available only in German.

Seminare – Wintersemester 2017/2018

Aktuelles

02.11. Die Zuordnung zwischen Themen und Betreuern finden Sie unten in der Themenübersicht.

Allgemeines

Bezeichnungen

Seminar "Algorithmen und Komplexität" für Bachelor (B-AK-BS)
Seminar "Komplexität" für Master (KTH-S, M-Theo-SA-S, M-Theo-SB-S)

Veranstaltungsform

Seminar (SWS: 2)
Veranstalter: Mario Holldack, Prof. Dr. G. Schnitger, Hannes Seiwert

Voraussetzungen: Sie müssen die Veranstaltungen 'Diskrete Modellierung' sowie 'Datenstrukturen' bestanden haben.

Termine

  • Obligatorische Zwischenbesprechungen: in der Woche vom 8. bis 12. Januar
  • Abgabe der ausgearbeiteten Vortragsfolien: spätestens am Tag vor der Zwischen-besprechung beim jeweiligen Betreuer per E-Mail
  • Blockseminar: vsl. am 19., 20. und 21. Februar ab 9:15, 14:15 bzw. 9:15 Uhr.
  • Abgabe der Ausarbeitung: nach dem Vortrag (der genaue Zeitpunkt wird noch bekannt gegeben)
Ein Infoblatt wurde in der Vorbesprechung ausgegeben.

Kontakt

Bei Fragen rund um die Veranstaltung helfen Mario Holldack und Hannes Seiwert (Raum 313 bzw. 303 in der RMS 11-15) gerne weiter.

Themen

Eine ausführliche Übersicht der Themen – jeweils mit einer Quellenangabe und einer kurzen Beschreibung – finden Sie in diesem PDF-Dokument. Grau markierte Themen wurden in der Vorbesprechung nicht vergeben. Die Kürzel [GS], [HS] und [MH] stehen für den jeweiligen Betreuer des Themas ([GS] = Georg Schnitger, [HS] = Hannes Seiwert, [MH] = Mario Holldack).

Komplexitätstheorie

  1. Threshold Computation und Postselection
  2. A Personal View of Average-Case Complexity
  3. Zwei-Wege-Automaten – wie stark ist Nichtdeterminismus? [GS]
  4. Lower Bounds for Monotone Circuits
  5. Large Peg-Army Maneuvers [MH]
  6. Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis
  7. Turning Evil Regexes Harmless [MH]
  8. Das Schubfachprinzip: Untere und obere Schranken für die Resolution
  9. On the resolution complexity of graph non-isomorphism
  10. Solving Single-Digit Sudoku Subproblems [MH]

Algorithmen

  1. An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions [GS]
  2. Optimal Partitioning for Dual-Pivot Quicksort [HS]
  3. Train Marshalling Is Fixed Parameter Tractable [GS]
  4. SAT-Algorithmen: Schöning-Algorithmus und Moser-Scheder-Algorithmus
  5. The Byzantine Generals Problem [GS]
  6. Matching Is As Easy As Matrix Inversion
  7. The Power of a Pebble: Exploring and Mapping Directed Graphs [HS]
  8. Faktorgraphen und Belief Propagation auf Bäumen [MH]
  9. Survey Propagation [MH]

Lerntheorie

  1. The Multi-armed bandit Problem: Stochastic bandits [HS]
  2. The Multi-armed bandit Problem: Adversarial bandits
  3. Beat the mean Bandit
  4. A Revealing Introduction to Hidden Markov Models [GS]