This page has moved to
You are being re-directed in 3 seconds...

Diese Seite ist umgezogen nach
Sie werden in 3 Sekunden weitergeleitet...


UNIDepartment of Mathematics and Computer ScienceUniversity of Paderborn

Algorithms and Complexity


back to HNI:
  Working Groups


Butterfly networks, such as the one above (left), constitute one of the most important topologies for inter process communication. We are indebted to Gitta Haverkamp for the 2D graphical representation (middle), taken from Alf Wachsmann's PhD thesis. We are indebted to Marcus Werner for the 3D-model representation (right).

High computing performance can only be achieved by a combination of powerful computer systems and algorithms that solve the given application problems as efficiently as possible. Therefore, the development of efficient algorithms has established itself as a classical branch of computer science. In our research area, we concentrate on solutions where current technological possibilities such as computer networks used as high-performance computers pose new challenges for algorithm development.

Parallel computer networks can potentially supply unlimited computing power. However, the efficient use of these networks is an extremely complex problem. We provide users with a programming environment that is easy to handle and guides them towards the development of efficient algorithms. In order to support such environments, efficient implementations of basic routing for communication and syncronisation are is needed. Our research on bridging models, which leads to theoretical evaluation and development of a BSP-like programming framework, and our PUB-library, constitute a valuable contribution to this area. Moreover, our work on data management in networks leads to provably efficient techniques. We implement and test these techniques in the DIVA-library and integrate them in the development of a distributed multimedia server.

To be able to navigate in a virtual 3-dimensional space, and to give a realistic optical impression of the changing scene, enormous demands are imposed on the underlying data structures that handle the scene. Above all, we have to guarantee real time processing that can handle approximately twenty frames per second. Our work on the development of such new types of data structures are incorporated into our prototype walk-through system PaRSIWal.

The algorithmic work described above has shown us that using randomized procedures can produce amazing gains in efficiency. We are therefore systematically studying the potential of randomized algorithms and using, or developing, probability theory for analysing such algorithms.

Our research is closely linked to our teaching. Our courses deal with methods and concepts of the development and analysis of efficient algorithms. We also run project groups and support diploma thesis that apply our theoretical insights in order to design efficient algorithms and libraries of basic routines.