Softwareprojekt über Anwendungen effizienter Algorithmen - SS
2009
Impressum
Termine
Dienstags, 16 Uhr,
geändert: Takustraße 9, Seminarraum 055
Arnimallee 3, Seminarraum 210
- Dienstag, 14. 4.: Vorbesprechung und Themenvergabe
- Dienstag, 21. 4.: Themenbesprechungen, eventuell weitere Themenvergabe
- Dienstag, 28. 4.: Themenbesprechungen, erste Projektvorstellungen?
- Dienstag, 5. 5.:
Themenbesprechungen, Präsentationen der Aufgabenstellungen,
Abschlusspräsentation vom vorigen Semester:
-
Zählen von dreidimensionale Polyominos auf dem
verdrillten Torus
(Jan Frederik Boldt,
Christian Kopf,
Christopher König,
Frank Schulze,
Florian Thiemer)
- Dienstag, 12. 5.: Präsentation der Aufgabenstellungen
- Team 1: Abzählen von Pseudotriangulierungen mit Zickzackpfaden
- Dienstag, 19. 5.: Präsentationen der Aufgabenstellungen
- Team 6: Passt ein regelmäßiges Ikosaeder durch ein gleich großes Ikosaeder?
- Team 3: Matrizenskalierung mit quadratischer Konvergenz
- Team 7: Zerlegung eines Polygons in zwei kongruente Polygone
- Team 4: Matrizenskalierung durch Netzwerkfluss
- Dienstag, 26. 5.: Präsentationen der Aufgabenstellungen
- Team 2: Der Unterteilungs-Überzusammensetzungs-Algorithmus
zum Schnitt von Bézier-Splines
- Dienstag, 23. 6.: Einzelbesprechungen
- Dienstag, 7. 7.:
Vorläufige Abschlusspräsentation
- Team 1: Abzählen und Optimieren von
Pseudotriangulierungen mit Zickzackpfaden
- Dienstag, 14. 7.:
(Vorläufige) Abschlusspräsentation
- Dienstag, 21. 7.:
Abschlusspräsentationen
- Team 1: Abzählen und Optimieren von
Pseudotriangulierungen mit Zickzackpfaden (Nachtrag)
- Team 2: Der Unterteilungs-Überzusammensetzungs-Algorithmus
zum Schnitt von Bézier-Splines
- Team 3: Matrizenskalierung mit quadratischer Konvergenz
- Team 4: Matrizenskalierung durch Netzwerkfluss
- Team 6: Passt ein regelmäßiges Ikosaeder durch ein gleich großes Ikosaeder?
- Weitere
Abschlusspräsentationen im Herbst
- Team 1: Abzählen und Optimieren von
Pseudotriangulierungen mit Zickzackpfaden (Nachtrag)
- Team 2: Der Unterteilungs-Überzusammensetzungs-Algorithmus
zum Schnitt von Bézier-Splines
- Team 3: Matrizenskalierung mit quadratischer Konvergenz
- Team 4: Matrizenskalierung durch Netzwerkfluss (Algorithmus 3)
- Team 6: Passt ein regelmäßiges Ikosaeder durch ein gleich großes Ikosaeder?
- Team 7: Zerlegung eines Polygons in zwei kongruente Polygone
Inhalt
Die Teilnehmer sollen in Teams Verfahren aus
verschiedenen Gebieten der effizienten Algorithmen implementieren und
damit experimentieren. Eine Ausweitung der Projekte in Bachelor-, Studien-,
Diplom- oder Masterarbeiten ist möglich. Das Softwareprojekt
steht sowohl Bachelor- als auch Master-Studenten offensteht, und es sollen sich gemischte
Teams unter der Leitung von ein oder zwei Master- oder Diplomstudenten
bilden.
Ablauf
Eine Arbeitsgruppe von typischerweise 5-10 Personen (je nach Umfang der
Aufgabe) kümmert
sich um ein Thema, liest die dazupassende Literatur, teilt sich die
Aufgabe in geeignete Teile ein, verteilt die Aufgaben und Rollen unter
sich, und legt in Absprache mit mir das Ziel
des
Praktikums fest. Zu Beginn des Semesters (in den ersten drei Wochen, d.h. bis
Dienstag,
den 5. Mai)
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?
Teams
- Team 1:
Philipp Cordes,
Arne Müller,
Andrej Sandorf.
- Team 2:
Christian Harwardt,
Ella Maria Kadas,
Tobias Ludwig,
Conrad Strathausen,
Kamil Adam Tarach.
- Team 3:
Selimkhan Achmerzajev,
Felix Langner,
Christoph Sackl.
- Team 4:
Paul Donners,
Dustin Eversmann,
Liqing Gao,
Wei Huang,
Zehe Wu.
- Team 6:
Christian Gätcke,
Cosima Hoffmann,
Thomas Pilger,
Frank Tiemann.
- Team 7:
Patrick Oliver Einig,
Robert Fels,
Franz Gatzke,
Norman Warnatsch.
Themen
- Abzählen und Optimieren von
Pseudotriangulierungen mit Zickzackpfaden. (für 6-8 Personen)
- Unterteilungs-Überzusammensetzungs-Algorithmus für
Nullstellen von Polynomen (für 3-4 Personen)
und zum Schnitt von Bézier-Kurven (insgesamt für 5-6 Personen)
- Matrizenskalierung mit quadratischer Konvergenz (für 3-4 Personen)
- numerisches Rechnen, lineare Algebra
- Literatur: Martin Fürer: Quadratic Convergence
for the Scaling of Matrices, Proc. 1st ALENEX, 2004, 216-223.
- Matrizenskalierung und biproportionale Wahlsysteme (für 3-5 Personen)
- Flüssen in Netzen
- Exaktes Rechnen mit Langzahlarithmetik
- Einbettung in das Java-Paket
BAZI
(Berechnung von Anzahlen mit Zuteilungsmethoden im Internet)
- Literatur:
Günter Rote und Martin Zachariasen,
Matrix scaling by
network flow.
In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), New Orleans, January 2007, pp. 848-854. doi:10.1145/1283383.1283474
- Verbesserte Realisierung von 3-Polytopen mit kleinen
Koordinaten (für 3-4 Personen)
- schlechte Beispiele von André Schulz; Dodekaeder
- Literatur: André Schulz: Lifting Planar
Graphs to Realize Integral 3-Polytopes and Topics in
Pseudo-Triangulations (Dissertation)
- Passt ein regelmäßiges
Ikosaeder durch ein gleich
großes Ikosaeder? (für 3-5
Personen)
- geometrische Konstruktionen im Raum
- Man kann in einen Würfel ein Loch bohren, durch das
man
einen gleich großen Würfel hindurchschieben kann. Geht das
auch mit anderen Körpern?
- Algorithmus für den Test, ob ein konvexes Polygon in
ein anderes hineinpasst: Bernard Chazelle, The polygon containment
problem. Advances in Computing Research, Vol. I: Computational
Geometry, (F.P. Preparata, Ed.), JAI Press, 1983, S. 1-33. Siehe auch
F. Avnaim and J. D. Boissonnat, Polygon placement under translation and
rotation, 5th Annual Symp. on Theoretical Aspects of Computer Science,
Bordeaux, February 11-13, 1988, Lectures Notes in Comp. Science 294,
Springer-Verlag, New-York, 1988, 322-333.
Roman Waupotitsch: Rotating a convex
polygon in a convex polygon, Diplomarbeit, Technische
Universität Graz, 1988.
K. A. Post. Triangle in a triangle: On a problem of Steinhaus.
Geometriae Dedicata 45 (1993), 115–120. doi:10.1007/BF01667408
- Zerlegung eines Bereichs in zwei kongruente Polygone (für 3-4 Personen)
- Vergleich verschiedener Algorithmen-Varianten
- Umgang mit ungenauen Daten
- Literatur:
Dania El-Khechen, Thomas Fevens, John Iacono und Günter Rote:
Partitioning a polygon into two mirror congruent pieces.
In: Proceedings of the 20th Canadian Conference on Computational Geometry, Montréal, August 13-15, 2008, pp. 131-134.
Kurzversion,
Langversion
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.
- Rhombuszerlegungen in drei Dimensionen
(für
3-4
Personen)
- Entknoten (für 3-4 Personen)
- Distance-avoiding sets in the plane, chromatic number
- Crossing number with rules +/0/- (Braß, Moser, Pach)
Günter Rote