Allgemeines: Wir haben etliche Fragen zusammengestellt, die sich chronologisch durch die Vorlesung im ziehen. Beachtet bitte, dass wir in der Prüfung eventuell auch konkrete Instanzen verwenden werden, statt ganz allgemein zu fragen. Zum Beispiel: Analysieren Sie Spiral-STC in diesem Beispiel! Es werden aber auch Beweise abgefragt! 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.

Kap. 1.1/1.2: Labyrinthe, Gitter und Graphen

• Wie arbeitet der Algorithmus von Shannon und welche Aussage kann man bezüglich seiner Güte treffen?
• Definieren Sie den Begriff der Kompetitivität.
• 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 besuchen) in einem Graphen lösen? Wie effizient ist ihre Strategie in Bezug auf den kompetitiven Faktor? Ist Ihre Strategie optimal?
• Wie effizient sind die Strategien DFS und BFS?
• Wenn nur die Knoten des Graphen besucht werden müssen, kann dann die Explorationsaufgabe auf Graphen kompetitiv gelöst werden? Was gilt bei Graphen ohne Mehrfachkanten und ohne Kantengewichte? Was gilt für planare, schlichte Graphen?
• Beweisen Sie: Die vollständige Online Exploration (Rückkehr zum Start) eines Graphen (alle Kanten und Knoten) besucht im Worst-Case doppelt so viele Kanten und Knoten, wie eine optimale Offline-Exploration.
• Wenn der Graph vollständig bekannt ist, was kann man dann über die Explorationsaufgabe bzw. über die Suchaufgabe sagen?

Kap. 1.3 Gitterförmige Umgebungen

• Beschreiben Sie die wesentliche Idee von SmartDFS.
• Geben Sie ein Beispiel an, wo der klassische DFS versagt. 1. Verbesserung? 2. Verbesserung?
• Führen Sie SmartDFS für die angegebene Szene aus.
• Welche Schranke erzielt SmartDFS? Ist diese Schranke scharf?
• Geben Sie eine untere Schranke für den kompetitiven Faktor des Problem an. Konstruieren Sie den Beweis dieser Schranke!
• Skizzieren Sie den Beweis zur Analyse von SmartDFS. Rekapitulieren Sie dazu die benötigten Aussagen (z.B. Offset-Lemma, Excess-Lemma, Kürzester-Weg-Lemma, etc.) und setzen Sie diese Aussagen für den Beweis zusammen!
• Beweisen Sie das Excess-Lemma!
• Beweisen Sie das Kürzester-Weg-Lemma!
• Wie kann man offline den kürzesten Weg in einem Gittergraphen berechnen? Welche Laufzeit hat ihr Verfahren?
• Welchen kompetitiven Faktor garantiert SmartDFS? Wird dieser Faktor erreicht?
• Skizzieren Sie den Beweis zur Kompetitiven Analyse von SmartDFS. Rekapitulieren Sie dazu die benötigten Aussagen (z.B. Narrow Passages Definition, Kanten-Lemma, Exploration-Lemma, etc.) und führen Sie den Induktionsbeweis!
• Wie verhalten sich die Spanning-Tree Algorithmen? Wie ist das zugrundeliegende Robotermodell? Warum versagt der SmartDFS Ansatz bei Gitterpolygonen mit Löchern?
• Skizzieren Sie anhand eines Beispiels, wie in der Analyse der Spanning-Tree Algorithmen wiederholte Besuche einer Zelle gezählt werden. Welche Schranke erzielen wir dabei und in welchem Sinne ist diese Schranke optimal?
• Welchen Kompetitiven Faktor erzielen die Spanning-Tree Algorithmen?
• Welche Idee liegt den Scan Algorithmen zugrunde? Welche Vorausschau nutzt der Agent aus?

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?
• Welche Varianten der eingeschränkten Exploration von Graphen werden unterschieden? Lassen sich die Varianten voneinander ableiten? Wenn ja, wie und mit welcher Einschränkung?
• Zeigen Sie, wie man aus einem Algorithmus der Stromkabel-Variante einen Algorithmus zur Akku-Variante ableiten kann. Um welchen Faktor erhöht sich die Laufzeit. Beweisen Sie den Faktor!
• Zeigen Sie, wie man mit Akku-Größe 4r einen Offline-Explorationsalgorithmus konzipiert, der 6|E| Schritte benötigt.
• Warum sind DFS oder BFS bei der Stromkabel-Variante eher ungeeignet?
• Erläutern Sie die Problematik des Ansatzes nur einen beschränkten DFS zu verwenden.
• Erläutern Sie das Grundprinzip des CFS Algorithmus (DFS, bDFS, Pruning, Merge, Liste von Bäumen). Welche Invarianten (Lemma 1.25) gelten? Skizzieren Sie den Algorithmus an einem Beispiel.
• Schätzen Sie den Aufwand des CFS Algorithmus ab. a) Nach Kantenbesuchen. b) Aufgeteilt in Kanten- und Knotenbesuche.
• Beweisen Sie die Invarianten (Lemma 1.25) des CFS Algorithmus!
• Welche Änderungen werden am Algorithmus vorgenommen, wenn keine Tiefenvorgabe gemacht werden kann? An welcher Stelle ändert sich die Analyse? Welche Laufzeiten garantiert der geänderte Algorithmus?
• Formulieren Sie die Invarianten ohne Tiefenvorgabe!
• Beschreiben Sie den Marker-Algorithmus zum Aufbau einer Karte eines Graphen. Analysieren Sie die Laufzeit! Welche Kosten werden unterschieden? Wie würde man mehrere Marker einsetzen?
• Was ist die lokale zyklische Ordnung an einem Knoten? Warum braucht man stets mindestens einen Marker um für einen Graphen mit lokaler zyklischer Ordnung eine Karte des Graphen durch Navigation aufzubauen?

2.1 Ausweg aus einem Labyrinth

• Erklären Sie die Idee des Pledge Algorithmus. Welches Modell liegt in dieser Problemstellung vor?
• Beweisen Sie die Korrektheit des Pledge-Algorithmus. Rekapitulieren Sie die wesentlichen Aussagen (z.B. Schnittfreiheit etc.) und fügen Sie diese für den Beweis zusammen.
• 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?
• Aus welchen Problemfällen sind die C-Frei und die C-Halb Bedingung jeweils entstanden?
• Beweisen Sie die Korrektheit der Kurve aus der Klasse K. Zeigen Sie, dass eine Kurve aus K schnittfrei sein muss!
• Nach wievielen Kantenbesuchen kann man den normalen Pledge-Algorithmus eigentlich stoppen, wenn die Anzahl der Kanten vorher bekannt gegenen wurde.
• Warum reicht es aus einen Kompass mit einem Fehler von kleiner als 90 Grad zu verwenden, um ein Labyrinth zu verlassen?
• Was sind delta-pseudo-orthogonale Szenen? Welche Bedingungen an Messgenauigkeit, an delta und Abweichung von der Ausgangsrichtung reichen aus, um horizontale und vertikale Kanten zu unterscheiden?

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?
• Was ist eine Out-Position und was ist eine IN-Position? Was gilt für BUG2 in den jeweiligen Szenen und warum?
• Erläutern Sie eine der Strategien VisBug, DistBug und TangentBug und schätzen Sie den Aufwand ab.
• Sind die zugehörigen Schranken scharf? Geben Sie Beispiele an!
• Wie ist der TangentGraph definiert und welche Eigenschaften hat dieser?
• Welche Heuristik kommt zur Bestimmung der Umlaufrichtung zum Einsatz?

2.4 Online Suche

• Warum ist das Suchen eines Zielpunktes in Polygonen 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?
• Formulieren Sie ein Funktional Ihrer Wahl und wenden Sie darauf das Theorem von Gal an!
• Gegeben ist ein konkretes Funktional. Welche Bedingungen müssen gezeigt werden und welcher kompetitiver Faktor ergibt sich dann?
• Beweisen Sie: Es gibt stets eine optimale Strategie für die m-Wege Suche, die zyklisch und monoton ist.
• Was verstehen wir unter 2-Wege Suche mit beschränkter Reichweite? Welche Aussage erlaubt es uns, die optimale Reichweite zu bestimmen und wie wird das dann gemacht?
• Beschreiben Sie die allgemeine Problemstellung, einen Strahl in der Ebene zu finden. Geben Sie eine untere Schranke für dieses Problem an. Beweisen Sie diese Schranke mit den Methoden der Vorlesung!
• Was ist das Window-Shopper Problem? Formulieren Sie die Bedingungen einer optimalen Strategie und zeigen Sie damit, dass diese optimal ist.
• Erläutern Sie die Bedingungen an eine optimale Strategie für das Window-Shopper Problem!
• Welche Strategie würden Sie wählen wenn es nur exakt zwei feste Orte für einen gesuchten Strahl gibt? Können Sie dann den komp. Faktor errechnen, wenn ja, wie?
• Wie ist eine logarithmische Spirale definiert? Wie sieht der worst-case für den kompetitiven Faktor aus? Geben Sie eine Formel dafür an! Warum ist die Spirale eine gute Strategie? Ist die Spirale bereits optimal?
• Was ist eine Straße? Welchen Faktor benötigt man mindestens, um den Zielpunkt der Straße zu suchen? Beweis dazu!
• Begründen Sie, warum es ausreicht, in sogenannten Trichter 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 erhalten bleiben.
• Was ist die verallgemeinerte Untere Schranke und wozu wird diese dann verwendet?
• Wie entstehen die jeweiligen Kurven für die Fälle kleiner und größer 90 Grad. Erläutern Sie die Konstruktion!
• Erläutern Sie das Konzept des Suchpfades. Was ist ein optimaler Suchpfad und was ist ein optimaler Search Ratio? Wie ist der genaue Zusammenhang zum kompetitiven Faktor?
• Geben Sie ein Beispiel für einen optimalen Suchpfad in einer speziellen Umgebung an!
• Welcher Zusammenhang besteht zwischen dem optimalen Search Ratio und einer kompetitiven Exploration bis zu einer bestimmten Tiefe.
• Zeigen Sie die Unterschiede der Approximation des optimalen Search Ratios bei Verwendung eines Agenten ohne Sicht und eines Agenten 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 Search Ratio bis auf 4C bzw. 8C approximieren kann.
• Führen Sie den Beweis mit dem Streckungsfaktor \beta durch. Wozu ist dieser wichtig? Geben Sie ein Beispiel an!
• Wenden Sie das Ergebnis der Beschränkten Exploration in Graphen für die Approximation des optimalen Suchpfades an.
• Geben Sie ein Beispiel für eine Suchaufgabe an, in der der optimale Suchpfad nicht konstant kompetitiv approximiert werden kann. Beweisen Sie Ihre Aussage!

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/Offline-Strategie zur Exploration aus? Welche Güte hat die Online Strategie? Beweis?
• Warum läßt sich diese Idee nicht auf beliebige Polygone übertragen? Was ist bei allgemeinen Polygonen zu tun? Wie wird die Aufgabe formuliert und in welcher Laufzeit kann diese optimal offline gelöst werden?
• Was ist das Problem, wenn man nur um eine Ecke schauen möchte? Geben Sie obere und untere Schranken für eine Online-Strategie dieses Problems an!
• Was ist der Shortest Path Tree innerhalb eines Polygons? Wozu wird dieser in der Online Strategie verwendet?
• Wie wird bei PolyExplore eine Folge von rechten Ecken exploriert? Was muss danach abgeschätzt werden?
• Geben Sie eine untere Schranke für das Online Explorationsproblem an!
• Skizzieren Sie den Beweis der unteren Schranke zur Online Exploration von Polygonen mit Löchern. Welche Schranke wird erzielt?
• Was folgern wir für die Approximation eines optimalen Suchpfades?