Themenbereiche sind unsere Forschungsbereiche

Unsere Studien-, Master- und Diplomarbeiten finden im Umfeld der Forschungsarbeiten und Projekte der Arbeitsgruppe statt. Einen Überblick über unsere Forschungsarbeiten erhalten Sie unter  Forschung und  Projekte. Die Mitarbeiter der Fachgruppe Algorithmen und Komplexität haben verschiedene Studien-, Bachelor, Diplom- und Masterarbeiten im Angebot: Die Themen richten sich einerseits nach den aktuellen Forschungsfragen der Mitarbeiter. Andererseits werden die Themen auf die Interessen, Vorstellungen und Wünsche der Studierenden abgestimmt. Daher beschreiben wir hier die Themengebiete und nur in Einzelfällen konkrete Themen. Zur Themenfindung nehmen Sie bitte daher Kontakt zu den Mitarbeitern auf und wenden Sie sich an die untern aufgeführten Ansprechpartner. Sie geben Ihnen Auskunft über mögliche Themenstellungen. Kommen Sie zu uns in der Fürstenallee vorbei oder sprechen Sie per E-Mail einen Termin mit uns ab.

Algorithmische Probleme in Dynamischen Systemen

Algorithmen, die mit wenigen lokalen Informationen Probleme in hochdynamischen Umgebungen lösen, stehen derzeit im Mittelpunkt unserer Forschung. Beispiele hierfür finden sich in unterschiedlichsten Bereichen: Verbünde vieler autonomer Roboter die ein unbekanntes Terrain erkunden, intelligente Peer-to-Peer Netze die ihre Struktur aktiv an neue Suchanfragen und Teilnehmer anpassen oder die Verwaltung einer Vielzahl von heterogenen Ressourcen in Großrechenzentren.

Smart Teams und Sensornetzwerke

• Kontakt: Barbara Kempkes

Lokale Algorithmen für große dynamische Netzwerke

Im Rahmen des  Sonderforschungsbereiches 901 "On-The-Fly Computing" beschäftigen wir uns mit grundlegenden Fragestellungen rund um die Funktionsweise großer (Peer-to-Peer-)Netzwerke. Wir betrachten dabei Netzwerke die so groß sind, dass nur noch verteilte Algorithmen sinnvoll eingesetzt werden können. Themenschwerpunkte unserer aktuellen Forschung bilden dabei das verteilte Suchen von Diensten und die dynamische Rollenzuweisung (Stichwort: Facility Location Problem). Abschlussarbeiten in diesem Themengebiet beschäftigen sich mit Entwurf, Analyse und Simulation von Algorithmen für solche dynamischen Netzwerke.

Kontakt:  Andreas Cord-Landwehr,  Peter Pietrzyk

Scheduling für On-The-Fly Compute Server

On-The-Fly Compute Center umschreiben unsere Vision von zukünftigen Großrechenzentren. Markante Merkmale sind ihre Größe sowie Heterogenität: Sie umfassen mehrere Millionen Knoten, welche jeweils über 10.000 Kerne enthalten. Diese Kerne sind dabei im Gegensatz zu heutigen Rechenkernen heterogen, so dass CPU-, GPU-, FPGA- und andere Beschleunigereinheiten auf ein und demselben Chip untergebracht sind.

Im Rahmen des  Sonderforschungsbereiches 901 "On-The-Fly Computing" beschäftigen wir uns mit grundlegenden Scheduling Techniken und anderen algorithmischen Fragestellungen für solche Großrechenzentren. Dabei geht es hauptsächlich um die Entwicklung und Evaluation von theoretisch handhabbaren Modelle und Algorithmen sowie deren formale Analyse. Hierbei ergeben sich viele interessante Fragestellungen für Bachelor- und Masterarbeiten. Mögliche Themenschwerpunkte umfassen z.B. Techniken für energieeffiziente und profitorientierte Schedulingstrategien.

Kontakt:  Peter Kling

Algorithmen der Computergraphik

Effiziente Algorithmen sind ein wesentlicher Bestandteil im Bereich der Computergrafik. Sie werden bei Problemen wie dem Echtzeitrendering komplexer CAD-Daten, der Kollisionserkennung, dem Motion Planning, beim fotorealistischen Rendering und in vielen weiteren Bereichen eingesetzt. Wir arbeiten an der Entwicklung neuer schneller Algorithmen zur Darstellung geometrischer 3D-Daten. Wir bewerten unsere Algorithmen durch die Analyse, Implementierung und Evaluierung der Methoden.  [mehr ...]

Abschlussarbeiten im Bereich Computergrafik beschäftigen sich mit dem Entwurf und der Entwicklung von Algorithmen und Datenstrukturen sowie deren systematisch durchgeführten experimentellen Evaluation. Dazu gehören des Weiteren eine gründliche Literaturrecherche in dem Bereich, eine Analyse der Laufzeit und des Speicherbedarfs, als auch eine Analyse der Bildqualität der entwickelten Verfahren. Um den reinen Implementierungsaufwand der Arbeiten zugunsten der wissenschaftlichen Auseinandersetzung mit dem Thema so weit wie möglich zu reduzieren, steht die von uns seit 2007 entwickelte Software PADrend (Platform for Algorithm Developement and Rendering) zur Verfügung.

Laufzeitvorhersage und automatische Adaption von Renderingverfahren

In der Literatur als auch als Gegenstand aktueller Forschung gibt es eine große Anzahl unterschiedlicher Algorithmen und Datenstrukturen, die für die Darstellung komplexer dreidimensionaler Datensätze verwendet werden können.
Occlusion-Culling-Algorithmen werden beispielsweise eingesetzt, um verdeckte Bereiche der Szene zu erkennen und so die Anzahl der berechneten Bilder pro Sekunde zu erhöhen. Die Occlusion-Culling-Algorithmen können jedoch je nach verwendeter virtueller Szene oder Betrachterstandpunkt in der Szene auch einen zusätzlichen Overhead erzeugen, so dass ihr Einsatz aufgrund der zusätzlich durchgeführten Operationen auch kontraproduktiv sein kann.
Zum einen zielt unsere Forschung in diesem Bereich auf die Identifizierung der für die Effizienz von Renderingalgorithmen relevanten Charakteristika der Szene ab. Können die relevanten Charakteristika dann effizient automatisch für eine gegebene Szene bestimmt werden, ist es darauf aufbauend möglich, geeignete Algorithmen für eine Szene  automatisch auszuwählen ---  ohne das sonst notwendige Expertenwissen. Des Weiteren können sogar für für unterschiedliche Standpunkte in der Szene oder für verschiedene Teile der Szene unterschiedliche Algorithmen ausgewählt werden, was insgesamt sogar zu einer besseren Laufzeit führen kann, als wenn nur ein einzelner Algorithmus ausgewählt wird.

Kontakt:  Claudius Jähn,  Ralf Petring

3-D-Darstellung auf mobilen Endgeräten

Die Echtzeitdarstellung von 3-D-Szenen auf mobilen Endgeräten (z. B. Smartphones, Tablet-PCs) stellt aufgrund der geringen Leistungsfähigkeit dieser Geräte eine besondere Herausforderung dar. Die Rechenleistung der eingebauten Grafikkarten und die Größe der Arbeitsspeicher sind viel geringer als auf einer Workstation. Dennoch sollen auch unterwegs aus CAD-Daten generierte Szenen visualisiert werden können.

Kontakt:  Benjamin Eikel

Automatische Wegeberechnung in virtuellen 3D-Szenen

Simulationssoftware für Materialflusssimulationen unterstützt das 3D-Layout von Simulationsmodellen. Für Anlagenteile wie Fließbänder oder Gabelstapler müssen Wege modelliert werden, um Waren oder Fahrzeuge über die modellierten Wege zu navigieren. Änderungen am Simulationsmodell durch den Modellierer erfordern zeitaufwendige Änderungen der modellierten Pfade.

Wir entwickeln Motion-Planning Algorithmen für den 3D-Raum, die Wege automatisch berechnen. Unsere Algorithmen berechnen allein aus der statischen virtuellen 3D-Szene die 2D-Fahrbahnoberfläche und speichern sie effizient in räumlichen Datenstrukturen (z.B. Octrees). Damit ist eine automatische Navigation von Fahrzeugen in mehrstöckigen Gebäuden, die über Rampen und Treppen verbunden sind, möglich (s. Bilder links). Diese Algorithmen laufen in 3D Echtzeit-Renderingsystemen.

In diesem Bereich bieten sich viele schöne Themen für Bachelor- oder Masterarbeiten an.

Kontakt:  Hendrik Renken,  Matthias Fischer