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.
„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.
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.
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
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.
 |
 |
 |
 |
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 |
18. Oktober 2007
Seit dem 18.10.2007 präsentiert sich die Webseite des Instituts für Theoretische Informatik im neuen Design.
18. Oktober 2007
Die neuen Vorlesungen für das Wintersemester 2007/08 sind online.
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.
18. Oktober 2007
Wir begrüßen unseren neuen Doktoranden Michael Elberfeld und freuen uns auf die gemeinsame Zusammenarbeit.
„ ε - λ - 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.
„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 M ⊆ N 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.
„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.
„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.
„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
Prof. Paul wird den Vortrag beschließen mit einem Überblick über laufende Industriekooperationen.
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.
Februar 2007
Wir gratulieren nun auch Frank Balbach zur seiner ebenso erfolgreichen Promotion zum Dr. rer. nat.
Januar 2007
Wir gratulieren Jan Arpe ganz herzlich zur erfolgreichen Promotion zum Dr. rer. nat.
