Arbeitsgruppe Algorithmen und Komplexität

Daten zum Seminar "Algorithmen & Komplexität" (WS 2014/15)

Informationen werden im Laufe des Semesters hinzugefügt.

Weitere Informationen befinden sich auf der Seite zur Organisation unserer Seminare.

Inhalt

Abgabetermine und Semesterplan

Die Abgabe sollte per Email an die Betreuer bis 12:00 Uhr mittags des jeweiligen Tages erfolgen.

Datum Termin
  Einlesen, Erarbeiten Ausarbeitungsgerüst (21 Tage)
Mo 17. 11.

individuell
Abgabe Ausarbeitungsgerüst (Zusammenfassung, Einleitung, Gliederung, Stichworte, Bibliographie)

Besprechung Ausarbeitungsgerüst
  Erstellung Ausarbeitung (21 Tage)
Mo 8. 12.

individuell
Abgabe Ausarbeitung (Erstversion)

Besprechung Ausarbeitung
  Überarbeitung Ausarbeitung (14 Tage)
Mo 22. 12.
Di 09. 01.
Abgabe Ausarbeitung (Review-Version)
Zuteilung Reviews
  Review (7 Tage)
Mo 19. 01. Abgabe der Reviews
  Überarbeitung Ausarbeitung (7 Tage)
Mo 26.01 Abgabe Ausarbeitung (Endversion)
  Ausarbeitung des Vortrags (14 Tage)
Mo 09. 02.15

individuell
Abgabe des Vortragsmaterials (Erstversion)

Besprechung des Vortragsmaterials
09.02. - 22.02.15 keine Bearbeitung während der Prüfungen
  Überarbeitung des Vortrags (10 Tage)
Do 05. 03.

Mo 09.03.,
Di 10.03.15
Abgabe des Vortagsmaterials (Endversion)

Blockveranstaltung mit Vorträgen

 

 

Themenliste

Dies ist eine Auswahl von Quellen, die für das Seminar verwendet werden können. Die meisten Arbeiten können aus dem Netz der Universität heruntergeladen werden. Sie können aber auch in Papierform bei den Betreuern eingesehen werden.

  1. F. Luccio: Algorithms, nymphs, and shepherds.
  2. G. Aloupis, E. Demaine, A. Guo, G. Viglietta: Classic Nindendo games ar (computationally) hard.
  3. R. Fleischer: Die another day.
  4. G. Viglietta: Gaming is a hard job, but someone has to do it!
  5. G. Viglietta: Lemmings is PSPACE-complete.
  6. F. Fomin, P. Heggernes, E. van Leeuven: Making life easier for firefighters.
  7. P. Boldi, M. Santini, S. Vigna: Measuring with jugs or what if mathematicians were asked to defuse bombs.
  8. T. Tamir: Scheduling with bully selfish jobs.
  9. D. Eppstein: solving single-digit Sudoku subproblems.
  10. M. Lampis, V. Mitsou: The ferry cover problem.
  11. H. Essed, W.Therese: The harrased waitress problem.
  12. A. Itai, M. Rodeh, H. Shachnai: The passport control problem or how to keep a dynamic service system load balanced?
  13. L. Brueggeman, M. Fellows, R. Fleischer, M. Lackner, C. Komusiewicz, Y. Koutis, A. Pfandler, F. Rosamond: Train marshalling is fixed parameter tractable.