Institut für Theoretische Informatik, Algorithmik
Suche
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Lehre
Wintersemester 2010/2011
Seminar Algorithmentechnik

Seminar Algorithmentechnik

Wintersemester 2010/11

Allgemeines

Inhalt

„Computer programming is an art, because it applies accumulated knowledge to the world, because it requires skill and ingenuity, and especially because it produces objects of beauty. A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better.“

Was Donald Knuth im Dezember des Jahres 1974 in seinem Aufsatz „Computer Programming as an Art“ über die Kunst des Programmierens schreibt, bezieht sich nicht zuletzt auf die Schönheit eines eleganten Algorithmen-Entwurfs. Der Programm-Code selbst ist schließlich nur die äußere Form, die der Programmierer der Idee, dem Algorithmus also, gibt. In unserem Seminar wollen wir uns Donald Knuths These anhand von ausgewählten aktuellen Publikationen aus dem Bereich der Algorithmik nähern und uns auf die Suche nach der Kunst im Algorithmen-Entwurf begeben.

Vorläufige Themenliste

Thema Bearbeiter Betreuer Termin Folien Ausarbeitung Literatur
Beyond the flow decomposition barrier Raphael Tanja 26.11. [GR98]
Construction sequences and certifying 3-connectivity Neil Ignaz 26.11. [Sch10]
Approximation algorithms for free-label maximization Frank Andreas 03.12. [dBG10]
Combinatorial curve reconstruction Roman Marcus 03.12. [ABE98]
Lovasz local lemma and satisfiability David Martin 10.12. [pdf] [GMSW09]
Finding strongly knit clusters in social networks Alexander Andrea 10.12. [MSST08]
Maximum flows and parametric shortest paths in planar graphs – Marcus [Eri10]
Instance-optimal geometric algorithms – Marcus [ABC09]
A nearly optimal algorithm for approximating replacement paths – Martin [Ber10]
An Improved LP-based Approximation for Steiner Tree – Andreas [BGRS10]
Dynamic Euclidean minimum spanning trees and extrema of binary functions – Robert [Epp95]
Paired approximation problems – Marcus [Epp10]
Applications of forbidden 0-1 matrices – Marcus [Pet10]

Weitere Themen werden noch bekanntgegeben.

Ablauf

In der Vorbesprechung werden nach einer kurzen Einführung in den Seminarablauf eine Reihe von Themen vorgestellt und unter den Teilnehmern aufgeteilt. Nach drei Wochen der Einarbeitung stellen die Teilnehmer ihr Thema in Form eines Kurzvortrages von etwa 5 Minuten vor. Anschließend folgen an regelmäßigen wöchentlichen Terminen die Hauptvorträge. An jedem Seminartermin finden ein bis zwei Vorträge statt. Ferner ist eine schriftliche Ausarbeitung in LaTeX zu erstellen, die das Thema übersichtlich zusammenfasst.

Beachtet bitte die Hinweise zur Zeitplanung und zur Gestaltung des Vortrags und der Ausarbeitung.

Termine

Datum Thema
22.10. Vorbesprechung
12.11. Kurzvorträge
26.11. Hauptvorträge
03.12. Hauptvorträge
10.12. Hauptvorträge
31.01. Ausarbeitung

Literatur

Artikel sind größtenteils aus dem Uninetz erreichbar.

[ABC09] Peyman Afshani, Jeremy Barbay, and Timothy M. Chan. Instance-optimal geometric algorithms. In FOCS ’09: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 129–138, Washington, DC, USA, 2009. IEEE Computer Society.
[ABE98] Nina Amenta, Marshall Bern, and David Eppstein. The crust and the β-skeleton: combinatorial curve reconstruction. Graph. Models Image Process., 60(2):125–135, 1998.
[Ber10] Aaron Bernstein. A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010.
[BGRS10] Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvo, and Laura Sanit. An Improved LP-based Approximation for Steiner Tree. In 42th ACM Symposium on Theory of Computing (STOC 2010, Best Paper Award), 2010.
[dBG10] Mark de Berg and Dirk Gerrits. Approximation algorithms for free-label maximization. In Haim Kaplan, editor, Algorithm Theory - SWAT 2010, volume 6139 of Lecture Notes in Computer Science, pages 297–308. Springer Berlin / Heidelberg, 2010.
[Epp95] D. Eppstein. Dynamic Euclidean minimum spanning trees and extrema of binary functions. Discrete and Computational Geometry, 13:111–122, 1995.
[Epp10] David Eppstein. Paired approximation problems and incompatible inapproximabilities. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010.
[Eri10] Jeff Erickson. Maximum flows and parametric shortest paths in planar graphs. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010.
[GMSW09] Heidi Gebauer, Robin Moser, Dominik Scheder, and Emo Welzl. The Lovasz local lemma and satisfiability. In Susanne Albers, Helmut Alt, and Stefan Näher, editors, Efficient Algorithms, volume 5760 of Lecture Notes in Computer Science, pages 30–54. Springer Berlin / Heidelberg, 2009.
[GR98] Andrew V. Goldberg and Satish Rao. Beyond the flow decomposition barrier. J. ACM, 45(5):783–797, 1998.
[Mos09] Robin A. Moser. A constructive proof of the Lovasz local lemma. In STOC ’09: Proceedings of the 41st annual ACM symposium on Theory of Computing, pages 343–350, New York, NY, USA, 2009. ACM.
[MSST08] Nina Mishra, Robert Schreiber, Isabelle Stanton, and Robert E. Tarjan. Finding strongly knit clusters in social networks. Internet Mathematics, 5(1):155–174, January 2008.
[Pet10] Seth Pettie. Applications of forbidden 0-1 matrices to search tree and path compression-based data structures. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010.
[Sch10] Jens Schmidt. Construction sequences and certifying 3-connectivity. Algorithmica, pages 1–17, 2010.