Alle Interessenten sind herzlich eingeladen.

Die Hochschullehrer des Instituts

Prof. Dr. Szafraniec (Universität Krakov)

I intend to use Naimark extensions to show how much of it may fit in. It is based on a surprisingly simple and rather known example. The abstract machinery is going to be explained in details.

Prof. Dr. Caroline Lasser  (FU Berlin)

Die Dynamik eines Moleküls wird durch die den Mikrokosmos bestimmende Gleichung beschrieben, die zeitabhängige Schrödinger-Gleichung. Ihre Lösung ist die Wellenfunktion, eine stark oszillierende komplexwertige Funktion.Die Zahl der örtlichen Freiheitsgrade ist hoch, so dass übliche Approximationsmethoden für partielle Differentialgleichungen hier nur bedingt greifen. Der Vortrag wird Ergebnisse aus der Visualisierung und numerischen Simulation solcher Systeme vorstellen und diskutieren.

Prof. Dr. Andreas Brandstädt (Universität Rostock)
(in Zusammenarbeit mit Chinh T. Hoáng, Van Bang Le, Vadim V. Lozin, Raffaele Mosca und anderen)

In einem endlichen ungerichteten Graphen heißt   unabhängige Knotenmenge, falls keine Kante aus zwei Knoten in verbindet. heißt vertex cover in , falls für alle Kanten aus mindestens einer der beiden Knoten in ist. Offenbar ist genau dann unabhängige Knotenmenge, wenn ihr Komplement vertex cover ist. Das Problem MAXIMUM INDEPENDENT SET fragt zu gegebenem Graphen nach einer größten unabhängigen Knotenmenge in , und das Problem VERTEX COVER fragt nach einem kleinsten vertex cover in . Damit hängen beide Probleme eng zusammen und sind bekanntlich NP-vollständig. Darüber hinaus ist MAXIMUM INDEPENDENT SET schwer approximierbar und schwierig bzgl. fixed parameter tractability. Wir diskutieren einige Methoden wie z. B. modulare Dekomposition bzw. Dekomposition durch Cliquenseparatoren zur Bestimmung einer größten unabhängigen Knotenmenge und geben effiziente Lösungen des Problems auf einer Reihe von speziellen Graphenklassen an, wie z. B. gewissen Verallgemeinerungen von chordalen Graphen und claw-freien Graphen.

Prof. Dr. Klaus Meer (TU Cottbus)
(in Zusammenarbeit mit I. Briquel und P. Koiran von der ENS in Lyon)

Wir untersuchen die Ausdrucksstärke spezieller Polynomfamilien, die über einem Körper K definiert sind. Die betrachteten Polynome entstehen dabei in natürlicher Weise aus Booleschen Formeln in konjunktiver Normalform. Jeder solchenFormel ist kanonisch ein Graph zugeordnet. Wir interessieren uns nun dafür, inwieweit die  Beschränkung von Parametern wie Baum- oder Cliquenweite für diesenGraphen Einfluss auf die Ausdrucksstärke der entstehenden Polynomfamilien hat. Solche Fragen stehen in engem Zusammenhang mit Valiants Theorie der Komplexität algebraischer Polynomfamilien.

Prof. Dr. Haiko Müller (University of Leeds)

Sowohl die Cliquenweite als auch die NLC-Weite messen die Komplexität von Graphen. Beide Parameter werden über einfache Operationen für markierte Graphen definiert (NLC heißt node-label controlled) und ähneln einander. Die jeweilige Weite ist die kleinste Anzahl verschiedener Marken, die man benötigt, um den Graphen zu erzeugen. Für alle Graphen gilt .
Wie auch die Baumweite sind Cliquenweite und NLC-Weite durch algorithmische Anwendungen motiviert. Alle Graphenprobleme, die in MSOL (monadic second order logic) definierbar sind, lassen sich in Linearzeit lösen, wenn mann die Eingaben auf Graphen beschränkter Baumweite beschränkt. Nun haben aber vollständige Graphen, trotz ihrer einfachen Struktur, unbeschränkte Baumweite, . Darum wurde die Cliquenweite eingeführt , denn sie verallgemeinert die Baumweite: , und hat ähnliche algorithmische Implikationen.
Die Baumweite wird über Baumzerlegungen definiert, und auch der Cliquen- und NLC-Weite liegen Zerlegungsbäume zugrunde. Die Weite einer Baumzerlegung ist einfach zu bestimmen, aber auch für einen festen Zerlegungsbaum ist die Cliquen- oder NL-Weite ist nicht so offensichtlich. Darum betrachtet man diese Parameter relativ zu einem Zerlegungsbaum. Wir zeigen nun, dass sich die relative NLC-Weite in Polynomialzeit berechnen lässt, das Entscheidungsproblem zur relativen Cliquenweite aber NP-vollständig ist.

Prof. Dr. Dieter Kratsch (Université de Metz)

There is a large collection of problems in theory and practice that do not seem to be solvable by efficient algorithms (unless P=NP). Among them are the NP-complete problems, the #P-complete counting problems and the PSPACE-complete problems. Various methods to achieve algorithms solving NP-hard problems have been developed among them approximation algorithms, heuristics and fixed-parameter algorithms. Another approach is to attack such problems in the classical way asking for exact solutions and worst-case running time analysis. Clearly polynomial-time algorithms solving an NP-hard problem are not possible unless P=NP. Nowadays research in this research domain concentrates on developing algorithms of running time O(c^n) with the base c as small as possible. The talk presents fundamental methods for the design and analysis of fast exponential-time algorithms: branching, dynamic programming and inclusion-exclusion algorithms.Our examples are  graph problems among them the coloring problem. The fastest currently known algorithm to compute the chromatic number of a given graph will also be presented.

Prof. Dr. Michael Karow (TU Berlin)

Als Pseudospektrum  einer Matrix A bezeichnet man die Menge der Eigenwerte  aller Matrizen, die man erhält, indem man zu A Störungen addiert, welche unterhalb einer gegebenen Normschranke liegen. Pseudospektren haben sich in den letzten Jahren als ein wichtiges Werkzeug sowohl für die Numerik als auch für die Systemtheorie erwiesen. Nach einer Einführung in die allgemeine Theorie diskutieren wir Pseudospektren für reelle und Hamiltonische Matrixstörungen sowie für gekoppelte lineare Systeme. Ein weiteres Thema wird der Zusammenhang zwischen Pseudospektren und strukturierten Eigenwertkonditionszahlen sein.

 Dr. Timo Reis (TU Berlin)

In der numerischen Simulation elektrischer Netzwerke hat man differentiell-algebraische Gleichungssysteme zu lösen, deren Größe heutzutage sehr häufig die Grenzen des Machbaren übersteigt. Eine Möglichkeit, diese Problematik zu umgehen, bietet die Modellreduktion, also die Approximation des Netzwerkmodells durch ein wesentlich kleineres. Hierbei ist es auch wichtig, dass das reduzierte System wichtige Eigenschaften des originalen Systems (wie etwa Stabilität, Passivität,...) erhält. Im Vortrag wird ein Modellreduktionsverfahren vorgestellt, dass all diese geforderten Eigenschaften besitzt und insbesondere die Struktur der Schaltungsgleichungen ausnutzt, um den Aufwand zur Berechnung des reduzierten Modells weiter zu erniedrigen.