Forschungsschwerpunkte

Die an diesem Lehrstuhl betriebene Forschung umfasst die Entwicklung effizienter Algorithmen sowohl im Bereich der sequentiellen wie auch der parallelen Programmierung, insbesondere für kombinatorische oder graphentheoretisch ausgerichtete Problemstellungen. Eine weitere, wichtige Komponente der Forschung ist die Komplexitätsanalyse von Problemen und Verfahren. Sie beinhaltet zum einen die Bestimmung oberer Schranken, d.h. die Abschätzung des Ressourcenbedarfs bekannter oder neu entwickelter Algorithmen, zum anderen aber auch die Herleitung unterer Schranken, die es erlauben, die inhärente Schwierigkeit eines Problems anzugeben oder die Eignung (Effizienz) gewisser Verfahren abzugrenzen.

Insbesondere beschäftigt(e) sich der Lehrstuhl mit algorithmischen Aspekten der folgenden Gebiete (Prof. Ernst W. Mayr ist seit Oktober 2015 im Ruhestand):

• Graphentheorie
• Randomisierte Algorithmen und Probabilistische Methoden
• Computeralgebra
• Petri-Netze
• Scheduling
• Bioinformatik
• Komplexitätstheorie
• Algorithmenanimation

Die Graphentheorie ist ein Teilgebiet der diskreten Mathematik, das eine sehr wichtige und weit verbreitete Rolle in der Informatik sowohl bei der Modellierung von Problemen als auch beim Entwurf und der Analyse von Algorithmen spielt. So führen zum Beispiel Probleme, die bei der Frequenzzuweisung im Bereich der Mobiltelefone auftreten, zu Färbungsproblemen von Graphen. Dabei werden häufig die Frequenzen als Farben und die Sendemasten als Knoten eines Graphen dargestellt. Im Bereich der Parallelrechnung werden sowohl Algorithmen als auch Netztopologien von massiv parallelen Rechnern mit Hilfe von Graphen modelliert. Mit Hilfe von Grapheinbettungen lassen sich Zuweisungen der einzelnen Prozesse auf die Prozessoren des Parallelrechners finden. Eine hohe Güte dieser Grapheinbettungen liefert eine Reduzierung des Kommunikationsoverheads bei gleichzeitiger guter Lastbalancierung und erlaubt somit eine effiziente Ausführung des Programms auf der vorgegebenen Rechnertopologie. Sowohl zur besseren Visualisierung (siehe auch Algorithmenanimation) als zur Erkennung von charakteristischer Eigenschaften von durch Graphen modellierter Zusammenhänge ist das Erkennen von Grobstrukturen in großen Graphen ein wichtiges Hilfsmittel. Hierbei ist man z.B. an einer algorithmischen und effizienten Erkennung von Clustern interessiert.

Ansprechpartner: Prof. Ernst W. Mayr, Hanjo Täubig.

Die Verwendung probabilistischer Methoden zur Analyse diskreter Strukturen geht auf Arbeiten des ungarischen Mathematikers Paul Erdös Ende der 40er Jahre zurück, in denen er Probleme der extremalen Kombinatorik und Graphentheorie behandelte. Eng verwoben mit der Entwicklung der probabilistischen Methode ist die Theorie der zufälligen Graphen, die einige Jahre später ebenfalls von Erdös, diesmal zusammen mit dem Wahrscheinlichkeitstheoretiker Alfred Renyi, eingeführt wurde. Erste Ansätze probabilistische Methoden auch in die theoretischen Informatik einzubringen gab es bereits Ende der 70er Jahre. So stammen bspw. die mittlerweile klassischen Primzahltests von Solovay und Strassen sowie von Rabin aus dieser Zeit. Heutzutage sind probabilistische Ansätze und Methoden aus vielen Bereichen der theoretischen Informatik nicht mehr wegzudenken. Für viele Probleme wurden in den letzten Jahren effiziente randomisierte Algorithmen gefunden, die deterministischen Verfahren in Bezug auf Laufzeit und/oder benötigte Hardwareressourcen weit überlegen sind. Oft sind randomisierte Algorithmen zudem auch viel einfacher zu analysieren und zu implementieren. Wir beschäftigen uns zur Zeit sowohl mit dem Entwurf und der Analyse randomisierter Algorithmen (z.B. für Scheduling-Probleme) als auch mit Existenzaussagen für verschiedene Eigenschaften, die zufällige Graphen einer gegebenen Graphklasse fast sicher besitzen.

Ansprechpartner: Prof. Ernst W. Mayr

Computeralgebra ist ein verhältnismäßig junges Gebiet, das zwischen Mathematik und Informatik angesiedelt ist. Die zentrale Aufgabe besteht in der Entwicklung von Algorithmen für algebraische Probleme. Der Lehrstuhl untersucht spezielle Strukturen, die aus Polynomen aufgebaut sind (so genannte Polynomideale). Das Studium solcher Objekte ist nicht nur von theoretischem Interesse, vielmehr finden die auf diesem Gebiet erzielten Ergebnisse Anwendung bei der Lösung einer ganzer Reihe von praktischen Problemen (Robotersteuerung, (nicht-)lineare Optimierung, Lösung von Differentialgleichungen, usw.).

Ansprechpartner: Prof. Ernst W. Mayr, Stephan Ritscher, Sandeep Sadanandan.

Petrinetze und ihre zahlreichen Varianten sind ein sehr erfolgreiches Modell zur Beschreibung paralleler und verteilter, konkurrierender Prozesse. Bei der algorithmischen Behandlung grundlegender Probleme für Petrinetze (z.B. Endlichkeitsproblem, Lebendigkeit, Erreichbarkeit, Fairness usw.) ergeben sich oft so große Komplexitäten, dass die Methoden praktisch nicht mehr brauchbar sind. Auch hier geht es daher darum, sich zunächst auf Teilproblemklassen einzuschränken und dort zu versuchen, effiziente Lösungsmethoden zu finden. Dies ist auch schon in zahlreichen Fällen geglückt, jedoch sind die zugehörigen Teilklassen von Petri-Netzen vom praktischen Standpunkt her zu beschränkt. Ein Bereich, der vielleicht wesentlich dazu beitragen kann, die Komplexitätsfrage in manchen Bereichen besser in den Griff zu bekommen, sind semilineare Mengen (die genau den Mengen von Tupeln natürlicher Zahlen entsprechen, die durch die Presburger Arithmetik beschreibbar sind). Aus diesem Grunde werden am Lehrstuhl eine Reihe von Fragestellungen untersucht, die mit der Beschreibung der Erreichbarkeitsmengen reversibler Petrinetze (oder, dazu äquivalent, dem Wortproblem bei endlich dargestellten kommutativen Halbgruppen) zusammenhängen. Diese Strukturen haben in mehreren Bereichen der Informatik eine zentrale Bedeutung, z.B. bei den Formalen Sprachen, bei Ableitungssystemen, in der Algebraischen Geometrie, bei Petrinetzen und bei den so genannten Polynomidealen (siehe auch Computeralgebra).

Ansprechpartner: Prof. Ernst W. Mayr.

Scheduling ist die Zuordnung so genannter Tasks auf eine parallele Maschine, so dass diese möglichst optimal ausgenutzt wird. Dies kann sowohl das Verteilen von verschiedenen Prozessen auf die Prozessoren eines Parallelrechners als auch die Anordnung einer gewöhnlichen Fertigungsstraße in der Industrie sein. Dabei sollen gegebene Nebenbedingung strikt oder zumindest weitgehend eingehalten werden, wie z.B. die zeitliche Reihenfolge gewisser Abläufe oder die Nichtgleichzeitigkeit verschiedener Tasks. Der Lehrstuhl befasst sich insbesondere mit stochastischem und online-Scheduling. Im Gegensatz zum gewöhnlichen Scheduling ist hierbei die vollständige Information über die einzelnen Tasks nicht von vornherein bekannt. Bestenfalls sind stochastische Verteilungen über das Auftreten der Tasks und deren Attribute vorhanden.

Ansprechpartner: Prof. Ernst W. Mayr, Hanjo Täubig.

Die Bioinformatik ist eine sehr junge und stark prosperierende Wissenschaft, die zwischen Informatik, Mathematik und Biologie angesiedelt ist. Die nicht zuletzt durch das Human Genome Project ausgelöste enorme Datenflut im Bereich der Biologie kann nur noch unter Zuhilfenahme von Rechnern beherrscht werden. Insbesondere sind Algorithmen zur Strukturvorhersage (wie von Proteinen oder der Sekundärstruktur von RNS) sowie zur Erkennung struktureller Ähnlichkeiten biologischer Daten aller Art von zentraler Bedeutung. Der Lehrstuhl beschäftigt sich insbesondere mit dem algorithmischen Aspekt der Bioinformatik.

Ansprechpartner: Prof. Ernst W. Mayr, Johannes Krugel, Arno Buchner, Hanjo Täubig.

Die Komplexitätstheorie versucht, Probleme qualitativ und quantitativ nach ihrer Lösbarkeit einzuordnen. Neben der fundamentalen Frage, ob ein Problem überhaupt algorithmisch lösbar ist, ist insbesondere die Frage von Bedeutung, ob sich ein Problem algorithmisch mit beschränkten Ressourcen lösen lässt. Bei der Ressourcenbeschränkung werden hauptsächlich Zeit- und Platzbeschränkungen betrachtet, die für die Praxis von besonderem Interesse sind. Der Lehrstuhl beschäftigt sich z.B. mit der Komplexität Boolescher Funktionen und von Modellen für parallele und verteilte Berechnung.

Ansprechpartner: Prof. Ernst W. Mayr.

Die Animation von Algorithmenabläufen ist aus zweierlei Sichtweisen bedeutend. Zum einen hilft die Visualisierung von abstrakten Algorithmen für das tiefere Verständnis dieser und ist daher insbesondere auch aus didaktischer Sicht von Interesse. Zum anderen hilft die Animation sowohl bei der Analyse der Algorithmen als auch bei Verbesserung existierender Algorithmen, da das Studium konkreter Abläufe bessere Einblicke in das Verhalten der Algorithmen liefern kann. Am Lehrstuhl beschäftigt man sich insbesondere mit der Animation von Graphalgorithmen, Schedulingalgorithmen und der Visualisierung von fundamentalen Datenstrukturen. Hierzu werden auch verschiedene Praktika angeboten.

Ansprechpartner: Prof. Ernst W. Mayr.