|
 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.
- 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.
- 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.
|
|
