50 Jahre Uni Lübeck

Institut für Theoretische Informatik

Ankündigungen 2010


  • Bronzemedaille für Team Lübeck 2 beim ACM Programmierwettbewerb

    22. November 2010

    Wir gratulieren ganz herzlich Team Lübeck 2 zur Bronzemedaille und Platz 10, sowie Team Lübeck 1 zum 32. Platz unter 67 teilnehmenden Teams.



  • Teamcoach PD Dr. M. Liskiewicz mit Team Lübeck 1 und 2


    Übergabe der Bronzemedaille an das Team Lübeck 2


    Team Lübeck 2: Ingmar Kaden, Sebastian Hungerecker, Martin Schuster


    Team Lübeck 1: Philipp Harms, Fabian Guth, Alexander Idelberger


  • Lübecker Studenten beim weltweit größten Programmierwettbewerb

    21. November 2010

    67 Teams konkurrieren in Bremen um die Teilnahme am Finale in Ägypten.

    Mit zwei Studententeams ist die Universität Lübeck an der nordwesteuropäischen Meisterschaft im Programmieren beteiligt. Die Ausscheidung für den 32. International Collegiate Programming Contest (ICPC) findet am Sonntag, dem 21. November 2010, in Bremen statt. Die besten Problemlöser qualifizieren sich für das Weltfinale im kommenden Jahr in Sharm el-Sheikh (Ägypten). Ausrichter dieses weltweit größten Wettbewerbs für Studierende der Informatik ist die Association for Computing Machinery (ACM).


    Aus Lübeck haben sich die Informatikstudenten Philipp Harms, Fabian Guth und Alexander Idelberger (Team 1) sowie Ingmar Kaden, Sebastian Hungerecker und Martin Schuster (Team 2) qualifiziert. In einem fünfstündigen Wettbewerb gilt es, für möglichst viele Problemstellungen eine effiziente Lösungsstrategie zu entwickeln und diese auch technisch korrekt umzusetzen. Betreut werden die Studenten von Priv.-Doz. Dr. rer. nat. Maciej Liskiewicz, der als Teamleiter mit nach Bremen fährt..


    Der North Western European Regional Contest (NWERC19) für den Internationalen Programmierwettbewerb findet vom 19. – 21. November an der Jacobs Universität Bremen statt. Insgesamt 67 Teams aus Großbritannien, Skandinavien, den Benelux-Staaten, Dänemark und Deutschland nehmen teil. Außer aus Lübeck kommen die deutschen Teams aus Rostock, Konstanz, Ulm, Karlsruhe, München, Bremen, Oldenburg, Nürnberg, Halle, Saarbrücken, Hamburg und Mainz.

    Die Problemstellungen des Bremer Wettbewerbs und die aktuelle Rangliste werden unter http://www.nwerc.eu/index.php veröffentlicht.

  • Kolloquium der Institute für Mathematik und Informatik

    9. November 2010, 16 Uhr c.t. im Seminarraum ITCS 2021, Gebäude 64 - 2. OG

    Dr. Fabian Wagner, Universität Ulm, Institut für Theoretische Informatik, hält einen Vortag:
    Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs


    The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time [Bo90,YBFT99]. We give restricted space algorithms for these problems proving the following results:

    • Isomorphism for bounded tree distance width graphs is in logspace and thus complete for the class. We also show that for this kind of graphs a canon can be computed within logspace.
    • For bounded treewidth graphs, when both input graphs are given together with a tree decomposition, the problem of whether there is an isomorphism which respects the decompositions (i.e. when only isomorphisms are considered, mapping bags in one decomposition blockwise onto bags in the other decomposition) is in logspace.
    • For bounded treewidth graphs, when one of the input graphs is given with a tree decomposition the isomorphism problem is in LogCFL.
    • As a corollary the isomorphism problem for bounded treewidth graphs is in LogCFL. This improves the known TC^1 upper bound for the problem given by Grohe and Verbitsky [GV06].
    This is joint work with Bireswar Das and Jacobo Torán
  • Kolloquium der Institute für Mathematik und Informatik

    07. Juli 2010, 17 Uhr c.t. in den Seminarräumen Cook/Karp, Gebäude 64 - EG

    Assistant Professor Bodo Manthey, Universität Twente, Department for Applied Mathematics, hält einen Vortag :
    Clustering und Smoothed Analysis:Warum ist k-Means schnell?


    Die k-Means-Methode ist einer der populärsten Clustering-Algorithmen. Der Hauptgrund dafür ist ihre hervorragende Laufzeit in der Praxis. Dem gegenüber steht eine exponentielle Worst-Case-Laufzeit.


    Wir schließen diese Lücke zwischen Theorie und Praxis mittels Smoothed Analysis: Ein Adversary wählt Datenpunkte, die dann anhand von Gaußverteilungen leicht verrauscht werden. Dies modelliert beispielsweise Messfehler und zerstört pathologische Worst-Case-Instanzen. Die Smoothed-Laufzeit ist die maximale erwartete Laufzeit, die der Adversary erreichen kann.


    Wir zeigen, dass die Smoothed-Laufzeit der k-Means-Methode polynomiell in der Anzahl der Datenpunkte und dem Kehrwert der Standardabweichung der Störung ist. Anschließend analysieren wir die k-Means-Methode für allgemeinere Distanzmaße, so genannte Bregman-Divergenzen. Diese umfassen Mahalanobis- Distanzen und Kullback-Leibler-Divergenz.

  • Verleihung des Philips Best Bachelor Preises

    25. Juni 2010

    Wir gratulieren Herrn Marcel Poelker zum Philips Best Bachelor Preis

  • ACM German Collegiate Programming Contest GCPC 2010

    Samstag, 12.06.2010, 10 - 15 Uhr im Seminarraum ITCS 2021

    Am Samstag 12.6.10 fand eine deutschlandweite Generalprobe für den im Herbst stattfindenden Internationalen ACM-Programmierwettbewerb statt. Live-Bericht / Veranstaltungsseite

  • Studentisches-Kolloquium der Institute für Informatik und Mathematik

    Mittwoch, den 05.05.10 17 Uhr in den Seminarräumen Karp/Cook, EG Gebäude 64 (bei nicht ausreichender Sitzplatzkapazität steht der Hörsaal AM3 zur Verfügung).

    Dr. Wolfgang Hildesheim, IBM Hamburg, hält einen Vortrag mit dem Titel:
    Information Management und industrielle Praxis - IBM und das Extreme Blue Programm

    “The world is getting more instrumented, interconnected und intelligent.” – eine Flut an Informationen folgt, welche intelligent verarbeitet werden muss. Dies ist das Herzstück der SMARTER PLANET Strategie der IBM Corporation. Die größten Herausforderungen, die Unternehmen in diesem Zusammenhang überwinden müssen, sind zum einen die Informationsexplosion und zum anderen die Überwindung von Datensilos, d.h. die Zusammenführung und Bereinigung aller Daten in Anwendungen, Prozessen und anderen Quellen für einen unternehmensweiten, zentralen Überblick. Unternehmen, die die anfallende Informationsflut gut meistern, bzw. sogar zu ihrem Nutzen auswerten können haben einen entscheidenden Wettbewerbsvorteil. Insofern kommt der Fähigkeit der "Value Creation" auf der Basis der verfügbaren Informationen eine entscheidende Bedeutung zu. Hinzu kommen ständig neue und schärfere Gesetze bzw. Regelungen bei den Themen Datenschutz, Datenarchivierung, Rechnungslegung und Risikomanagement.


    Anhand der "Information Agenda Strategie" der IBM und den zugehörigen Technologien soll in das Thema eingeführt werden. Information Management ist eine der fünf Softwarebrands der IBM und ermöglicht die Verwaltung digitaler Informationen in Datenbankumgebungen, durch Informationsintegrations-Lösungen sowie z.B. Business-Intelligence Lösungen oder Werkzeugen zur Vorhersage von Trends. Dies wird überblicksartig gezeigt und gemeinsam diskutiert.


    Anhand des Vortrages sollen typische unterschiedliche Tätigkeiten in der IT-Industrie vorgestellt werden, um einen Einblick in den industriellen Arbeitsprozeß zu geben.


    Abschließend soll das "Extreme Blue" Programm der IBM vorgestellt werden, bei dem Studenten die Möglichkeit haben kurzzeitig bei TOP-Entwicklungsprojekten mitzuarbeiten.

  • Forschungsseminar zur Komplexitätstheorie

    Montag, den 22.02.10 von 12.30 Uhr bis 17.20 Uhr im Seminarraum ITCS 2021

    Am 22.02.10 von 12.30 Uhr bis 17.20 Uhr findet ein Forschungsseminar zur Komplexitätstheorie im Institut für Theoretische Informatik statt. Interessierte Studierende und Mitarbeiter anderer Institute sind dazu herzlich eingeladen. (Kontakt: Ilka Schnoor, Michael Elberfeld)

    Planung

    Uhrzeit Vortragende und Themen
    12.30 Eintreffen
    12.40 Oleg Verbitsky (HU Berlin)
    A LOGSPACE Isomorphism Test for Interval Graphs
    Zusammenfassung anzeigen
    13.30 Mittagspause
    14.45 Peter Lohmann, Heribert Vollmer (Uni Hannover)
    Complexity Results for Modal Dependence Logic
    Zusammenfassung anzeigen
    15.30 Michael Elberfeld (Uni Lübeck)
    Computing Tree Decompositions of Bounded Width in Logspace
    Zusammenfassung anzeigen
    16.15 Kaffeepause
    16.35 Martin Mundhenk (Uni Jena)
    Formelauswertung für intuitionistische Logik
    Zusammenfassung anzeigen
    17.20 Ende