50 Jahre Uni Lübeck

Institut für Theoretische Informatik

Ankündigungen 2005


  • 52. Theorietag findet in Lübeck statt

    16.–17. August 2005, Universität zu Lübeck

    Der 52. Workshop über Komplexitätstheorie, Datenstrukturen und Effiziente Algorithmen findet in Lübeck statt.

  • FCT 2005 Konferenz findet in Lübeck statt

    17.–20. August 2005, Scandic Hotel Lübeck

    Die fünfzehnte FCT Konferenz (15th International Symposium on Fundamentals of Computation Theory) findet dieses Jahr in Lübeck statt.

  • 6. Lübecker Hochschultag

    17. November 2005, Musik- und Kongresshalle (MuK) Lübeck, Willy-Brandt-Allee 10

  • Wir gratulieren Bodo Manthey zur erfolgreichen Promotion zum Dr. rer. nat. mit summa cum laude und zur Verleihung des Fakultätspreises der Universität zu Lübeck für die beste Promotion 2005.

  • Der Protest geht weiter!

  • Lübeck kämpft für seine UNI !

    Bilder von der Demonstration am 10.11.2005
  • 07. Dezember 2005, 17 Uhr ct, Raum Cook/Karp, Geb. 64
    Prof. Kurt Mehlhorn, Max-Planck-Institut für Informatik, Saarbrücken
    Curve and Surface Reconstruction (der Vortrag wird in deutscher Sprache gehalten)
    Abstract zu seinem Vortrag und PDF-File zum Downloaden
  • 25. Oktober 2005, 16 Uhr ct, R 21, Geb. 64, 2. OG.
    Dipl.-Ing. Dipl.-Math. Martin Zinner, Dresden
    Ausfalldetektoren und das Consensus-Problem im Crash-Recovery-Modell

    Der Vortrag stellt eine neue und pragmatische Herangehensweise vor, um Consensus in asynchronen Systemen, die mit Ausfalldetektoren (failure detectors) versehen sind, zu lösen. Diese Herangehensweise kann in praktischen Systemen implementiert werden. Das betrachtete Fehlermodell läßt zu, daß Netzwerkverbindungen verloren gehen, daß Prozesse abstürzen und daß unter bestimmten Umständen der Ausfall von Prozessen nicht erkannt wird, bzw. daß aktive Prozesse verdächtigt (d.h. als abgestürzt eingestuft) werden. Byzantinische Fehler treten nicht auf, abgestürzte Prozesse können hochgefahren werden.

    Consensus kann mit Hilfe von Ausfalldetektoren, die schwache Vollständigkeit (d.h. jeder abgestürzte Prozeß wird von wenigstens einem Prozeß schließlich permanent verdächtigt) erfüllen, gelöst werden. Fälschlicherweise verdächtigte Prozesse werden gegebenenfalls heruntergefahren.

    Erfüllt der Ausfalldetektor starke Vollständigkeit (d.h. abgestürzte Prozesse werden von allen Prozessen schließlich permanent verdächtigt) und ausgewählte Genauigkeitseigenschaften (accuracy properties), dann werden falsch verdächtigte Prozesse nicht heruntergefahren.

  • 04. Oktober 2005, 11 Uhr ct, R 21, Geb. 64, 2. OG.
    Dipl.-Inf. Tino Teige, Uni Rostock
    Zum Transversal-Problem auf Hypergraphen und seiner Bedeutung

    Das Transversal-Problem auf Hypergraphen weist als eine Verallgemeinerung des Vertex-Cover-Problems auf Graphen einen engen Bezug zu zahlreichen Problemen aus verschiedenen Gebieten der Informatik wie z.B. den Datenbanken, der Logik, der Künstlichen Intelligenz und der Spieltheorie auf. Die genaue Komplexität des Problems für den allgemeinen Fall ist noch nicht geklärt. Das Entscheidungsproblem liegt in co-NP, aber es wird vermutet, dass es nicht co-NP-vollständig ist. Für eine Reihe von Teilklassen der Hypergraphen ist das Problem in (output-)polynomialer Zeit lösbar.

    In diesem Vortag wird zunächst das Transversal-Problem definiert und bekannte Ergebnisse zu seiner Komplexität zusammengetragen. Kurz werden einige seiner verwandten Probleme aus der Logik vorgestellt. Im Hauptteil dieses Vortrags werden die wichtigsten natürlichen Teilklassen der Hypergraphen untersucht, für die das Transversal-Problem effizient gelöst werden kann.

    Eine sehr wichtige Teilklasse stellen die simplen a-azyklischen Hypergraphen dar. Die Komplexität des Transversal-Problems für diese Teilklasse war bis zum Jahr 2003 ein offenes Problem. Mit Hilfe des in dieser Arbeit eingeführten Konzeptes der isolierten Eliminationsordnung wird direkt auf Hypergraphen gezeigt, dass für simple a-azyklische Hypergraphen das Transversal-Problem (output-)polynomial ist. Im Gegensatz zum bisherigen Ergebnis wird der Umweg über die Logik vermieden und zudem die Zeitschranke verbessert.

  • 04. Oktober 2005, 13 Uhr ct, R 21, Geb. 64, 2. OG.
    Dipl.-Inf. Christian Hoffmann, TU Ilmenau
    Ein schneller randomisierter Primzahltest

    Primzahltests sind Algorithmen, die Primzahlen von zusammengesetzten Zahlen unterscheiden. Wir betrachten hierbei Monte-Carlo-Algorithmen mit einseitigem beschränkten Fehler. Sie klassifizieren Primzahlen immer richtig, während sie zusammengesetzte Zahlen mit unabhängig von der Eingabe beschränkter Wahrscheinlichkeit auch fälschlicherweise als Primzahlen einstufen können. Durch mehrmalige Wiederholung eines solchen Primzahltests erhält man ein für die Praxis ausreichend verlässliches Verfahren zur Erkennung von Primzahlen.

    Sehr häufig wird der Miller-Rabin-Primzahltest eingesetzt. Er hat eine Fehlerwahrscheinlichkeit von höchstens 1/4. Ein neuer Primzahltest ist der randomisierte starke quadratische Frobenius-Test (RQFT), der in [Gra98] vorgeschlagen wird und Fehlerwahrscheinlichkeit <1/7710 hat, während die Laufzeit asymptotisch der von drei Iterationen des Miller-Rabin-Tests entspricht.

    Der RQFT wird im Vortrag vorgestellt. Dazu wird erläutert, auf welchen mathematischen Zusammenhängen der Test beruht. Außerdem wird die Laufzeit des RQFT diskutiert. Ausgehend von der Darstellung in [Gra98] wird auch auf eine alternative Implementierung eingegangen --- [CP01, Abschnitt 3.5.3], zugeschnitten auf den RQFT ---, die sich als etwas schneller erwiesen hat. Ergebnisse von experimentellen Laufzeitmessungen werden ebenfalls präsentiert.

    [Gra98] Grantham, Jon: A Probable Prime Test With High Confidence.
    Journal of Number Theory, 72:32--47, 1998.

    [CP01] Crandall, Richard und Carl Pomerance: Prime Numbers ---
    A Computational Perspective. Springer, 2001.
  • 04. Oktober 2005, 15 Uhr ct, R 21, Geb. 64, 2. OG.
    Dipl.-Inf. Christian Hundt, Uni Rostock
    Weitenbeschränkte Datenbankanfragesprachen

    Der Einfluss von Datenbanken in heutiger Software nimmt stetig zu. Nichtsdestoweniger ist das zentrale Problem in der Datenbanktheorie (Conjunctive Query; CQ) schwierig in Bezug auf die Berechnung mit dem Computer. Das CQ-Problem, welches nach der Antwort zu einer gegebenen Anfrage (genauer: konjunktiven Anfrage) sucht, ist im allgemeinen NP-schwer.

    Während praktische Datenbanksysteme dies ignorieren, gibt es eine Reihe theoretischer Lösungsansätze zu diesem Problem. Für Anfragen mit kreisfreier oder nahezu kreisfreier Struktur (beschränkte Weite) kann das CQ-Problem effizient berechnet werden und ist zudem gut parallelisierbar. Die zur Zeit attraktivste Methode heißt Hyperbaumweite und wurde von Gottlob, Leone und Scarcello in 2002 vorgestellt. Verwandte Begriffe sind Anfrageweite (Chekuri und Rajaraman, 1997) und Baumweite (Freuder, 1990). Der gemeinsame Nachteil dieser Methoden ist die abstrakte, unintuitive und nichtkonstruktive Art, in der sie eingeführt wurden.

    Im Vortrag wird ein konstruktiver und praktischer Ansatz zur Formulierung von konjunktiven Anfragen mit beschränkter Weite vorgestellt: Konstruktorweite. Der neue Begriff ist verwandt zur Hyperbaumweite und Anfrageweite. Als Beispiel für eine praktische Anwendung der eingeführten Methode werden Datenbankanfragesprachen vorgestellt, die den Grad der Kreisfreiheit durch ihre Syntax implizit garantieren. Derartige Sprachen bieten eine Reihe von Vorteilen. Erstens garantieren sie die effiziente Berechnung des CQ-Problems, zweitens kann der Grad der Kreisfreiheit durch die Syntax vorgegeben werden und drittens kann die Datenstruktur zur effizienten Berechnung, die Baumdekomposition, leicht aus den Anfragen abgeleitet werden und muss nicht, wie bei anderen Methoden, mit hohen Kosten berechnet werden.

  • 22. Februar 2005, 16 Uhr ct, R 21, Geb. 64, 2. OG
    Prof. Akira Maruoka, Dept. of Computer and Mathematical Sciences,Graduate School of Information Sciences Tohoku University Sendai, Japan
    Negation-limited Circuit Complexity

    Recently there has been substantial progress in obtaining strong lower bounds on size of monotone circuits computing certain Boolean functions. It is natural to ask if we could put together and make use of the approaches developed so far for monotone case to derive strong lower bounds for more general models. For such a generalized model we consider circuits with a limited number of negation gates and obtain superpolynomial lower bound for circuits computing certain NP complete problem.