Softwareprojekt über Anwendungen effizienter Algorithmen - SS
2008
Impressum
Termine
Dienstags, 16 Uhr, Raum 055
- Dienstag, 15. 4.: Vorbesprechung und Themenvergabe
- Dienstag, 22. 4.: Eventuell Vergabe weiterer Themen für
Nachzügler, individuelle Projektbesprechungen nach Vereinbarung
- Projektpräsentation
Martin Stärk, Andrej Sandorf - Rechteckige Kartogramme
- Dienstag, 29. 4.: keine Projektvorstellungen
- Dienstag, 6. 5.: Projektvorstellungen
- Wladimir Degtjarew, Marco Jeschke, Mohamed Keita, AiQuan Li,
Mikhail Popov, Sebastian Wojtowicz: Fallende Bausteine
- Dominic Christoffel, Johannes Kulick, Tu Nguyen, Stefan
Otte, Alexander Pepper, Matthias Rost: Evakuierung
- Dienstag, 13. 5.: Projektvorstellungen
- Michael Dell, Jonathan Guntermann, Peter Krauß,
Thomas Pilger, Thilo Ratnaweera: Durchdringung von Körpern
- Sina Kewitz, Markus Hoffmann: Sudoku
- Alan Akbik, Marc Berendes, Adrian de Rivero: Abzählen von
Pseudotriangulierungen mit Zickzackpfaden
- Dienstag, 20. 5.: voraussichtlich noch kein Treffen
- Dienstag, 27. 5.: Kein Treffen
- Dienstag, 3. 6.: Zwischenberichte - da sich keine Gruppe
angemeldet hat, findet kein Treffen statt.
- Dienstag, 17. 6.: Zwischenberichte
- Dienstag, 8. 7.: Abschlusspräsentationen
- Dienstag, 15. 7.: (vorläufige) Abschlusspräsentationen
Inhalt
Die Teilnehmer sollen in Teams Verfahren aus verschiedenen Gebieten der
effizienten
Algorithmen implementieren und damit experimentieren. Eine Ausweitung
der Projekte in Studien-, Diplom- oder Masterarbeiten ist
möglich.
Ursprünglich war geplant, dass das
Softwareprojekt auch
Bachelor-Studenten offensteht, und dass sich Teams unter der Leitung
von ein oder zwei Master- oder Diplomstudenten bilden. Die
Bachelor-Studenten, die dieses Softwareprojekt nach dem neuen
Studienplan für ihr Studium
brauchen, beginnen ihr Studium aber gerade erst. Da sich daher kaum
Bachelor-Studenten angemeldet haben, wird der Teilnehmerkreis (wie in
den vergangenen Jahren) vorwiegend aus Diplomstudenten in höheren
Semestern
und aus Masterstudenten bestehen.
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 6. 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?
Themen
- Evakuierung bei Katastrophen, Bewertung des Verkehrsnetzes.
(für 3-6
Personen)
- Beschaffung und Aufbereitung der Daten, (z.B. ATKIS) Graphenalgorithmen,
Experimente und Aufbereitung der Ergebnisse; im Zusammenhang mit
geographischen Informationssystemen
- Literatur: (noch nicht aufgeschrieben, grober Entwurf zu einer verwandten
Fragestellung, nur FU-intern erreichbar; nur die erste Seite ist
relevant.)
- Team: Dominic Christoffel, Johannes Kulick, Tu Nguyen, Stefan
Otte, Alexander Pepper, Matthias Rost
- Simulation fallender Bausteine. (für 4-6 Personen)
- physikalische
Modellierung,
Implementierung des Gauß'schen Prinzip des kleinsten Zwanges.
Schnittstelle mit kommerzieller Software zur quadratischen Optimierung
(CPLEX,
am Institut verfügbar, eventuell in Zusammenhand mit der
Modellierungssprache AMPL oder ZIMPL), Visualisierung
- Literatur: (siehe z. B. M. Paterson und U.
Zwick, Overhang) G.
Rote und U. Zwick, Collapse (in Vorbereitung, Vortrag),
Visualisierung der Animation eines Prototyps
- Team: Wladimir Degtjarew, Alexandre Dupuis, Marco Jeschke,
Mohamed Keita,
AiQuan Li, Mikhail Popov,
Sebastian Wojtowicz
- Passt ein regelmäßiges
Ikosaeder durch ein gleich
großes Ikosaeder? (für 3-4
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
- Team: Michael Dell, Jonathan Guntermann, Peter Krauß,
Thomas Pilger, Thilo Ratnaweera
- Klassifikation von
Sudoku-Aufgaben nach Variabilität des Lösungsweges
- Graphenanalyse; Aufzählungsalgorithmen; Formulierung von
geeigneten Kriterien
- siehe zum Beispiel David
Eppstein's Sudoku-Programm
- Team: Sina Kewitz, Markus Hoffmann; zusätzliche
Teammitglieder sind willkommen.
- Rhombuszerlegungen in drei Dimensionen
(für
3-4
Personen)
- Abzählen von
dreidimensionalen Polyominos auf einem Zylinder (z.B. 4×4)
(für
3-5
Personen)
- Datenstrukturen für kombinatorische Probleme, Umgang
mit
großem Speicherbedarf
- Literatur: (zum Vergleich: Gill Barequet, Micha
Moffie, Ares Ribó, and
Günter Rote: Counting
polyominoes on twisted cylinders)
- Entknoten (für 3-4 Personen)
- Rechteckige Kartogramme. (für 3-4 Personen)
- Modellierung, Datenaufbereitung, Eingabeformat
ArcInfo.
Verarbeitung
geometrischer
Daten, Schnittstelle mit kommerzieller
Software
(CPLEX) oder Ersatz durch freie Software (z. B. SoPlex oder lpsolve), graphische Ausgabe
- Literatur: On Rectangular Cartograms.
M. van Kreveld and B.
Speckmann.
Computational Geometry: Theory and Applications, 37(3):175-187, 2007. A
Linear Programming Approach to Rectangular Cartograms. B. Speckmann,
M. van Kreveld, and S. Florisson.
Proc. 12th International Symposium on Spatial Data Handling (SDH), pp.
527-546, 2006.
- Team: Henning Heinold, Patrick Jungermann, Bogumil Mikolajczyk
- Untere Schranken für on-line q-adische
Überdeckung von Intervallen (state-space
methods)
- Datenstrukturen für kombinatorische Probleme, Umgang
mit
großem Speicherbedarf
- Literatur: Marek Lassak, Janusz Januszewski, Günter
Rote und Gerhard
Woeginger: Solution
to problem 74, Mathematische Semesterberichte 43 (1996), 94-100.
- Matrizenskalierung mit quadratischer Konvergenz.
- Literatur: Martin Fürer: Quadratic Convergence
for the Scaling of Matrices, Proc. 1st ALENEX, 2004, 216-223.
- Unterteilungs-Überzusammensetzungs-Algorithmus für
Nullstellen von Polynomen.
- Verbesserte Realisierung von 3-Polytopen mit kleinen
Koordinaten
- schlechte Beispiele von André Schulz; Dodekaeder
- Literatur: André Schulz: Lifting Planar
Graphs to Realize Integral 3-Polytopes and Topics in
Pseudo-Triangulations (Dissertation)
Günter Rote