| Semester | Wintersemester 2023/2024Sommersemester 2023Wintersemester 2022/2023Sommersemester 2022Wintersemester 2021/2022Sommersemester 2021Wintersemester 2020/2021Sommersemester 2020Wintersemester 2019/2020Sommersemester 2019Wintersemester 2018/2019Sommersemester 2018Wintersemester 2017/2018Sommersemester 2017Wintersemester 2016/2017Sommersemester 2016Wintersemester 2015/2016Sommersemester 2015Wintersemester 2013/2014Sommersemester 2013Wintersemester 2012/2013Sommersemester 2012Wintersemester 2011/2012Sommersemester 2011Wintersemester 2010/2011Wintersemester 2009/2010Wintersemester 2008/2009 |
| Modulnummer | INF-ALG-019 |
| Veranstaltungsnummer | INF-ALG-019 |
| Studiengänge | Diplom Informatik, Informatik Master, Wirtschaftsinformatik Master, Informations-Systemtechnik Bachelor, Informations-Systemtechnik Master, Elektrotechnik Bachelor, Elektrotechnik Master |
| IBR Gruppe | ALG (Prof. Fekete) |
| Art | Seminar |
| Dozent | |
| Assistenten | Dr. Christiane Schmidt Ehemalige Wissenschaftliche Mitarbeiterin Dr. Tom Kamphans Ehemaliger Wissenschaftlicher Mitarbeiter |
| LP | 4 |
| SWS | 0+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 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) | |