Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V

Parallele Systeme und Algorithmen, Approximationsalgorithmen und ihre Anwendungen

Prof. Dr. Marek Karpinski

Schwerpunkte in Forschung und Lehre

  • Schnelle parallele und randomisierte Algorithmen
  • Parallele und verteilte Systeme, On-Line Algorithmen
  • Algorithmische Geometrie und VC Dimension
  • Approximationsalgorithmen für NP-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.

Effiziente parallele Algorithmen und Berechnungskomplexität

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.

Algorithmische Geometrie und Integer Programming

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 für harte Berechnungsprobleme

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 NP-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.

Randomisierte Branching Programme in CAD Design und Hardware / Sofware Verifikation

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.

Fehlerresistente Übertragungssysteme

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.

Computeralgebra Implementierungsgruppe

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 Interpolationsalgorithmen, 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.

Links zu anderen Forschungsgruppen und Projekten

Last Change: 09/27/99 at 09:10:19
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope