|
|
| |
Titelseite
->
Inhaltsverzeichnis
->
2 Berichte der Abteilungen
2.2 Abteilung für Informatik II |
||
|
Theoretische Informatik(A. Schönhage)
Schwerpunkte in Forschung und Lehre
KomplexitätstheorieBei den komplexitätstheoretischen Untersuchungen stehen Themen im Vordergrund, die sich im Zusammenhang mit Grundaufgaben der Numerischen Mathematik stellen. Zu nennen sind hier die algebraischen Komplexitätsfragen bezüglich des Rechnens mit Polynomen und Matrizen, z.B. Matrixmultiplikation und Verwandtes. Neben weiterer Verbesserung der bisher bekannten Resultate geht es hierbei auch darum, die bisher rein theoretischen Einsichten für praktische Anwendungen zu erschließen. Ferner ist hier ein derzeit laufendes DFG-Projekt Erforschung multiplikativer Komplexitäten von Grundaufgaben beim Rechnen mit univariaten und multivariaten Polynomen zu nennen.
Effiziente numerische AlgorithmenDie schon länger bekannten Schranken zur Bitkomplexität des Rechnens mit langen Zahlen bzw. hohen Genauigkeiten sind inzwischen in die Praxis umgesetzt. In den vergangenen Jahren wurde eine umfangreiche Grundsoftware zum schnellen Rechnen mit ganzen, rationalen, reellen und komplexen Zahlen in beliebiger Genauigkeit entwickelt und für ,,Turing Prozessoren`` implementiert, die auf realen Rechnern effizient emulierbar sind. Dieses System ist im sogenannten ,,TP-book`` beschrieben (A. Schönhage, A. Grotefeld, E. Vetter: Fast Algorithms - a multitape Turing machine implementation, B.I. 1994). Im Vordergrund steht der weitere Ausbau dieser Software, besonders in Richtung auf schnelle (und sichere) Nullstellenberechnung von komplexen Polynomen mit Anwendungen wie z.B. der Berechnung von Matrixeigenwerten.
Computer-AlgebraDiese numerische Software hat auch enge Bezüge zur Computer-Algebra. Interessante Anwendungen ergeben sich beim Rechnen mit Polynomen über endlichen Körpern und bei der Faktorisierung von Polynomen mit ganzzahligen Koeffizienten im Hinblick auf das Rechnen mit algebraischen Zahlen. Geplant ist, die oben erwähnte Nullstellenberechnung mit Gröbnerbasen zu kombinieren.
Technische Informatik(J.K. Anlauf)
Schwerpunkte in Forschung und Lehre
Pulsverarbeitende Neuronale NetzeKlassische Neuronale Netzwerkalgorithmen werden für vielfältige Anwendungen eingesetzt, bei denen es auf Lernfähigkeit und Adaptivität ankommt. Sie implementieren allerdings nur einen Teilaspekt der Informationsverarbeitung, die in natürlichen Neuronalen Netzen stattfindet, da von diskreten Nervenimpulsen abstrahiert wird und nur mittlere Impulsraten betrachtet werden. Die Information, die in dem exakten Zeitpunkt einzelner Impulse liegt, wird dabei völlig ignoriert. Es ist jedoch bekannt, daß natürliche Nervensysteme ihre Ergebnisse häufig so schnell berechnen, daß ihnen währenddessen keine Zeit bleibt, Impulsraten auch nur näherungsweise zu schätzen. In diesem Forschungsvorhaben soll das Potential Pulsverarbeitender Neuronaler Netze (PNN's) für praktische Anwendungen untersucht werden. Insbesondere wird nach Algorithmen gesucht, die die simultane Segmentierung und Klassifizierung von Bildinhalten erlauben. Dazu wird ein verteilter, eventgetriebener Simulator für PNN's (C. Graßmann) entwickelt, der eine effiziente Simulation auch großer Netzwerke auf einem heterogenen Cluster von Workstations und PC's erlaubt. Ein weiterer Schwerpunkt ist die Suche nach Hardware-Architekturen, die eine wesentliche Beschleunigung derartiger Simulationen gegenüber konventionellen Rechnern erlauben.
Technische Anwendungen Neuronaler NetzeDie Theorie neuronaler Netze soll anhand von praktischen Problemen weiterentwickelt werden. Dazu laufen derzeit eine Reihe von Industriekooperationen, die meist vor Ort von Doktoranden und Diplomanden unterstützt werden:
Besonderes Augenmerk wird dabei auf die Generalisierungsfähigkeit der verwendeten Algorithmen sowie deren Robustheit und Industrietauglichkeit gelegt.
Methodik des Hardware-EntwurfsDer systematische Entwurf digitaler Schaltungen mittels Hardwarebeschreibungssprachen (VHDL) stellt einen weiteren Arbeitsschwerpunkt dar. Zur praktischen Umsetzung steht ein Elektroniklabor (G. Schnitzler) mit den notwendigen Tools zur Verfügung.
Betriebssysteme(Ch. Strelen)
Schwerpunkte in Forschung und Lehre
Universelle stochastische ModelleÜblich zur Leistungsbewertung von Rechen- und Kommunikationssystemen sind Simulationsmodelle und analytische Modelle, letztere für formelmäßige oder numerische Auswertung, exakt oder näherungsweise. Seit längerem gibt es Werkzeuge, mit denen Modelle spezieller Problemklassen dargestellt und analysiert werden können, und zwar normalerweise simulativ oder analytisch-numerisch. Ziel dieses Projektes ist eine einheitliche Darstellung von stochastischen Modellen für simulative, exakte numerische oder näherungsweise numerische Auswertung. Das Konzept dafür, genannt Übergangsklassen, ist für eine große Klasse von Modellen geeignet, die auf Markov-Ketten basieren. Ein Modell in dieser Darstellung, ein U-Modell, kann unmittelbar simuliert werden. Ist die Zustandsraumgröße im Bereich des Machbaren, kann es automatisch in eine Markov-Kette umgewandelt werden, die dann mit üblichen Methoden zu analysieren ist. Ist der Zustandsraum zu groß, kann es mit der DA-Methode, siehe unten, näherungsweise analysiert weden. Modelle der üblichen Klassen wie z.B. ganz allgemeine Warteschlangenmodelle oder erweiterte stochastische Petrinetze (GSPN) können automatisch in U-Modelle übersetzt werden. Somit stellen diese eine universelle Schnittstelle zwischen den verschiedenen verbreiteten Modell-Paradigmen und den Analysemethoden dar.
Simulation von Markov-ModellenSchnelle Verfahren für die Simulation diskreter stochastischer Modelle werden benötigt, weil einerseits großer Bedarf besteht, solche Modelle simulativ zu analysieren, und andererseits Simulation inhärent rechenzeitaufwendig ist. Die Suche nach parallelen Simulationsalgorithmen widersetzt sich bisher einer befriedigenden allgemeinen Lösung, obwohl an vielen Stellen daran geforscht wird. Wir verfolgen für eine spezielle Klasse von stochastischen Modellen einen alternativen Lösungsansatz. Diese Markov-Modelle sind dadurch gekennzeichnet, daß ihr Verhalten durch eine Markov-Kette beschrieben wird, auch wenn diese nicht unmittelbar sichtbar ist. Es gibt viele derartige Modelle für wichtige Anwendungen; als Beispiele seien nur allgemeine Warteschlangenmodelle und stochastische Petrinetze genannt. Die Methode beruht auf Replikation von Simulationsläufen, die parallel durchgeführt werden. Das Problem besteht dabei darin, daß hier jedesmal die Einschwingphase durchlaufen werden muß, bis sich stationäre Verhältnisse eingestellt haben; bei der üblichen sequentiellen Vorgehensweise geschieht das nur einmal. Gibt es in einem Simlationsmodell seltene Ereignisse, dann entstehen ganz allgemein bei der Simulation Aufwandsprobleme, so auch hier. Mit mathematischen Methoden, die der simultanen Iteration für Eigenvektoren ähnlich sind, läßt sich der Aufwand bei der verfolgten Vorgehensweise entscheidend reduzieren. Ein anderer Ansatz beruht auf der Methode von Courtois. Die angestrebten Methoden für die Simulation von Markov-Modellen ermöglichen Lösungen für zwei wichtige Probleme, nämlich massiv parallele Simulation und seltene Ereignisse.
Aggregationsmethoden für die Analyse von Markov-ModellenDie in den letzten Jahren entwickelte Disaggregations-Aggregations-(DA-) Methode dient dazu, Modelle mit sehr vielen Zuständen analysierbar zu machen. Dabei werden Partitionen des Zustandsraumes betrachtet und statt einzelner Zustandswahrscheinlichkeiten solche für die Teilmengen von Zuständen, sog. Makrowahrscheinlichkeiten. Für die Rechnung werden implizit jedoch auch die einzelnen Zustandswahrscheinlichkeiten benötigt. Bei der verfolgten Vorgehensweise werden sie mit Entropiemaximierung näherungsweise verfügbar gemacht. Die DA-Methode eignet sich für zahlreiche interessante Markov-Modelle, deren Analyse bekanntermaßen schwierig ist. So konnten beispielsweise Blockiernetze, Fork-Join-Systeme und stochastische Petrinetze für Performability-Modelle damit behandelt werden. Die laufenden Arbeiten betreffen weitere Anwendungen, die mathematischen Eigenschaften der Methode, steife Systeme, also solche mit seltenen Ereignissen, und die Analyse der transienten, zeitabhängigen Phase.
Entwurfsbegleitende Leistungsbewertung paralleler und verteilter ProgrammeFür existierende parallele und verteilte Programme und Dienste werden auf vorhandenen Rechenanlagen durch Messung Leistungscharakteristika statistisch ermittelt. Damit entsteht eine Basis, mit der auch unfertige Programmiersysteme durch Simulation analysiert werden können, auch für nicht verfügbare Rechner- und Netzkonfigurationen.
| ||