Moderne Rechnersysteme liefern in vielerlei Hinsicht erweiterte Anwendungsmöglichkeiten:
- Parallele Rechnernetze erlauben die Behandlung äußerst komplexer algorithmischer Probleme.
- Das Internet bietet die Möglichkeit zum weltweiten Informationsaustausch und hat sogar das Potenzial, als gigantischer Parallelrechner genutzt zu werden.
- Drahtlose Kommunikationssysteme erlauben sehr flexible Kommunikation auch zwischen mobilen Stationen.
- Hardware-Unterstützung für Graphikanwendungen ermöglicht Echtzeit- Navigation in sehr komplexen virtuellen Szenen.
Eine besondere Herausforderung stellen Rechensysteme dar, die aus unterschiedlichen Komponenten (z.B. unterschiedlich leistungsfähigen Prozessoren, Speichermedien oder Kommunikationssystemen) bestehen, und deren Struktur sich mit der Zeit verändert. Die algorithmischen Fragestellungen, die sich bei der Realisierung und effizienten Nutzung solcher heterogenen, dynamischen Systeme ergeben, stehen zurzeit im Zentrum unserer Arbeiten.
Paralleles Rechnen: Peer-to-Peer-basiertes Web Computing
Rechnernetzwerke können potentiell nahezu unbegrenzte parallele Rechenleistung zur Verfügung stellen, ihre effiziente Nutzung stellt jedoch ein extrem komplexes Problem dar. Die von uns entwickelte PUB-Bibliothek findet mittlerweile auch international Anwender. Unsere Web- Computing Bibliothek PUB-Web geht nun einen Schritt weiter und nutzt das Internet als Parallelrechner. Hier gehören insbesondere die auf einem Peer-to-Peer System basierende Konstruktion sowie die verteilte, auf der Basis von nur sehr beschränktem lokalen Wissen arbeitende Lastbalancierung zu den zentralen Herausforderungen.
Computergrafik: Echtzeitnavigation in riesigen Szenen
Um in einem virtuellen dreidimensionalen Raum navigieren und einen fotorealistischen Eindruck erzeugen zu können, werden u. a. enorme Ansprüche an Datenstrukturen gestellt, mit denen solche Szenen verwaltet, und mit denen Bilder gerendert werden. Ein derzeitiger Schwerpunkt liegt bei uns auf der Entwicklung von Methoden, zu gegebener Blickposition und -richtung in Echtzeit Entscheidungen über das in diesem Fall effizienteste der anwendbaren Rendering-Verfahren zu treffen. In einem ersten Schritt arbeiten wir an derartigen Methoden zur Unterstützung der Entscheidung, ob es sich lohnt, Culling Verfahren einzusetzen. Zudem erproben wir unsere Ansätze in Anwendungen zur Produktionsplanung und -steuerung gemeinsam mit Partnern im Heinz Nixdorf Institut.
Lokale Strategien in dynamischen Netzwerken: Die neue Herausforderung
Dynamische Netzwerke, d.h. Netzwerke, in denen Knoten ihre (geometrische/ geographische) Position mit der Zeit verändern können, spielen in vielen Bereichen eine wichtige Rolle. Sie tauchen z.B. als Datenstruktur für bewegliche Objekte in der Computergrafik, als Modelle für drahtlose, mobile Kommunikationsnetzwerke oder als Bewegungsmuster von Explorationen auf. Als Beispielproblem untersuchen wir die algorithmischen Probleme, die sich durch die Aufgabe ergeben, ein unbekanntes Gelände durch eine große Zahl von Robotern zu erforschen. Auch hier ist die Entwicklung von lokalen Strategien, die zu global gutem Verhalten führen, eine zentrale Herausforderung.
Algorithmische Spieltheorie und Preisoptimierung
Die kombinatorische Preisoptimierung umfasst eine Vielzahl natürlicher Optimierungsprobleme, die sowohl bei der Berechnung erlösmaximierender Produktpreise basierend auf Informationen über die Präferenzen potentieller Kunden als auch beim Design von Auktionsmechanismen in strategischen Szenarien - einem zentralen Problem der algorithmischen Spieltheorie - eine Rolle spielen. Wir betrachten diese Probleme vor allem unter algorithmischen Aspekten mit einem Fokus auf Methoden zur Approximation und Techniken zur Randomisierung - zweier zentraler Paradigmen im Bereich der Algorithmen und Komplexitätstheorie.
Randomisierung: Eine grundlegende algorithmische Technik
Unsere algorithmischen Arbeiten haben uns immer wieder gezeigt, dass die Nutzung von Randomisierungstechniken große Effizienzvorteile liefert. Daher setzen wir uns systematisch mit dem Potenzial von randomisierten Algorithmen auseinander und entwickeln bzw. nutzen wahrscheinlichkeitstheoretische Methoden für ihre Analyse.
Unsere Lehre: Eng mit der Forschung gekoppelt
Unsere Lehrveranstaltungen vermitteln Methoden und Konzepte für die Entwicklung und Analyse effizienter Algorithmen. Wir veranstalten Projektgruppen und unterstützen Diplomarbeiten, die unsere theoretischen Einsichten anwenden, um effiziente Algorithmen und Bibliotheken zu entwickeln.
