Seminar Algorithmik
| Semester | |
| Module # | INF-ALG-019 |
| Event # | INF-ALG-019 |
| Programmes | Diplom Informatik, Computer Science Master, Business Information Systems Master, Computer and Communication Systems Engineering Bachelor, Computer and Communication Systems Engineering Master, Electrical Engineering Bachelor, Electrical Engineering Master |
| IBR Group | ALG (Prof. Fekete) |
| Type | Seminar |
| Lecturer | |
| Assistant | Dr. Christiane Schmidt Ehemalige Wissenschaftliche Mitarbeiterin |
| Credits | 4 |
| Hours | 0+2 |
| Time & Place | Die Vorbesprechung findet am 09.04.2008 in Room 262A statt. In einer Blockveranstaltung am 19.06.2008 ab 14 Uhr werden die Vorträge gehalten. Die Abgabe der Ausarbeitungen muss bis zum 05.06.2008 erfolgen. |
| Certificates | Schriftliche Ausarbeitung und erfolgreicher Seminarvortrag. Die Note wird abhängig von der aktiven Teilnahme am Seminar sowie der Qualität des Vortrages und der Ausarbeitung bestimmt. Vortrag: Ihr Vortrag sollte ca. 45-60 Minuten dauern. Das Medium ist frei, Sie können also Tafel, Overhead-Projektor, Beamer mit PowerPoint, Beamer mit PDF, oder was auch immer Sie sinnvoll finden, einsetzen. Natürlich sollten Sie bei exotischen Wünschen diese erstmal mit dem Betreuer klären, und unbedingt auch Programm-, Programmversions- und sonstige Kompatibilitätsfragen besprechen. Ausarbeitung: Schreiben Sie eine Ausarbeitung, die Sie zwei Wochen vor dem Vortrag abgeben. Die Ausarbeitung soll ca. 5 Seiten lang sein. Generell interessiert uns aber, dass Sie da eine selbstverfasste Zusammenfassung eines selbst verstandenen Artikels abgeben. Mehr als zehn Seiten sollten es dennoch nicht werden, immerhin geht es hier um die Kunst des Zusammenfassens. |
| Content | Das Seminar Algorithmik im Sommersemester 2008 beschäftigt sich mit einer Reihe von aktuellen Artikeln, die relativ wenig an Vorwissen erfordern. Schwerpunkt sind diesmal geometrische Themen und solche, bei denen es um die Lösung von Problemen mit unvollständiger Information geht; letztere sind verwandt mit dem Inhalt der aktuellen Vorlesung "Online-Algorithmen". Zu tun hat man es dabei mit Problemen wie (1) dem Gassiführen eines Hundes an einer Leine beschränkter Länge, (2) dem Finden eine Kreis- oder (3) Ellipsenmitteplunkts, (4) dem Kauf einer BahnCard, (5) Bewegungsplanung für Roboter in geometrischer Umgebung oder (6) in Gittern, (7) die Koordination von Robotern, (8+9) dem Vergleich von Kurven, oder (10) der Exploration von Graphen. Unten beschrieben sind die Originalauszüge der Autoren zu den eigenen Artikeln, die jeweils auf englisch erschienen, aber von überschaubarer Länge sind. |
Thema 4: The Bahncard ProblemIn this paper, we generalize the Ski-Rental Problem to the Bahncard Problem which is an online problem of practical relevance for all travelers. The Bahncard is a railway pass of the Deutsche Bundesbahn (the German railway company) which entitles its holder to a 50% price reduction on nearly all train tickets. It costs 240DM, and it is valid for 12 months. Similar bus or railway passes can be found in many other countries. For the common traveler, the decision at which time to buy a Bahncard is a typical online problem, because she usually does not know when and where she will travel next. We show that the greedy algorithm applied by most travelers and clerks at ticket offices is not better in the worst case than the trivial algorithm which never buys a Bahncard. We present two optimal deterministic online algorithms, an optimistic one and a pessimistic one. We further give a lower bound for randomized online algorithms and present an algorithm which we conjecture to be optimal; a proof of the conjecture is given for a special case of the problem. It turns out that the optimal competitive ratio only depends on the price reduction factor (50% for the German Bahncard Problem), but does not depend on the price or validity period of a Bahncard.Thema 6: Exploring Simple Grid PolygonsWe investigate the online exploration problem of a shortsighted mobile robot moving in an unknown cellular room without obstacles. The robot has a very limited sensor; it can determine only which of the four cells adjacent to its current position are free and which are blocked, i. e., unaccessible for the robot. Therefore, the robot must enter a cell in order to explore it. The robot has to visit each cell and to return to the start. Our interest is in a short exploration tour, i. e., in keeping the number of multiple cell visits small. For abitrary environments without holes we provide a strategy producing tours of length S<=C+1/2E-3 where C denotes the number of cellsthe area, and E denotes the number of boundary edgesthe perimeterof the given environment. Further, we show that our strategy is competitive with a factor of 4/3 , and give a lower bound of 7/6 for our problem. This leaves a gap of only 1/6 between the lower and the upper boundThema 10: Exploring Unknown Undirected GraphsA robot has to construct a complete map of an unknown environment modeled as an undirected connected graph. The task is to explore all nodes and edges of the graph using the minimum number of edge traversals. The penalty of an exploration algorithm running on a graph G = (V(G), E(G)) is the worst-case number of traversals in excess of the lower bound IE(G)I that it must perform in order to explore the entire graph. We give an exploration algorithm whose penalty is O(lV(G)l) for every graph. We also show that some natural exploration algorithms cannot achieve this efficiency. | |