- Institute of Operating Systems and Computer Networks
- News
- About us
- Connected and Mobile Systems
- Distributed Systems
- Algorithms
- Microprocessor Lab
- Education
- Services
- Spin-Offs
- Research Cooperations
Seminar Algorithmik
Semester | Summer 2009 Winter 2023/2024Summer 2023Winter 2022/2023Summer 2022Winter 2021/2022Summer 2021Winter 2020/2021Summer 2020Winter 2019/2020Summer 2019Winter 2018/2019Summer 2018Winter 2017/2018Summer 2017Winter 2016/2017Summer 2016Winter 2015/2016Summer 2015Winter 2013/2014Summer 2013Winter 2012/2013Summer 2012Winter 2011/2012Summer 2011Winter 2010/2011Winter 2009/2010Winter 2008/2009 |
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 | |
Assistants | Dr. Christiane Schmidt Ehemalige Wissenschaftliche Mitarbeiterin Dr. Tom Kamphans Ehemaliger Wissenschaftlicher Mitarbeiter |
Credits | 4 |
Hours | 0+2 |
Time & Place | Die Vorbesprechung findet am 15.04.2009 in Room 262A statt. ACHTUNG NEU: In einer Blockveranstaltung am 26.06.2009 von 9 - 12 Uhr in Room 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. |
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. 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. |
Content | 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 CircleConsider 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 EllipseBiedl 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 ExplorationWe 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 PolygonsGiven 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) |