Informatik-Logo
Fakultät für Informatik - Technische Universität München

Lehrstuhl für Effiziente Algorithmen

TUM-Logo

Oberseminar Theoretische Informatik Sommersemester 2007

Esparza, Mayr, Scheideler, Veith

Mittwochs um 14:00 Uhr s.t., Raum MI 03.11.018


*Mi, 02.05.2007
Dr. Sven Kosub
Fixpunktanalyse boolescher dynamischer Systeme
Es werden Dichotomieaussagen für die Komplexität des Findens und des Zählens von Fixpunkten in booleschen dynamischen Systemen, d.h., in diskreten dynamischen Systemen über der Zustandsmenge {0,1}, präsentiert. Für eine Klasse F boolescher Funktionen und einer Klasse G von Graphen ist ein (F,G)-System ein boolesches dynamisches System, dessen lokale Transitionen zu F und dessen Netzwerk zu G gehören. Wir zeigen, dass folgende Klassifikationen gelten, falls die lokalen Transitionen durch Wertetabellen gegeben sind: Es seien F eine unter Superposition abgeschlossene Klasse von booleschen Funktionen und G eine unter Minorenbildung abgeschlossene Graphenklasse.

  1. Wenn F alle selbstdualen Funktionen und G alle planaren Graphen umfasst, dann ist das Finden von Fixpunkten in (F,G)-Systemen NP-hart; in allen anderen Fällen gibt es Polynomialzeit-Algorithmen.

  2. Wenn F alle Minimum-Funktionen, alle Maximum-Funktionen oder alle selbstdualen, monotonen Funktionen sowie G alle planaren Graphen umfasst, dann ist die Bestimmung der Fixpunktanzahl in (F,G)-Systemen #P-vollständig; in allen anderen Fällen gibt es Polynomialzeit-Algorithmen.

Für Repräsentierungen der Transitionsfunktionen durch Formeln und Schaltkreise werden ähnliche Dichotomien angegeben.

Der Vortrag basiert auf zwei Arbeiten, bei denen eine unter Mitautorenschaft von Christopher M. Homan (Rochester) entstanden ist.

*Mi, 23.05.2007
Dr. Sven Kosub
Kombinatorische Beziehungsanalyse im Internet
Die Gewährleistung von Routingstabilität im Internet ist eine Herausforderung für jede Netzwerkadministration. Ist Routing innerhalb eines Autonomous Systems noch unter weitgehend vollständiger Kontrolle der Administratoren, so basiert interdomain routing vor allem auf zwischen unabhängigen Internetteilnehmern vereinbarten vertraglichen Beziehungen, die ihren Niederschlag in unterschiedlichen Import-/Exportregeln für BGP-Daten und damit in eingeschränkter Erreichbarkeit finden. Solche Regeln aus beobachtbaren Daten abzuleiten ist von großer Bedeutung für effizientes trouble shooting.

In diesem Vortrag werden wir dahin gehend das Problem betrachten, aus Informationen, die in lokalen Routing-Tabellen enthalten sind, auf die vertraglichen Beziehungen (customer-to-provider, peering-to-peering und sibling-to-sibling) zwischen den autonomen Systemen zu schließen. Basierend auf geeigneten Begriffen von Kreisfreiheit im Graph der Geschäftsbeziehungen diskutieren wir algorithmische Lösungen für die darauf aufbauenden kombinatorischen Optimierungsprobleme. Experimente mit realen Daten zeigen, dass die gewonnenen Algorithmen im Vergleich zu bereits existierenden Algorithmen die geringste Anzahl von Fehlklassifikationen produzieren.
*Mi, 13.06.2007
Matthias Baumgart
Eigenschaften Bispannender Graphen
Bispannende Graphen sind Graphen, deren Kantenmenge aus zwei disjunkten Spannbäumen besteht. Wird jeder Kante ein Gewicht zugeordnet, können in Abhängigkeit dieser Gewichtsfunktion unterschiedliche Gewichtsklassen von Spannbäumen entstehen. Im Vortrag werden spezielle Gewichtsfunktionen betrachtet und ihre Auswirkung auf die Gewichtsklassen der Spannbäume bispannender Graphen analysiert. Interessant ist diese Analyse insbesondere im Hinblick auf Zusammenhänge im Spannbaumgraphen eines gewichteten Graphen. Hier besteht zum Beispiel die Frage, wie viele Kantentauschoperationen nötig sind, um einen i-kleinsten Spannbaum in einen j-kleinsten Spannbaum zu überführen. Bekannt ist, dass man von einem 1-kleinsten (minimalen) Spannbaum zu einem k-kleinsten Spannbaum höchstens k-1 Kantentauschoperationen benötigt.
*Mi, 20.06.2007
Oleg Pikhurko
Getting exact Turan results via stability
For a k-graph F, the Turan function ex(n,F) is the maximum size of an F-free k-graph on n vertices. In general, it is notoriously hard to determine. Even if we know ex(n,F) asymptotically, the exact computation might turn out to be a difficult task. I will discuss the stability approach for proving exact Turan results that was suggested by Simonovits in the 1960s and used recently by Furedi, Keevash, Mubayi, Sudakov and others.

Some of the presented results are joint work with Zoltan Furedi, Dhruv Mubayi, and Miklos Simonovits.
*Mi, 27.06.2007
Dmitry Chibisov
Optimization of Robot Motion for Multiple Tasks with Constrained Velocity and Orientation of the End-Effector
In this talk we discuss the kinematic properties of robots with 6 rotation joints and describe an approach for optimization of robot motion due to given geometric and differential constraints (i.e. constraints on velocity and orientation of the robot end-effector during the execution of some tasks, and limits on velocities and accelerations during the overall workcycle). We consider the non-academic, highly nonlinear model of a commercially available robot and discuss several objectives for optimal motion. We describe an approach to calculation of minimum-time robot trajectories for multiple tasks with constrained velocity and orientation of the end-effector. In order to reduce the time required for execution of prescribed tasks with such type of constraints we parameterize admissible orientation and velocity spaces using computation of Moore-Penrose pseudoinverses of matrices with polynomial entries. We use computer algebra system Maple to perform these calculations and to derive formulae and procedures for numerical optimization by the method of steepest descent. Finally, the computational examples will be presented.
*Mi, 11.07.2007
Dr. Martin Sachenbacher
Constraint-based Models and Algorithms for Self-Diagnosis and -Repair
Due to the increasing complexity of technical systems (e.g., embedded automotive systems, reconfigurable factories, or intelligent buildings), there is growing interest in algorithmic methods for automatically monitoring, diagnosing, reconfiguring, and repairing such systems based on a model of their behavior. The main challenge is to develop algorithms that can efficiently reason through a large space of component interactions to quickly identify most likely current system states (monitoring and diagnosis), and generate least-cost desired system states (planning and reconfiguration). Both of these tasks can be mathematically framed as combinatorial optimization problems over a set of finite constraints. In this talk, I will present algorithmic approaches for solving such problems by combining ideas from artifical intelligence and operations research, and also highlight some of the currently open research issues.

Stefan Eckhardt