TU BRAUNSCHWEIG
| Carl-Friedrich-Gauß-Fakultät | Informatik
Informatikzentrum

Master-Seminar Algorithmik

Semester Wintersemester 2016/2017 [ Andere Semester: Winter 17/18 · Sommer 17 · Sommer 16 ]
Modulnr. INF-STD-18, INF-STD-20
Veranst.Nr. INF-ALG-019, INF-ALG-029
Studieng. Master Informatik, Master Wirtschaftsinformatik, Master Elektrotechnik
IBR Gruppe(n) ALG (Prof. Fekete)
Art Seminar
Dozent
Photo Prof. Dr. Sándor P. Fekete
Abteilungsleiter
s.fekete[[at]]tu-bs.de
+49 531 3913111
Raum 335
Assistenten
Photo Dr. Victor Alvarez
Ehemaliger Wissenschaftlicher Mitarbeiter
alvarez[[at]]ibr.cs.tu-bs.de
Photo Phillip Keldenich
Wissenschaftlicher Mitarbeiter
keldenich[[at]]ibr.cs.tu-bs.de
+49 531 3913112
Raum 318
Photo Dr. Christian Scheffer
Wissenschaftlicher Mitarbeiter
scheffer[[at]]ibr.cs.tu-bs.de
+49 531 3913113
Raum 331
Photo Arne Schmidt
Wissenschaftlicher Mitarbeiter
aschmidt[[at]]ibr.cs.tu-bs.de
+49 531 3913115
Raum 319
Photo Dominik Krupke
Wissenschaftlicher Mitarbeiter
krupke[[at]]ibr.cs.tu-bs.de
+49 531 3913116
Raum 315
Photo Christian Rieck
Wissenschaftlicher Mitarbeiter
rieck[[at]]ibr.cs.tu-bs.de
+49 531 3913114
Raum 314
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 aktuellen Artikeln sowie Ausschnitten aus Büchern. Die genauen Themen sowie eine Abstract sind weiter unten aufgeführt.
Termin(e)
[ Kalender abonnieren | Kalender herunterladen ]
Datum Beschreibung
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: Ausarbeitung und Vortrag:

Hinweise

Teilnehmerzahl

Es werden 4 Plätze für Studierende auf Masterniveau angeboten.

Ausarbeitung

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

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 Masterstudenten

Grundsätzlich ist es im Masterbereich möglich, an aktuellen Forschungsthemen aus der Algorithmik zu arbeiten. Falls kein spezielles Thema gewünscht ist, wird nach Rücksprache mit dem Teilnehmer ein Thema aus einer Liste von Themen zugewiesen.

Die Themen dieses Semesters sind:

Gomory-Hu Trees

The network flow problem was first introduced by Ford Fulkerson who introduced the basic concept of flow, cut, etc. and provided the main tool, the maximum-flow minimum-cut theorem. Ford and Fulkerson wrote about the flow between two special points, the source and the sink. Mayeda then took up the multi-terminal problem, where flows are considered between all pairs of nodes in a network. In the discussed paper of Gomory and Hu it is continued with the multi-terminal problem, giving results on realizability, analysis and synthesis.

The Geometric Maximum Traveling Salesman Problem

The classical Traveling Salesman Problem asks for a tour through a given set of vertices such that the total distance of this tour is minimized. Instead of minimizing the total length, one can also asks for a maximum total tour length. It can be shown that such an optimal tour can be computed in time O(n) if distances are determined by the Manhatten metric, while it is NP-hard under Euclidean distances.

Algorithms for Ham-Sandwich Cuts

Given disjoint sets P_1, P_2, ..., P_d in R^d with n points in total, a ham sandwich cut is a hyperplane that simultaneously bisects the P_i. There is an algorithm for finding ham-sandwich cuts in every dimension d>1. When d=2, the algorithm is optimal, having complexity O(n). For dimension d>2, the bound on the running time is proportional to the worst-case time needed for constructing a level in an arrangement of n hyperplanes in dimension d-1.

Generalizing Ham-Sandwich Cuts to Equitable Subdivisions

Given gn red points and gm blue points in the plane in general position, there exists an equitable subdivision of the plane into g disjoint convex polygons, each of which contains n red points and m blue points.This is a generalization of the Ham Sandwich Theorem for the plane. There is also an efficient algorithm for constructing such equitable subdivisions.

aktualisiert am 01.11.2016, 17:22 von Phillip Keldenich
printemailtop