Seminare – Wintersemester 2016/2017

Aktuelles

Die Vorträge finden
  • am 23.01. von 9:15 bis 14:00 Uhr in SR 307 (RMS 11-15) und
  • am 25.01. von 8:30 bis 12:00 Uhr sowie von 14:45 bis 18:15 Uhr in K III (Neue Mensa)
zu den folgenden Themen statt:

Montag, 23.01.2017:
- Fun with semirings
- Faktorgraphen und Belief Propagation auf Bäumen
- Gaming is a hard job, but someone has to do it
- Classic Nintendo Games are (Computationally) Hard

Mittwoch, 25.01.2017:
- The Complexity of Weighted Greedy Matching
- Künstliche Neuronale Netze
- Alternation
  (Mittagspause)
- Rechnen mit Licht
- A Fast Quantum Mechanical Algorithm for Database Search
- Closed Timelike Curves Make Quantum and Classical Computing Equivalent

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 finden in der Woche vom 12. bis 16.12.2016 statt. Die Abgabe der Vortragsfolien erfolgt bis spätestens 09.01.2017 beim jeweiligen Betreuer per E-Mail.

Das Blockseminar findet am 23. und 25.01.2017 statt.

Ein Infoblatt wird in der Vorbesprechung ausgegeben.

Ablauf

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.

Berechnungswelten und (un)gewöhnliche Berechnungsmodelle

  1. Fun with semirings: a functional pearl on the abuse of linear algebra (Bachelor) [MH]
  2. Faktorgraphen und Belief Propagation auf Bäumen (Bachelor) [MH]
  3. A Fast Quantum Mechanical Algorithm for Database Search (Bachelor, Master) [HS]
  4. Closed Timelike Curves Make Quantum and Classical Computing Equivalent (Bachelor, Master) [HS]
  5. Threshold Computation und Postselection (Bachelor, Master)
  6. Rechnen mit Licht (Bachelor, Master) [MH]
  7. Infinite-Time Turing Machines (Bachelor, Master) [HS]
  8. A Personal View of Average-Case Complexity (Bachelor, Master) [HS]
  9. Alternation (Bachelor, Master) [GS]
  10. Zwei-Wege-Automaten – wie stark ist Nichtdeterminismus? (Bachelor)

Komplexität: Untere Schranken und Schwierigkeit von Problemen

  1. The Byzantine Generals Problem (Bachelor) [GS]
  2. Lower Bounds for Monotone Circuits (Bachelor)
  3. Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Bachelor, Master)
  4. Gaming is a hard job, but someone has to do it (Bachelor, Master) [MH]
  5. Classic Nintendo Games are (Computationally) Hard (Bachelor, Master) [MH]

Klassische und brandaktuelle Algorithmen

  1. The Hungarian Method for the Assignment Problem (Bachelor) [MH]
  2. Künstliche Neuronale Netze (Bachelor) [GS]
  3. The Complexity of Weighted Greedy Matching (Bachelor, Master) [HS]
  4. An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions (Bachelor, Master)
  5. Greedy Algorithms for Steiner Forest (Master)