TU BRAUNSCHWEIG
| Carl-Friedrich-Gauß-Fakultät | Informatik
Informatikzentrum

Seminar Algorithmik

Semester Sommersemester 2008 [ Andere Semester: ]
Modulnr. INF-ALG-019
Veranst.Nr. INF-ALG-019
Studieng. Diplom Informatik, Master Informatik, Master Wirtschaftsinformatik, Bachelor Informations-Systemtechnik, Master Informations-Systemtechnik, Bachelor Elektrotechnik, Master Elektrotechnik
IBR Gruppe(n) ALG (Prof. Fekete)
Art Seminar
Dozent
Photo Prof. Dr. Sándor P. Fekete
Abteilungsleiter
s.fekete[[at]]tu-bs.de
+49 531 3913111
Raum 335
Assistent
Photo Dr. Christiane Schmidt
Ehemalige Wissenschaftliche Mitarbeiterin
cschmidt[[at]]ibr.cs.tu-bs.de
LP 4
SWS 0+2
Ort & Zeit

Die Vorbesprechung findet am 09.04.2008 in Raum 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.

Scheinerwerb

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.

Inhalt

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 Problem

In 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 Polygons

We 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 cells—the area—, and E denotes the number of boundary edges—the perimeter—of 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 bound

Thema 10: Exploring Unknown Undirected Graphs

A 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.

aktualisiert am 08.10.2009, 17:12 von Martin Lorek
printemailtop