Robin Delius, University of Paderborn

25. September 2008, 15:30 Uhr, F1.110

Simulationbegleitende Bausteinmodellierung im Materialflussimulator d³Fact

Aufgabe der Diplomarbeit war die Betrachtung von simulationsbegleitenden Modellierungsaufgaben und den daraus resultierenden Problemfeldern „Zustand einer Simulation“ & „Validität eines Modells“. In der Arbeit wurden Methoden erarbeitet, die den Anwender während der Modellierung bei seiner Aufgabe unterstützen, den Simulationszustand möglichst lange aufrecht zu erhalten. Weil in Abhängigkeit des Modellierungsprozesses diese Zustandstreue nicht automatisch überprüft werden kann, wurden insbesondere Unterstützungsfunktionen am Beispiel der Simulationsumgebung d3FACT entwickelt, die zur Laufzeit die dynamische Anpassung der Modellbausteine und damit des kompletten Simulationsmodells erlauben

(Abschlussvortrag Diplomarbeit)

Adrian Ogierman, University of Paderborn

23. September 2008, 13:00 Uhr, F1.110

Bewegungsdynamische 3D-Szenen und ihre Schwierigkeiten

Die 3D-Computergrafik ist in der heutigen Zeit allgegenwärtig. Seien es nun wissenschaftliche Simulationen, die Verwendung in der Industrie zur Planung und theoretischen Überprüfung von technischem Gerät (wie z.B. Automobilen oder Schiffen), medizinische Diagnostik, oder die Unterhaltung durch Spiele. Mit zunehmender Entwicklung steigen die Erwartungen an die Darstellung und Interaktion mit der virtuellen Umgebung. Letztere soll hochgradig komplex sein und möglichst realistisch dargestellt werden. Dies setzt jedoch ein fein granulares Model mit vielen Einzelobjekten und der Bewegung derer voraus.

An diesem Punkt setzt meine Diplomarbeit an. Untersucht wurde eine Tiefseeszene mit vielen tausend Objekten (Fische), bei der sich jedes davon über die gesamte Szene bewegen konnte. Zwei Hauptgebiete wurden genauer beleuchtet, das konservative/approximative Culling und die Verwaltung der Bewegung selbst. Untersucht wurden folgende Fragestellungen:

1. Was passiert beim Einsatz von Cullingalgorithmen auf einem solchen Szenentyp?

2. Kann man statische Cullingalgorithmen auf diesen Szenentyp adaptieren?

3. Spielt der Szenenaufbau, wie z.B. die Objektbewegung und -position, eine Rolle beim Culling in diesem Szenentyp?

4. Ist eine Verwaltung vieler tausend Objekte in Echtzeit möglich?

5. Welche Wechselbeziehungen existieren zwischen Culling und einer möglichen Bewegungsverwaltung?

6. Kann Culling als Unterstützung oder Vorarbeit für eine Bewegungsverwaltung dienen?

7. Ist eine Reduktion des Berechnungsaufwands bei Simulation von flüssiger Objektbewegung möglich?

(Abschlussvortrag Diplomarbeit)

Peter Pietrzyk, University of Paderborn

23. September 2008, 13:30 Uhr, F1.110

Lokale Strategien zur Optimierung von Kommunikationsketten

Mit einem stationären BaseCamp und einem mobilen Explorer sind zwei Roboter mit einer beschränkten Kommunikationsreichweite gegeben. Bei dem Kommunikationskettenproblem geht es darum, die Kommunikation zwischen diesen beiden Robotern auch über große Entfernungen aufrechtzuerhalten. Dies wird mit weiteren mobilen Robotern, den so genannten Relays, ermöglicht. Sie müssen sich zwischen dem BaseCamp und dem Explorer so anordnen, dass sie das Kommunikationssignal trotz ihrer beschränkten Kommunikationsreichweite weiterleiten können. Die Relays werden nicht von einer globalen Instanz gesteuert, sondern müssen ihre Bewegung selbst anhand von lokalen Informationen festlegen. Dabei ist ihre Anzahl möglichst gering zu halten.

Im Zuge der Diplomarbeit wurden, auf bereits bekannten Strategien aufbauend, zwei weitere Strategien für die Steuerung der Relays entwickelt und ihre Eigenschaften in verschiedenen Szenarien untersucht.

(Abschlussvortrag Diplomarbeit)

Bastian Degener, University of Paderborn

23. September 2008, 14:00 Uhr, F1.110

Assignment problems in Smart Teams

We consider a set of robots that has to organize itself without outer control. The robots have a limited range and have to solve global task assignment problemsunder these hard localöity constraints. We discuss lower bounds and complexity aspects and present a constant factor approximation with constant factor resource augementation.

Projektgruppe ReMoSim, University of Paderborn

15. September 2008, 9:00 Uhr, F1.110

3D-Rendering und Modellierung von simulationsgesteuerten Fertigungssystemen

Die Projektgruppe „3D-Rendering und Modellierung von simulationsgesteuerten Fertigungssystemen“ hat in den vergangenen zwei Semestern einen 3D-Editor zur Bearbeitung von Fabrikszenen entwickelt. Dieser Editor ist mit einem Simulationskernel verbunden, der auf dem Fabrikmodell Materialflusssimulationen durchführt. Die 3D-Szene im Editor wird durch ein von der Projektgruppe entwickeltes Renderingverfahren berechnet. Das Rendering erfolgt parallel auf einem Rechnercluster und verwendet Detailstufen von Objekten (level of detail), welche durch den zuvor in der Fachgruppe entwickelten Randomized-Sample-Tree erstellt werden. Die Projektgruppe wird den Aufbau des Systems und der verwendeten Techniken sowie Ergebnisse präsentieren.

Swetlana Agne, University of Paderborn

10. September 2008, 14:00 Uhr, F1.110

Verteilte Graph-Exploration unter unvollständiger Information

Ziel dieser Arbeit ist der Entwurf und die Analyse von Online-Algorithmen zur Exploration von Bäumen mit einer Gruppe von autonomen mobilen Agenten unter Zuhilfenahme partieller Informationen über den Baum.

Ein Baum mit n Knoten soll von k Agenten (Robotern) durchsucht werden. Diese starten im Wurzelknoten und können sich entlang der Kanten von Knoten zu Knoten bewegen. Der Baum ist durchsucht, wenn jeder Knoten von mindestens einem Roboter besucht wurde. Jeder Roboter braucht eine Zeiteinheit und eine Energieeinheit um eine Kante abzuschreiten.

Bei den Kostenmaßen wird zwischen Zeit- und Energiemodel unterschieden. Im Zeitmodel sind die Kosten definiert als Maximum der Zeiten, die die einzelnen Roboter benötigen. Beim Energiemodell sind die Kosten das Maximum der Kanten, die die einzelnen Roboter durchlaufen.

Bei den partiellen Informationen über den Graphen handelt es sich unter anderem um den Grad des Baums, die Anzahl der Knoten sowie die Tiefe und Dichte des Baums. Derartige Information kann auch auf jeder Kante vorhanden sein; sie beschreibt dann die Eigenschaften des zugehörigen Teilbaums. Es soll untersucht werden, inwiefern diese Informationen die existierenden und in der Literatur beschriebenen Online-Algorithmen verbessern können. Außerdem sollen neue Algorithmen entwickelt und analysiert werden, die diese Informationen effizient nutzen.

(Abschlussvortrag Diplomarbeit)

Barbara Schneider, University of Paderborn

3. September 2008, 14:00 Uhr, F1.110

Local Strategies for connecting stations by small robotic networks

Consider a group of m stations with fixed positions in the plane and a group of n mobile robots, called relays, aiming at building a communication network between the stations consisting of as few relays as possible. We present two strategies for dimensionless, identical (anonymous), oblivious and disoriented relays with limited viewing radius for constructing such a network. These strategies resemble natural strategies of swarms for maintaining formations. A relay does not communicate with others, its decision - whether to remove itself from the system, or where to move - consists only of the relative positions of its neighbors within its viewing radius. We provide a theoretical analysis of worst-case scenarios and upper and lower bounds for the number of relays used by the strategies. In addition, we show some preliminary experimental results.

Daniel Warner, University of Paderborn

13. August 2008, 14:00 Uhr, F1.110

Modelle und Algorithmen für Online File Allocation

Die Arbeit "Modelle und Algorithmen für Online File Allocation" führt in Online-Probleme, Online-Algorithmen und kompetitive Analyse ein, stellt Modelle und Online-Algorithmen für das File Allocation Problem (FAP) vor und analysiert Online-Algorithmen für ein neues Modell d-FAP für das FAP.

Beim FAP werden Online-Algorithmen zur Verwaltung von Kopien einer Datei in einem Netzwerk betrachtet. Dabei werden Kopien einer Datei auf einer Teilmenge der Knoten abgelegt. Wir werden dann mit einer online eintreffenden Anfragesequenz von Lese- und Schreibanfragen auf Knoten des Netzwerks konfrontiert. Ein Online-Algorithmus für das FAP muss die Anfragen bedienen und darf nach jeder Anfrage neue Kopien auf Knoten anlegen oder vorhandene Kopien löschen, solange stets mindestens eine Kopie vorhanden ist. Das Bedienen einer Anfrage, Replikationen und Löschoperationen sind mit Kosten verbunden. Ziel ist es, die Kosten möglichst gering zu halten.

Im Vortrag präsentiere ich einen Teil meiner Ergebnisse bei der Untersuchung eines neuen modifizierten Modells d-FAP: Der Algorithmus "Count" für das FAP auf uniformen Netzwerken ist (3+1/d+1/(D*d))-kompetitiv auf uniformen Netzwerken im neuen Modell d-FAP, und die Kompetitivitätsanalyse ist optimal.

(Abschlussvortrag Studienarbeit)

Nicolas Heine, University of Paderborn

13. August 2008, 14:30 Uhr, F1.110

Analyse von Graphtransformationen zur Aufrechterhaltung dynamischer Zufallsnetzwerke

Mit der Flipper Operation wurde eine Graphtransformation zum Aufbau und zur Aufrechterhaltung d-regulärer Zufalls-Netzwerke vorgestellt. Wird diese Operation wiederholt auf ein Netzwerk angewendet, werden mit hoher Wahrscheinlichkeit Expander-Graphen erzeugt. Im Rahmen dieser Diplomarbeit soll die Flipper Operation (sowie Varianten dieser) auf dynamischen Netzwerken untersucht werden. Dabei sollen die Untersuchungen sowohl für reguläre also auch nicht reguläre Netzwerke durchgeführt werden.

Im Mittelpunkt der Analysen steht das Verhalten im dynamischen Fall, also beim Einfügen und Entfernen von Knoten. Hierbei werden insbesondere verschiedene Einfüge- und Löschstrategien untersucht und verglichen. Von besonderem Intresse ist hierbei die Frage, wie häufig die Wartungsoperation (Flipper Operation) angewendet werden muss, um die Expansionseigenschaft aufrecht zu halten.

(Antrittsvortrag Diplomarbeit)

Katharina Lürwer-Brüggemeier, University of Paderborn

13. August 2008, 15:00 Uhr, F1.110

On Faster Integer Calculations using Non-Arithmetic Primitives

The unit cost model is both convenient and largely realistic for describing integer decision algorithms over +,x . Additional operations like division with remainder or bitwise conjunction, although equally supported by computing hardware, may lead to a considerable drop in complexity. We show a variety of concrete problems to benefit from such non-arithmetic primitives by presenting and analyzing corresponding fast algorithms.

Sabine Naewe, University of Paderborn

6. August 2008, 14:00 Uhr, F1.110

Classification and Unification of Uniform Data Allocation Strategies

In meiner Diplomarbeit will ich das allgemeine Szenario der Verteilung von Daten und Bearbeitung von Anfragen hierzu untersuchen. Hierfür wurden schon sehr viele Methoden und Strategien entwickelt, die unterschiedliche Voraussetzungen und Ansätze benutzen. Diese sollen nun aufgearbeitet und miteinander verglichen werden. Es werden dabei die verschiedenen Vorgehensweisen erläutert und die wichtigsten explizit vorgestellt. Kriterien hierfür sind die Laufzeit der Datenverteilung bzw. der Anfragenbeantwortung sowie die Contention, welche die maximale Belastung eines Speichermoduls angibt. Anschließend sollen die möglichen Anwendungen dieser Verfahren dargestellt werden.

(Antrittsvortrag Diplomarbeit)

Peter Pietrzyk, University of Paderborn

6. August 2008, 14:30 Uhr, F1.110

Lokale Strategien zur Optimierung von Kommunikationsketten

Mit einem stationären BaseCamp und einem mobilen Explorer sind zwei Roboter mit einer beschränkten Kommunikationsreichweite gegeben. Bei dem Kommunikationskettenproblem geht es darum, die Kommunikation zwischen diesen beiden Robotern auch über große Entfernungen aufrechtzuerhalten. Dies wird mit weiteren mobilen Robotern, den so genannten Relays, ermöglicht. Sie müssen sich zwischen dem BaseCamp und dem Explorer so anordnen, dass sie das Kommunikationssignal trotz ihrer beschränkten Kommunikationsreichweite weiterleiten können. Die Relays werden nicht von einer globalen Instanz gesteuert, sondern müssen ihre Bewegung selbst anhand von lokalen Informationen festlegen. Dabei ist ihre Anzahl möglichst gering zu halten.

Für die Steuerung der Relays sind bereits einige Strategien entwickelt und ihre Eigenschaften untersucht worden. Ziel dieser Diplomarbeit ist es, diese Strategien miteinander zu vergleichen und Gründe für ihre unterschiedliche Güte zu finden.

(Antrittsvortrag Diplomarbeit)

Alexander Klaas, University of Paderborn

16. July 2008, 14:00 Uhr, F1.110

Dezentrale echtzeitfähige Steuerungsalgorithmen für ein fahrerloses Transportsystem

In einem fahrerlosen Transportsystem werden automatisch betriebene Fahrzeuge dazu verwendet, Güter oder Personen zu befördern. Die Navigation ist dabei eine wesentliche Aufgabe. Damit die Fahrzeuge autonom einen bestimmten Ort erreichen können, sind echtzeitfähige Steuerungsalgorithmen erforderlich. Aus Gründen wie Skalierbarkeit und Flexibilität ist die Motivation gegeben, dass die Fahrzeuge die dazu notwendigen Berechnungen dezentral ausführen. Für ein konkretes fahrerloses Transportsystem, dem Schienenverkehrsprojekt "`Neue Bahntechnik Paderborn"' der Universität Paderborn, werden in dieser Arbeit solche Algorithmen entwickelt und in Form eines Multiagentensystemes in dem Materialflusssimulator d3Fact implementiert. Simulationen demonstrieren ihre Leistungsfähigkeit.

(Abschlussvortrag Bachelorarbeit, zusammen mit der FG Dangelmaier)

Sabine Helwig, University of Erlangen

2. July 2008, 14:00 Uhr, F1.110

Theoretical Analysis of Initial Particle Swarm Behavior

Particle Swarm Optimization (PSO) is a population-based algorithm for solving (mainly continuous) optimization problems. In this talk, we will analyze particle trajectories in the first iteration. We will prove that in PSO algorithms particles are initialized very close to the boundary with overwhelming probability with respect to the search space dimensionality, and that many particles leave the search space at the beginning of the optimization process. These are first theoretical steps indicating the importance of bound handling for PSO. Experimental investigations confirm the theoretical results and demonstrate that bound handling has significant impact on particle swarm performance.

Peter Sanders, Universität Karlsruhe

27. Juni 2008, 14:15 Uhr, F0.530

Algorithm Libraries for Multi-core Processors

With the advent of ubiquitous multi-core processrs, every performance critical application needs to be parallelized. This enormous burden can be lightened if we have reuseable parallel versions of the most frequently used algorithms. We have started work in this direction by looking at one of the most heavily used algorithm libraries: the C++ STL. By now we have parallel versions of most STL functions and the library is part of the newest GCC distribution. The talk will focus on algorithmic issues and performance evaluation.

Dieser Oberseminarvortrag ist eine gemeinsame Veranstaltung mit dem Oberseminar der  Arbeitsgruppe Monien

Vahan Mkrtchyan, Yerevan State University

25. Juni 2008, 14:00 Uhr, F1.110

Disjoint matchings in regular graphs

We will survey the authors' previous and current results that are related to the problem of constructing special maximum matchings in graphs. We will also discuss the naturally arising problem of disjoint matchings in graphs.

A considerable attention will be paid to the relationship between the theory of disjoint matchings developed by the author and his students, and prominent conjectures of Berge,Fulkerson, Fan-Raspaud and their generalization given by Paul Seymour. A number of approaches will be presented which might lead to the proof of these conjectures.

Michael Kortenjan, University of Paderborn

18. Juni 2008, 14:00 Uhr, F1.110

Clustering triangle centers as a step within SEC-Tree constructions

Size Equivalent Cluster Trees (SEC-Trees) have been developed in order to organize large 3 dimensional scenes as a preprocessing, allowing to render such scenes at a constant frame rate.

One step with the preprocessing is clustering centers of triangles using a variation of density based clustering algorithms. This algorithm starts by assigning an initial neighborhood to each triangle. Then, a flooding approach is applied, searching for other triangle centers contained within the smallest neighborhood at first and continuing by searching for their neighbor. This is reapeted until no more center points are found. If the number of points encountered is above some threshold, this set of points is considered to be a cluster, otherwise the neighborhood is increased.

The costs of this algorithm depend on the definition of initial neighborhoods and how neighborhoods are increased. Two examples will be given and analyzed in this talk.

Frank Hellweg, University of Paderborn

6. Juni2008, 14:00 Uhr, F2.211

Algorithmen für Clustering unter Bewegung für k-Means- und k-Median-Zielfunktionen

Diese Arbeit beschäftigt sich mit dem k-Means- und euklidischen k-Median-Clustering sich bewegender Objekte. Probleme, für die Bewegungsclustering relevant ist, treten zum Beispiel in Ad-hoc-Netzen auf.

Die Formalisierung des Problems ist analog zu der von Har-Peled für Radius-Clustering verwendeten [1] gewählt: Die zu clusternden Objekte sind n Punkte im R^d, deren Bewegung sich durch Polynome mit durch eine Konstante g beschränktem Grad darstellen lässt. Das Ziel ist, ein Clustering zu berechnen, das zu jedem Zeitpunkt einen Approximationsfaktor zum optimalen Clustering garantiert.

Das von Har-Peled vorgestellte Verfahren wird auf k-Means- und euklidisches k-Median-Clustering übertragen, und es werden O(1)-Approximationsalgorithmen angegeben, um Bewegungsclusterings zu berechnen. Diese Algorithmen sind polynomiell in n. Ein weiterer Algorithmus für das k-Median-Problem, der von linearer Bewegung der Punkte ausgeht, ist linear in n und polynomiell in k.

Zudem wird gezeigt, dass sich für k-Means- und euklidisches k-Median-Bewegungsclustering Kernmengen konstruieren lassen.

[1] Sariel Har-Peled: Clustering Motion, Discrete & Computational Geometry Volume 31, Issue 4 (03/2004), S. 545ff., 2004

(Abschlussvortrag Masterarbeit)

Swetlana Belikow, University of Paderborn

4. Juni 2008, 14:00 Uhr, F1.110

Verteilte Graph-Exploration unter unvollständiger Information

Ziel dieser Arbeit ist der Entwurf und die Analyse von Online-Algorithmen zur Exploration von Bäumen mit einer Gruppe von autonomen mobilen Agenten unter Zuhilfenahme partieller Informationen über den Baum. Ein Baum mit n Knoten soll von k Agenten (Robotern) durchsucht werden. Diese starten im Wurzelknoten und können sich entlang der Kanten von Knoten zu Knoten bewegen. Der Baum ist durchsucht, wenn jeder Knoten von mindestens einem Roboter besucht wurde. Jeder Roboter braucht eine Zeiteinheit und eine Energieeinheit um eine Kante abzuschreiten. Bei den Kostenmaßen wird zwischen Zeit- und Energiemodel unterschieden. Im Zeitmodel sind die Kosten definiert als Maximum der Zeiten, die die einzelnen Roboter benötigen. Beim Energiemodell sind die Kosten das Maximum der Kanten, die die einzelnen Roboter durchlaufen. Bei den partiellen Informationen über den Graphen handelt es sich unter anderem um den Grad des Baums, die Anzahl der Knoten sowie die Tiefe und Dichte des Baums. Derartige Information kann auch auf jeder Kante vorhanden sein; sie beschreibt dann die Eigenschaften des zugehörigen Teilbaums. Es soll untersucht werden, inwiefern diese Informationen die existierenden und in der Literatur beschriebenen Online-Algorithmen verbessern können. Außerdem sollen neue Algorithmen entwickelt und analysiert werden, die diese Informationen effizient nutzen.

(Antrittsvortrag Diplomarbeit)

Martin Ziegler, University of Paderborn

28. Mai 2008, 14:00 Uhr, F1.110

A Vision of Oblivious Culling

Die Computergrafik 'kennt' eine unueberschaubare Bandbreite von Cullingalgorithmen, die also, bei gegebener Szene und Standpunkt, verdeckte Objekte vor dem Rendering ausfiltern. Je nach Szene lohnt sich dies, oder eben auch nicht; bzw. man moechte den algorithmischen Aufwand fuer das Ausfiltern (von "sorgfaeltig" ueber "grosszuegig" bis "gar nicht") steuern: angepasst an die jeweilige Szene oder sogar den Standpunkt darin. Wir stellen als vielversprechendes Kriterium hierfuer das SICHTBARKEITSVERHAELTNIS vor: den Bruchteil der Objekte, die (zumindest teilweise) sichtbar sind; und diskutieren Ansatze, dies effizient zu berechnen.

Mario Mense, University of Paderborn

14. Mai 2008, 14:00 Uhr, F1.110

On Redundant and Fair Storage in Dynamic Heterogeneous Storage Systems

We sketch the problem of designing an adaptive hash table for redundant data storage in a system of storage devices with arbitrary capacities. Ideally, such a hash table should make sure that (a) a storage device with x% of the available capacity should get x% of the data, (b) the copies of each data item are distributed among the storage devices so that no two copies are stored at the same device, and (c) only a near-minimum amount of data replacements is necessary to preserve (a) and (b) under any change in the system.

As hash tables satisfying (a) and (c) are already known, we present the first hash table called SPREAD that can satisfy all three properties as long as this is in principle possible and which solves this problem for the first time. As long as (a) and (b) can in principle be satisfied, SPREAD preserves (a) for every storage device within a (1 ± epsilon) factor, with high probability, where epsilon>0 can be made arbitrarily small, guarantees (b) for every data item, and only needs a constant factor more data replacements than minimum possible in order to preserve (a) and (b).

Adrian Ogierman, University of Paderborn

7. Mai 2008, 14:00 Uhr, F1.110

Sichtbarkeitsprobleme bei massiver Bewegungsdynamik von Objekten in komplexen 3D-Szenen

Seit Beginn der 3D-Grafik existiert das Problem zu hoher Komplexität. Seitdem wird an Verfahren zur Komplexitätsreduktion gearbeitet. Eines dieser Verfahren ist Culling. Cullingverfahren versuchen möglichst nur sichtbare Objekte zur Grafikpipeline zu leiten.

Die gängigen Standardverfahren wurden für statische Szenen entwickelt, Abwandlungen für dynamische Szenen sind zumeist auf einen der beiden Punkte beschränkt:

1. geringfügige Bewegungsdynamik der Objekte (zumeist durch Benutzer hervorgerufen)

2. geringe Anzahl der Objekte

Existieren diese Beschränkungen nicht, so ist eine explizite Datenstruktur zur Bewegungsverwaltung von Nöten. In dieser Diplomarbeit sollen Verfahren abgewandelt und entwickelt werden um auch bei massiver Bewegungsdynamik einer extrem hohen Anzahl von Objekten effektives Culling sowie eine effiziente Objektverwaltung zu ermöglichen. Dabei soll möglichst weder das Rendering noch die Datenstrukturverwaltung soweit überwiegen, dass eine Echtzeitnavigation nicht mehr möglich ist

(Antrittsvortrag Diplomarbeit)

Stephan Arens, University of Paderborn

7. Mai 2008, 14:30 Uhr, F1.110

Culling unter Verwendung hierarchischer Cluster

In 3D Anwendungen müssen häufig Szenen mit sehr vielen Dreiecken dargestellt werden, so dass Grafikhardware ihre Leistungsgrenzen erreicht. Es sind jedoch nur selten alle Dreiecke sichtbar, weshalb Culling Verfahren versuchen, möglichst effizient nur die sichtbaren Dreiecke für das Rendern auszuwählen. Um nicht jedes Dreieck einzeln auf seine Sichtbarkeit zu testen, werden Dreiecke in hierarchischen Datenstrukturen zusammengefasst, z.B. in einem Octree.

Es soll nun durch agglomeratives Clustering eine hierarchische Datenstruktur über die Dreiecke der Szene aufgebaut werden. Durch ein passendes Distanzmaß wird erreicht, dass die Knoten des Hierarchiebaums möglichst kleine Ausmaße besitzen und floglich mit einer höheren Wahrscheinlichkeit vor dem Rendern durch das Culling aussortiert werden, als es bei einem Quadtree der Fall ist. Besondere Schwierigkeiten entstehen durch die sehr große Menge an Dreiecken, die ein neues Vorgehen für das Clustern erfordern.

(Antrittsvortrag Diplomarbeit)

Christoph Weddemann, University of Paderborn

2. Mai 2008, 14:00 Uhr, F1.310

k-Center-Clustering für geometrische Datenströme

Wer kennt das nicht: „Es ist Samstagabend, die Partylust hat nahezu ihren Höchstwert erreicht, doch unglücklicherweise herrscht in der Universitätsstadt Paderborn die Vorherrschaft der schlechten Feiern. Leider liegt die nächste, akzeptable Alternative zur Abendgestaltung mindestens zwei Stunden Autofahrt entfernt“. Hier stellt sich doch die Frage, warum alle guten Discotheken immer so unendlich weit auswärtig liegen müssen.

Veranschaulicht man eine geometrische Punktmenge als Städte eines Landes, wobei die Distanz zwischen Städten die Zeit für den Weg repräsentiert. Nun möchte man k Partylocations errichten, so dass die maximale Anreisezeit minimal ist. Dieses Optimierungsproblem wird formaler als k-Center Clustering bezeichnet.

Im Rahmen dieser Studienarbeit wird die Funktionsweise eines Datenstrom-Algorithmus vorgestellt, der für eine unspeicherbar große Menge von Eingabepunkten eine approximierte Lösung für das NP-harte k-Center-Clustering-Problem bestimmt. Durch das Arbeiten auf einer approximierten Punktemenge, der ursprünglichen Eingabesequenz, wird eine Laufzeit erzielt, die, unter bestimmten Kriterien, nur noch linear von der Anzahl der Eingabepunkte abhängt. Der Schwerpunkt dieses Vortrages zielt vielmehr auf das Verständnis der Arbeitsweise, des vorgestellten Algorithmus, und weniger auf eine detaillierte Analyse.

(Studienarbeit)

Sven Kurras, University of Paderborn

23. April 2008, 14:00 Uhr, F1.110

Die Grafikkarte als Parallelcomputer

Grakkarten nutzen bereits seit geraumer Zeit Parallelverarbeitung zur Durchsatzsteigerung. Zunehmend wurde deren Rechenpower auch für nicht-grasche Probleme genutzt, als Manko blieben aber allzu spezialisierte und kreative Implementierungen. Aktuelle Modelle von Nvidia ermöglichen hingegen mittels CUDA nahezu uneingeschränktes Programmieren in C. Zudem entspricht die Architektur der GPU weitgehend dem Modell einer CRCW-LPRAM. Dementsprechend intensiv wird derzeit über Anwendungsbereiche dieses Parallelcomputers nachgedacht - erstmalig auch seitens der Hersteller, welche mit einem Verbund dieser GPUs den HPC-Markt betreten. Wie also steht es um die praktische Relevanz in nicht-graschen Anwendungen? Durch Implementierung ausgewählter Algorithmen werden Stärken und Schwächen dieses Systems untersucht.

(Abschlussvortrag Studienarbeit)

Tobias Koch, University of Paderborn

23. April 2008, 14:30 Uhr, F1.110

Visibility Culling und mehrstufiges Caching von virtuellen Szenen auf mobilen Geräten

Die Darstellung großer virtueller Szenen verursacht aufgrund des erforderlichen Datenvolumens eine Reihe von Problemen. Einerseits überfordert die Vielzahl von Polygonen schnell die Rechenleistung einer Grafikkarte, andererseits reicht auch der lokale Speicher vieler Rechner nicht aus, um die gesamte Umgebung vorrätig zu halten. In wesentlich deutlicherem Maße trifft dies auch auf mobile Geräte zu.

Im Falle geschlossener Szenen mit eingeschränkter Sichtweite, wie etwa bei Gebäuden, kann beiden Problemen durch die Verwendung von Visibility-Culling-Verfahren begegnet werden. Im Rahmen dieser Diplomarbeit werden hierzu die potenziell sichtbaren Polygonmengen (engl.: Potentially Visible Sets, kurz: PVS) berechnet. Durch die Unterteilung der virtuellen Umgebung in Zellen, deren Grenzen Teile der restlichen Szene verdecken und somit als Occluder fungieren, ist es möglich, sichtbare und unsichtbare Bereiche zu identifizieren. Hiermit kann eine Auswahl der erforderlichen Daten erfolgen und sowohl die darzustellende Polygonanzahl als auch das zu speichernde Datenvolumen mitunter drastisch reduziert werden.

Vorgestellt wird ein Verfahren, um das erforderliche Transfervolumen bei einer Bewegung durch eine im Netzwerk gespeicherte Szene zu verringern. Untersucht und bewertet werden verschiedene Prefetching- und Caching-Strategien, welche die Daten im eingeschränkten lokalen Speicher verwalten. Die Ergebnisse geben Aufschluss über die erforderlichen Bandbreiten, Prefetching-Zeitpunkte sowie Verdrängungsalgorithmen, um eine möglichst fehlerfreie Darstellung der virtuellen Umgebung zu erlauben.

(Abschlussvortrag Diplomarbeit)

Alexander Spot, University of Paderborn

16. April 2008, 14:00 Uhr, F1.110

Analyse von Algorithmen zur ganzzahligen Polynomauswertung

Mittels Bshoutys Algorithmus ist die Auswertung von ganzzahligen Polynomen so möglich, dass die dafür aufgewandten arithmetischen Operationen sich in konstanter Zeit durchführen lassen. Dabei spielt es keine Rolle wie gross die in den einzelnen Zwischenschritten erzeugten Ergebnisse werden. Das ist aber mit den heutigen Rechner nicht umsetzbar. Denn dort steht nur eine beschränkte Rechengenauigkeit zur Verfügung. Das führt zur der Fragestellung, die in dieser Studienarbeit beantwortet wird: Ist Bshoutys Algorithmus mittlerweile praktikabel einsetzbar? Die Beantwortung dieser Frage erfolgt durch Vergleich mit anderen Verfahren zur Auswertung von ganzzahligen Polynomen, konkret: Bshoutys Algorithmus, Horner Schemata, Look-Up Tabellen.

(Abschlussvortrag Studienarbeit)