LEA
Fakultät für Informatik der Technischen Universität München
Lehrstuhl für Effiziente Algorithmen
Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Oberseminar Theoretische Informatik SS 01

Brauer, Esparza, Mayr, Steger

Mittwochs um 14:00 Uhr s.t., Raum S2229

[Zusammenfassung des nächsten Vortrags (Donnerstag, 25. Juli 2001)]

*Do,31.5.2001, 17:00
Catherine Greenhill (University of Melbourne)
Hamiltonian decompositions of random bipartite regular graphs
A random d-regular graph on n vertices a.a.s. has an edge-decomposition into Hamilton cycles, when d is an even constant. (Here a.a.s. means `asymptotically almost surely'; i.e. with probability tending to 1 as n tends to infinity). Kim and Wormald proved this using the small subgraph conditioning method. Recently, Kim, Wormald and I proved the corresponding result for random bipartite regular graphs, using the same method. Perhaps surprisingly, the result is harder to prove for bipartite graphs. Two critical quantities needed for the proof are analysed using the differential equations method.
*Mi,13.6.2001
Thomas Bayer
Formgedächtnismaterialien und Computeralgebra
When modeling shape memory alloys one has to construct a free energy $\Phi(F,\theta)$ which has to assume global minima on various strata of the orbit space of the symmetry group $G$ depending on the temperature $\theta$. We provide an algorithm for decomposing a $G-$variety ($G$ finite) $X$ and its orbit space $Z = X/G$ in different strata, each corresponding to a different orbit type. An application to the construction of $\Phi$ for Nickel-Titanium alloys is presented.
*Mi,20.6.2001
Barbara König
Analyse von Graphtransformations-Systemen
Graphtransformations-Systeme sind im allgemeinen Turing-maechtig und daher sind automatischen Verifikationsverfahren nicht anwendbar. Es ist allerdings moeglich, Graphtransformation-Systeme mit Hilfe von sogenannten Petri-Graphen (einer Kombination aus Graphen und Petri-Netzen) zu approximieren, die die erreichbaren Graphen und die moeglichen Zustandsuebergaenge nach oben und unten abschaetzen.
In dem Vortrag wird behandelt, wie man solche Approximationen aus Graphtransformations-Systemen, gegeben durch einen Startgraph und einer Menge von Regeln, ableiten kann und mit welchen Methoden man aus ihnen Informationen extrahieren kann.
Eine solche Methoden ist es, einen Petri-Graph als endlichen Automaten zu betrachten und damit die Menge aller moeglichen Wege durch erreichbare Graphen abzuschaetzen. Ausserdem wird untersucht, welche praedikatenlogischen Formeln auf Graphen die Eigenschaft haben, dass aus ihrer Gueltigkeit fuer die Approximation auch die Gueltigkeit fuer das eigentliche System folgt.
*Mi,27.6.2001
Mark Scharbrodt
Competitive analysis in stochastic scheduling: A new approach to average case analysis
We propose a new approach for analysing the performance of scheduling algorithms: The average case competitive analysis. With the problem of minimizing the total sum of completion times on parallel machines we show how this analysis yiedls new insights into stochastic scheduling policies. We show that, given a simple LIST--rule, the expected competitive ratio is a constant independent on the number of jobs. In contrast, the worst case ratio grows linearly with the number of jobs. We use sophisticated proof techniques that use concentration results and carefully deal with jobs that do not behave as expected. In that way we provide an in--depth investigation of the strategy's performace space.
*Mo,2.7.2001, 17:15
Tim van Beek (sd&m AG)
Quantencomputer
*Mi,4.7.2001
Martin Raab
Gröbnerbasen, torische Ideale und Matroide
In diesem Vortrag wird gezeigt, wie man Methoden aus der Computeralgebra auf die ganzzahlige lineare Programmierung anwenden kann. Für die in diesem Zusammenhang betrachteten Ideale können Gröbnerbasen in polynomiellem Platz berechnet werden. Um Aussagen über die Struktur dieser Gröbnerbasen zu erhalten, betrachten wir das Optimierungsproblem auf Matroiden und Schnitten von Matroiden.
*Mi,11.7.2001
Denis Therien (derzeit Uni Tübingen, ansonst Uni McGill, Montreal)
Definability of regular languages in first-order logic
First-order logic offers a convenient framework to describe regular languages. I will present old and new results about the model: in particular, deep connections with algebra will be emphasized and shown to often yield decision procedures to test if a language is expressible within a given class of formulas. Interesting open questions will also be discussed.
*Do,19.7.2001, 13:00
Michal Mnuk
Grapheneigenschaften, Polynomideale und Färbbarkeit
Mehrfache Beschreibung von mathematischen Objekten mit verschiedenen Mitteln führt oft zur Verbesserung des Verständnisses für innere Zusammenhänge. Im Vortrag wird eine Methode zur Repräsentierung von Grapheneigenschaften durch Polynomideale vorgestellt. Es werden Vorteile, aber auch inhärente Einschränkungen diskutiert. Anschließend wird gezeigt, wie diese Methode beim Studium der Färbbarkeit von Graphen verwendet werden kann.
*Mi,25.7.2001
Peter Rossmanith
Exact Solutions for Closest String and Related Problems
Closest String is one of the core problems in the field of consensus word analysis with particular importance for computational biology. Given k strings of same length and a positive integer d, find a "closest string" such that none of the given strings has Hamming distance greater than d from s. Closest String is NP-complete. In biological practice, however, d usually is very small. We show how to solve Closest String in linear time for constant d (the exponential growth in d is bounded by (2d)^d). We extend this result to the closely related problems d-Mismatch and Distinguishing String Selection. Moreover, we give a linear time algorithm for Closest String when k = 3 and d is arbitrary. Finally, the practical usefulness of our findings is substantiated by some experimental results.

Martin Raab Last modified: Wed Jul 25 10:34:18 CEST 2001