50 Jahre Uni Lübeck

Institut für Theoretische Informatik

Ankündigungen 2007


  • Wissenschaftliche Mitarbeiterstelle zu besetzen

    Ab sofort

    Am Institut sind derzeit eine Stelle neu zu besetzten im Projekt Data Hiding. Die Möglichkeit zur Promotion ist auf dieser Stelle gegeben. Mehr Informationen finden sich auf unser Seite mit Stellenangeboten.

  • Vortrag von Ilka Schnoor

    „Die Komplexität von Default Logik“

    20. November 2007, 16 Uhr ct, ITCS Seminarraum 2021, Geb. 64, 2. OG

    Frau Ilka Schnoor, Rochester Institute of Technology, hält einen Vortrag im Rahmen unseres Oberseminars Theoretische Informatik.

    Default Logik wurde 1980 von Raymund Reiter eingeführt um die Benutzung von Standard-Annahmen für Schlussfolgerungen zu modellieren. Die Semantik dieser nicht-monotonen Logik basiert auf einer Fixpunktgleichung, die Mengen von Schlussfolgerungen (sog. Extensions) definiert. Aus diesem Kontext ergeben sich drei verschiedene Probleme: Die Frage ob eine solche Extension existiert, die Frage ob ein gegebene Formel in einer Extension enthalten ist und die Frage ob eine gegebene Formel zu allen Extensions gehört.

    In diesem Vortrag gebe ich eine Einführung in Reiters Default Logik und präsentiere dann eine Komplexitäts-Klassifikation der obigen Probleme in Bezug auf syntaktische Einschränkungen.

  • ACM Nordwesteuropäische Meisterschaften im Programmieren

    18. November 2007

    Das Team der Universität zu Lübeck: Henning Block, Markus Hüllebrandt und Sönke Ludwig unter der Betreuung von M. Liskiewicz hat am Sonntag, 18.11.2007 bei dem ACM-Wettbewerb Northwestern Europe Regional Programming Contest (NWERC) in Utrecht, Niederlande, teilgenommen. Das Team hat 3 von 10 Problemen gelöst und schließlich Platz 27 (von 51) erreicht. Resultate

  • 7. Lübecker Hochschultag 2007

    15. November 2007

    Unsere Schwerpunkte auf dem diesjährigen Hochschultag sind die Kryptologie (wie verhindert man das Ausspähen von Daten), das Traveling-Salesperson-Problem (suche die kürzeste Reiseroute durch die Metropolen Europas und die Hauptstädte der USA), das Bin-Packing-Problem (finde die optimale Anordnung) und ein Experiment aus der Quanteninformatik.

  • Neuer Briefkasten für Übungszettel

    12. November 2007

    Im ITCS gibt es nun einen Briefkasten, in den Übungszettel geworfen werden können, falls niemand anwesend sein sollte, der diese entgegennehmen kann. Der Briefkasten befindet sich an der Eingangstür zum TCS Seminarraum.

    Position des Briefkastens Einwurf eines Übungsblatts
  • Neue ITCS Webseite geht Online

    18. Oktober 2007

    Seit dem 18.10.2007 präsentiert sich die Webseite des Instituts für Theoretische Informatik im neuen Design.

  • Lehrveranstaltungen des Wintersemesters 2007/08 online

    18. Oktober 2007

    Die neuen Vorlesungen für das Wintersemester 2007/08 sind online.

  • Podcast für einige Vorlesung verfügbar

    18. Oktober 2007

    Mit Beginn des Wintersemesters 2007/2008 sind die Vorlesungen Logik für Informatiker und Informatik A für MLS auch als Podcasts verfügbar. Damit können Studierende die Vorlesungen zur Vertiefung noch einmal anhören.

  • Dipl.-Inf. Michael Elberfeld tritt Doktorandenstelle an.

    18. Oktober 2007

    Wir begrüßen unseren neuen Doktoranden Michael Elberfeld und freuen uns auf die gemeinsame Zusammenarbeit.

  • Vortrag von Igor Tunjic

    „ ε - λ - Modelle“

    13. November 2007, 16 Uhr ct, ITCS Seminarraum 2021, Geb. 64, 2. OG

    Herr Igor Tunjic, Fakultät IV der TU-Berlin, hält einen Vortrag im Rahmen unseres Oberseminars Theoretische Informatik.

    Der λ-Kalkül erlaubt uns eine Sicht auf Funktionen, die weniger mengentheoretisch geprägt ist als viel mehr prozedural. Das heißt wir begreifen die Funktionen nicht primär als Mengen von geordneten Paaren, sondern eher als Regeln nach denen die Ausdrücke des Kalküls (Terme) verändert werden. Trotz der einfachen syntaktischen Aufbaus des λ-Kalküls ist es möglich alle maschinell berechenbaren Funktionen in diesem auszudrücken. Die Konzepte des λ-Kalküls wie z.B. gebundene Variablen oder der Fixpunktoperator sind eng mit den Konzepten der heutigen Programmiersprachen verbunden, und es verwundert daher nicht, dass der λ-Kalkül als Inspiration für viele Themengebiete der Computerwissenschaft diente. Die Frage nach der Semantik des λ-Kalküls wurde also nicht zuletzt durch die Entwicklung moderner Programmiersprachen inspiriert.

    Die unter der Leitung von Prof. Dr. Bernd Mahr am Institut für Formale Modelle, Logik und Programmierung der TU-Berlin entwickelte Theorie der ε-Strukturen vermittelt eine andere Sicht auf Objekte des mathematischen Denkens. Sie erlaubt explizit Strukturen, die zu sich selbst in einer ε-Beziehung stehen.

    In meiner Diplomarbeit möchte ich diesen Gedanken weiterführen. Ein schönes Ergebnis wäre es, wenn es mir gelänge die Nicht-Einschränkung der ε-Mengen bezüglich der ε-Relation auszunutzen, um das Modell von Scott als Ausgangspunkt der Entwicklung der denotationellen Semantik neu und sinnvoll zu interpretieren.

  • Vortrag von Prof. Akira Maruoka

    „Consistency of Natural Relations on Sets“

    8. November 2007, 17 Uhr ct, ITCS Seminarraum 2021, Geb. 64, 2. OG

    Prof. Maruoka, Faculty of Science and Engineering, Ishinomaki Senshu University, Japan hält einen Vortrag im Rahmen der Kolloquien der Institute für Mathematik und Informatik.

    The natural relations for sets are those definable in terms of the emptiness of the subsets corresponding to Boolean combinations of the sets. For pairs of sets, there are just five natural relations of interest, namely, strict inclusion in each direction, disjointness, intersection with the universe being covered, or not. Let N denote {1,2,...,n } and $n \choose 2$ denote { (i,j) | i,j ε N and i < j }. A function g on $n \choose 2$ specifies one of these relations for each pair of indices. Then g is said to be consistent on MN if and only if there exists a collection of sets corresponding to indices in M such that the relations specified by g hold between each associated pair of the sets. It is proved that if g is consistent on all subsets of N of size three then g is consistent on N. It is also shown that the result concerning binary natural relations can be generalized to r-ary natural relations for arbitrary r ≥ 2.

  • Vortrag von Peter Damaschke

    „Transversalen von Hypergraphen, parametrisiert“

    10. Juli 2007, 16 Uhr ct, ITCS Seminarraum 2021, Geb. 64, 2. OG

    Prof. Peter Damaschke, Computer Science and Engineering, Chalmers University, Göteborg, hält einen Vortrag im Rahmen unseres Oberseminars.

    Transversalen (hitting sets) sind Mengen von Knoten in Hypergraphen, die jede Hyperkante schneiden. Das Problem der Konstruktion aller Transversalen taucht in vielen Bereichen der Informatik auf, darunter Logik, algorithmisches Lernen, Bioinformatik, Datenbanken, Kommunikationsnetze. Ein notorisch offenes Problem ist die Frage, ob die Transversalen in Polynomzeit (in der Größe des Outputs) konstruiert werden können.

    Im Vortrag geht es jedoch um parametrisierte Versionen des Problems, in denen z.B. die Größe der Transversalen, sowie die Anzahl der Hyperkanten oder der Rang, d.h., die Anzahl der Knoten in jeder Hyperkante, beschränkt sind. Die Komplexitätsschranken sind exponentiell, jedoch nur in den jeweiligen Parametern, die in der Praxis oft hinreichend klein sind.

    Der Vortrag ist eine erweiterte Version eines Beitrages zu STACS 2007.

  • Vortrag von Bodo Manthey

    „Minimale Zyklenüberdeckungen“

    19. Juni 2007, 16 Uhr ct, ITCS Seminarraum 2021, Geb. 64, 2. OG

    Dr. Bodo Manthey, Yale University, New Haven, Department of Computer Science, wird diese Woche einen Vortrag im Rahmen unseres Oberseminars halten.

    Eine Zyklenüberdeckung eines Graphen ist eine Menge an Zyklen, so dass jeder Knoten auf genau einem Zyklus liegt. Zyklenüberdeckungen sind ein wichtiger Baustein für Approximationsalgorithmen, z.B. für Routing-Probleme oder das Shortest-Common-Superstring-Problem. Um die Güte der approximativen Lösungen zu verbessern, möchte man bestimmte Zyklenlängen von vornherein ausschließen: In einer L-Zyklenüberdeckung ist die Länge jedes Zyklus in der Menge L.

    Es wird untersucht, wie gut sich L-Zyklenüberdeckungen minimalen Gewichts approximieren lassen. Dazu werden Approximationsalgorithmen und Nichtapproximierbarkeitsresultate präsentiert. Die Nichtapproximierbarkeit beruht hierbei nicht auf komplexitätstheoretischen Annahmen, sondern gilt ohne weitere Bedindungen.

    Schließlich wird gezeigt, dass solche Nichtapproximierbarkeitsresultate für L-Zyklenüberdeckungen maximalen Gewichts nicht existieren.

  • Vortrag von Wolfgang Paul

    „Garantiert Fehlerfreies Design in industriellen Computersystemen“

    7. Juni 2007, 17 Uhr ct, V1 – Vorklinikum, Gebäude 61

    Prof. Wolfgang Paul, Universität des Saarlandes und DFKI, hält einen Vortrag im Rahmen des VIP-Kolloquims.

    Formale Verifikation gestattet heute den Nachweis, dass ganze Computersysteme von industrieller Komplexität - von der Hardware über die Systemsoftware und die Kommunikationssysteme bis zu den Anwendungen - fehlerfrei entworfen sind. Wir erläutern die wesentlichen Theorien und Werkzeuge, mit denen solche Nachweise geführt werden

    1. Eine außerordentliche reiche - der Komplexitätstheorie nicht unähnliche - durchgängige Theorie der Korrektheit realer Computersysteme.
    2. Konsistenzbeweise für Semantiken verschiedener Abstraktionsstufen.
    3. Eine Werkzeugumgebung, welche die verteilte kooperative Entwicklung formaler Korrektheitsbeweise für ganze Computersysteme unterstützt.
    4. CAV-Systeme, in denen sowohl automatische als auch interaktive Beweiswerkzeuge integriert sind.

    Prof. Paul wird den Vortrag beschließen mit einem Überblick über laufende Industriekooperationen.

  • Jan Arpe erhält Stipendium

    1. März 2007

    Jan Arpe hat ein Post-Doc-Stipendium des DAAD erhalten, zu dem wir ihm ganz herzlich gratulieren. Jan wird bald für ein Jahr nach Berkeley ziehen.

  • Promotion von Frank Balbach

    Februar 2007

    Wir gratulieren nun auch Frank Balbach zur seiner ebenso erfolgreichen Promotion zum Dr. rer. nat.

  • Promotion von Jan Arpe

    Januar 2007

    Wir gratulieren Jan Arpe ganz herzlich zur erfolgreichen Promotion zum Dr. rer. nat.