Master-Seminar Algorithmik
| Semester | |
| Programmes | Computer Science Master, Business Information Systems Master, Computer and Communication Systems Engineering Master |
| IBR Group | ALG (Prof. Fekete) |
| Type | Seminar |
| Lecturer | |
| Assistants | Dr. Phillip Keldenich Wissenschaftlicher Mitarbeiter keldenich[[at]]ibr.cs.tu-bs.de +49 531 3913112 Room 318 |
| Credits | 5 |
| Hours | 0+2 |
| Prerequisites | Voraussetzungen für die Bearbeitung der einzelnen Themen sind jeweils individuell aufgeführt. Sind diese in Klammern gesetzt, sind sie zwar hilfreich, aber keine Voraussetzung. |
| Certificates | 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. |
| Registration | Anmeldung zentral (über StudIP). Das Kick-off Meeting findet am Donnerstag, den 11.10.2018 um 13:30 Uhr im IZ 313 statt. |
| Content | Das Seminar Algorithmik beschäftigt sich dieses Semester mit einer Reihe von Tourproblemen. Die genauen Themen sowie eine Abstract sind weiter unten aufgeführt. |
| Schedule | 11.10.2018, 13:30 Kick-off Meeting (IZ313) 29.10.2018 Deadline Pflichttreffen mit dem Betreuer 07.12.2018 Peer-Review 14.12.2018 Feedback 21.12.2018 Finale Abgabe der Ausarbeitung 14.01.2019, 10:00 Vorträge (IZ313) |
| References | Literaturrecherche: Ausarbeitung und Vortrag: How to read/write a paper: |
HinweiseTeilnehmerzahlEs werden 4 Plätze für Studierende auf Masterniveau angeboten.AusarbeitungDie Ausarbeitung soll etwa 8-10 Seiten lang sein. Generell interessiert uns, dass Sie da eine selbstverfasste Zusammenfassung eines selbst verstandenen Artikels abgeben. Wesentlich mehr als die genannte Seitenzahl sollte es nicht werden, immerhin geht es hier um die Kunst des Zusammenfassens. Wir erwarten, dass Sie selbstständig zusätzliche Quellen recherchieren. VortragIhr Vortrag soll etwa 30 Minuten (reine Vortragszeit) dauern. Anschließend wird es eine kurze Diskussionsrunde mit Fragen geben. Das Medium ist frei, Sie können also Whiteboard, Overhead-Projektor, Beamer mit PowerPoint, Beamer mit PDF, 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. Themen für MasterstudentenDas Algorithmikseminar beschäftigt sich in diesem Semester mit einer Reihe von Tourproblemen. Die angegebenen Voraussetzungen sind Empfehlungen. Euklidisches TSP und Aroras PTAS Gegeben seien n Punkte in der Ebene. Gesucht ist eine kürzeste Tour, so dass jeder Knoten genau einmal besucht ist. Dies ist das euklidische TSP. Ende der 90er Jahre haben Arora und Mitchell unabhängig voneinander eine (1+e)-Approximation für dieses Problem angegeben, wobei e eine beliebige Zahl größer als 0 ist. Sie wurden dafür mit dem Gödel-Preis ausgezeichnet. Voraussetzungen: Algorithmen und Datenstrukturen, Approximationsalgorithmen, Theoretische Informatik 2 Watchman Es soll eine Tour durch das innere eines Gebiets gesucht werden, so dass jeder Punkt des Gebiets von einem Punkte der Tour aus gesehen werden kann. Es lässt sich zeigen, dass das Problem NP-schwer ist für Gebiete die Löcher enthalten, aber in polynomieller Zeit für lochfreie (d.h. einfache) Gebiete gelöst werden kann. Voraussetzungen: Algorithmen und Datenstrukturen, Algorithmische Geometrie Graph TSP Für das Graph-TSP (alle Kantengewichte eines gegebenen Graphen sind 1) ist eine Approximation bekannt, die die 1.5-Approximation von Christofides schlägt. Die Grundlage dafür sind Matchingstrategien. Voraussetzungen: Netzwerkalgorithmen, Approximationsalgorithmen Concorde Concorde ist ein Solver für das TSP, der unterschiedliche Ansätze zum Lösen verwendet und kombiniert. Voraussetzungen: Lineare Optimierung | |