| Semester | |
| Module # | INF-STD-18, INF-STD-20 |
| Event # | INF-ALG-019, INF-ALG-029 |
| Programmes | Master Wirtschaftsinformatik, Master Informations-Systemtechnik, Master Informatik, Master Elektrotechnik, Diplom Informatik, Bachelor Informations-Systemtechnik, Bachelor Informatik, Bachelor Elektrotechnik |
| IBR Group | ALG (Prof. Fekete) |
| Type | Seminar |
| Lecturer | |
| Assistant |  Stephan FriedrichsEhemaliger 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: - Ausarbeitung
Die Ausarbeitung soll etwa 10 Seiten lang sein. Generell interessiert uns, dass Sie da eine selbst verfasste Zusammenfassung eines selbst verstandenen Artikels abgeben. Wesentlich mehr als zehn Seiten sollen es nicht werden, immerhin geht es hier um die Kunst des Zusammenfassens. Wir erwarten, dass Sie selbstständig zusätzliche Quellen recherchieren. Die wesentlichen Qualitätskriterien der Ausarbeitung sind vor allem die Strukturierung des Inhalts, selbstständiges Arbeiten, Anteil der Eigenarbeit, Literaturrecherche, präzise Quellenangaben, sowie die Form. - Vortrag
Ihr Vortrag soll 40 Minuten dauern. Das Medium ist frei, Sie können Beamer mit PDF, Beamer mit PowerPoint, Whiteboard, Overheadprojektor, eine Kombination daraus oder was auch immer Sie für sinnvoll erachten, 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. Wichtige Merkmale eines guten Vortrags sind unter anderem ein souveräner Umgang mit der Vortragssituation, gut ausgearbeitete Materialien, fachlich korrekter Inhalt und vor allem die Aufarbeitung des Inhalts in vortragsgeeigneter Form.
|
| 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 | | [ Subscribe Calendar | Download Calendar ] | | Date | Description |
|---|
| 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| Zeit | # | Thema |
|---|
| 09:00 - 10:00 | (8) | Lawn Mowing | | 10:00 - 11:00 | (5) | The Orthogonal Milling Problem with Turn Costs | | 11:00 - 12:00 | (6) | Minimum Covering with Travel Cost | | 12:00 - 12:45 | | Mittagspause | | 12:45 - 13:45 | (4) | Geometric Complexity of Some Location Problems | | 13:45 - 14:45 | (10) | Minkowski Sums |
Freitag, 17.01.2014| Zeit | # | Thema |
|---|
| 09:00 - 10:00 | (2) | Fast Lower Bounds for Bin Packing Problems | | 10:00 - 11:00 | (3) | Approximation Algorithms for Scheduling | | 11:00 - 12:00 | (9) | The Freeze-Tag Problem | | 12:00 - 12:45 | | Mittagspause | | 12:45 - 13:45 | (7) | Robot Dispersion | | 13:45 - 14:45 | (1) | Minimum Dilation Spanning Trees | | 14:45 - 15:45 | (11) | Witnessability |
Themen für Bachelorstudenten(1) Minimum Dilation Spanning Trees Will 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 Problems Will 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 SchedulingThemen für Bachelor- und Masterstudenten(4) Geometric Complexity of Some Location Problems Betrachtet 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 Costs Beim 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 Cost Wir 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 SumsThemen für Masterstudenten(11) Witnessability Um 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. |
