Softwareprojekt über Anwendungen effizienter Algorithmen - WS
2012/13
Impressum
Termine
Dienstags, 16–19 Uhr,
Takustraße 9, Seminarraum 049
- Dienstag, 16. 10.: Vorbesprechung und Themenvergabe
- Dienstag, 23. 10.: eventuell weitere Themenvergabe, Einzelbesprechungen
- Dienstag, 30. 10.: Projektvorstellungen, Einzelbesprechungen
- Dienstag, 6. 11.: Projektvorstellungen
- Team 1 (Punkte in möglichst allgemeine Lage bringen)
- Team 5 (Überholen)
- Team 3 (Kurvenapproximation)
- Dienstag, 13. 11.: Projektvorstellung
- Team 2 (Trennung von Voronoi-Gebieten)
- Dienstag, 27. 11.: Zwischenpräsentationen
- Team 2 (Trennung von Voronoi-Gebieten)
- Dienstag, 4. 12.: Zwischenpräsentation
- Dienstag, 11. 12.: Zwischenpräsentation
- Dienstag, 8. 1. 2013: Zwischenpräsentationen
- Team 1 (Punkte in möglichst allgemeine Lage bringen)
- Team 3' (Kurvenapproximation)
- Dienstag, 15. 1. 2013: Abschlusspräsentationen
- Dienstag, 22. 1. 2013: Abschlusspräsentationen
- Dienstag, 29. 1. 2013: Abschlusspräsentationen
- Team 2: Trennung von Voronoi-Gebieten
- Dienstag, 5. 2. 2013: Abschlusspräsentationen
- Dienstag, 12. 2. 2013: Abschlusspräsentationen
- Team 1 (Punkte in möglichst allgemeine Lage bringen)
- Dienstag, 26. 2. 2013: Abschlusspräsentationen
- Team 3' (Kurvenapproximation)
- Team 5 (Überholen)
Inhalt
Die Teilnehmer sollen in Teams Verfahren aus
verschiedenen Gebieten der effizienten Algorithmen für geometrische Aufgaben implementieren und
damit experimentieren. Eine Ausweitung der Projekte in Bachelor- oder Masterarbeiten ist möglich. Das Softwareprojekt
steht sowohl Bachelor- als auch Masterstudenten offen, und es sollen sich gemischte
Teams unter der Leitung von ein oder zwei Masterstudenten
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
Mittwoch, den 12. November)
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:
Marco Gester,
Daniel Jentsch,
Hongliang Jiang,
Simon Putzke,
Andrej Szaffranietz,
Stephan Zeisberg.
- Team 2:
Martin Gebert,
Sascha Schreckenbach,
Jonathan Sharyari.
- Team 3:
Stefan Behrendt,
Ralf Öchsner,
Ying Wei,
(Anja Cerceja,
Christoph Michel).
- Team 5:
Matthias Kupferschmidt,
Marlina Spanel,
Yusuf Karabulut.
Themen
- Punkte in allgemeine Lage bringen (für 3–7 Personen)
- Ein Spiel, das man für einen interaktiven Wettbewerb verwenden
könnte: Man soll n Punkte so zeichnen und verschieben, dass
sie in möglichst "allgemeiner Lage" sind: Das kann zum
Beispiel heißen, dass der vollständige Graph (oder ein anderer
gegebener Graph), wenn er mit geraden Strecken gezeichnet wird,
möglichst große Abstände zwischen den Ecken und Kanten (oder auch
zwischen Schnittpunkten von Kanten) haben soll, oder dass alle Winkel
möglichst verschieden von 0 und 180 Grad, oder voneinander sind.
- Damit das Spiel Spaß macht, soll es Hilfen für den Benützer geben:
Der kleinste Winkel, kleinste Abstand, usw. soll sichtbar angezeigt werden.
Man soll gewisse Strecken oder Winkel starr machen können, sodass
man Teilmengen als ganze verschieben kann.
- Das Programm soll möglichst portabel sein.
- Trennung von Voronoi-Gebieten
(für 3–7 Personen)
- Es gibt eine Vermutung, dass man
n gegebene rote Punkte R in der Ebene immer durch
höchstens
n blaue Punkte B "trennen" kann, sodass
im Voronoidiagramm von
R vereinigt mit
B
keine zwei roten Gebiete benachbart sind.
Andererseits vermutet man, dass es nie mit weniger als
n blauen Punkten geht, außer wenn die roten Punkte auf
einer Geraden liegen.
Diese Vermutungen sollen experimentell untersucht werden.
- Geometrische Bibliotheken (CGAL)
- Optimierung, lokale Verbesserung
- kombinatorische Optimierung, Mengenüberdeckungsproblem
- Software für ganzzahlige lineare Optimierung,
CPLEX,
Gurobi,
FICO-Xpress
- Computerexperimente
- Blocking Delaunay Triangulations.
O. Aichholzer, R. Fabila-Monroy, T. Hackl, M. van Kreveld, A. Pilz,
P. Ramos, und B. Vogtenhuber.
Proc. Canadian Conference on Computational Geometry, CCCG 2010, Winnipeg, August 911, 2010.
- Approximation von Punktfolgen durch Spline- oder Kreisbogenketten
(für 3–7 Personen)
-
Beispiel: Man zeichnet den Graphen einer Funktion, oder eine einfache
Kurve wie eine Hyperbel mit Mathematica oder
Maple, als Polygonzug.
Dann möchte man dieses Bild in einem Zeichenprogramm weiterverarbeiten
(zum Beispiel in Ipe),
aber man möchte es möglichst kompakt speichern, bei vorgegebener
Fehlertoleranz.
- Material über Bézier-Splines findet man im Netz und in Büchern.
- Literatur über biarcs: siehe zum Beispiel
Approximation
of an open polygonal curve with a minimum number of circular arcs
and biarcs
Diese Literatur ist nur zur Inspiration gedacht. Im Gegensatz zu den hier dargestellten Algorithmen geht es im Projekt um einfache Heuristiken.
- Übersicht:
Astrid Sturm.
A Survey of Methods for Approximating Curves.
Technical Report ECG-TR-124101-01, Freie Universität Berlin, 2002.
- Realisierung von triangulierten dreidimensionalen Polytopen mit kleinen
Koordinaten (für 4–6 Personen)
- Optimales Überholen von Autos (für 4–6 Personen)
- Bewegungsplanung für Roboter
- Rechnen in einem fünfdimensionalen Konfigurationsraum
- Dynamische Programmierung, Bellman'sches Optimalitätprinzip
- Raum-Zeit-Diagramm
- Simulation
- Visualisierung
- Tripartites Matching von Punkten im Raum
Günter Rote
