| 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/2010Sommersemester 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 | |
| Assistent | Dr. Christiane Schmidt Ehemalige Wissenschaftliche Mitarbeiterin |
| LP | 4 |
| SWS | 0+2 |
| Ort & Zeit | Die Vorbesprechung findet am 30.10.2008 um 14 Uhr in Raum 262A statt. In einer Blockveranstaltung am 26.01.2009 ab 15 Uhr werden die Vorträge gehalten. Die Abgabe der Ausarbeitungen muss bis zum 12.01.09 erfolgen. |
| Scheinerwerb | 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 | |
Thema 4: On Two Dimensional PackingThe paper considerspacking of rectanglesinto an infinite bin. Similar to theTetris game, the rectangles arrive from the top and, once placed, cannot be moved again. The rectangles are moved inside the bin to reach their place. For the case in which rotations are allowed, we design an algorithm whose performance ratio is constant. In contrast, if rotations are not allowed, we show that no algorithm of constant ratio exists. For this case we design an algorithm with performance ratio ofO(log(1/var epsilon)), where var epsilon is the minimum width of any rectangle. We also show that no algorithm can achieve a better ratio thanImage for this case.Thema 6: Path Planning Strategies for a Robot for a Point Mobile Automaton Moving Amidst Unknown Obstacles of Arbitrary ShapeThe problem of path planning for an automaton moving in a two-dimensional scene filled with unknown obstacles is considered. The automaton is presented as a point; obstacles can be of an arbitrary shape, with continuous boundaries and of finite size; no restriction on the size of the scene is imposed. The information available to the automaton is limited to its own current coordinates and those of the target position. Also, when the automaton hits an obstacle, this fact is detected by the automaton's "tactile sensor." This information is shown to be sufficient for reaching the target or concluding in finite time that the target cannot be reached. A worst-case lower bound on the length of paths generated by any algorithm operating within the framework of the accepted model is developed; the bound is expressed in terms of the perimeters of the obstacles met by the automaton I in the scene. Algorithms that guarantee reaching the target (if the target is reachable), and tests for target reachability are presented. The efficiency of the algorithms is studied, and worst-case upper I bounds on the length of generated paths are produced.Thema 7: Gathering of Asynchronous Robots with Limited ControlIn this paper we study the problem of gathering a collection of identical oblivious mobile robots in the same location of the plane. Previous investigations have focused mostly on the unlimited visibility setting, where each robot can always see all the others regardless of their distance.In the more difficult and realistic setting where the robots have limited visibility, the existing algorithmic results are only for convergence (towards a common point, without ever reaching it) and only for semi-synchronous environments, where robots' movements are assumed to be performed instantaneously.In contrast, we study this problem in a totally asynchronous setting, where robots' actions, computations, and movements require a finite but otherwise unpredictable amount of time. We present a protocol that allows anonymous oblivious robots with limited visibility to gather in the same location in finite time, provided they have orientation (i.e., agreement on a coordinate system).Our result indicates that, with respect to gathering, orientation is at least as powerful as instantaneous movements.Thema 8: Computing the Hausdorff Distance Between Curved ObjectsThis paper describes an algorithm for computation of the Hausdorff distance between sets of plane algebraic rational parametric curves. The Hausdorff distance is one of the frequently used similarity measures in geometric pattern matching algorithms. It is defined for arbitrary non-empty bounded and closed sets A and B. Hausdorff distance assigns to each point of one set the distance to its closest point on the other and takes the maximum over all these values. We work with Euclidean distance as point to point distance measure. | |