Praktikum über effiziente Algorithmen - SS 2007

Impressum

Nächste Termine

Dienstags, 16 Uhr, Raum 055
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 2-3 Personen kümmert sich um ein Thema, liest die dazupassende Literatur, teilt sich die Aufgabe in geeignete Teile ein, 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 8. 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


1. Visualisierung des optimalen Spannergraphen mit gewissen Einschränkungen (z.B. Baumstruktur oder Planarität) für 4 (und mehr) Punkte: Drei Punkte werden vorgegeben (sind aber beweglich), die Ebene wird je nach der kombinatorischen Struktur des optimalen Graphen, in Abhängigkeit von der Lage des vierten Punktes, eingefärbt. siehe z.B. Giri Narasimhan and Michiel Smid: Approximating the stretch factor of Euclidean graphs. SIAM J. Comput. 30 (2000), 978-989. Jorge Ariza, Jairo Durango
2. Abzählen von dreidimensionalen Polyominos auf einem Zylinder  (z.B. 4x4)
 Gill Barequet, Micha Moffie, Ares Ribó, and Günter Rote: Counting polyominoes on twisted cylinders
3. Schnittpunkt von Bézier-Splines und B-Splines im Zeichenprogramm ipe siehe z.B. Kenneth I. Joy: CUBIC UNIFORM B-SPLINE CURVE REFINEMENT (lecture notes)
 Frederik Hermans, Damian Schmidt, Pascal Becker
4. Berechnung von Golomb-Maßstäben mit divide&conquer, schneller Fourier-Transformation (FFT) (siehe auch Don Knuth: Bitwise tricks.)
5. Beispiele zur Zerlegung einer Zahlenmenge in drei Mengen mit gleicher Summe mit eindeutiger Lösung.
 Helmut Alt, Hans Bodlaender, Marc van Kreveld, Günter Rote, and Gerard Tel: Wooden geometric puzzles: design and hardness proofs
(siehe auch Don Knuth: Bitwise tricks.)
 Daniel Werner, Maurice Wolter (und evtl. Felix Jachan)
6. Durchschnittsgraphen von Strecken
 Doug West: Open Problems (1991).
Scheinerman's conjecture auf Wikipedia.
Erzeugung planarer Graphen
7. Klassifikation von Sudoku-Aufgaben nach Variabilität des Lösungsweges
 siehe zum Beispiel David Eppstein's Sudoku-Programm
 Roland Höpfner, Michael Krüger, Frederik Kühn
8. Abzählen von Pseudotriangulierungen mit Zickzackpfaden
 Oswin Aichholzer, Günter Rote, Bettina Speckmann, and Ileana Streinu: The zigzag path of a pseudo-triangulation Adrian de Rivero, Alan Akbik (und evtl. Kenar Abdullah)
9. Isotopie zwischen Triangulierungen, mit Anwednung zur Vereinfachung von Landkarten (siehe z.B. Damian Merrick, Martin Nöllenburg, Alexander Wolff, Marc Benkert: Morphing Polygonal Lines: A Step Towards Continuous Generalization, Proc. 23rd European Workshop on Computational Geometry, Graz, März 2007, S. 6-9.
 M. Floater und C. Gotsman, How to morph tilings injectively, Journal of Computational and Applied Mathematics,101 (1999), 117-129.
Craig Gotsman und V. Surazhsky: Guaranteed intersection-free polygon morphing, Computers and Graphics 25 (2001), 67-75.
siehe auch Éric Colin de Verdière, Michel Pocchiola, Gert Vegter: Tutte's barycenter method applied to isotopies, Computational Geometry: Theory and Applications 26 (2003), 81-97.
Vortragsunterlagen über Pseudotriangulierungen, Kapitel 5 und Übungen 11-12.		 Sebastian Dill, Frank Beier, Henning Böhme, Alexander Seibert
10. Entknoten
 Ivan Dynnikov: Arc-presentations of links: Monotonic simplification, Fundam. Math. 190 (2006), 29-76; arXiv:math/0208153

(zum Vergleich: Oliver Dasbach, Stefan Hougardy: Does the Jones Polynomial detect unknottedness?, Experimental Mathematics 6 (1997), 51-56.)


11. Fallende Würfel (Simulation)
 (siehe auch M. Paterson und U. Zwick, Overhang)
 Florian Thiel, Miao Wang und Robert Richter

Günter Rote
Last modified: Mon May 7 23:26:39 CEST 2007