| Semester | Winter 2023/2024Summer 2023Winter 2022/2023Summer 2022Winter 2021/2022Summer 2021Winter 2020/2021Summer 2020Winter 2019/2020Summer 2019Summer 2018Winter 2017/2018Summer 2017Winter 2016/2017Summer 2016Winter 2015/2016Summer 2015Winter 2013/2014Summer 2013Winter 2012/2013Summer 2012Winter 2011/2012Summer 2011Winter 2010/2011Winter 2009/2010Summer 2009Winter 2008/2009 |
| Programmes | Computer Science Bachelor, Business Information Systems Bachelor, Computer and Communication Systems Engineering Bachelor |
| 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 317 |
| 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 ein Abstract sind weiter unten zu finden. |
| 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 6 Plätze für Studierende auf Bachelorniveau angeboten.AusarbeitungDie Ausarbeitung soll etwa 6-8 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 Bachelorstudenten im Wintersemester 2018/2019Das Algorithmikseminar beschäftigt sich in diesem Semester mit einer Reihe von Tourproblemen. Die angegebenen Voraussetzungen sind Empfehlungen. Hamiltonkreise, Einführung und Varianten des Traveling Salesman Problems Beim Hamiltonkreisproblem sucht man in einem ungewichteten Graphen einen Kreis, der jeden Knoten genau einmal besucht. Das TSP beschreibt dieses Problem auf gewichteten Graphen. Es lässt sich zeigen, dass beide Probleme in unterschiedlichesten Szenarien NP-schwer sind. Voraussetzungen: Algorithmen und Datenstrukturen, Theoretische Informatik 2 Approximationen und Heuristiken Es lässt sich zeigen, dass das allgemeine TSP nicht approximierbar ist. Sobald man die Dreiecksungleichung auf die Kantengewichtsfunktion anwenden kann, lässt sich eine 1.5-Approximation finden. Des Weiteren gibt es einfache Heuristiken, um eine gegebene Tour zu verbessern. Voraussetzungen: Algorithmen und Datenstrukturen (1+2), Netzwerkalgorithmen Max TSP Beim MaxTSP wird eine Tour größtmöglichen Gewichts gesucht. Es lässt sich zeigen, dass das Problem in der Ebene unter der Manhattan-Metrik in linearer Zeit lösbar ist. Im dreidimensionalen Raum ist das Problem NP-schwer. Voraussetzungen: Algorithmen und Datenstrukturen, Theoretische Informatik 2 Lawn Mower und Milling Problem Bei diesen Problemen betrachtet man ein gegebenes Gebiet, welches man mit einem Rasenmäher in einer kürzestmöglichen Tour überdecken möchte. Beim Lawn Mower Problem ist es erlaubt, das Gebiet zu verlassen; beim Milling ist man gezwungen, dauerhaft innerhalb des Gebiets zu bleiben. Es kann gezeigt werden, dass die Probleme NP-schwer und approximierbar sind. Voraussetzungen: Algorithmen und Datenstrukturen (1+2), Theoretische Informatik 2, Netzwerkalgorithmen Minimum Covering with Travel Cost Bei diesem Problem ist ein Polygon gegeben, welches mit einem Roboter mittels Scans erkundet werden soll. Die Scanreichweite des Roboters ist dabei begrenzt. Zusätzlich soll der Roboter so wenig Strecke wie möglich bei der Erkundung zurücklegen. Das Problem ist NP-schwer. Für verschiedene Varianten existieren O(1)-Approximationen. Voraussetzungen:Algorithmen und Datenstrukturen (1+2), Theoretische Informatik 2, Netzwerkalgorithmen IP Formulierungen In der Praxis lässt sich das TSP mit ganzzahliger Optimierung relativ gut lösen. Dabei sind gute IP-Formulierungen mit zusätzlichen und geeigneten Cuts notwendig. Voraussetzungen: Lineare Optimierung Concorde Concorde ist ein Solver für das TSP, der unterschiedliche Ansätze zum Lösen verwendet und kombiniert. Voraussetzungen: Lineare Optimierung | |