|
|
|
TU München
Der Lehrstuhl für Effiziente Algorithmen der Fakultät für Informatik
der Technischen Universität München wurde im Frühjahr 1993 erstmalig
besetzt
und beschäftigt derzeit ca. 20 Mitarbeiter. Die an diesem Lehrstuhl
betriebene Forschung umfaßt 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 sich der Lehrstuhl mit algorithmischen Aspekten der folgenden Gebiete:
Graphentheorie
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.
Randomisierte Algorithmen und Probabilistische Methoden
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.
Computeralgebra
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.).
Petri-Netze
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).
Scheduling
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.
Bioinformatik
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.
Komplexitätstheorie
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.
Algorithmenanimation
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.
Erstellung und Verwaltung von Literaturdatenbanken
Quellenangaben in wissenschaftlichen Publikationen sollten in
einheitlicher Weise und internationalen Standards genügend erfolgen.
Dies in der akademischen Praxis (und darüber hinaus) umzusetzen, ist
mitunter recht mühsam, weil einerseits eine große Anzahl an Regeln zu
beachten ist und andererseits nicht jederzeit alle notwendigen
Informationen verfügbar sind. Zur Vereinfachung gibt es am Lehrstuhl
für Effiziente Algorithmen seit über 15 Jahren die bibliographische
Datenbank LEABiB. In ihr sind etwa 72.000 Literaturangaben zur
Theoretischen Informatik als BibTeX-Einträge referenziert und über das
WWW abrufbar. Datensammlungen dieser Größenordnung konsistent und
aktuell zu halten, ist jedoch sehr zeitaufwendig.
Der Lehrstuhl beschäftigt sich daher mit Algorithmen zur
Datenerfassung, Datenkonvertierung und Steigerung der Datenqualität für
Literaturdatenbanken.
|
|
|
|
