Seminar Algorithmik

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.

• Google Scholar
• ACM Digital Library
• Citeseer (Research Index) Citation Index
• DBLP
• Universitätsbibliothek der TU-Braunschweig

• Tipps+Tricks zu (La)TeX
• slidetemplates

Ablauf der Vorträge

Donnerstag, 16.01.2014

Freitag, 17.01.2014

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.

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

(3) Approximation Algorithms for Scheduling

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.

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

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

(7) Robot Dispersion

(8) Lawn Mowing

(9) The Freeze-Tag Problem

(10) Minkowski Sums

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.