Praktikum über effiziente Algorithmen

Impressum

Nächste Termine

Am Beginn des Wintersemesters wird noch einmal ein Nachtragstermin für die Abschlussberichte stattfinden.

Inhalt

Kleine Arbeitsgruppen sollen Verfahren aus verschiedenen Gebieten der effizienten Algorithmen implementieren und damit experimentieren. Eine Ausweitung der Projekte in Studien- oder Diplomarbeiten ist möglich.

Ablauf

Eine kleine Arbeitsgruppe von typischerweise 1-3 Personen kümmert sich um ein Thema, liest die dazupassende Literatur, teilt sich die Aufgabe geeignete Teile ein, und legt in Absprache mit mir das Ziel des Praktikums fest. Zu Beginn des Semesters (in den ersten drei Wochen) werden diese Ziele und Zwischenziele, wenn möglich mit Terminvorgaben, schriftlich festgehalten, stichwortartig auf 1/2 bis 1 Seite Länge, und die Gruppe präsentiert ihr Projekt. Im Laufe des Semesters werden laufend, je nach Fortschritt, Zwischenergebnisse der verschiedenen Projekte präsentiert und diskutiert. Am Ende steht eine Abschlusspräsentation, sowie ein Abschlussbericht von etwa 10 Seiten Länge, der alles Wichtige über die Praktikumsarbeit, und insbesondere, was dabei gelernt wurde, enthalten sollte: Wurden die ursprünglichen Ziele des Praktikums erreicht? Welche Schwierigkeiten sind aufgetreten? Welche alternativen Lösungen wurden verworfen? Was hätte man anders oder besser machen können?

Themen

Abzählen und Aufzählen
1. einfache Kreise, Hamilton'sche Kreise, und Paarungen in planaren Graphen H. Alt, U. Fuchs, K. Kriegel, On the Number of Simple Cycles in Planar Graphs.
In Springer Lecture Notes in Computer Science, Volume 1335, pp. 15-24, Proceedings, Workshop on Graph-Theoretic Concepts in Computer Science - WG '97, Berlin, 1997;
und in Combinatorics, Probability & Computing 8 (5): (1999).
"Transfer matrix method", siehe Doron Zeilberger, Symbol-Crunching with the Transfer-Matrix Method in Order to Count Skinny Physical Creatures, INTEGERS (http://www.integers-ejcnt.org), 0, Article A9 (29 pages) (2000).
Andreas Stoffel, Jens Schönfeld
2. Polyominos Counting polyominoes on twisted cylinders, Gill Barequet, Micha Moffie, Ares Ribó und Günter Rote, Manuskript, Dezember 2004, 29 Seiten.
vorhandene Programme
Frank Viernau, Markus Decke
3. Sudoku-Gitter Mit dem "dancing links"-Algorithmus, siehe http://www-cs-faculty.stanford.edu/~knuth/preprints.html, P159 Christopher Merkel, Marc Kranz, Markus Luszak
4. Sudoku-Gitter durch Graphenisomorphie, mit dem Programm nauty Kaspar Schleiser, Matthias Puech, Lars Kuhnt
(4a. Sudoku-Gitter) Abzählen von Gitterpunkten in Polytopen
5. Triangulierte Flächen Mit einem angepassten "dancing links"-Algorithmus, siehe http://www-cs-faculty.stanford.edu/~knuth/preprints.html, P159 Florian Schilling, Lena Schlipf, Benjamin Jankovic
Triangulierungen mit vorgegebenen Flächeninhalten

6. Die "thrackle"-Vermutung
Richard Hirsch, Jannes Schröter, David Seelbinder

Schneiden


7. mit einem geraden Schnitt:
durch Kreispackungen

Marshall Bern, Erik Demaine, David Eppstein, and Barry Hayes, "A Disk-Packing Algorithm for an Origami Magic Trick," in Proceedings of the 3rd International Meeting of Origami in Science, Mathematics, and Education (OSME 2001), Monterey, California, March 9-11, 2001, pages 17-28.
Ein allgemeiner Übersichtsartikel (survey.pdf, 450MB): Erik Demaine, J. O'Rourke: A Survey of Folding and Unfolding in Computational Geometry.

Britta Weber, Stefanie Frick, Anne Driemel

8. Zerlegung in kongruente Polygone

G. Rote: Decomposition of a polygon into two congruent pieces. (unvollendetes Manuskript)

Kimmo Eriksson: Splitting a polygon into two congruent polygons, American Mathematical Monthly 103 (1996), 393-400.

Benjamin Bartsch
Falten

Erik Demaine's Folding and Unfolding Page

Ein allgemeiner Übersichtsartikel (survey.pdf, 450MB): Erik Demaine, J. O'Rourke: A Survey of Folding and Unfolding in Computational Geometry.


9. Stäbe: mit Pseudotriangulierungen

Ileana Streinu, A Combinatorial Approach to Planar Non-Colliding Robot Arm Motion Planning, Proc. 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA. IEEE Computer Society, 2000, pp. 443-453.
Ausführlichere Fassung: Ileana Streinu: Pseudo-Triangulations, Rigidity and Motion Planning. Manuskript, 51 Seiten.

Zu Implementierungsfragen: Ileana Streinu: Combinatorial Roadmaps in Configuration Spaces of Simple Planar Polygons, in: Saugata Basu and Laureano Gonzalez-Vega (eds.) Proceedings of the DIMACS Workshop on on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science , DIMACS, 2003, pp. 181-206.

zum Vergleich: Animation eines anderen Entfaltungsalgorithmus, von Michael Zilske
weitere Animationen (im SVG-Format)

Adrian de Rivero, Marc Berendes, Alan Akbik

10. Einfalten eines Kreises (oder einer anderen Form)

Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Anna Lubiw, and Godfried T. Toussaint, "Hiding Disks in Folded Polygons," in Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG'98), Montréal, Québec, Canada, August 10-12, 1998.

siehe Verstecken eines Kreises

Ingo Mohr, Tilman Walther und Bettina Selig

(Moleküle)

11. Realisierung eines konvexen Polytops mit gegebenen Flächennormalen und Flächeninhalten Satz von Minkoswki.
J. J. Little. Extended Gaussian images, mixed volumes, and shape reconstruction. In Proc. 1st Ann. Sympos. Comput. Geom., pages 15-23, 1985.
Peter Gritzmann and Alexander Hufnagel, A polynomial time algorithm for Minkowski reconstruction, In Proc. 11th Ann. Sympos. Comput. Geom., 1995, pp. 1-9.
Max Neumann, Robert Hartmann, Sebastian Martens
Bewegungssimulation

12. Metamorphe Polyederketten

Robert Byrnes: Metamorphs, Transforming Mathematical Surprises, Tarquin Publications.

Martin Dittmar, Jan Kettner
13. fallende Würfel Mike Paterson and Uri Zwick, Overhang, SODA'06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete Algorithms, 2006, pp. 231-240.

eine Möglichkeit zur Analyse von Gleichgewichten:
siehe Robert Connelly, Erik D. Demaine, und Günter Rote, Infinitesimally locked self-touching linkages with applications to locked trees, in: "Physical Knots: Knotting, Linking, and Folding Geometric Objects in R3." Editors: Jorge Alberto Calvo, Kenneth C. Millett, and Eric J. Rawdon. Contemporary Mathematics, vol. 304, American Mathematical Society 2002, pp. 287-311.

Marco Walter, Nicolai Kamenzky

Literatur und Verweise

Günter Rote
Last modified: Tue May 2 18:48:43 CEST 2006