Diplomprüfung Theoretische Informatik Teil 2

Kurs : Algorithmische Geometrie 1840

Datum : 27.09.1999
Zeit : 14.30 Uhr

Dauer : 30 Minuten

Prüfer : Prof. Dr. Rolf Klein

Beisitzer : Dipl. Math. Elmar Langetepe

Note : 1.7

• Wie kann man das dichteste Paar von Punkten in einer Menge naiv berechnen?

Alle Abstände ermitteln und Minimum bilden geht in O(n²).

• Wie geht’s effizienter?

Sweep Algorithmus zur Bestimmung des dichtesten Punktpaares in der Ebene geschildert.

• Welche Datenstrukturen werden eingesetzt?

AVL-Baum für das Verzeichnis mit dem Streifen der Breite MinDistSoFar. Abfrage des Rechtecks d/2d beschrieben und begründet warum nur max. 6 Punkte darin enthalten sein können.

• Wie sieht‘s mit der Laufzeit aus

O(nlogn)

• Warum geht’s nicht schneller?

Weil man sonst das Problem der Epsilon-Closeness auch schneller lösen könnte.

• Was versteht man unter Epsilon-Closeness?

Def. KE1 S.33

• Warum kann man das Problem der Epsilon-Closeness nur in \Omega(nlogn) Zeit lösen?

Korollar mit Beweisansatz über Zusammenhangskomponenten und Entscheidungsbaum zitiert.

• Was ist ein Voronoi Diagramm?

Definition angegeben.

• Zeichnen Sie zu gegebener Punktmenge ein Voronoi Diagramm! (aus 5 Punkten)
• Was können Sie über einen wachsenden Kreis um einen Punkt in einer Voronoi-Region sagen?

Er trifft zuerst genau auf einen Punkt, nämlich den in dessen VR der Kreismittelpunkt liegt. Allgemein gilt: Trifft der Kreis auf zwei Punkte, so liegt der Mittelpunkt auf einer Kante. Trifft der Kreis auf drei oder mehr Punkte, so liegt der Mittelpunkt auf einem Voronoi-Knoten

• Was versteht man unter der Delaunay-Triangulation?

Definition angegeben

• Welche besonderen Eigenschaften der Delaunay Triangulation kennen Sie?

Maximalität der kleinsten Winkel, Umkreis um jedes Dreieck aus DT enthält keinen anderen Punkt aus der zugrundeliegenden Punktmenge.

• Warum gehört die konvexe Hülle immer zur Delaunay-Triangulation?

Begründung: Lemma 5.2

• Erläutern Sie das inkrementelle Verfahren zur Konstruktion einer Delaunay-Triangulation!

Dabei Konflikte, Edge Flips, DAG etc. erläutert. Insbesondere die mittlere Laufzeitver-besserung durch Einführung der Vater-/Stiefvater – Sohnbeziehungen und ihre Abbildung im DAG erklärt. (Hier hatte ich leider einige Lücken – siehe Benotung).

• Garantiert dieses Verfahren eine Laufzeit von O(nlogn)?

Nein! Worst-case ist immer noch O(n²)

• Können Sie dazu ein Beispiel angeben?

Ja! Abbildung 6.11 wiedergegeben.

• Kenne Sie einen Algorithmus der immer aus jedem Labyrinth herausfindet und das nur mit Tastsensor und Winkelmesser?

Pledge Algorithmus erläutert.

• Entkommt der Pledge-Algorithmus auch aus einer rechts gewundenen Spirale?

Prof. Klein hatte eine rechts herum gewundene Spirale gezeichnet und ein Robotersymbol ins Zentrum gezeichnet. Da der Roboter jetzt nur noch rechtsherum laufen konnte, kam er natürlich mit einem erheblich ‚überdrehten‘ Winkelzähler aus der Spirale heraus. Die Lösung ist, das der Roboter mehrmals – und jeweils abwechselnd auf der Innen- und Aussenseite – aus der Spirale heraus und wieder hinein oszilliert bei jeder Bewegung hinein verliert er allerdings eine Umdrehung, so daß er schlußendlich doch entkommt. (Diese Antwort gab Prof. Klein dann selbst, da ich ehrlich gesagt zunächst etwas ratlos war)

• Wie kann man zeigen, dass Pledge immer entkommt?

Skizzenhaftes Erläutern des Beweises zu Theorem 7.1. Ich hatte den Eindruck, ein Hinweis auf Lemma 7.2 hätte ihm schon genügt.

• Kennen Sie die Eulersche Formel?

Leichte Frage zum Schluß...

• Wie zeigt man ihre Korrektheit?

Dto.

Insgesamt verlief auch diese Prüfung in einer angenehmen und ruhigen Atmosphäre. Prof. Klein hat einen bekannt ruhigen Prüfungsstil, die Fragen bauen häufig auf den Antworten des Kandidaten auf und konzentrieren sich bei diesem Kurs offenbar auf die ‚grossen‘ Themen Sweep, konvexe Hüllen, Voronoi-Diagramme, Delaunay-Triangulation und Bewegungsplanung. Man kann eine der Kurseinheiten zu Beginn der Prüfung als nicht prüfungsrelevant deklarieren. Bei vielen Studenten – und auch bei mir – war dies die dritte Kurseinheit.

Von besonderer Wichtigkeit bei dieser Prüfung ist es m.E. kleinere Beispiele für grafische Darstellungen von V-Diagrammen, Delaunay-Triangulationen, Polygonen etc. vorzubereiten. Ebenso kommen grafisch untermauerte ‚Beweise‘ und/oder Komplexitätsabschätzungen ganz gut an (z.B. Abb. 2.5, 4.3, 4.9, 6.11 um nur einige zu nennen). Keine der Begründungen und Beweise mußte dabei formal korrekt ausgeführt werden!

Prof. Klein ist ein empfehlenswerter Prüfer und das Fach ‚Allgorithmische Geometrie‘ ist eine interessante Alternative zu den ‚klassischen‘ Kursen der Theoretischen Informatik, da der Bezug zu praktischen Problemen eigentlich immer gegeben ist.

Viel Erfolg!