Mehr als 250 Studentinnen und Studenten aus ganz Nordwesteuropa trafen sich Ende November in den Niederlanden zum "Um-die-Wette-Programmieren". Die Universität zu Lübeck war mit drei Teams und zwei Betreuern vertreten.
Vom 22. November 2013 bis 24. November 2013 fand in Delft (Niederlande) der Northwestern European Regional Contest statt, die nordwesteuropäische Vorrunde zum internationalen studentischen Programmierwettbewerb ACM-ICPC. 92 Teams zu je drei Studentinnen und Studenten aus 46 Universitäten und zehn Ländern waren von der TU Delft eingeladen worden, sich im Programmieren zu messen. Die Teams aus Lübeck belegten ehrenvolle Plätze im Mittelfeld (44, 48 und 54). Sieger des Wettbewerbs war das Team "geen.opdracht5" der TU Delft. Die Plätze zwei und drei gingen an Mannschaften aus Cambridge (Großbritannien) und dem Saarland (Deutschland). Diese drei Teams werden die Region Nordwesteuropa bei der internationalen Endrunde 2014 in Jekaterinburg (Russland) vertreten.
Ziel des fünfstündigen Wettbewerbs war es, möglichst viele der insgesamt zehn gegebenen Probleme zu lösen. Die gestellten Aufgaben waren zwar oft kurzweilig formuliert (zum Beispiel: Wie weit muss man springen, um trockenen Fußes über eine Gracht (niederländischer Kanal) zu kommen? Wie viel Silber kann ein Marineoffizier ergattern, der eine Flotte von Transportschiffen angreift? Wie wahrscheinlich ist es, dass ein Kartentrick funktioniert? Wie kann man einen Weihnachtsbaum gleichmäßig mit Kugeln schmücken?), waren aber alles Andere als einfach zu lösen. Man musste neben hervorragenden Programmierkenntnissen in den Programmiersprachen Java, C oder C++ über ein breites Wissen in verschiedenen Bereichen der Informatik und Mathematik verfügen. Darüber hinaus galt es, geschickt zu taktieren und einfachere Probleme schnell zu identifizieren und zu lösen, denn bei Punktgleichstand entschied die benötigte Zeit über Sieg und Niederlage. Für jede falsche Antwort gab es 20 Strafminuten, die eingereichte Lösung sollte also möglichst beim ersten Mal richtig sein und mit den geheimen Testfällen der Jury funktionieren. Am Ende hatte das Team "geen.opdracht5" als einziges alle zehn Probleme richtig gelöst und wurde unter viel Beifall und Anerkennung aller Beteiligten zum Sieger gekürt.
Das offizielle Scoreboard des NWERC2013 kann man hier ansehen.
Die Teams aus Lübeck:
Weitere Bilder vom Wettbewerb finden sich hier. Bilder aus dem Training finden sich hier
Die Teams der Universität zu Lübeck bedanken sich bei ihren Sponsoren NXP Semiconductors Germany GmbH und den Lübecker Nachrichten für die Unterstützung.
Dozentinnen/Dozenten Prof. Dr. math. Rüdiger K. Reischuk, Oliver Witt, M.Sc.
Angaben Kurs, Anmeldung bis 19.9.2012 bei witt@tcs.uni-luebeck.de Zeit und Ort: Blockveranstaltung 23.09.2013 9:00 - 07.10.2013 18:00, ITCS 2021
Voraussetzungen / Organisatorisches Bachelor-Absolventen, die das Masterstudium Informatik an der Universität zu Lübeck beginnen wollen, und im Bereich der Theoretische Informatik über geringere Kenntnisse verfügen als im Lübecker Bachelorstudiengang vermittelt wird 10-tägige LV, jeweils 2 x 1,5h vormittags und 2 x 1,5h nachmittags teils als Vorlesung, teils seminaristisch, teils als Übung
Inhalt kurze Auffrischung: Formale Sprachen, Grammatiken und Automaten das Turing-Maschinenmodell, (Un-)Entscheidbarkeit und Aufzählbarkeit Halteproblem, Church-Turing These, Satz von Rice Platz- und Zeitmaße, Effizienz, Komplexitätsklassen Polynomialzeitreduktion, NP-Vollständigkeit Erfüllbarkeitsproblem, graphtheoretische Optimierungsprobleme Modellierung und Analyse algorithmischer Konzepte beherrschen Möglichkeiten und Grenzen der Informatik beurteilen können algorithmische Probleme nach ihrer Komplexität klassifizieren können
Empfohlene Literatur J. Hopcroft, R. Motwani, J. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley S. Arora, B. Barak, Computational Complexity, Cambridge University Press
Wir gratulieren Martin Schuster ganz herzlich zum besten Studienabschluss im Master Informatik.
Der Preis wurde anlässlich der Absolventenfeier am 13.07.2013 überreicht. Weitere Einzelheiten....
The conference WG 2013 continues the series of 38 previous WG's. Since 1975, it took place twenty one times in Germany, four times in the Netherlands, twice in Austria, the Czech Republic and France as well as once in Italy, Slovakia, Switzerland, Norway, the United Kingdom, Greece and in Israel. WG conferences aim to connect theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas of Computer Science and by extracting new problems from applications. The goal is to present recent results and to identify and explore directions of future research. WG 2013 will be held in the Radisson Blu Senator Hotel in Lübeck.
Bei dem Minimum-Cost-Flow-Problem handelt es sich um ein klassisches kombinatorisches Optimierungsproblem. In den letzten 50 Jahren wurden eine Reihe von Algorithmen für Minimum-Cost-Flows entwickelt, und es scheint, dass sowohl das Problem als auch die Algorithmen gut verstanden sind. Allerdings widersprechen empirische Studien den bewiesenen Worst-Case-Laufzeiten. Der Successive-Shortest-Path-Algorithmus (SSP) beispielsweise hat im Worst-Case exponentielle Laufzeit, zeigt in der Praxis aber eine bessere Laufzeit als einige polynomiale Algorithmen.
Smoothed Analysis ist eine Methode, um Performance-Garantien für Algorithmen zu beweisen, die im Worst-Case schlecht sind. Hierbei wird die erwartete Laufzeit analysiert, wenn Instanzen leicht "verrauscht" werden. Dieses Verrauschen kann zum Beispiel Messfehler modellieren.
Um diese Diskrepanz zwischen Worst-Case- und beobachteter Laufzeit von SSP zu erklären, führen wir eine Smoothed Analysis von SSP durch. Wir beweisen eine Smoothed-Laufzeit von O(nm*phi*(m+n*log n)), wobei phi der Smoothing-Parameter ist. Dies zeigt, dass Worst-Case-Instanzen für SSP nicht robust sind und dass es unwahrscheinlich ist, in der Praxis eine Worst-Case-Instanz zu bekommen.
Der Vortrag basiert auf einer Zusammenarbeit mit Tobias Brunsch, Heiko Röglin (Universität Bonn) und Kamiel Cornelissen (Universiteit Twente).
39 Teams aus 6 Universitäten traten am 15. Juni 2013 beim GCPC'13 (German Collegiate Programming Contest) der ACM (Association for Computing Machinery) gegeneinander an. Der GCPC ist ein offizieller Vorwettbewerb zu dem regionalen Wettbewerb für Nord-West-Europa (NWERC), der am 22.-24. November 2013 in Delft stattfindet.
Von der Universität zu Lübeck haben in diesem Jahr drei Teams teilgenommen. Wir freuen uns, dass auch zwei weitere Teams aus Hamburg und Rostock als Gastteams bei uns am Wettbewerb teilgenommen haben (sie haben allerdings außer Konkurrenz teilgenommen). Gewonnen hat das Team "hacKIT" aus Karlsruhe. Platz zwei und drei belegten die Teams "We don't have a team name" aus LMU München und "3 fast 3 FAUrious" aus Erlangen. Unser Team "Teammate" (Paul Ketelsen, Ruben Beyer, Malte Skambath) erreichte mit 5 gelösten Problemen Platz 5, Team "Kuno" (Max Bannach, Marco Kabelitz, Claudius Pott) und Team "Ballmer Peak" (Alexander Idelberger, Norman Freier, Fabian Klötzl) haben jeweils 4 Probleme gelöst und die Plätze 8 und 9 erreicht. Wir gratulieren ganz herzlich zu dieser Leistung.
Die offiziellen Ergebnisse von GCPC 2013 sind auf der Seite veröffentlicht worden.
Unsere Lübecker Teams:
Unser Gastteam aus Rostock:
Unser Gastteam aus Hamburg:
Weitere Bilder finden sich hier.
In diesem Vortrag wird ein System erläutert, welches die übliche state-of-the-art Odometrie mit freiverfügbaren Stadtplänen kombiniert, um letztendlich von einem Video den Pfad der Kamera durch die Stadt zu ermitteln.
Dabei wird ausgehend von dem durch ein Visualodometry-System ermitteltem Bewegungspfad eine 3D-Punktwolken-Rekonstruktion der Umgebung erstellt, in welcher wiederum Objekte erkannt werden, und die zusammen mit dem Pfad gegen einen gegebenen Stadtplan gematcht wird, um die Genauigkeit des ermittelten Pfades zu verbessern sowie die globale Startposition in einem Weltkoordinatensystem zu finden.
Ursprünglich durch eine biologische Fragestellung motiviert, werden Blattpotenzen heute als neue natürliche Teilklasse der gut untersuchten chordalen Graphen verstanden. Während ein Graph genau dann chordal ist, wenn er für einen Baum T der Durschnittsgraph einer Menge von Teilbäumen in T ist, verlangen Blattpotenzen zusätzlich, dass jeder Teilbaum eine Scheibe bildet, d.h. für einen Zentralknoten v in T und einen Radius r genau die Knoten von T enthält, die zu v höchstens Abstand r haben. Damit ergeben die Blattpotenzen außerdem eine schöne Verallgemeinerung der bekannten Unit-Interval-Graphen, bei denen T ein Pfad sein muss und alle Radi gleich.
Während chordale Graphen und Unit-Interval-Graphen in Linearzeit erkannt werden können und seit langem durch verbotene induzierte Teilgraphen charakterisiert wurden, sind effiziente Erkennungsalgorithmen oder eine vollständige Charakterisierung der Blattpotenten bisher nicht bekannt. Der Vortrag stellt einen neuen Zugang zu diesen Fragestellungen vor und präsentiert erste neue Ergebnisse, die auf eine baldige Lösung hoffen lassen.
