Praktikum Effiziente Algorithmen

• SWS: 3P
• Zeit: Do 15-18
• Ort: Takustraße 9, SR 055
• Vorbesprechung: Donnerstag 25.10., 15 Uhr c.t.

Inhalt

Ablauf

Themen

• Auseinanderfalten von Polygonen

Zwei ebene Polygone mit derselben Folge von Seitenlängen können immer stetig ohne Selbstüberlappung ineinander transformiert werden, wenn man die Kanten als Stäbe fester Länge betrachtet, die an den Ecken beweglich miteinander verbunden sind. Für diesen Vorgang gibt es verschiedene Algorithmen, die implementiert werden können. (Für einige Beispiele gibt es Animationen, die aus einer vorläufigen Implementierung entstanden sind.)
• Kanonische Pseudotriangulierungen

Eine Pseudotriangulierung einer ebenen Punktmenge ist etwas ähnliches wie eine Triangulierung, d.h. eine Zerlegung der Ebene in Gebiete. Die Menge aller Pseudotriangulierungen lässt sich auf eine gewisse indirekte Art durch lineare Ungleichungen beschreiben. Indem man ein lineares Programm löst, kann man gewisse Pseudotriangulierungen auszeichnen. Welche Pseudotriangulierungen dabei herauskommen, ist noch nicht untersucht.
• Realisierung orientierbarer Matroide

 
• Das Assoziaeder

Das Assoziaeder ist ein schönes kombinatorisches und geometrisches Objekt. Es ist ein Polytop, dessen Ecken die Triangulierungen eines konvexen Polygons repräsentieren, und dessen Kanten den Triangulierungen entsprechen, die durch Kippen einer Kante auseinander hervorgehen. Auch viele andere sogenannte Catalan-Strukturen werden dadurch dargestellt, wie zum Beispiel binäre Bäume oder die Möglichkeiten, ein nichtassoziatives Produkt  a*b*c*d*e  zu klammern (daher der Name Assoziaeder). Es gibt verschiedene geometrische Realisierungen des Assoziaeders, unter anderem eine neue. Diese Polytope sollen dargestellt (zum Beispiel mit polymake) und miteinander verglichen werden.
• Wege in Chirotopen

Ein Chirotop gibt die Orientierung aller Dreiecke einer ebenen Punktmenge an (und analog für Punktmengen in höheren Dimensionen). (In Wirklichkeit sind Chirotope noch etwas allgemeiner.) Wenn man die Punkte bewegt, ändert sich das Chirotop nur lokal. Für kleine Punktmengen und kleine Dimensionen gibt es eine Liste aller Chirotope. Es soll untersucht werden, mit wievielen lokalen Änderungen man von einem Chirotop zu einem anderen kommen kann.
• Optimale Zufallsstrategien für Suchprobleme

Gewisse Optimierungsaufgaben lassen sich als Suchprobleme auf einem Würfel darstellen, dessen Kanten orientiert sind, sodass gewisse Eigenschaften gelten (z.B. dass der Würfel und jede Seite des Würfels eine eindeutige Senke (Ecke ohne ausgehende Kanten) hat. Das Bestimmen einer optimalen randomisierten Strategie zum Finden der Senke kann man mit Hilfe der Spieltheorie als (riesiges) lineares Programm formulieren. Für gewisse Varianten wurde dieses Problem bereits gelöst. Andere Fragen, zum Beispiel die Bestimmung aller optimalen Strategien, sind noch offen.
• Der Expansionskegel in höheren Dimensionen

Der Expansionskegel beschreibt alle (Richtungen von) Bewegungen einer Punktmenge, bei denen sich alle Punkte voneinander entfernen. In der Ebene kennt man die Struktur dieses Kegels genau, bicht jedoch bei räumlichen Punktmengen.
• Realisierung von dreidimensionalen Polytopen mit kleinen Koordinaten

Es gibt ein Verfahren, das jeden gegebenen kombinatorischen Typ eines Polytops mit n Seiten so realisiert, dass die Koordinaten der Ecken ganze Zahlen mit höchstens O(n²) Bits sind. Hier soll man versuchen verschiedene Polyeder (zum Beispiel das Pentagondodekaeder) mit möglichst kleinen Koordinaten darzustellen.
• Optimierung von Roboterbahnen

Voraussetzungen

Perspektiven: