TU BRAUNSCHWEIG
| Carl-Friedrich-Gauß-Faculty | Computer Science
Informatikzentrum

Bachelor-Seminar Algorithmik

Module #INF-STD-18, INF-STD-20
Event #INF-ALG-019, INF-ALG-029
ProgrammesBachelor Informations-Systemtechnik, Bachelor Elektrotechnik, Bachelor Informatik
IBR Group(s)ALG (Prof. Fekete)
TypeSeminar
Lecturer
PhotoProf. Dr. Sándor P. Fekete
Abteilungsleiter
s.fekete[[at]]tu-bs.de
+49 531 3913111
Room 335
Assistants
PhotoPhillip Keldenich
Wissenschaftlicher Mitarbeiter
keldenich[[at]]ibr.cs.tu-bs.de
+49 531 3913112
Room 318
PhotoDr. Christian Scheffer
Wissenschaftlicher Mitarbeiter
scheffer[[at]]ibr.cs.tu-bs.de
+49 531 3913113
Room 331
PhotoArne Schmidt
Wissenschaftlicher Mitarbeiter
aschmidt[[at]]ibr.cs.tu-bs.de
+49 531 3913115
Room 319
PhotoDominik Krupke
Wissenschaftlicher Mitarbeiter
krupke[[at]]ibr.cs.tu-bs.de
+49 531 3913116
Room 315
PhotoChristian Rieck
Wissenschaftlicher Mitarbeiter
rieck[[at]]ibr.cs.tu-bs.de
+49 531 3913114
Room 314
Credits5
Hours0+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). Die Vorbesprechung für das Seminar erfolgt am 12.04.2017 um 11:00 Uhr im Besprechungsraum der Abteilung Algorithmik (IZ313).
Content 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.
Schedule
[ Subscribe Calendar | Download Calendar ]
DateDescription
12.04.2017, 11:00 Uhr Kickoff-Meeting (IZ313)
26.04.2017 Pflichttreffen mit dem Betreuer
26.05.2017 Peer-Review
02.06.2017 Feedback
19.06.2017 Final Version und erste Vortragsversion
27.06.2017 Vorträge (IZ313)
References Literaturrecherche: Ausarbeitung und Vortrag: How to read/write a paper:

Hinweise

Teilnehmerzahl

Es werden 6 Plätze für Studierende auf Bachelorniveau angeboten.

Ausarbeitung

Die 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.

Vortrag

Ihr 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 Sommersemester 2017

Das Seminar beschäftigt sich in diesem Semester mit verschiedenen Themen des Art-Gallery-Problems.

Das Art-Gallery Problem Es wird eine Einführung in das allgemeine Art-Gallery Problem gegeben und die Komplexität untersucht. Dabei wird gezeigt, dass n/3 Wächter für einfache Polygone ausreichend und manchmal notwendig sind.

Das orthogonale Art-Gallery-Problem Chvátal hat gezeigt, dass für allgemeine n-eckige Polygone n/3 Wächter ausreichen um das Polygon zu beleuchten. In diesem Thema wird gezeigt, dass für orthogonale Polygone n/4 Wächter ausreichen und dass diese manchmal notwendig sind.

Einteilung in L-förmige Teilstrukturen In diesem Thema wird ein alternativer Beweis für die Anzahl an Wächtern in orthogonalen Polygonen gezeigt. Dabei wird das Polygon in L-förmige Teilstrukturen unterteilt und anhand dieser Unterteilung die Position der Wächter ermittelt. Es wird ein Algorithmus angegeben der eine Lösung in Zeit O(n log log n) findet.

Das Flutlicht-Problem Gegeben seien drei Winkel, die sich zu 2pi aufsummieren, n Punkte und eine Dreiteilung k1 + k2 + k3 = n. Kann die Ebene in Sektoren mit den angegeben Winkeln aufgeteilt werden, sodass Sektor i genau ki viele Punkte enthält? Wie schnell lässt sich eine Lösung finden? In dem vorliegenden Artikel wird gezeigt, dass eine solche Unterteilung immer möglich ist und eine Lösung in O(n log n) Zeit gefunden werden kann.

Beleuchtung mit orthogonalen Flutlichtern Gegeben sei ein rechtwinklinges Polygon mit n Löchern und h Löchern. Wie viele Flutlichter mit rechtwinkligem Öffnungswinkel werden benötigt, um das Polygon zu beleuchten? In dem vorliegenden Artikel werden scharfe Schranken angegeben, wie viele Lichter immer reichen, und wie deren Positionen in linearer Zeit gefunden werden können.

Das \alpha-Flutlicht Problem Gegeben sei ein einfaches Polygon. Gesucht ist die minimale Anzahl von Flutlichtern mit gegebenem Winkel \alpha, die an den Knoten des Polygons positioniert werden müssen, um das Polygon auszuleuchten. Es wird gezeigt, dass dieses Problem für jeden festen Winkel NP-schwer ist. Es wird weiterhin gezeigt, dass das Problem auch dann NP-schwer ist, wenn die Wächter im inneren des Polygons positioniert werden können und dass beide Varianten APX-schwer sind.


last changed 2017-05-08, 07:37 by Christian Rieck
printemailtop