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

Seminar Algorithmik

Semester Wintersemester 2013/2014 [ Andere Semester: Winter 17/18 · Sommer 17 · Winter 16/17 · Sommer 16 · Winter 15/16 · Sommer 15 · Sommer 13 · Winter 12/13 · Sommer 12 · Winter 11/12 · Sommer 11 · Winter 10/11 · Winter 09/10 · Sommer 09 · Winter 08/09 ]
Modulnr. INF-STD-18, INF-STD-20
Veranst.Nr. INF-ALG-019, INF-ALG-029
Studieng. Diplom Informatik, Master Informatik, Master Wirtschaftsinformatik, Bachelor Informations-Systemtechnik, Master Informations-Systemtechnik, Bachelor Elektrotechnik, Master Elektrotechnik, Bachelor Informatik
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
Assistent
Anonymous Photo Stephan Friedrichs
Ehemaliger Wissenschaftlicher Mitarbeiter
LP 5
SWS 0+2
Voraussetzungen Voraussetzungen für die Bearbeitung der einzelnen Themen sind jeweils individuell aufgeführt. Es ist zu beachten, dass es sich dabei lediglich um empfohlenes Vorwissen handelt; es ist nicht nötig, die entsprechenden Prüfungen abgelegt zu haben. Sind Voraussetzungen in Klammern gesetzt, sind sie zwar hilfreich, aber kein Muss.
Sprache Deutsch oder Englisch, abhängig vom Betreuer
Scheinerwerb

Schriftliche Ausarbeitung und erfolgreicher Seminarvortrag. Die Note wird abhängig von Qualität des Vortrages und der Ausarbeitung bestimmt:

Ausarbeitung

Die Ausarbeitung soll etwa 10 Seiten lang sein. Generell interessiert uns, dass Sie da eine selbst verfasste Zusammenfassung eines selbst verstandenen Artikels abgeben. Wesentlich mehr als zehn Seiten sollen es nicht werden, immerhin geht es hier um die Kunst des Zusammenfassens. Wir erwarten, dass Sie selbstständig zusätzliche Quellen recherchieren.

Die wesentlichen Qualitätskriterien der Ausarbeitung sind vor allem die Strukturierung des Inhalts, selbstständiges Arbeiten, Anteil der Eigenarbeit, Literaturrecherche, präzise Quellenangaben, sowie die Form.

Vortrag

Ihr Vortrag soll 40 Minuten dauern. Das Medium ist frei, Sie können Beamer mit PDF, Beamer mit PowerPoint, Whiteboard, Overheadprojektor, eine Kombination daraus 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.

Wichtige Merkmale eines guten Vortrags sind unter anderem ein souveräner Umgang mit der Vortragssituation, gut ausgearbeitete Materialien, fachlich korrekter Inhalt und vor allem die Aufarbeitung des Inhalts in vortragsgeeigneter Form.

Anmeldung Die Anmeldung für das Seminar erfolgt über Stud.IP, Details sind auf den offiziellen Seiten der Studiengänge Bachelor sowie Master Informatik. Wenn Sie einen Platz bekommen haben, müssen Sie sich zusätzlich noch verbindlich in einer Liste eintragen (Frist: siehe Kalender).
Inhalt Das Seminar Algorithmik beschäftigt sich dieses Semester mit einer Auswahl von klassischen sowie aktuellen Papern rund um unser Lehrangebot.
Termin(e)
[ Kalender abonnieren | Kalender herunterladen ]
Datum Beschreibung
01.11.2013, 15:00 Uhr Vorbesprechung und Themenvergabe (IZ 313)
08.11.2013 Verbindliche Anmeldung (IZ 334)
09.01.2014, 23:59 Uhr Abgabe Ausarbeitung
13.01.2014, 23:59 Uhr Abgabe Folien Vorversion
16.01.2014, 09:00 Uhr Seminarvorträge (IZ 313)
17.01.2014, 09:00 Uhr Seminarvorträge (IZ 313)
Literatur/Links Literaturrecherche: Ausarbeitung und Vortrag:

Ablauf der Vorträge

Donnerstag, 16.01.2014

Zeit # Thema
09:00 - 10:00 (8) Lawn Mowing
10:00 - 11:00 (5) The Orthogonal Milling Problem with Turn Costs
11:00 - 12:00 (6) Minimum Covering with Travel Cost
12:00 - 12:45 Mittagspause
12:45 - 13:45 (4) Geometric Complexity of Some Location Problems
13:45 - 14:45 (10) Minkowski Sums

Freitag, 17.01.2014

Zeit # Thema
09:00 - 10:00 (2) Fast Lower Bounds for Bin Packing Problems
10:00 - 11:00 (3) Approximation Algorithms for Scheduling
11:00 - 12:00 (9) The Freeze-Tag Problem
12:00 - 12:45 Mittagspause
12:45 - 13:45 (7) Robot Dispersion
13:45 - 14:45 (1) Minimum Dilation Spanning Trees
14:45 - 15:45 (11) Witnessability

Themen für Bachelorstudenten

(1) Minimum Dilation Spanning Trees

Will man eine Menge von n Punkten mit möglichst kurzer Gesamtlänge verbinden, dann berechnet man einen Minimalen Aufspannenden Baum (MST). Dabei kann aber möglicherweise die Länge im Baum zwischen zwei Punkten deutlich größer sein als wenn man sie direkt verbindet. Diesen "Umwegfaktor" nennt man auch "Dilation". Wie schwer ist es, einen Baum mit möglichst kleinem Umwegfaktor zu bestimmen? Hier wird gezeigt, dass das ein NP-schweres Problem ist.

Voraussetzungen: Algorithmen und Datenstrukturen II oder Netzwerkalgorithmen
Student: Maximilian Kühl
Betreuer: Wenbo Xu

(2) Fast Lower Bounds for Bin Packing Problems

Will man eine Menge von Objekten in möglichst wenige Container packen, dann hat man es mit dem NP-schweren Problem "Bin Packing" zu tun. Wie kann man dafür möglichst schnelle und trotzdem gute untere Schranken für die Zahl der Container berechnen? Das wird hier untersucht.

Voraussetzungen: Algorithmen und Datenstrukturen II
Student: Maik Hansemann
Betreuer: Christos Orlis

(3) Approximation Algorithms for Scheduling

Voraussetzungen: -
Student: Kai Brennecke
Betreuer: Christos Orlis

Themen für Bachelor- und Masterstudenten

(4) Geometric Complexity of Some Location Problems

Betrachtet man n Punkte auf der Geraden oder in der Ebene, gibt es eine ganze Reihe von möglichen Standortproblemen. Für viele davon (z.B. den Median) kann man Linearzeitalgorithmen angeben. Für andere (z.B. die Entscheidung, ob es zwei gleiche Punkte oder eine große Lücke gibt) ist das nicht so einfach. Hier wird gezeigt, dass das unter bestimmten Annahmen gar nicht möglich ist, weil man mindestens Omega(n log n) Rechenzeit benötigt.

Voraussetzungen: Algorithmen und Datenstrukturen II (für Bachelor), Computational Geometry (für Master)
Student: Julian Troegel
Betreuer: Dr. Michael Hemmer

(5) The Orthogonal Milling Problem with Turn Costs

Beim Milling-Problem geht es darum, eine Fläche (einen Rasen) abzudecken (zu mähen), ohne sie dabei zu verlassen (ohne Abkürzungen durch Blumenbeete zu nehmen). Besonders teuer ist dabei das Abbiegen. Wie schwer ist das Problem? Welche Schranken gibt es für Lösungen? Wie kann man es approximieren? All das wird hier untersucht.

Voraussetzungen: Algorithmen und Datenstrukturen II oder Netzwerkalgorithmen (für Bachelor)
Student: Maximilian Ernestus
Betreuer: Prof. Dr. Sándor P. Fekete

(6) Minimum Covering with Travel Cost

Wir betrachten n Punkte auf einer Geraden oder in der Ebene. Diese sollen überdeckt werden, z.B. indem man sie abscannt. Dafür muss man auch noch von Scanpunkt zu Scanpunkt fahren. Die Gesamtkosten hängen dabei von der Gesamtzahl der Scanpunkte und der zurückgelegten Distanz ab. Wie kann man das machen, ohne dass eine der beiden Größen mehr als notwendig in Anspruch nimmt? Dafür lassen sich Approximationslösungen angeben.

Voraussetzungen: Algorithmen und Datenstrukturen II (für Bachelor), Computational Geometry (für Master)
Student: Arne Schmidt
Betreuer: Marina Tvorogova

(7) Robot Dispersion

Voraussetzungen: -
Student: Inga Menke
Betreuer: Dr. Henning Hasemann

(8) Lawn Mowing

Voraussetzungen: -
Student: Maria Born
Betreuer: Prof. Dr. Sándor P. Fekete

(9) The Freeze-Tag Problem

Voraussetzungen: -
Student: Jan-Marc Reinhardt
Betreuer: Prof. Dr. Sándor P. Fekete

(10) Minkowski Sums

Voraussetzungen: -
Student: Emanuel Fürchtegott
Betreuer: Dr. Michael Hemmer

Themen für Masterstudenten

(11) Witnessability

Um das Art-Gallery-Problem zu lösen ist folgende Frage von großem Interesse: Ist es möglich, endlich viele Punkte W (Witnesses) im Polygon zu platzieren, so dass jede Auswahl von Wächtern, die W bewacht, automatisch auch das ganze Polygon bewacht? Der entsprechende Artikel beantwortet diese Fragen und gibt einen exzellenten Einblick in Sichtbarkeitsprobleme in Polygonen.

Voraussetzungen: Computational Geometry
Student: Konstantin Birker
Betreuer: Stephan Friedrichs

aktualisiert am 15.01.2014, 16:55 von Stephan Friedrichs
printemailtop