Zusammenfassung: Im klassischen p-Medianproblem geht es darum, p neu zu errichtende Einrichtungen
in einem gegebenen Netzwerk so zu platzieren, dass die Summe der gewichteten
Abstände der gewählten Standorte zu den Knoten des Netzwerks minimiert wird.
Bei reversen Medianproblemen allerdings sind die p Standorte bereits gegeben
und man kann mit Hilfe eines gegebenen Budgets die Kantenlängen im Netzwerk
verändern. Ziel ist es nun, die Summe der gewichteten Abstände der bereits
gegebenen Standorte zu den Knoten bezüglich der neuen Kantenlängen zu minimieren.
Man kann zeigen, dass das reverse 1-Medianproblem auf bipartiten Graphen
mit linearen Kostenfunktionen stark NP-schwer ist und es
(sofern P ungleich NP) keinen polynomialen
Approximationsalgorithmus mit konstanter Gütegarantie gibt. In diesem Vortrag
wird daher auf spezielle Graphen eingegangen (z.B. Bäume, Kreise und Cacti),
die es erlauben, eine Optimallösung in polynomialer Zeit zu berechnen.
29. November 2005 14.15
Petra Fakler (ZAIK)
Klassifizieren mit Entscheidungsbäumen
Zusammenfassung: Entscheidungsbäume werden verwendet, um besser und mit weniger
Fehlern eine Entscheidung treffen zu können. Sie veranschaulichen
aufeinanderfolgende hierarchische Entscheidungen. Sie können z.B. in der
Medizin zur Diagnose von Krankheiten eingesetzt werden.
22. November 2005 14.15
Nicole Radde und Jutta Gebert (ZAIK)
Unser Aufenthalt in Los Alamos: Arbeitsergebnisse und sonstige Berichte
15. November 2005 14.15
Ilse Fischer (Uni Wien)
Eine polynomiale Methode für die Abzählung von Plane Partitions
und Alternierenden Vorzeichenmatrizen
Abstrakt: 5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1 sind alle Möglichkeiten 5 als
Summe
von natürlichen Zahlen zu schreiben. Man nennt diese Menge die
(Zahlen-)Partitionen
von 5. Plane Partitions und Alternierende Vorzeichenmatrizen sind in
einem gewissen
Sinne zweidimensionale Verallgemeinerungen von Partitionen. Die
Bedeutung dieser Objekte
wird einerseits durch ihr Auftreten in anderen Gebieten wie der
Darstellungstheorie
von klassischen Gruppen oder der statistischen Mechanik manifestiert,
andererseits
führt die Abzählung dieser Objekte unter den verschiedensten
Nebenbedingungen immer
wieder zu eleganten Formeln, die in der Regel nur schwer zu beweisen
sind. Die Standardmethode,
die sich in den letzten Jahren zur Abzählung von Plane Partitions und
Alternierenden
Vorzeichenmatrizen herauskristallisiert hat, besteht darin, das
Abzählproblem
auf die Berechnung einer (im Allgemeinen nicht-trivialen) Determinante
zurückzuführen.
In meiner Habilitationsschrift stelle ich eine alternative,
``polynomiale'' Methode vor, die
unter anderem zu neuen Beweisen und Verallgemeinerungen der
Bender-Knuth
(ex-)Vermutung und
des Alternierenden-Vorzeichenmatrix-Satzes geführt hat.
8. November 2005 14.15
Niels Lange (ZAIK)
Untersuchung der Geometrie von Biomolekülen mittels Alpha Shapes
25. Oktober 2005 14.15
Prof. Michael Malmros Sørensen (Aarhus School of Business)
Polyhedral Computations for the Simple Graph Partitioning Problem
18. Oktober 2005 14.15
Robert Nickel (FernUni Hagen)
Stabile Hochzeiten, Zuweisungsspiele und beides gleichzeitig - Wenn der
öffentliche Dienst mit der freien Wirtschaft konkurriert.
11. Oktober 2005 14.15
Lars Kaderali (ZAIK)
N.N.
04. Oktober 2005 14.15
Martin Lätsch (ZAIK)
2-gerichtete Graphen
Zusammenfassung: Im Vortrag wird die Klasse der 2-gerichteten Graphen über eine
Verallgemeinerung des unabhängigen Mengen Problems eingeführt. Weiterhin werden
einige Eigenschaften 2-gerichteter Graphen vorgestellt.
27. September 2005 14.15
Stefan Neuhaus (ZAIK)
Kalibrierung von Bewertungsfunktionen
Kurzzusammenfassung: Die Spielstärke von Computerprogrammen zum Spielen von vielen (nicht-kooperativen) Spielen wie Schach, Dame, 4-Gewinnt etc. hängt entscheidend davon ab, wie gut die Programme die Vorteilhaftigkeit bestimmter Spielsituationen einschätzen können. Gängigerweise werden gut passende Faktoren einer Bewertungsfunktion durch jahrelange Ausprobiererei bestimmt. Doch es kann auch anders gehen. Ein alternativer Ansatz zum (eher semi-)automatischen Lernen einer Bewertungsfunktion wird vorgestellt und es wird gezeigt, wie gut sich dieser am Beispiel eines Schach-Programms mit (unsprünglich) "Großmeister-Stärke" schlägt.
20. September 2005 14.15
Niko Beerenwinkel (UC Berkeley)
Algebraic Statistics for Biological Sequence Analysis
Abstract: Biological sequence analysis is based on discrete statistical models
coupled with efficient algorithms for parameter estimation and statistical
inference. Over the past 10 years methods from abstract algebra and
algebraic geometry have been applied increasingly to the analysis of
statistical models giving rise to the new field of algebraic statistics.
We apply algebraic statistical methods to models of sequence evolution.
For phylogenetic tree models, this approach gives rise to the
phylogenetic invariants, a set of polynomials that characterize the
family of distributions encoded by the tree hidden Markov model. Pairwise
sequence alignment is based on the pair hidden Markov model. The
framework of algebraic statistics offers a general and efficient solution
to the parametric sequence alignment problem, i.e. to finding the set of
all optimal alignments for all parameter choices. This connection is via
passing from standard to tropical algebra and to the polytope algebra.
13. September 2005 14.15
Kamel Ben Khalifa (ZAIK)
A complexity index for satisfiability problems
6. September 2005 14.15
Kamel Ben Khalifa (ZAIK)
The complexity of satisfiability problems
30. August 2005 14.15
Kamel Ben Khalifa (ZAIK) (fällt aus)
The complexity of satisfiability problems
23. August 2005 14.15
Susanne Heuser (ZAIK)
Eisbergverbände
Zusammenfassung: Die formale Begriffsanalyse kann dazu eingesetzt werden, auf Grundlage
einer Datentabelle
eine Hierarchie von Begriffen, den Begriffsverband, aufzubauen. Die
Visualisierung des Begriffsverbandes
durch Liniendiagramme ist hilfreich, um im Datensatz vorhandene
Strukturen und Zusammenhänge zu erkennen.
Arbeitet man mit großen Datensätzen, so erhält man Begriffsverbände, die
sich aufgrund ihrer Größe
nicht mehr gut grafisch darstellen lassen. Eine Möglichkeit, wesentliche
Strukturen des Datensatzes dennoch
sichtbar zu machen, bieten die sogenannten Eisbergverbände. Dieses
Konzept möchte ich im Vortrag vorstellen.
16. August 2005 14.15
Nicole Radde (ZAIK)
Bayesscher Ansatz zum Lernen genregulatorischer Netzwerke
Zusammenfassung: Heute geht es im Dienstagsseminar über das Lernen genregulatorischer
Netzwerke aus Messdaten mit einem Bayes´schen Ansatz.
Um die Vorgänge in einer Zelle auf molekularer Ebene zu verstehen, ist
es wichtig, die zugrunde liegenden Wechselwirkungen zwischen
Zellkomponenten wie beipielsweise den Genen und ihren Produkten zu
untersuchen. Ein Hauptziel in der Bioinformatik ist es deswegen, aus
Genexpressionsdaten, die aus Microarray-Experimenten gewonnen werden,
das zugehörige regulatorische Netz zu konstruieren. Normalerweise hat
man dabei das Problem, das Netzwerk aus nur sehr wenigen Daten in einem
hochdimensionalen Parameterraum lernen zu müssen. Hier bietet sich ein
Bayes´scher Ansatz an, der a priori-Verteilungen über die zu lernenden
Parameter annimmt. Ein solcher Ansatz soll heute vorgestellt werden.
09. August 2005 14.15
Susanne Heuser (ZAIK)(fällt aus)
N.N.
02. August 2005 14.15
Jutta Gebert (ZAIK)
Chemische Organisationstheorie
Zusammenfassung: In diesem Vortrag wird eine Theorie von P. Dittrich und P. Speroni erläutert, die Reaktionssysteme
algebraisch beschreiben. Im ersten Schritt wird eine statische Analyse des Systems vollzogen, wobei verschiedene Merkmale von
Molekülmengen untersucht werden. In besonders ausgezeichneten Reaktionssystemen bilden Molekülmengen mit gewissen
Merkmalen einen Verband. Hier soll auch der Bogen zur Begriffsanalyse gespannt werden. Im zweiten Schritt wird die Dynamik des Systems berücksichtigt,
indem die Bewegungen im Zustandsraum den
Bewegungen zwischen
den Molekülmengen zugeordnet werden.
26. Juli 2005 14.15
Bernhard Fuchs (ZAIK)
Steiner-Touren
Zusammenfassung: Steiner-Touren seien Touren, die hoechstens doppelt so lang sind wie ein opt. Steinerbaum. Sie
kommen als Zwischenschritt im klassischen Beweis dafuer vor, dass ein MST
hoechstens doppelt so gross ist wie ein opt. Steinerbaum, werden aber
nicht weiter beachtet.
Ich stelle mir/uns die Frage, ob man eine solche Tour wohl leicht finden
koennte, und motiviere, warum einen das interessieren koennte.
19. Juli 2005 14.15
Dominique Andres (ZAIK)
Spielchromatische Zahlen verschiedener Graphenklassen --- Ein
Überblick
Zusammenfassung:
Ein von Bodlaender eingeführtes 2-Personen (maker-breaker)
Graphenfärbungsspiel definiert für jede nichtleere Klasse von
Graphen einen Parameter, die sogenannte spielchromatische Zahl.
Ein Grundproblem der kompetitiven chromatischen Graphentheorie besteht
darin, möglichst gute obere Schranken
für die spielchromatische Zahl bestimmter vorgegebener Graphenklassen
zu finden.
Im Vortrag wird ein Überblick über die diesbezüglichen
Resultate der Literatur der letzten 15 Jahre geboten.
12. Juli 2005 14.15
Ralf Müller (ZAIK)
Synchronisationsmaße für neurophysiologische Daten
Zusammenfassung: Bei der Verarbeitung von Information im Gehirn richtet sich seit einigen
Jahren das Augenmerk zunehmend auf unterschiedliche
Synchronisations-Effekte. Im Vortrag werde ich zuerst in die
Problematik von Frequenz- und Phasen-Analysen von EEG Daten einführen.
Danach werde ich einen Überblick über derzeit verwendete Maße zur
Berechnung der Stärke von Synchronisationen geben. Zuletzt werde ich
noch ein paar abschließende Bemerkungen zum Vergleich der Maße geben.
05. Juli 2005 14.15
Alexander Schönhuth (ZAIK)
Kartenmischen
Zusammenfassung: Es werden verschiedene Kartenmischtechniken vorgestellt und das Mischen als
Markoff-Ketten modelliert. Darauf aufbauend kann man, indem man die Konvergenzraten (auf englisch
sinnigerweise mixing rates genannt) bezueglich der Grenzverteilung dieser
Markoff-Ketten untersucht, Prognosen zum Grad der Durchmischung der
Kartenspiele abgeben. Dies wird mit sich bringen, dass eine beliebte Mischtechnik ueberhaupt nicht
dazu geeignet ist, Kartenspiele zu mischen, eine andere jedoch sehr wohl.
28. Juni 2005 14.15
Martin Lätsch (ZAIK)
Eine Abschätzung des minimalen orientierten Durchmessers durch
dominierende Mengen
Zusammenfassung: Der minimale orientierte Durchmesser d eines Graphen G
ist der kleinste Durchmesser einer Orientierung des Graphen. Im Vortrag
wird gezeigt, dass für bestimmte Graphenklassen: d <= 5D-1 gilt. Mit D =
Dominanzzahl von G.
21. Juni 2005 14.15
Christian Hagemeier (ZAIK)
Dynamische Programmierung in k-Bäumen
Zusammenfassung: Befaßt man sich mit graphentheoretischen Problemen, stößt man oft auf
schwierig zu lösende Probleme ("umgangssprachlich" gerne auch als
NP-vollständig bezeichnet ;-) ). Eine natürliche Fragestellung ergibt
sich dann unmittelbar: Wenn das Problem auf allgemeinen Graphen schwer
lösbar ist, wie verhält es sich dann auf speziellen Graphklassen?
Bäume bieten sich dann auf Grund ihrer strukturellen Eigenschaften oft
als eine natürliche Ausgangsbasis für solche Untersuchungen an. Im
Vortrag möchte ich eingangs auf das dazu häufig eingesetzte
Lösungsschema der dynamischen Programmierung eingehen. Daran
anschließend möchte ich die graphentheoretische Struktur der Bäume auf
sogenannte k-Bäume erweitern ("traditionelle" Bäume sind in dieser
Terminologie 1-Bäume, serienparallele und außenplanare Graphen 2-Bäume).
Dazu führe ich den Begriff der Baumzerlegung ein. An einem Beispiel soll
dann die Idee der dynamischen Programmierung in k-Bäumen verdeutlicht
werden. Abschließen möchte ich mit einigen Bemerkungen zu weiteren
Ergebnissen in diesem Forschungsbereich.
14. Juni 2005 14.15
Jürgen Gräfe (ZAIK)
Illumass
07. Juni 2005 14.15
Anna Schulze
Approximationsverfahren für oktilineare Steinerbäume
31. Mai 2005 14.15
Petra Fakler (ZAIK)
Basel II und die Auswirkungen auf das Kreditgeschäft
24. Mai 2005 14.15
Ralf Müller (ZAIK) (fällt wegen Krankheit aus)
N.N.
17. Mai 2005 14.15
Stefan Neuhaus (ZAIK)
Das Springerproblem auf beliebigen n x m - Spielbrettern
10. Mai 2005 14.15
Silvia Daun (Mathematisches Institut Köln)
Modeling cerebral perfusion in situation of severe head injury
Zusammenfassung: A mathematical model for the description of
cerebral hemodynamics is developed. This model is able to
simulate the regulation mechanisms working on the small cerebral
arteries and arterioles, and thus to adapt dynamically the blood
flow in brain. Special interest is laid on the release of
catecholamines and their effect on heart frequency, cardiac
output and blood pressure. Therefore this model is able to
describe situations of severe head injuries in a very realistic
way.
26. April 2005 14.15
Christian Gießelbach (ZAIK)
Ein Färbungsproblem in partitionierten Graphen
Zusammenfassung: Resultate zur Komplexität des Problems und einfache Heuristiken
19. April 2005 14.15
Nicole Radde (ZAIK)
Modellierung biochemischer Netze - ein Anwendungsbeispiel
Zusammenfassung: In dem Vortrag wird ein Modell für die Regulierung des bgl-Operons in
Escherichia coli durch das Protein H-NS vorgestellt. Dabei geht es
speziell um den Einfluss der zweiten Bindestelle für H-NS innerhalb des
Operons. Wir verwenden stückweise lineare Differentialgleichungen, deren
Parameter wir aus Mutantenexperimenten schätzen.
12. April 2005 14.15
Martin Olschewski (ZAIK)
Schwachstellen in der WEP-Verschlüsselung
Zusammenfassung: Der Vortrag geht über zwei Schwachstellen
in der WEP-Verschlüsselung, die üblicherweise zur Absicherung von
WLANs verwendet wird.
5. April 2005 14.15
Katja Korherr
Adjazenzmatrizen von maximalem Rang
29. März 2005 14.15
Timm Pliefke
Ein polynomialer Netzwerk Simplex Algorithmus zur Berechnung von Flüssen mit minimalen Kosten
Zusammenfassung: Der Netzwerk Simplex Algorithmus ist eine graphentheoretische Spezialisierung des von Dantzig entwickelten Simplex Algorithmus für lineare Programme. Er transformiert das Kernkonzept des herkömmlichen Simplex Algorithmus auf die strukturellen Besonderheiten von Netzwerken und bildet auf diese Weise ein effektives Lösungsverfahren für das bekannte Minimum Cost Flow Problem (MCFP). Obwohl sich der Netzwerk Simplex Algorithmus in seinen zahlreichen Varianten in der Praxis bewährt hat, blieb es über lange Zeit ein offenes Problem, die polynomiale Beschränktheit der Komplexität des Verfahrens für das MCFP nachzuweisen. Hier gelang es Orlin 1995 mit dem so genannten Premultiplier Algorithmus eine Spezialform des Netzwerk Simplex Algorithmus zu entwickeln, der für ein MCFP mit polynomialer Komplexität eine Optimallösung generiert.
Das Ziel des Vortrages besteht darin, ein grundlegendes Verständnis für die Problematik des Netzwerk Simplex Algorithmus zu schaffen, die Einflussgrößen der Komplexität des Verfahrens darzulegen und aufbauend auf diesen Erkenntnissen die Polynomialität des Premultiplier Algorithmus zu veranschaulichen.
22. März 2005 14.15
Jutta Gebert (ZAIK)
Modellierung und Visualisierung biochemischer Netze
Zusammenfassung: In diesem Dienstagsseminar wird ein Modell der Stickstoffaufnahme im Corynebacterium glutamicum präsentiert. In dem Modell werden stückweise lineare Differentialgleichungen verwendet, deren Parameter anhand von Daten aus Western Blots geschätzt werden. Anschließend wird eine Visualisierungsmethode für solche biochemischen Netze vorgestellt.
Vorhersage des Überlebens nach Chemotherapie beim Non-Hodgkin-Lymphom
1. März 2005 14.15
Seminar fällt aus
22. Februar 2005 14.15
Sven Oliver Krumke (TU Kaiserslautern)
Aufzugsteuerung ist (meistens) einfach
Zusammenfassung: Das Problem, einen Aufzug "optimal" zu steuern, läßt sich als
Transportproblem auf einem Pfad- oder Tausenfüßlergraphen formulieren.
Im Offline-Fall läßt sich das Problem, einen kürzesten Transportplan zu
finden, auf Pfadgraphen optimal in polynomial lösen, auf Tausendfüßlern
(im Wesentlichen die einfachste Teilklasse von Bäumen) wird das Problem
aber NP-schwer. Wir zeigen, daß ein einfacher Algorithmus, der im
Worst-Case 3/2-approximativ ist, bei zufälliger Eingabe mit hoher
Wahrscheinlichkeit eine optimale Lösung liefert und dies auch selbst
zertifizieren kann. Darüberhinaus stellen wir Ergebnisse über die
probabilistische Analyse des entsprechenden Online-Problems vor, bei dem
Aufträge erst nach und nach bekanntwerden.
