| Semester | Wintersemester 2023/2024Sommersemester 2023Wintersemester 2022/2023Sommersemester 2022Wintersemester 2021/2022Sommersemester 2021Wintersemester 2020/2021Sommersemester 2020Wintersemester 2019/2020Sommersemester 2019Wintersemester 2018/2019Sommersemester 2018Wintersemester 2017/2018Sommersemester 2017Sommersemester 2016Wintersemester 2015/2016Sommersemester 2015Wintersemester 2013/2014Sommersemester 2013Wintersemester 2012/2013Sommersemester 2012Wintersemester 2011/2012Sommersemester 2011Wintersemester 2010/2011Wintersemester 2009/2010Sommersemester 2009Wintersemester 2008/2009 |
| Modulnummer | INF-STD-18, INF-STD-20 |
| Veranstaltungsnummer | INF-ALG-019, INF-ALG-029 |
| Studiengänge | Informatik Bachelor, Wirtschaftsinformatik Bachelor, Informations-Systemtechnik Bachelor |
| IBR Gruppe | ALG (Prof. Fekete) |
| Art | Seminar |
| Dozent | |
| Assistenten | Dr. Victor Alvarez Ehemaliger Wissenschaftlicher Mitarbeiter Dr. Phillip Keldenich Wissenschaftlicher Mitarbeiter keldenich[[at]]ibr.cs.tu-bs.de +49 531 3913112 Raum 317 |
| LP | 5 |
| SWS | 0+2 |
| Voraussetzungen | 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. |
| Scheinerwerb | 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. |
| Anmeldung | Anmeldung zentral (über StudIP). Die Vorbesprechung für das Seminar erfolgt am 24.10.2016 um 13:00 Uhr im Besprechungsraum der Abteilung Algorithmik (IZ313). |
| Inhalt | Das Seminar Algorithmik beschäftigt sich dieses Semester mit einer Reihe von Buchkapiteln und Papern. Die genauen Themen sowie ein Abstract sind weiter unten zu finden. |
| Termine | 24.10.2016, 13:00 Uhr Kickoff-Meeting (IZ313) 09.01.2017 Peer-Review 16.01.2017 Feedback 23.01.2017 Final Version 27.01.2017 Erste Vortragsversion 06.02.2017 Vorträge (IZ313) |
| Literatur/Links | Literaturrecherche:
|
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Üblicherweise werden einige Themen aus dem Buch der Beweise vorgeschlagen. Falls spezielle Themen aus eigenem Interesse gewünscht sind, ist dies sicherlich möglich. Die Themen dieses Semesters sind: Drei Anwendungen der Eulerschen PolyederformelDie Eulersche Polyederformel setzt für zusammenhängende ebene Graphen die Anzahl von Ecken, Kanten und Gebieten in Beziehung. Dieser Satz wird vorgestellt und auf drei Probleme angewendet. Der FünffarbensatzEin berühmter Satz über planare Graphen besagt, dass sich jeder planare Graph mit nur 4 Farben so färben lässt, dass benachbarte Knoten unterschiedliche Farben haben. Der Beweis dieses Satzes kann derzeit nur per Computer geführt werden. Wesentlich einfacher ist es zu zeigen, dass höchstens 5 Farben immer ausreichen. Searching for Empty Convex PolygonsEin Problem in der algorithmischen Geometrie ist die Identifikation von Teilmengen einer Punktmenge, die bestimmte Eigenschaften erfüllen. Die gewünschten Eigenschaften in diesem Thema sind Leere und Konvexität. Es existieren Beziehungen zwischen diesen Eigenschaften. Diese und ein Algorithmus für das Finden von leere, konvexen Polygonen ist der grobe Inhalt dieses Themas. Maximum Degree of Bipartite Embeddings of Trees in the PlaneEin bipartiter Graph ist ein Graph bei dem die Knotenmenge in zwei disjunkte Teilmengen aufgeteilt werden kann, so dass Kanten nur zwischen Knoten aus verschiedenen Mengen existieren. Das Problem dieses Themas betrachtet einen vollständig bipartiten Graphen mit gleichgroßen Bipartitionen, bei dem außerdem, wird er in der Ebene dargestellt, keine drei Punkte kollinear sind. Für solche Graphen kann gezeigt werden, dass sie einen planaren, aufspannenden, bipartiten Baum T beinhalten, so dass der Maximalgrad von T maximal drei ist. | |