Softwareprojekt über Anwendungen effizienter Algorithmen - SS
2010
Impressum
Termine
Dienstags, 16 Uhr,
Takustraße 9, Seminarraum 055
- Dienstag, 13. 4.: Vorbesprechung und Themenvergabe
- Dienstag, 20. 4.: Einführung in Grundlagen des geometrischen
Rechnens;
Themenbesprechungen, eventuell weitere Themenvergabe
- Dienstag, 27. 4.: Einzelbesprechungen
- Dienstag, 4. 5.: Projektvorstellung
-
Team 6:
Bewegliche Bezeichnungen bei der Luftraumüberwachung
- Dienstag, 11. 5.: Weitere Projektvorstellungen
- Team 2: Optimale Stadt
- Team 4: Triangulierungen mit optimalem Seitenverhältnis
- Dienstag, 18. 5.: Weitere Projektvorstellung
- Team 3: Das Tammes-Problem
- Dienstag, 1. 6.: Abschlusspräsentation
-
Team 6:
Bewegliche Bezeichnungen bei der Luftraumüberwachung
- Dienstag, 22. 6.: Abschlusspräsentation
-
Team 2: Optimale Stadt: Vergleich mit inkrementellen Greedy-Algorithmen
- Dienstag, 13. 7.: Abschlusspräsentation
-
- Team 4: Triangulierungen mit optimalem Seitenverhältnis
- Donnerstag, 15. 7., 16:15 Uhr: Abschlusspräsentation (Nachtrag)
- Team 4A vom WS 09/10: David Breßler, Roland Günther, Max Merkx, Stefan
Nolte, Patrick Remmler
Passt ein regelmäßiges Ikosaeder durch ein gleich großes Ikosaeder?
- Auf unbestimmte Zeit verschoben: Abschlusspräsentation
- Team 3: Das Tammes-Problem
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
Montag,
den 3. 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 2:
Benjamin Dittwald,
Anton Smilevets,
Simon Stapelfeld,
Ulrich Westhoff
-
Team 3:
Jakob Mischek,
Nicolai Steinke,
Lukas Benedix,
Kadir Tugan
-
Team 4:
Markus Decke,
Michael Krüger,
Maximilian Porsch,
René Richter
-
Team 6:
Oliver Erler,
Frederik Feiten,
Robert Kunze,
Hai Nguyen,
Daniel Rhiel,
Maciej Wienszczak.
Themen
- EATCS-Logo: Optimale Approximation von Europa. (für 5–6 Personen)
- Geometrische Approximation
- Übersicht:
Astrid Sturm.
A Survey of Methods for Approximating Curves.
Technical Report ECG-TR-124101-01, Freie Universität Berlin, 2002.
- Optimale Stadt: Vergleich mit inkrementellen Greedy-Algorithmen (für 3–4 Personen)
- Implementierung und Vergleich verschiedener Heuristiken;
verschiedene Zielfunktionen
- Literatur:
Erik D. Demaine, Sándor P. Fekete, Günter Rote, Nils Schweer,
Daria Schymura, and Mariano Zelke.
Integer point sets minimizing average pairwise l1 distance: What
is the optimal shape of a town?
Proceedings of the 21st Canadian
Conference on Computational Geometry, Vancouver, August 17–19, 2009,
4 pages;
erweiterte Fassung.
- Tammes-Problem: n Punkte auf der Kugel mit
größtmöglichem Minimalabstand (für 3–4 Personen)
- geometrisches Rechnen; Optimierung; Rechenexperimente
- Triangulierung einer Punktmenge mit bestmöglichem Seitenverhältnis
(Verhältnis von längster Seite eines Dreiecks zur darauf senkrecht
stehenden Höhe). Visualisierung des Kippbereiches bei drei
gegebenen und einem vierten variablen Punkt. (für 3–4 Personen)
Konstruktion eines Beispiels mit zwei durchgehend verschiedenen
optimalen Triangulierungen (als Basis für einen NP-Schwerheitsbeweis).
- Geometrisches Rechnen; Visualisierung; Grafik
- Experimente
- LMT-Skelett: Yang Dai, Naoki Katoh, Siu-Wing Cheng, LMT-skeleton
heuristics for several new classes of optimal triangulations,
Computational Geometry, Volume 17, Issues 1–2, October 2000, Pages
51–68, doi:10.1016/S0925-7721(00)00016-X.
-
M.T. Dickerson, J.M. Keil and M.H. Montague, A large subgraph of the
minimum weight triangulation. Discrete Comput. Geom. 18
(1997), pp. 289–304. doi:10.1007/PL00009320
- Überblick (zum Vergleich):
Dirk Gerrits, René Gabriëls, Peter Kooijmans.
A Survey of Mesh
Generation Techniques, 25 Seiten.
- Vergleiche auch Abbildung 3 in
Wolfgang Mulzer and Günter Rote:
Minimum-weight triangulation is NP-hard,
Journal of the ACM 55, no. 2 (May
2008), Article 11, 29 pp.
doi:10.1145/1346330.1346336
- Blockieren der Sichtbarkeit durch Kreise (für 3–4 Personen)
- Geometrisches Rechnen; Visualisierung; Grafik; Implementierung von Heuristiken
- Experimente mit verschiedenen Radien
- Nataša Jovanović, Jan Korst, Zharko Aleksovski, Radivoje
Jovanović.
Hiding in the Crowd: Asymptotic Bounds on Blocking Sets.
Proceedings of the 26th European Workshop on Computational Geometry (EuroCG'10),
Dortmund, März 2010, S. 197–200, Herausgeber: Jan Vahrenhold.
- Dynamic Labeling of Moving Points in Air Traffic Control (für 5–7 Personen)
- Map Labeling
- Heuristiken, Grafik, Optimierung
- zur Inspiration:
Mark de Berg, Dirk H.P. Gerrits.
Approximation algorithms for free-label maximization.
Proceedings of the 26th European Workshop on Computational Geometry (EuroCG'10),
Dortmund, März 2010, S. 77–80, Herausgeber: Jan Vahrenhold.
- Verbesserte Realisierung von 3-Polytopen mit kleinen
Koordinaten (für 3–4 Personen)
- LMT-skeleton for locally optimal triangulations with various objectives
- Zerlegung eines Bereichs in zwei kongruente Polygone (für
3–4 Personen: oder mehr: mit Spiegelungen)
- 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.
A. M. Bruckstein and D. Shaked
Crazy cuts: dissecting planar shapes into two identical parts,
in: Mathematics of Surfaces XIII,
Lecture Notes in Computer Science,
Volume 5654
(2009),
Springer Berlin/Heidelberg,
pp. 75–89
- Rhombuszerlegungen in drei Dimensionen
(für
3–4
Personen)
Günter Rote
Last modified: Tue Jul 13 18:32:02 CEST 2010