|
Über symbolisch-numerische
Lösungsverfahren für
polynomiale Gleichungssysteme
Prof. Dr. Gert-Martin Greuel, Prof. Dr. Gerhard Pfister
Fachbereich Mathematik, Universität Kaiserslautern
Symbolische Verfahren der Computeralgebra wie z.B. Gröbnerbasis-
oder Resultantenmethoden haben sich als sehr vielversprechend bei der
Aufbereitung von algebraischen Gleichungssystemen zur numerischen
Lösung erwiesen. Es wird über neue Entwicklungen auf diesem
Gebiet und Implementierungen in SINGULAR berichtet.
Das MORE-Konzept
- Realisierung und Anwendungen in der Verifikation
Dipl.-Inform. Andreas Hett
Fakultät für angewandte Wissenschaften,
Albert-Ludwigs-Universität, Freiburg
Binary Decision Diagrams (BDDs)
als Datenstruktur zur Repräsentation und Manipulation von
Booleschen Funktionen sind insbesondere im Bereich der Verifikation
weit verbreitet und werden erfolgreich auch im industriellen Bereich
eingesetzt.
Mit wachsender Zahl von Anwendungen sind aber auch inhärente Nachteile
sichtbar geworden, und es hat sich als sinnvoll herausgestellt,
die Kernalgorithmen der BDD-Pakete neu zu überdenken.
Dies hat zur Entwicklung des MORE--Konzeptes geführt, bei dem durch die
Einführung von Operatorknoten im BDD alle
Synthesealgorithmen auf eine Basisoperation, nämlich den
Level-Tausch, zurückgeführt werden.
Im Vortrag wird die Umsetzung des Konzeptes und seine Anwendung
auf Probleme der kombinatorischen und sequentiellen Verfikation diskutiert.
Ein Vergleich zu klassischen ITE-basierten Techniken ergibt eine
konkurrenzfähige, vielfach bessere Performanz.
Empirischer Entwurf von Anwendungsalgorithmen
Prof. Dr. Dorothea Wagner
Fakultät für Mathematik und
Informatik, Universität Konstanz
Bei der algorithmischen Behandlung echter Anwendungsprobleme werden
Anforderungen gestellt, die über eine angemessene mathematische
Problemmodellierung und den Entwurf eines entsprechenden abstrakten
Algorithmus hinausgehen. So ist etwa für den Entwurf von praktikablen
Anwendungsalgorithmen eine genauere Analyse der Daten und eine
systematische experimentelle Studie der Algorithmen erforderlich.
Darüber hinaus spielen Robustheit der Algorithmen gegenüber
Änderungen der Problemstellung oder
die Frage der Validierung der Ergebnisse eine Rolle.
Im Vortrag wird über
Erfahrungen und Ideen berichtet, die sich im Rahmen des Projektes bei
mehreren konkreten Anwendungsproblemen beim Algorithmenentwurf als
hilfreich erwiesen haben.
Explorieren und Durchsuchen unbekannter Umgebungen
Prof. Dr. Rolf Klein
Fachbereich Informatik, Fernuniversität Hagen
Autonome mobile Systeme wie z. B. Reinigungs- und Service-Roboter
müssen, je nach Aufgabe, einige Grundfunktionen beherrschen.
Dazu gehören insbesondere das vollständige Erkunden (Explorieren)
unbekannter Umgebungen und das Suchen nach einem Zielobjekt.
Für diese Aufgaben und verschiedene Sensormodelle entwickeln
und implementieren wir einfache Online-Strategien, für die
garantiert werden kann, dass - im Vergleich zur optimalen
Offline-Lösung - ihre Kosten beschränkt sind.
Automatisches Zeichnen von Graphen: Theorie und
Praxis
Dr. Sebastian Leipert,
Institut für Informatik, Universität zu Köln
Prof. Dr. Stefan Näher, Fachbereich Mathematik und Informatik,
Martin-Luther Universität Halle-Wittenberg
Exemplarisch werden theoretische Resultate der Arbeitsgruppe zur
Schichtplanarität vorgestellt und eine Softwaredemonstration des
AGD-Servers und von GraphWin durchgeführt.
Schichtgraphen gehören in der Praxis zu den am häufigsten
vorkommenden Graphen und bis
vor zwei Jahren war unbekannt, ob solche Graphen in polynomieller Zeit auf
Schichtplanarität getestet werden können.
Schichtplanarität ist dabei eine besondere
Form der Planarität, die abhängig von der speziellen
Darstellung der Schichtgraphen ist.
Wir zeigen, dass dieses Problem in polynomieller Zeit gelöst
werden kann und präsentieren darüber hinaus einen
Einbettungsalgorithmus zur Bestimmung einer
schichtplanaren Einbettung, der ebenso wie der von uns
entwickelte Schichtplanaritätstest eine lineare Laufzeit besitzt.
Der AGD-Server erlaubt es Anwenderprogrammen (clients) auf
den unterschiedlichsten Plattformen (z.B. nicht auf LEDA aufsetzend,
nicht in C++ implementiert oder gar auf einem fremden Betriebssystem
laufend), die Algorithmen zum Zeichnen von Graphen aus der AGD-Bibliothek
aufzurufen. Innerhalb des AGD-Projekts existieren zur Zeit zwei AGD-Clients:
der GraphWin-Editor, der mit einem lokalen AGD-Server
kommuniziert, und Java-GraphWin (die Java-Variante von GraphWin),
der über eine Socket-Schnittstelle mit einem AGD-Server,
der irgendwo im Internet installiert sein kann, Kontakt aufnimmt.
Die Demonstration zeigt die Benutzung des AGD-Servers über das Internet
und gibt dabei gleichzeitig einen Überblick über die
zur Zeit in der AGD-Bibliothek enthaltenen Algorithmen.
Zeichnen von geometrischen Graphen
Prof. Dr. Franz J. Brandenburg
Fakultät für Mathematik und Informatik, Universität Passau
Beim Zeichnen von Graphen geht es um visuelle Darstellungen von Graphen.
Die meisten Algorithmen betrachten dabei Knoten als kleine Punkte und Kanten
als dünne Linien.
Aber, in der Praxis sind die Knoten echte Rechtecke oder
Kreise und die Kanten haben aufgrund ihrer Strichstärke
eine positive Breite.
Diese Attribute werden von den hier betrachteten geometrischen Graphen
berücksichtigt.
Wir diskutieren die hierdurch auftretenden Probleme für klassische Verfahren
beim
Zeichnen von Graphen und stellen Erweiterungen in Theorie und Praxis vor.
Geometrische Graphen ergeben sich auch aus speziellen Graph Clusterings.
Bewegungsminimierung bei der Flow-Shop-Verarbeitung
Prof. Dr. Egon Wanke
Heinrich-Heine-Universität Düsseldorf,
Abteilung für Informatik, Mathematisches Institut
Betrachtet wird eine Flow-Shop-Verarbeitung an geradlinig angeordneten
Maschinen, die von einem (oder mehreren) Arbeiter(n) bedient werden müssen.
Damit die Verarbeitung nicht blockiert, muß der Arbeiter fortlaufend seine
Arbeitsposition wechseln. Die von dem Arbeiter insgesamt zurückgelegte Strecke
zur Verarbeitung aller Jobs an den Maschinen soll minimiert werden. Die
Problemstellung tritt insbesondere in förderbandgesteuerten
Kommissionieranlagen auf.
In solchen Anlagen werden Behälter oder Kartons von Arbeitern mit Ware
gefüllt, die an bestimmten Positionen neben dem Förderband gelagert wird.
Vorgestellt werden verschiedene Algorithmen sowie untere Schranken für die
Bewegungsminimierung eines Arbeiters an einem Förderband.
Einpassung von Dreiecksoberflächennetzen
Prof. Dr. Heinrich Müller
Informatik VII, Universität Dortmund
Gegeben sind zwei Dreiecksoberflächennetze M und N im Raum
sowie ein Approximationskriterium. Gesucht ist eine Bewegung A
für M, so daß die Abweichung zwischen A(M) und N bezüglich
des Approximationskriteriums möglichst klein wird. Es sollen zwei
Lösungsverfahren für dieses Problem vorgestellt werden. Die eine
Lösung ist ein zweistufiges Verfahren aus einer merkmalsbasierten
Grobeinpassung und einer iterativen Feineinpassung. Das zweite
Verfahren besteht in einem ``Abwandern'' der einen Oberfläche durch
die andere, bei dem verschiedene Maßnahmen zur Suchraumeinschränkung
angewendet werden. Beide Verfahren sind praktisch einsetzbar.
Hexaedernetzgenerierung durch kombinatorische Schälprozesse
Dr. Matthias Müller-Hannemann
Fachbereich Mathematik, Technische Universität Berlin
Vom klassischen Maschinenbau bis hin zu neuen Anwendungen in der
Geologie und Medizin benötigt die numerische Analyse und Simulation
von komplexen 3D-Werkstücken mit Finite-Elemente-Methoden die möglichst
automatische Generierung von geeigneten Hexaedernetzen.
Der Vortrag beschreibt einen neuen Ansatz,
der darauf basiert, mit der Generierung eines qualitativ guten
Oberflächennetzes aus Vierecken zu starten, um dann nachfolgend in
einem kombinatorischen Schälprozeß das Werkstück schrittweise
in Hexaeder zu zerlegen.
Dieser Schälprozeß nutzt die Zykelstruktur des Dualgraphen des
generierten Oberflächen-Vierecksnetzes. Die
Zykelstruktur wird iterativ ``geschält'' bis man zum Dualgraphen eines
Hexaeders gelangt. Durch Reversion des Schälprozesses wird dann eine
kombinatorische Hexaederzerlegung konstruiert und schließlich
geometrisch eingebettet.
| 
