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
  - IST.hub

Seminar Algorithmik

Semester	Winter 2008/2009 Summer 2023 Winter 2022/2023 Summer 2022 Winter 2021/2022 Summer 2021 Winter 2020/2021 Summer 2020 Winter 2019/2020 Summer 2019 Winter 2018/2019 Summer 2018 Winter 2017/2018 Summer 2017 Winter 2016/2017 Summer 2016 Winter 2015/2016 Summer 2015 Winter 2013/2014 Summer 2013 Winter 2012/2013 Summer 2012 Winter 2011/2012 Summer 2011 Winter 2010/2011 Winter 2009/2010 Summer 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	Prof. Dr. Sándor P. Fekete Abteilungsleiter s.fekete[[at]]tu-bs.de +49 531 3913111 Room 335
Assistant	Dr. Christiane Schmidt Ehemalige Wissenschaftliche Mitarbeiterin
Credits	4
Hours	0+2
Time & Place	Die Vorbesprechung findet am 30.10.2008 um 14 Uhr in Room 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.
Certificates	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
Thema 4: On Two Dimensional Packing The 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 Shape The 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 Control In 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 Objects This 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.