Seminare – Wintersemester 2018/2019

Aktuelles

  • 25.10.2018

    Bitte reichen Sie Ihren Entwurf und Ihre Gliederung bis spätestens 2.12.2018 ein. Im Abschnitt „Meilensteine im Detail“ des Leitfadens finden Sie weitere Erläuterungen.

    Falls Sie Ihr Thema wechseln möchten, setzen Sie sich bitte möglichst zeitnah mit Ihrem Betreuer in Verbindung. Noch nicht vergebene Themen finden Sie ganz unten auf dieser Webseite.

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), 5 CP
Veranstalter: Mario Holldack, Prof. Dr. G. Schnitger, Hannes Seiwert

Voraussetzungen und nützliche Vorkenntnisse: Sie müssen die Veranstaltungen 'Diskrete Modellierung' sowie 'Datenstrukturen' bestanden haben.
Außerdem werden Vorkenntnisse aus der Veranstaltung GL-1 sowie mathematische Grundkenntnisse nachdrücklich empfohlen.
Für Themen aus dem Bereich der Algorithmen empfehlen sich zudem Vorkenntnisse aus den Veranstaltungen Approximationsalgorithmen oder Effiziente Algorithmen, für Themen aus dem Bereich der Komplexitätstheorie empfehlen sich Vorkenntnisse aus der Theoretischen Informatik 2.

Termine

  • Vorbesprechungen und Themenvergabe:
    Mittwoch, 24.10. um 8:15 in SR 11 (Robert-Mayer-Str. 11–15, Erdgeschoss)
  • Abgabe von Entwurf und Gliederung:
    2. Dezember
  • Zwischenbesprechung:
    10.-14. Dezember (konkreten Termin mit Betreuer absprechen)
  • Abgabe der ersten Versionen von Folien und Ausarbeitung:
    13. Januar
  • Zwischenbesprechung:
    21.-25. Januar (konkreten Termin mit Betreuer absprechen)
  • Abgabe der überarbeiteten Vortragsfolien und der finalen Ausarbeitung:
    10. Februar
  • Vorträge als Blockseminar:
    4. März von 13 bis 18 Uhr sowie 5.-6. März von 8 bis 18 Uhr.
In diesem Infoblatt finden Sie allgemeine Informationen zur Organisation dieses Seminars. Ein ausführlicher Leitfaden mit weiteren organisatorischen Details, Tipps und weiterführender Literatur zum Erstellen guter Vorträge ergänzt das Infoblatt.

Kontakt

Bei Fragen rund um die Veranstaltung helfen Mario Holldack und Hannes Seiwert (Raum 313 bzw. 303 in der Robert-Mayer-Straße 11–15) gerne weiter.

Themen

Eine ausführliche Übersicht der Themen – jeweils mit einer Quellenangabe und einer kurzen Beschreibung – 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).

Algorithmen

  • The Hungarian Method for the Assignment Problem [MH]
  • Matching Is As Easy As Matrix Inversion [MH]
  • An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions [MH]
  • A Universal Algorithm for Sequential Data Compression [MH]
  • Time Bounds for Selection und die Akra-Bazzi-Methode [HS]
  • Improved Analysis of a Max-Cut Algorithm based on Spectral Partitioning [HS]
  • Fast Distributed PageRank Computation [GS]
  • Low-Density Parity-Check Codes [GS]
  • The Small-World Phenomenon: An Algorithmic Perspective
  • Auction algorithms for network flow problems: A tutorial introduction
  • The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
  • SAT-Algorithmen: Schöning-Algorithmus
  • SAT-Algorithmen: Moser-Scheder-Algorithmus

Komplexität

  • A Personal View of Average-Case Complexity [GS]
  • On the Optimality of Bellman-Ford-Moore Shortest Path Algorithm [HS]
  • Tetris is hard, even to approximate [HS]
  • Extended Regular Expressions: Succinctness and Decidability [MH]
  • Smoothed Complexity and Pseudopolynomial-Time Algorithms
  • Not being (super)thin or solid is hard: A study of grid Hamiltonicity
  • Lower Bounds for Monotone Circuits
  • Complexity of Counting and #P-Completeness
  • Algebraic Computation Models
  • The Complexity of Escaping Labyrinths and Enchanted Forests
  • (Interactive Proofs and Graph Isomorphism)