Allgemeines: Wir haben etliche Fragen zusammengestellt, die sich chronologisch durch die Vorlesung im SS07 ziehen. Beachtet bitte, dass wir in der Prüfung eventuell auch konkrete Instanzen verwenden werden, statt ganz allgemein zu fragen. Zum Beispiel: Analysieren Sie Spirac-STC in diesem Beispiel!
Und: Diese Liste hat natürlich keinen Anspruch auf Vollständigkeit!!!! Die Übungen gehören ebenfalls zum Prüfungsstoff. Wer regelmäßig die Übungen besucht hat, sollte damit keine Probleme haben.
Bei sehr gut verlaufenden Prüfungen werden wir am Ende zwei relativ schwere Fragen aus dem Stoff der Vorlesung/Übungen stellen. Zumindest eine davon sollte zufriedenstellend beantwortet werden, um eine 1.0 Benotung zu rechtfertigen.

1.1-1.2 Labyrinthe und Gitter

• Erläutern Sie den Unterschied zwischen Labyrinth, Labyrinthgraph, Gittergraph, planarer Graph und allgemeiner Graph.
• Was ist der Unterschied zwischen Explorieren eines Graphen und Suchen nach einem Ziel in einem Graphen? Welche Aufgabe ist leichter in Bezug auf Kompetitivität?
• Wie würden Sie die Online Explorationsaufgabe (alle Kanten und Knoten) in einem Graphen lösen? Wie effizient ist ihre Strategie? Ist Ihre Strategie optimal?
• Wenn nur die Knoten des Graphen besucht werden müussen, kann dann die Explorationsaufgabe auf Graphen kompetitiv gelöst werden? Was gilt bei Graphen ohne Mehrfachkanten und ohne Kantengewichte? Was gilt für planare Graphen?
• Beweisen Sie: Die vollständige Online Exploration (Rückkehr zum Start) eines (Labyrinth-)Graphen (alle Kanten und Knoten) besucht im Worst-Case doppelt so viele Kanten und Knoten, wie eine optimale Exploration.
• Definieren Sie den Begriff der Kompetitivität.
• Wenn der Graph vollständig bekannt ist, was kann man dann über die Explorationsaufgabe bzw. über die Suchaufgabe sagen?

1.3 Gitterförmige Umgebungen

• Beschreiben Sie die wesentliche Idee von SmartDFS.
• Zeigen Sie ein Beispiel, wo der klassische DFS versagt. 1. Verbesserung? 2. Verbesserung?
• Führen Sie SmartDFS für die angegebene Szene aus.
• In welchem Sinne ist SmartDFS optimal?
• Geben Sie eine untere Schranke für den kompetitiven Faktor des Problem an. Skizzieren Sie den Beweis dieser Schranke!
• Skizzieren Sie die Beweisidee zur Analyse von SmartDFS.
• Wie verhalten sich die SpanningTree Algorithmen? Wie ist das zugrundeliegende Robotermodell? Warum versagt der SmartDFS Ansatz?
• Welche Arten von Kanten unterscheiden wir bei den Spanning Trees und wie geht diese Unterscheidung in die Analyse der Algorithmen ein?
• Skizzieren Sie anhand eines Beispiels, wie in der Analyse der SpanningTree Algorithmen wiederholte Besuche einer Zelle gezählt werden. Welche Schranke erzielen wir dabei und in welchem Sinne ist diese Schranke optimal?
• Welche Idee liegt den Scan Algorithmen zugrunde?
• Wie ist die zentrale Aussage der Scan Algorithmen?

1.4 Eingeschränkte Exploration von Graphen

• Was verstehen wir unter beschränkter Exploration eines Graphen? Warum ist es sinnvoll, ein solches Modell zu betrachten? Wie verhält sich dieser Ansatz zum normalen DFS?
• Erläutern Sie die Problematik des Ansatzes einen beschränkten DFS zu verwenden.
• Erläutern Sie das Grundprinzip des CFS Algorithmus. Welche Invarianten gelten? Skizzieren Sie den Algorithmus an einem Beispiel.
• Schätzen Sie den Aufwand des CFS Algorithmus ab.

2.1 Ausweg aus einem Labyrinth

• Erklären Sie die Idee des Pledge Algorithmus. Welches Modell liegt in dieser Problemstellung vor?
• Warum ist der Pledge Algorithmus korrekt? Welche wesentliche Eigenschaft eines zurückgelegten Pfades nutzen wir aus?
• Führen Sie den Pledge Algorithmus in der angegebenen Szene aus!
• Welche Probleme können bei der realen Umsetzung des Pledge Algorithmus die Korrektheit zerstören?
• Welche formalen Bedingungen an eine Kurve C reichen aus, damit der Roboter, der dieser Kurve folgt, das Labyrinth verläßt? Skizzieren Sie den Beweis für diese Aussage!
• Welche Schlußfolgerungen können wir aus den Bedingungen zur Korrektheit ziehen?
• Nach wievielen Kantenbesuchen kann man den normalen Pledge-Algorithmus stoppen!

2.2-2.3 Navigation mit Tastsensoren und beschränkter Sicht

• Welches Modell wird hier betrachtet? Skizzieren Sie den Beweis der unteren Schranke zu diesem Problem!
Erläutern Sie eine der Strategien Bug1, Bug2, Wechsel1 und Wechsel2 und schätzen Sie den Aufwand ab. Welche generelle Beweisidee steckt dahinter? Erläutern Sie eine der Strategien VisBug, DistBug und TangentBug und schätzen Sie den Aufwand ab.
• Sind die zugehörigen Schranken scharf?
• Wie ist der TangentGraph definiert und welche Eigenschaften hat dieser?
• Welche wesentlichen Züge weist eine Strategie in diesem Modell auf, welche Fragen sind also immer zu beantworten?
• Welche Heuristik kommt zur Bestimmung der Umlaufrichtung zum Einsatz?

2.4 Online Suche

• Warum ist das Suchen eines Zielpunktes im Allgemeinen nicht kompetitiv?
• Was ist die beste Suchstrategie für die m-Wege Suche? Beweisen Sie den Faktor, der erreicht wird. Ist die optimale Strategie eindeutig?
• Was ist eine Straße? Welchen Faktor benötigt man mindestens, um den Zielpunkt der Straße zu suchen? Beweis!
• Begründen Sie, warum es ausreicht, in sogenannten Funnel Polygonen nach dem Ausgang zu suchen.
• Skizzieren Sie die Idee, die hinter der optimalen Strategie zur Suche in Straßen steckt. Welche Bedingungen müssen für ein Wegstück w gelten, a) wenn die Bezugspunkte des Funnels wechseln, b) wenn die Bezugspunkte des Funnels bleiben.
• Was ist die verallgemeinerte Untere Schranke und wozu wird diese dann verwendet?
• Erläutern Sie das Konzept des Suchpfades. Was ist ein optimaler Suchpfad und was ist ein optimaler Search Ratio? Wie ist der Zusammenhang zum kompetitiven Faktor?
• Geben Sie ein Beispiel für einen optimalen Suchpfad an!
• Welcher Zusammenhang besteht zwischen dem optimalen Suchradius und einer kompetitiven Exploration bis zu einer bestimmten Tiefe.
• Zeigen Sie die Unterschiede der Approximation des optimalen Suchradius bei Verwendung eines blinden Roboters (nicht: Blindenroboter) und eines Roboters mit Sicht, falls eine kompetitive beschränkte Exploration vorausgesetzt werden kann.
• Beweisen Sie, dass unter den oben gegebenen Umständen die Doubling Strategie den optimalen Suchradius bis auf 4C bzw. 8C approximieren kann.
• Führen Sie den Beweis mit dem Streckungsfaktor \beta durch.
• Wenden Sie das Ergebnis der Beschränkten Exploration in Graphen für die Approximation des optimalen Suchpfades unter an.

2.5 Online Exploration

• Welche Strecken müssen besucht werden, wenn ein einfaches Polygon vollständig exploriert werden soll.
• Was ist der Vorteil bei rechtwinkeligen Polygonen? Wie sieht hier die Online-Strategie zur Exploration aus?
• Warum läßt sich diese Idee nicht auf beliebige Polygone übertragen?
• Was ist der Shortest Path Tree innerhalb eines Polygons?
• Skizzieren Sie den Beweis der unteren Schranke zur Online Exploration von Polygonen mit Löchern.
• Welche Folgerung ziehen wir daraus bezüglich der Approximation des Search Ratios?