|
- Leiter:
-
Prof. Dr. Marek Karpinski
Parallele Systeme und Algorithmen,
Approximationsalgorithmen und ihre Anwendungen
Email: karpinski@cs.uni-bonn.de
- Sekretariat:
-
Christine Marikar
Tel.: 0228/73-4327
Fax: 0228/73-4440
Email: secret5@cs.uni-bonn.de
Raum: N 316
- Professoren:
-
Prof. Dr. Michael Clausen
Kommunikationssysteme und Algorithmen
Email: clausen@cs.uni-bonn.de
Prof. Dr. Thomas Lengauer
Diskrete Algorithmen und ihre Anwendung
Email: lengauer@cs.uni-bonn.de
- Wissenschaftliche Mitarbeiter:
-
Priv.-Doz. Dr. Elias Dahlhaus
Dr. Carsten Dorgerloh
Dipl.-Inform. Dipl.-Math. Heiko Goeman
Dipl.-Inform. Christoph Günzel
Dr. Patrick Hamilton
Dipl.-Inform. Frank Kurth
Dipl.-Inform. Dirk Meyer
Dipl.-Inform. Yakov Nekritch
Dr. Amin Shokrollahi (beurlaubt)
Dr. Jürgen Wirtgen
- Technische Angestellte:
-
Ignatios Souvatzis
Leszek Paszkiet
- DAAD-Stipendiatin:
-
Dipl.-Ing. Vlora Arifi
- Forschungsgruppe:
-
- Leiter:
-
Prof. Dr. Thomas Lengauer, Ph.D.
Diskrete Algorithmen und ihre Anwendung
Tel.: 0228/73-4218/-4712 und
02241/14-2776/-2777
Fax: 02241/14-2656
- Wissenschaftliche Mitarbeiter:
-
Dipl.-Inform. Oliver Eulenstein
Dipl.-Inform. Mike Schäfer
(M. Karpinski)
- Schnelle parallele und randomisierte Algorithmen
- Parallele und verteilte Systeme, On-Line Algorithmen
- Algorithmische Geometrie und VC Dimension
- Approximationsalgorithmen für
 -harte
kombinatorische Optimierungsprobleme und Anwendungen - Berechnungskomplexität, Boolesche Schaltkreise, Branching
Programme und VLSI-Entwurf
- Kodierungs- und Dekodierungsalgorithmen für fehlerresistente ATM
Systeme
Die Forschungsvorhaben erfolgen in drei Arbeitsgruppen: Effiziente
parallele Algorithmen und Berechnungskomplexität,
Approximationsalgorithmen für harte Berechnungsprobleme und
Fehlerresistente Übertragungssysteme.
Diese Gruppe beschäftigt sich mit grundsätzlichen Fragen des Entwurfs
paralleler Algorithmen, Organisation von Parallelrechnern und
verteilten Systemen sowie mit dabei entstehenden
Kommunikationsproblemen. Man hat auch grundsätzliche Probleme der
Randomisierung (Zufallssteuerung) als Berechnungsressource untersucht.
Für einige wichtige Berechnungsprobleme erscheinen heutzutage
randomisierte bzw. pseudo-randomisierte Algorithmen effizienter als
deterministische Algorithmen in Bezug auf Laufzeit, Hardware-Größe,
Schaltkreistiefe usw. Hier hat man in letzter Zeit wesentliche
Fortschritte erzielt sowohl im Entwurf effizienter paralleler
Algorithmen für grundlegende Probleme als auch in dem Verständnis der
grundlegenden Komplexität der Optimierungsprobleme, wie z.
B. Integer Programming und Knapsack.
Man hat auch weitere Untersuchungen von parallelen Algorithmen für
grundlegende algebraische und geometrische Probleme und verschiedenen
Anwendungen solcher Algorithmen in Bezug auf kombinatorische
Optimierungsfragen durchgeführt. Man hatte des weiteren untere
Schranken für parallele RAM-Maschinen und algebraische
Entscheidungsbäume untersucht.
In den vergangenen Jahren wurden mehere Probleme der Algorithmischen
Geometrie studiert, die mit der Berechnungskomplexität der
eingeschränkten Integer Programme und der Programme höhern
Grades (s.g. Smooth Programs) eng verknüpft waren.
Man hatte die hier ereichten Resultate im Entwurf der effizienten
Approximationsalgorithmen für ausgewählte Optimierungsprobleme
angewendet. Man hat hier neue obere und untere randomisierte Schranken
erziehlt. Man hat auch vor kurzem das Problem der s.g. VC
Dimension der sigmoidalen und Pfaffschen neuronalen Netzwerke gelöst,
das seit einigen Jahren offen war.
Approximationsalgorithmen bieten oft eine praktische Möglichkeit, mit
besonders schweren Berechnungsproblemen effizient umzugehen. Seit
Anfang der neunziger Jahre ist ein rasanter Fortschritt im Entwurf
effizienter Approximationsalgorithmen für kombinatorische
Optimierungsprobleme und in unserem Verständnis der
Approximationshärtephenomenen der Berechnungsprobleme zu verzeichnen.
Man hat in unserer Gruppe wesentliche Fortschritte im Entwurf von
effizienten Approximationsalgorithmen für harte algebraische und
kombinatorische Optimierungs- und Zählprobleme erzielt, die teilweise
die Lösung der lange Zeit offenen Probleme darstellen. Man hatte
u.a. auch den heutzutage besten Approximationsalgorithmus
für Steiner Tree Probleme entwickelt, der eine große Anzahl von
Anwendungen hat.
Des weiteren wurden die ersten Polynomialzeit Approximationsschemata
für -harte dichte Instanzen von Optimierungsproblemen,
wie z.B. MAX-CUT, SEPARATOR and BISECTION konstruiert. Es
wurden auch on-line Approximationsalgorithmen für Load Balancing und
Job Scheduling Probleme untersucht. Man versucht z.Z. eine
Programmierungsplattform und Softwarebibliotheken zu erstellen, um
konstruierte Algorithmen praktisch in verschiedenen Implementationen
auf Effizienz zu untersuchen.
Verschiedene Anwendungen unserer Algorithmen wurden angegangen,
u.a. im Schaltkreis- und VLSI-Entwurf, praktischen Computer
Scheduling Problemen, Network Design, neuronalen Netzwerken und
molekularer Biologie.
Ziel dieser Forschung ist der Entwurf von effizienten
Verifikationsverfahren, die auf s.g. randomisierten
geordneten read-once branching Programmen (OBDDs)
basieren. Hier hat man wesentliche Fortschritte erziehlt im Entwurf
erster effizienter Verifikationsverfahren für viele grundlegende
Funktionen und Probleme, wie z.B. für Multiplikations-,
Inversions- und Divisionsschaltkreise und für verschiedene
nichtlineare Optimierungsprogramme. Man untersucht Anwendungen dieser
randomisierten branching Programme im Bereich der formalen Verifikation
von VLSI-Schaltkreisen in CAD (Computer-Aided Design) und Verifikation
der allgemeinen Programme.
Ziel dieser Forschung ist der Entwurf und die Analyse der effizienten
Kodierungs- und Dekodierungsalgorithmen für multimediale
Erasure-Resistente ATM-basierte Übertragungssysteme. Erste
solche Algorithmen, die auf der Invertierung von Cauchy Matrizen
basieren, wurden 1995 in Zusammenarbeit mit Forschungsinstituten in
Berkeley entwickelt. Unser Ziel ist es, schnellere Erasure Codes zu
konstruieren mit annähernd Echtzeit Kodierungs- und
Dekodierungslaufzeiten, die notwendig für die nächste Generation der
ATM-basierten Übertragungssysteme sind. Die Methoden basieren auf
algebraischen Ansätzen schneller Invertierung bestimmter Matrizen
über kleinen endlichen Körpern und zielen auf Entwürfe von
Linearzeit MDS-Codes ab.
Es wurden mehrere Implementationen in Computer-Algebra Systemen
durchgeführt, ausgehend von etwas älteren Implementationen in
Scratchpad II und AXIOM Systemen. Das Ziel dieser Arbeitsgruppe ist
die Unterstützung der Forschungsarbeiten in Bereichen der
Optimierungsverfahren, parallelen Algorithmen und algorithmischen
Lerntheorie. Im Vordergrund standen hierbei effiziente algebraische
Interpolationsalgrithmen, effiziente approximative Zählalgorithmen und
Lernalgorithmen für Boolesche Funktionen, Entscheidungsbäume und
Polynome über kleinen endlichen Körpern.
Die obengenannten Forschungsaktivitäten wurden unterstützt durch die
Deutsche Forschungsgemeinschaft, Volkswagen-Stiftung, DAAD,
Max-Planck-Forschungspreis (Karpinski), National Science Foundations
(USA), IBM und ESPRIT BR.
Weitere Informationen über die beschriebenen Forschungsaktivitäten
sind elektronisch unter folgender URL-Adresse verfügbar:
http://theory.cs.uni-bonn.de/.
(M. Clausen)
- Audio-Kommunikation
- Daten-Kommunikation
Die theoretische Basis unserer aktuellen Forschungstätigkeit spiegelt
sich wider in den drei Buchprojekten Fast Fourier Transforms
(Clausen / Baum, BI 1993), Coding Theory and Bilinear Complexity
(Shokranian / Shokrollahi, Scientific Series Vol. 21, 1993) und
Algebraic Complexity Theory (Bürgisser / Clausen / Shokrollahi,
Grundlehren der mathematischen Wissenschaften Vol. 315, Springer
1997). Vor diesem Hintergrund beschäftigt sich unsere Arbeitsgruppe
mit dem Entwurf von Systemen und effizienten Algorithmen zur
Kommunikation. Einen Schwerpunkt bilden hierbei Systeme, die dem
Audio-Bereich zuzuordnen sind. Während es sich hier um die
Kommunikation mit hochstrukturierten Daten handelt, geht ein zweiter
Schwerpunkt auf codierungstheoretische Probleme bei der Kommunikation
beliebiger Daten ein.
In der Lehre spiegelt sich dies im Angebot der Kern- und
Grundvorlesungen Audiosignalverarbeitung I & II,
Computeralgebra I & II sowie in vertiefenden Spezialvorlesungen
zu diesen Gebieten wider. Dabei liegt der Schwerpunkt in den kommenden
Semestern auf Spezialvorlesungen aus der Audiosignalverarbeitung. Das
Vorlesungsangebot wird durch Seminare in Grund- und Hauptstudium sowie
durch Praktika und Projektgruppen abgerundet. Hierbei haben die
Projektgruppen einen besonderen Stellenwert, da sie, bei
zweisemestriger Laufzeit, ein intensives und kontinuierliches Arbeiten
an gegebenen Projekten ermöglichen und so z.B. einen guten
Einstieg in Richtung Diplomarbeit liefern. In Projektgruppen kann
außerdem, bei zweisemestriger Teilnahme, sowohl ein Seminar- als auch
ein Praktikumsschein erworben werden. Momentan in unserer
Arbeitsgruppe angeboten werden die Projektgruppen Digitale
Musikbibliotheken und Audiosignalverarbeitung.
Die Audiosignalverarbeitung beschäftigt sich mit der Speicherung und
Verarbeitung digitaler Musik- und Sprachsignale. Steigende
Anforderungen an Effizienz, Qualität und Kapazität im Zuge
fortschreitender Multimedialisierung gewichten in immer stärkerem
Maße die Informatikkomponente dieses interdisziplinären Gebietes.
Die Schwerpunktthemen innerhalb unserer Arbeitsgruppe, die sich
teilweise aus Industriekooperationen ergeben, sind der Entwurf von
Datenstrukturen und effizienten Algorithmen zur Kompression und zum
Denoising von Audio- und Breitbandsprachsignalen. Neben klassischen
Verfahren wie schnellen Fourier- und Wavelettransformationen entwickeln
wir unter Einbeziehung psychoakustischer Modelle neue flexible Methoden
zur adaptiven Signalanalyse. Dabei werden zeitkritische Algorithmen
auf digitalen Signalprozessoren realisiert.
Im Rahmen unseres MiDiLiB-Projekts behandeln wir Verfahren zur robusten
Editierung komprimiert archivierter Daten. Da in modernen digitalen
Bibliotheken Daten verstärkt in komprimierter Form abgelegt werden,
sind dadurch auftretende Seiteneffekte, wie z.B. digitale
Generationseffekte, zu beachten und Verfahren zu deren Vermeidung zu
realisieren. Innerhalb der Projektarbeit werden die entwickelten
Verfahren sowohl an state-of-the-art Codern (z.
B. MPEG-Audio) als auch an Neuentwicklungen getestet.
Digitalisierung und weltweite Vernetzung haben zu einer Flut von Daten
höchst unterschiedlichen Inhalts und Formats geführt, die es durch
gezielte multimediale Techniken sinnvoll zu nutzen gilt. Während für
rein textuelle Dokumente in diesem Zusammenhang schon eine Reihe von
Methoden zu Indexierung, Browsing und Retrieval entwickelt wurden,
steht man bei multimedialen Dokumenten hier noch vor vielen ungelösten
Problemen. Vor diesem Hintergrund beteiligt sich unsere Arbeitsgruppe
mit dem MiDiLiB-Projekt am DFG-Schwerpunktprogramm Verteilte
Verarbeitung und Vermittlung digitaler Dokumente. In unserem Projekt
sollen, unter Berücksichtigung musikwissenschaftlicher Erkenntnisse,
Verfahren zu inhaltsbasierter Indexierung, Retrieval und Kompression
von Audiodaten in digitalen Musikbibliotheken entwickelt werden.
Während Visualisierung und Animation weitverbreitete Konzepte zur
Informationsvermittlung und -darstellung sind, hat die Sonifikation als
akustisches Informationskonzept erst in jüngster Zeit verstärkt
Beachtung gefunden. In Kooperation mit dem Sportwissenschaftlichen
Institut der Universität Bonn wurde von unserer Arbeitsgruppe ein
System zur Umsetzung kinematischer und dynamischer Bewegungsdaten in
Höreindrücke entwickelt. Dieses System zur akustischen
Bewegungstransformation wird von den Sportwissenschaftlern in der
Motorikforschung eingesetzt.
Bei der Übertragung von Nachrichten über gestörte oder überlastete
Kanäle (Telefonleitungen, Satellitenkommunikation, CD, Internet)
werden Codierungsverfahren zur Fehlerkorrektur verwendet. Herr
Shokrollahi hat in Kooperation mit amerikanischen Kollegen unter
anderem effiziente Codier- und Decodierverfahren zur Behebung von
Paketverlusten in Hochgeschwindigkeitsnetzen (wie z.B. dem
Internet) entwickelt.
Weitere Informationen sind auch elektronisch verfügbar über das
MiDiLiB-Projekt unter http://grieg.cs.uni-bonn.de/ und über die
Abteilungs-Homepage http://theory.cs.uni-bonn.de/.
(Th. Lengauer)
- Molekulare Bioinformatik
- Computergestützte Chemie.
- Diskrete Optimierungsmethoden in Naturwissenschaft und Technik
Die Bearbeitung der Forschungsvorhaben erfolgt in Arbeitsgruppen, die
sowohl an der GMD - Forschungszentrum Informationstechnik GmbH als
auch an der Universität Bonn plaziert sind.
Die dreidimensionale Struktur von Proteinen bildet die Grundlage für
ihre chemische Funktion. Daher ist die Vorhersage
dreidimensionaler Proteinstrukturen auf der Basis der
Aminosäuresequenz des Proteins eine wesentliche Komponente eines
effektiven rechnergestützten Entwurfs biochemischer Wirkstoffe. In
der Arbeitsgruppe wurde das Programmsystem ToPlign entwiclet, das es
erlaubt, auf der Basis der Kenntnis einer Proteinsequenz mit dem
Verfahren der sogenannten ähnlichkeitsbasierten Modellierung
Modelle für die Proteinstruktur zu entwickeln. Das System wurde an
bereits bekannten Strukturdaten validiert und mehrfach -- auch im
Rahmen internationaler Experimente -- erfolgreich zu sogenannten
Blindvorhersagen, d.h. echten Vorhersagen in Unkenntnis der
Struktur eingesetzt. Die zugrundeliegenden Methoden umfassen sowohl
algorithmische Entwicklungen wie auch die Ableitung neuartiger
Kostenfunktionen zur Bewertung von Proteinmodellen. Ein Teil der
Arbeiten am ToPLign System war die Basis für die Dissertation von Ralf
Thiele. ToPLign ist auf dem WWW verfügbar. Die Arbeiten wurden vom
BMBF gefördert.
Untersuchungen in der Arbeitsgruppe, die auf eine Erweiterung der
homologiebasierten Strukturvorhesagemethoden zielen und mathematische
Methoden aus der Matroid-, Graphen- und Knotentheorie benutzen, wurden
im Rahmen eines DFG Projektes gefördert.
Die Erfahrungen der Forschungsgruppe im Bereich der
Proteinstrukturvorhersage werden zur Zeit in ein vom BMBF gefördertes
Projekt eingebracht, bei dem es darum geht, aus diversen
experimentellen Daten (Expressionskarten für Gene in gesunden und
kranken Geweben) nach Zielproteinen für Krankheitsdiagnose und
-therapie zu kommen.
Der Bindungsprozeß von Liganden an Proteine, der die Grundlage
sämtlicher biochemischer Wechselwirkungen darstellt, wird allgemein
als Docking bezeichnet. In der Arbeitsgruppe wurde das
Programmsystem FlexX entwickelt, mit dem in wenigen Minuten Laufzeit
niedermolekulare Liganden in Bindungstaschen von Proteinen plaziert
werden können. Das Programm ist bei etwa vergleichbaren Ergebnissen
Größenordnungen schneller als andere Dockingprogramme. Es wird zur
Zeit in kooperierenden Industrieunternehmen eingesetzt, ist auf dem WWW
verfügbar und wird international vermarktet. Die Entwicklung von
FlexX war die Basis für die Dissertation von Mathias Rarey. Die
Entwicklung von Dockingmethoden für den Fall, daß die Proteinstruktur
nicht bekannt ist, ist in fortgeschrittener Bearbeitung. Die Arbeiten
werden vom BMBF gefördert.
Im Rahmen der Dissertation von Oliver Eulenstein wurden Algorithmen zur
Findung von Duplikationsereignissen von Genen während der Evolution
entwickelt. Die Auffindung solcher in Genomdaten versteckten
Ereignisse ist eine wesentliche Voraussetzung für eine genaue
Bestimmung der Funktion von Proteinen. Ferner wurde die Äquivalenz
verschiedener in diesem Bereich entwickelter Kostenmaße nachgewiesen.
Die Dissertation von Benno Schwikowski enthält neuartige Algorithmen
zur gleichzeitigen Berechnung multipler Alignment und evolutionärer
Bäume von biologischen Sequenzen. Die Forschungsarbeiten von Benno
Schwikowski und Oliver Eulenstein entstanden im Rahmen einer
Kooperation mit dem DKFZ Heidelberg (Dr. Martin Vingron).
Prof. Lengauer koordiniert den DFG Schwerpunkt Informatikmethoden
zur Analyse und Interpretation großer genomischer Datenmengen, dessen
Förderung im Jahre 1998 beginnt.
Ziel dieser Forschung, die im Rahmen des SFB 408 Anorganische
Festkörper ohne Translationssymmetrie in Zusammenarbeit mit
chemischen und physikalischen Instituten der Universität Bonn sowie
der DLR Porz durchgeführt wird, ist die Analyse der räumlichen
Struktur von anorganischen amorphen Clustern mithilfe von z.
T. diskreten, z.T. numerischen rechnergestützten
Verfahren. Eingabedaten sind a priori Kenntnisse über die amorphen
Systeme sowie Informationen, die aus Spektren verschiedenster Art
gewonnen werden. Es wurde ein Programmsystem entwickelt, das
qualitativ hochwertige Modelle von Clustern aus amorphem Quartz mit bis
zu etwa zweitausend Atomen berechnet. Ferner wurden Algorithmen
entwickelt, mit denen Strukturmodelle erzeugt werden können, die
vorgegebene Statistiken beweisbar genau einhalten.
Bei der Schnittbilderstellung in der lederverarbeitenden
Industrie werden beliebig geformte Schablonen disjunkt auf beliebig
geformten Unterlagen (Tierhäuten) plaziert, wobei die
Verschnittfläche minimiert werden soll. Hinzu kommen diverse
Nebenbedingungen. Forschungen in diesem Bereich führten im Jahre 1994
zu einer Dissertation. Zur Zeit wird das entsprechende Problem auf
Textilien bearbeitet. Es entstand ein Programm, das nicht nur
Schnittbilder mit einer Qualität erzeigt, die der von menschlichen
Legern vergleichbar ist. Es kann auch eine Gütegarantie etwa der Art
,,0,8% schlechter als optimal`` gegeben werden. Manche der gezeigten
Schnittbilder sind sogar beweisbar optimal. Auch dieses System wird
vermarktet. Die Software ist Basis einer Dissertation im Jahre 1997.
Das Projekt wurde und wird zu erheblichen Anteilen von der DFG
gefördert.
In der Automobilindustrie treten komplexe dreidimensionale
Packungsprobleme auf. Gesamtziel ist, die Aggregate innerhalb eines
Fahrzeugs so zu plazieren, daß bei kompakten Außenmaßen
größtmöglicher Komfort für den Fahrgast und hohe
Wartungsfreundlichkeit erzielt wird. Die Lösung solcher Probleme mit
rechnergestützten Optimierungsverfahren steckt heute noch in den
Anfängen. Im Dialog mit einem führenden Automobilhersteller und mit
Förderung vom BMBF entwickeln wir Modelle und Methodiken für diese
Probleme.
Arbeiten zum Layout integrierter Schaltkreise, die im Rahmen
eines DFG Projektes gefördert wurden, resultierten in einem
Softwaresystem, mit dem sich beweisbar gute Verdrahtungen und
Plazierungen integrierter Schaltkreise erzeugen lassen. Die Methodik
basiert auf Versionen der ganzzahligen Programmierung. Das System
berechnet obere und untere Schranken für die Kanaldichte, die sich in
allen praktisch aufgetretenen Fällen um höchstens 2 unterscheiden.
Die Layoutqualität kann für Schaltkreise mit bis zu mehreren
zigtausend Netzen erreicht werden.
Prof. Lengauer koordiniert den DFG Schwerpunkt Effiziente
Algorithmen für diskrete Probleme und ihre Anwendungen, der sich seit
1995 in der Förderung befindet.
Am Institut SCAI werden in der Arbeitsgruppe darüber hinaus die Themen
Anwendung von Petrinetzen, Computer Algebra, Vorhersagen der
Struktur organischer Kristalle und Monte-Carlo und
Molekulardynamikmethoden in der Bioinformatik und rechnergestützten
Chemie bearbeitet. Über alle Forschungsaktivitäten geben gesonderte
Publikationen von SCAI detaillierte Auskunft, siehe auch auf dem WWW
unter http://www.gmd.de/SCAI/.
| 