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

Seminar Algorithmik

SemesterSommersemester 2009 [ Andere Semester: Winter 17/18 · Sommer 17 · Winter 16/17 · Sommer 16 · Winter 15/16 · Sommer 15 · Winter 13/14 · Sommer 13 · Winter 12/13 · Sommer 12 · Winter 11/12 · Sommer 11 · Winter 10/11 · Winter 09/10 · Winter 08/09 ]
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)
ArtSeminar
Dozent
PhotoProf. Dr. Sándor P. Fekete
Abteilungsleiter
s.fekete[[at]]tu-bs.de
+49 531 3913111
Raum 335
Assistenten
PhotoDr. Christiane Schmidt
Ehemalige Wissenschaftliche Mitarbeiterin
cschmidt[[at]]ibr.cs.tu-bs.de
PhotoDr. Tom Kamphans
Ehemaliger Wissenschaftlicher Mitarbeiter
LP4
SWS0+2
Ort & Zeit

Die Vorbesprechung findet am 15.04.2009 in Raum 262A statt.

ACHTUNG NEU: In einer Blockveranstaltung am 26.06.2009 von 9 - 12 Uhr in Raum 262A werden die Vorträge gehalten.

Die Vortragsreihenfolge lautet: Marcus Apel, Marc Jandt, Bessem Medimagh, Zhiwei Chen.

ACHTUNG NEU: Die Abgabe der Ausarbeitungen muss bis zum 12.06.2009 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. 40 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 2009 beschäftigt sich mit einer Reihe von aktuellen Artikeln, die relativ wenig an Vorwissen erfordern. Unten beschrieben sind die Originalauszüge der Autoren zu den eigenen Artikeln, die jeweils auf englisch erschienen, aber von überschaubarer Länge sind.

Thema 2: Searching for the Centre of a Circle

Consider the problem of an agent or robot searching for the centre of a circle. The robot has only a limited number of capabilities. It can detect whether it is inside the circle or not. It can mark the point which it occupies. It can move in a straight line, possibly towards a mark which it made previously. It can make 90 an 180 degree turns. It can move to the middle of a line segment determined by two marked points, if it is on the line segment. The searcher starts at the edge of the circle. The objective is for the searcher to move to the centre of the circle as quickly as possible.

Thema 3: Searching for the Center of an Ellipse

Biedl et al. first posed the problem of finding the center of a circle, starting from a point on the boundary, using a limited number of operations. We solve an open problem, presented in their work: finding the center of the ellipse and provide results of experiments showing how these algorithms perform under the introduction of errors.

Thema 7: Optimal Constraint Graph Exploration

We address the problem of exploring an unknown graph G = (V; E) from a given start node s with either a tethered robot or a robot with a fuel tank of limited capacity, the former being a tighter constraint. In both varaitations of the problem, the robot can only move along the edges of the graph, i.e, it cannot jump between non-adjacent vertices. In the tethered robot case, if the tether (rope) has length l, then the robot must remain within distance l from the start node s. In the second variation, a fuel tank of capacity C forces the robot to return to s after traversing C edges. The eciency of algorithms for both variations of the problem is measured by the number of edges traversed during the exploration. We present an algorithm for a tethered robot which explores the graph in Theta(|E|) edge traversals. The problem of exploration using a robot with a limited fuel tank capacity can be solved with a simple reduction from the tethered robot case and also yields a Theta(|E|) algorithm. This improves on the previous best known bound of O(|E| + |V| log^2 |V|) in [4]. Since the lower bound for the graph exploration problems is |E|, our algorithm is optimal, thus answering the open problem of Awerbuch, Betke, Rivest, and Singh [3].

Thema 8: Touring a Sequence of Polygons

Given a sequence of k polygons in the plane, a start point s, and a target point, t, we seek a shortest path that starts at s, visits in order each of the polygons, and ends at t. If the polygons are disjoint and convex, we give an algorithm running in time O(kn log(n/k)), where n is the total number of vertices specifying the polygons. We also extend our results to a case in which the convex polygons are arbitrarily intersecting and the subpath between any two consecutive polygons is constrained to lie within a simply connected region; the algorithm uses O(nk^2 log n) time. Our methods are simple and allow shortest path queries from s to a query point t to be answered in time O(k log n + m), where m is the combinatorial path length. We show that for nonconvex polygons this "touring polygons " problem is NP-hard. The touring polygons problem is a strict generalization of some classic problems in computational geometry, including the safari problem, the zoo-keeper problem, and the watchman route problem in a simple polygon. Our new results give an order of magnitude improvement in the running times of the safari problem and the watchman route problem: We solve the safari problem in O(n^2 log n) time and the watchman route problem (through a fixed point s) in time O(n^3)

aktualisiert am 12.06.2009, 13:15 von Martin Lorek
printemailtop