- 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 | Winter 2013/2014 Summer 2023Winter 2022/2023Summer 2022Winter 2021/2022Summer 2021Winter 2020/2021Summer 2020Winter 2019/2020Summer 2019Winter 2018/2019Summer 2018Winter 2017/2018Summer 2017Winter 2016/2017Summer 2016Winter 2015/2016Summer 2015Summer 2013Winter 2012/2013Summer 2012Winter 2011/2012Summer 2011Winter 2010/2011Winter 2009/2010Summer 2009Winter 2008/2009 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Module # | INF-STD-18, INF-STD-20 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Event # | INF-ALG-019, INF-ALG-029 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Programmes | Business Information Systems Master, Computer and Communication Systems Engineering Master, Computer Science Master, Electrical Engineering Master, Diplom Informatik, Computer and Communication Systems Engineering Bachelor, Computer Science Bachelor, Electrical Engineering Bachelor | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
IBR Group | ALG (Prof. Fekete) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Type | Seminar | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Lecturer | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Assistant | Stephan Friedrichs Ehemaliger Wissenschaftlicher Mitarbeiter | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Credits | 5 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Hours | 0+2 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Prerequisites | Voraussetzungen für die Bearbeitung der einzelnen Themen sind jeweils individuell aufgeführt. Es ist zu beachten, dass es sich dabei lediglich um empfohlenes Vorwissen handelt; es ist nicht nötig, die entsprechenden Prüfungen abgelegt zu haben. Sind Voraussetzungen in Klammern gesetzt, sind sie zwar hilfreich, aber kein Muss. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Language | German or English, depending on the supervisor | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Certificates | Schriftliche Ausarbeitung und erfolgreicher Seminarvortrag. Die Note wird abhängig von Qualität des Vortrages und der Ausarbeitung bestimmt:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Registration | Die Anmeldung für das Seminar erfolgt über Stud.IP, Details sind auf den offiziellen Seiten der Studiengänge Bachelor sowie Master Informatik. Wenn Sie einen Platz bekommen haben, müssen Sie sich zusätzlich noch verbindlich in einer Liste eintragen (Frist: siehe Kalender). | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Content | Das Seminar Algorithmik beschäftigt sich dieses Semester mit einer Auswahl von klassischen sowie aktuellen Papern rund um unser Lehrangebot. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Schedule | 01.01.2000, 00:00 Vorbesprechung und Themenvergabe 01.01.2000, 01:00 Verbindliche Anmeldung 01.01.2000, 02:00 Abgabe Ausarbeitung 01.01.2000, 03:00 Abgabe Folien Vorversion 01.01.2000, 04:00 Seminarvorträge 01.01.2000, 05:00 Seminarvorträge | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
References | Literaturrecherche: Ausarbeitung und Vortrag: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Ablauf der VorträgeDonnerstag, 16.01.2014
Freitag, 17.01.2014
Themen für Bachelorstudenten(1) Minimum Dilation Spanning TreesWill man eine Menge von n Punkten mit möglichst kurzer Gesamtlänge verbinden, dann berechnet man einen Minimalen Aufspannenden Baum (MST). Dabei kann aber möglicherweise die Länge im Baum zwischen zwei Punkten deutlich größer sein als wenn man sie direkt verbindet. Diesen "Umwegfaktor" nennt man auch "Dilation". Wie schwer ist es, einen Baum mit möglichst kleinem Umwegfaktor zu bestimmen? Hier wird gezeigt, dass das ein NP-schweres Problem ist.
(2) Fast Lower Bounds for Bin Packing ProblemsWill man eine Menge von Objekten in möglichst wenige Container packen, dann hat man es mit dem NP-schweren Problem "Bin Packing" zu tun. Wie kann man dafür möglichst schnelle und trotzdem gute untere Schranken für die Zahl der Container berechnen? Das wird hier untersucht.
(3) Approximation Algorithms for Scheduling
Themen für Bachelor- und Masterstudenten(4) Geometric Complexity of Some Location ProblemsBetrachtet man n Punkte auf der Geraden oder in der Ebene, gibt es eine ganze Reihe von möglichen Standortproblemen. Für viele davon (z.B. den Median) kann man Linearzeitalgorithmen angeben. Für andere (z.B. die Entscheidung, ob es zwei gleiche Punkte oder eine große Lücke gibt) ist das nicht so einfach. Hier wird gezeigt, dass das unter bestimmten Annahmen gar nicht möglich ist, weil man mindestens Omega(n log n) Rechenzeit benötigt.
(5) The Orthogonal Milling Problem with Turn CostsBeim Milling-Problem geht es darum, eine Fläche (einen Rasen) abzudecken (zu mähen), ohne sie dabei zu verlassen (ohne Abkürzungen durch Blumenbeete zu nehmen). Besonders teuer ist dabei das Abbiegen. Wie schwer ist das Problem? Welche Schranken gibt es für Lösungen? Wie kann man es approximieren? All das wird hier untersucht.
(6) Minimum Covering with Travel CostWir betrachten n Punkte auf einer Geraden oder in der Ebene. Diese sollen überdeckt werden, z.B. indem man sie abscannt. Dafür muss man auch noch von Scanpunkt zu Scanpunkt fahren. Die Gesamtkosten hängen dabei von der Gesamtzahl der Scanpunkte und der zurückgelegten Distanz ab. Wie kann man das machen, ohne dass eine der beiden Größen mehr als notwendig in Anspruch nimmt? Dafür lassen sich Approximationslösungen angeben.
(7) Robot Dispersion
(8) Lawn Mowing
(9) The Freeze-Tag Problem
(10) Minkowski Sums
Themen für Masterstudenten(11) WitnessabilityUm das Art-Gallery-Problem zu lösen ist folgende Frage von großem Interesse: Ist es möglich, endlich viele Punkte W (Witnesses) im Polygon zu platzieren, so dass jede Auswahl von Wächtern, die W bewacht, automatisch auch das ganze Polygon bewacht? Der entsprechende Artikel beantwortet diese Fragen und gibt einen exzellenten Einblick in Sichtbarkeitsprobleme in Polygonen.
|