 Mi, 12.11.2003
|
Stefan Eckhardt
Zufällige planare Graphen
|
|
Über zufällige Graphen im allgemeinen gibt es eine Menge Forschungsergebnisse.
Wenn man den zufälligen Graphen darauf bedingt, dass er planar ist, dann
stellt es sich heraus, dass man nur ein sehr wenig Über die Eigenschaften
dieser Subklasse weiß.
In diesem Vortrag soll kurz auf das Thema "zufällige planare Graphen" auf n
Knoten eingegangen werden und Resutate zum Thema "Erzeugen zufälliger planare
Graphen" sowie "Subgraphen zufälliger planarer Graphen" skizziert werden.
Dann wird eine Subklasse der planaren Graphen, die auf n Knoten mit genau m
Kanten, untersucht und auf die selben Problemstellungen, wie bei den planaren
Graphen i.A. eingegangen, u.a. die "Erzeugung" zufälliger planarer Graphen
mit Hilfe einer Markov Kette.
|
|
|
Mi, 19.11.2003
|
Dmytro Chibisov
Computer Algebra im wissenschaftlichen
Rechnen: Finite-Element-Methode (FEM) mit Maple
|
|
Rationale Arithmetik, Rechnen mit symbolischen Konstanten, symbolisches
Integrieren und Differenzieren, Visualisierungsmöglichkeiten machen Computer
Algebra zu einem attraktiven und anerkannten Werkzeug für die einzelnen
Aufgabenstellungen des wissenschaftlichen Rechnens. Der Vortrag zeigt, wie
die Implementierung und Analyse der FEM-Algorithmen und Datenstrukturen
mit Computer Algebra System Maple mit viel geringerem Aufwand gestaltet
werden kann im Vergleich zu "üblichen" Programmiersprachen, wie z.B. C++,
Java oder Fortran. Anschließend wird die Möglichkeit der automatischen
Übersetzung des untypisierten Maple-Codes in die strengtypisierte
Programmiersprache Java behandelt. Als numerisches Beispiel wird die Lösung
der zweidimensionalen Poisson-Gleichung auf komplexen geometrischen Regionen
mit Dirichlet-Randbedingungen vorgestellt.
|
|
|
Mi, 26.11.2003
|
Prof. Ernst W. Mayr
Polynomial Ideal Power - A Survey
|
|
We consider the polynomial ring with variables $x_1,\ldots,x_n$ and
coefficients from a field like the rationals or $GF(2)$. Systems of such
polynomials define algebraic varieties, as the sets of their common zeroes.
A fundamental problem for polynomial ideals is the word problem: Given a
test polynomial, is it contained in some given polynomial ideal? It is known
that the computational complexity of this word problem is very high
(EXPSPACE-complete for the case of rational coefficients).
We show how polynomial ideals can be used to model some formal systems in
mathematics and computer science, e.g., commutative semigroups or Petri
nets, and discuss complexity theoretic consequences.
|
|
|
Do, 27.11.2003, 17:15 Uhr, HS 2 (MI 00.04.011)
|
Sonderankündigung Kolloquium: Prof. Farid Ablayev (Kazan State University)
On the Computational Power of Classical and Quantum Branching Programs
|
We describe a model of a Quantum Branching Program
(qbp) and study its computational power. We define several natural
restrictions on this model, including bounded-width and
read-once qbps.
Our model of quantum width-2 branching program corresponds to quantum
computations based on a single quantum bit. Informally speaking, our main
result shows that polynomial-length computations based on one quantum bit
are very powerful.
More precisely, we present upper and lower bounds on the power of quantum and
stochastic branching programs of constant width. We show that any
language in NC^1 can be recognized with exact acceptance by a
width-2 quantum branching program of polynomial length, in contrast
to the classical case where width 5 is necessary unless NC^1=ACC. This
separates width-2 quantum programs from width-2 doubly stochastic programs as
we show the latter cannot compute the middle bit of the multiplication
function. We also show that constant-width quantum and stochastic branching
programs can be simulated by classical branching programs of larger but
bounded width, so the languages accepted by
them are in NC^1.
This is a joint work with Christopher Moore
and Christopher Pollett.
|
| Um 17:00 Uhr c.t., HS 2 (MI 00.04.011) |
|
|
Fr, 28.11.2003, 15:00 Uhr s.t.
|
Dr. Werner Seiler, Institut fuer wissenschaftliches Rechnen (IWR), Universität Heidelberg
Involutive Basen
|
|
Involutive Basen sind eine spezielle Art von (im allgemeinen nicht
reduzierten) Gr"obner-Basen, die "uber zus"atzliche kombinatorische
Eigenschaften verf"ugen.Die Theorie der involutiven Basen f"uhrt auch zu einer
Alternative zu dem klassischen Buchberger-Algorithmus f"ur die Berechnung von
Gr"obner-Basen, die sich in Vergleichsrechnungen als sehr effizient erwies.
Ziel des Vortrags ist es, eine allgemeine Einf"uhrung in die Ideen hinter
involutiven Basen und in deren Anwendungen (insbesondere die Strukturanalyse
polynomialer Moduln) zu geben.
|
|
|
Mi, 3.12.2003
|
Thomas Bayer
Berechnung optimaler Beschreibungen von Orbitraeumen und Strata von endlichen Gruppen
|
|
Kompakte Lie-Gruppen treten als Symmetriegruppen von zahlreichen
physikalischen Systemen (z.B. Mechanik, Hochenergiephysik,
Materialwissenschaften) auf. Um die Konstruktion von Potentialen, die
invariant bzgl. einer endlichen Gruppe sind, zu erleichtern,
geht man vom Darstellungsraum (auf dem die Gruppe operiert, i.a. R^n)
zum Orbitraum ueber. Der Orbitraum kann in endlich viele so
genannte Strata disjunkt zerlegt werden. Aus wichtigen Resultaten von
Broecker und Scheiderer folgt, dass jedes d-dimensionale Stratum bzw.
sein Abschluss mit maximal d bzw. d(d+1)/2 vielen Ungleichungen
beschrieben werden kann. Es werden ein konstruktives Verfahren, das fuer
beide Faelle genau d viele Ungleichungen liefert, und eine untere
Schranke (mindestens d viele Ungleichungen sind notwendig) vorgestellt.
|
|
|
Mi, 10.12.2003
|
Klaus Holzapfel
Dichte-basiertes Clustern in großen Graphen
|
Die Analyse von großen Netzwerken mit sehr
vielen Elementen (z.B. WWW, biochemische
Reaktionsnetze oder große soziale
Beziehungsgeflechte) wird häufig mittels
geeigneten Abstraktionen durchgeführt. Die
hierfür verwendeten Techniken beruhen
unter anderem auf einem dichte-basierten
Konzept.
Wir diskutieren, ausgehend von einer
Darstellung typischer Eigenschaften der
zugrundeliegenden Netzwerke, die
Komplexität des Erkennens von dichten
Substrukturen. Da das zugehörige
Entscheidungsproblem in vielen Fällen
NP-vollständig ist, betrachten wir ferner
ein entsprechendes
Optimierungsproblem. Abschließend werden
einige Heuristiken aus dem Bereich der
Community-Erkennung im WWW (mittels des
Hyperrefernz-Graphen) erläutert.
|
|
|
Mi, 17.12.2003
|
Markus Holzer
On The NP-Completeness of the NURIKABE Pencil Puzzle
|
NURIKABE (engl. coating wall) is a solitaire puzzle, which was
invented by Nikoli Inc., a Japanese publisher---Nikoli is publisher's
name of Japan's No. 1 puzzle magazine Nikoli, which contains a wide
variety of puzzles like, e.g., visual puzzles, word puzzles, and
number puzzles. We show that NURIKABE is intractable, namely
NP-complete. Moreover, we study the computational complexity of
variants of the game, when some rules are forbidden.
Zum letzten Termin vor Weihnachten gibt es Glühwein,
Kinderpunsch und Kekse.
|
|
|
Mi, 07.01.2004
|
Stefan Pfingstl
Dublettenerkennung - Schranken und Verfahren
|
|
Die Erkennung von Dubletten in großen
Datenbeständen ist ein bisher noch nicht
zufriedenstellend gelöstes Problem.
Es werden Schranken und die Verfahren gezeigt,
die die Äquivalenzklassen und deren
Kardinalität der Daten bestimmen.
|
|
Di, 20.01.2004, 13:00 Uhr s.t.
|
Dr. Thomas Sturm
(Ansprechpartner: Thomas Bayer)
History, State, and Perspectives of Applied Quantifier Elimination
|
|
The REDLOG package of the computer algebra system REDUCE extends the
idea of symbolic computation from computer algebra to first order
logic. Development started around 1992 with real quantifier
elimination algorithms. Over the years the system has been
continuously extended by further domains and algorithms: real numbers,
complex numbers, p-adic numbers, and quantified propositional
calculus. The integration of Presburger arithmetic (additive theory of
the integers) is in progress, and that of free term algebras is under
consideration. Furthermore there are both the theoretical foundation
and an experimental implementation available for combining the various
domains within the framork of constraint logic programming. The talk
gives and overview on the various REDLOG domains, their application
range, and complexity issues. This will be supplemented by a brief
introduction of REMIS, a database of REDLOG examples, which is
available online since 2000.
|
|
|
Mi, 21.01.2004
|
Prof. Dr. Klaus Wagner
(Ansprechpartner: Sven Kosub)
Eine Reduzierbarkeit für sternfreie Sprachen
|
Es wird ein logik-basierter Reduzierbarkeitsbegriff betrachtet, unter dem die
Klassen der Dot-Depth-Hierarchie abgeschlossen sind und bezüglich dessen
diese Klassen vollständige Mengen besitzen. Durch die entsprechende
Halbordnung der Grade wird die durch die Dot-Depth-Hierarchie gegebene
Struktur der sternfreien Sprachen verfeinert. Es werden strukturelle
Eigenschaften der Halbordnung der Grade untersucht und ein Anfangsstück
dieser Halbordnung genau charakterisiert. Dabei wird die sehr enge Beziehung
zwischen den sternfreien Sprachen und Komplexitätsklassen innerhalb der
Polynomialzeithierarchie ausgenutzt.
Gemeinsame Arbeit mit Victor L. Selivanov, Novosibirsk
|
|
|
Mi, 28.01.2004
|
Johannes Nowak
A New Indexing Method for Approximate Pattern Matching with One Mismatch
|
|
We consider the problem of designing an efficient index for
approximate pattern matching. This topic is still a challenge in
combinatorial pattern matching.
We present a new index structure that allows to report all substrings
of a text that match a given input pattern with one mismatch in linear time
with respect to the pattern length. The size
of our index is $O(n\log(n))$
on average and with high probability, where $n$ is the length of
the text.
|
|
|
Mi, 04.02.2004
|
Jan Griebsch
Hierarchische Graphen
|
|
Graphen werden oft benutzt, um strukturierte Daten zu untersuchen. Beispiele
sind Graphen, die die Beziehung von Domains im Internet darstellen, oder
biochem. Netzwerke, die die Interaktion chemischer Reaktionen in der Zelle
modellieren. Solche Graphen sind oft zu gross um effizient analysiert und
dargestellt werden zu koennen. Oft laesst sich jedoch eine Semantik
definieren, die den Graphen in eine Hierarchie von Teilgraphen zerlegt.
Es werden Ansaetze und Datenstrukturen vorgestellt, die eine effiziente
Navigation in solchen hierarchischen Graphen ermoeglichen sollen.
|
|
|
Mi, 11.02.2004
|
Sven Kosub
Beziehungsprobleme 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 traffic engineering. In
diesem Vortrag werden wir dahin gehend das Problem betrachten, aus
Informationen, die in den BGP routing tables enthalten sind, auf die
vertraglichen Beziehungen (customer-to-provider,
peering-to-peering und sibling-to-sibling) zwischen den
autonomen Systemen zu schließen. Dazu geben wir graphentheoretische
Charakterisierungen für dieses Problem an und diskutieren algorithmische
Lösungen für darauf aufbauende kombinatorische Optimierungsprobleme. Von
besonderem Interesse bei der Modellierung der Probleme ist hierbei die
Annahme wirtschaftlicher Rationalität bei den Internetteilnehmern.
|
|
|
Mi, 18.02.2004
|
Henning Bordihn, Universität Potsdam
Parallele vs. sequentielle
Ersetzungssysteme unter dem Aspekt der Beschreibungskomplexität
|
|
L-Systeme sind String-Ersetzungssysteme, die sich von
Phrasen-Struktur-Grammatiken, wie zum Beispiel den kontextfreien
Grammatiken, dadurch unterscheiden, dass in jedem Ableitungsschritt
alle Symbole der Satzform parallel ersetzt werden. Solche parallelen
Grammatikformalismen wurden 1968 von A. Lindenmayer eingführt, um die
Entwicklung biologischer Organismen zu formalisieren. Diese
Formalismen erlauben es zum Beispiel, allein aufgrund der Regeln über
die Zellteilung mathematische Aussagen über die Schnelligkeit des
Wachstums der Organismen zu treffen (Wachstumsfunktionen).
In diesem Vortrag soll zunächst ein überblick über die wichtigsten
Ergebnisse zur Beschreibungskomplexität von L-Systemen mit
kontextfreien Produktionen gegeben werden, wobei neben eher
klassischen Komplexitätsmaßen (Anzahl der Nichtterminale oder
Produktionen) auch spezifische, biologisch motivierte Kriterien
betrachtet werden. Hierzu zählen insbesondere der Synchronisierungs-
und der Nichtdeterminiertheitsgrad sowie die Anzahl der aktiven
Symbole.
Anschließend werden diese Ergebnisse denen für die entsprechenden
sequentiellen Mechanismen gegenübergestellt.Dabei werden auch die
bedeutendsten Varianten der Systeme (mit oder ohne Hilfssymbole,
tabellierte Systeme etc.) berücksichtigt, weshalb auch kooperierende
verteilte (CD) Grammatiksysteme in die Diskussion einbezogen werden.
Auf diese Weise wird festgestellt, in welchen Fällen die parallelen
oder die sequentiellen Mechanismen effizientere Beschreibungen für
die Sprachen liefern, die sie gemeinsam erzeugen können.
Schließlich wird untersucht, welcher Grad der Parallelität in der
Ersetzung tatsächlich bei der Erzeugung der Sprachen benötigt wird.
Dieser Parallelitätgrad besitzt eine Reihe von Querbezügen zu vielen
der o.g. Maße der Beschreibungskomplexität, so dass neue Einsichten
zum Beispiel in die Theorie der Wachstumsfunktionen gewonnen werden
können.
|
|
Moritz Maaß
|
