|
Tree Fitting:
an Algebraic Approach using Split Distances
Dr. Rick Desper
DKFZ Heidelberg
Phylogeny reconstruction is an important problem for genetic
researchers. One leading method for phylogenetic reconstruction is to
use sequence data to infer an evolutionary time between pairs of
extant species, which will generate a metric on the set of species,
and then to fit a tree metric to this observed metric. Linear
programming approaches have tradionally assigned edge weights, given a
tree topology and a metric, using constraints upon the leaf-to-leaf
distances represented by the solution. With n leaves, this leads to
O(n^2) constraints. We define split distances to be the average
distance among all pairs of leaves across a given edge. We prove that
split distances are an algebraic basis for the vector space generated
by tree metrics. Since there are only O(n) split distances for a
given tree topology, we are led to a linear program which has the same
number of bounds as variables, and thus algebraic methods may be
applied. Furthermore, the solution to this linear program points the
way towards better tree topologies, by assinging a zero weight to at
least one false edge. This feature suggests a heuristic for complete
tree reconstruction, given noisy distance data.
Strategiebildung unter Unsicherheit
Dr. Rainer Feldmann
Fachbereich Mathematik und Informatik,
Universität Paderborn
Es werden die Ergebnisse von drei Algorithmen vorgestellt, die im
Rahmen des SPP entwickelt wurden:
CCSN ist ein Algorithmus zur strategischen Planung, der Unsicherheiten
der heuristischen Bewertungsfunktion kompensiert, indem mehrere
blattdisjunkte Strategien ermittelt werden.
FHR ist ein selektives Verfahren zur Spielbaumsuche,
das erfolgreich auf der Cray T3E parallelisiert wurde.
QSOLVE ist ein sequentielles, auf dem Davis Putnam Algorithmus
beruhendes Verfahren zur Lösung des QSAT Problems.
Complexity of simpler polynomial ideals
Anna Bernasconi
Institut für Informatik, Technische Universität München
The method of Groebner bases is a technique that provides algorithmic
solutions to a variety of problems, for instance, solvability of systems
of algebraic equations, ideal membership and representation problems,
primary decomposition, determination of various properties of ideals
(like dimension, radicality, primality).
While the worst-case lower bound for problems like ideal membership and
Groebner bases computation are terrible (these problems are known to be
exponential space complete) seemingly precluding any application in
practice, it turns out that more ``encouraging'' bounds can be derived for
some special classes of ideals and/or for some problems that really tend to
occur in practical applications, like solvability and radical membership.
Such advances will be necessary in order to apply polynomial ideals in
fields like robotics, motion planning, vision, modeling, constrained
programming, and others.
In this talk, we will analyze subclasses of ideals (ideals over finite
fields, toric ideals, low-dimension ideals) which are of practical relevance
and at the same time permit efficient solutions of the basic problems
mentioned above.
Ein Algorithmus für die Synthese von
Input-Output-Automaten
Prof. Dr. Wolfgang Thomas
Informatik VII, Mathematisch-Naturwissenschaftliche Fakultät,
RWTH Aachen
Wir untersuchen die automatische Konstruktion nichtterminierender
Input-Output-Automaten (wie z.B. Verkehrssteuerungen, Kontrollsysteme).
Auf abstrakter Ebene wird das Problem durch ein unendliches Spiel
(zwischen dem Automaten und seiner Umgebung) modelliert; führt der
Automat eine Gewinnstrategie aus, so stellt er eine korrekte Lösung dar.
Wir stellen einen neuen Algorithmus für die Konstruktion solcher
Automaten vor. Er ist anwendbar für die wichtige Klasse der sog.
"Paritätsspiele", für die bis heute offen ist, ob die
Automatenkonstruktion in Polynomzeit möglich ist. Das vorgeschlagene
Verfahren erzeugt den gesuchten Automaten durch lokale Optimierungen
und ist den bisher bekannten Algorithmen überlegen.
| 
