This site is available only in German.

Seminare – Wintersemester 2018/2019

Aktuelles

  • 14.02.2019
    Das Blockseminar findet am 4. März von 13 bis ca. 16:30 Uhr und am 5. März von 9 bis ca. 16:30 Uhr, jeweils in SR 307, statt. Die Liste der Vorträge finden Sie ganz unten auf dieser Webseite.

  • 04.02.2019
    Die Abgabefrist für die überarbeiteten Vortragsfolien und die finale Ausarbeitung wurde um eine Woche verlängert.
    Der neue Abgabetermin ist der 17.02.2019.

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 17. Februar
  • Vorträge als Blockseminar:
    4. März von 13 bis ca. 16:30 Uhr und 5. März von 9 bis ca. 16:30 Uhr, jeweils in SR 307
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.

Terminplan

Montag, 4. März, 13 Uhr bis ca. 16:30 Uhr in SR 307
  1. Matching Is As Easy As Matrix Inversion
  2. An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions
  3. On the Optimality of Bellman-Ford-Moore Shortest Path Algorithm
Dienstag, 5. März, 9 Uhr bis ca. 16:30 Uhr in SR 307
  1. Fast Distributed PageRank Computation
  2. Improved Analysis of a Max-Cut Algorithm based on Spectral Partitioning
  3. Spektrale Algorithmen für das binäre Paintshop-Problem

    Mittagspause

  4. Heuristiken für das binäre Paintshop-Problem
  5. Algebraic Computation Models
  6. A Personal View on Average-Case Complexity