[ Universität Bonn | Informatik | Abteilung V | english version ]

Algorithmen (Prof. M. Karpinski)

Randomisierte und approximative Algorithmen:

In diesem Bereich beschäftigt sich Professor Karpinski mit grundsätzlichen Fragen der Berechnungskomplexität, des Entwurfs approximativer Algorithmen, der Organisation von parallelen und verteilten Systemen sowie mit dabei entstehenden Kommunikationsproblemen. 

Professor Karpinski beschäftigt sich auch mit grundsätzlichen Problemen der Randomisierung (Zufallssteuerung) als Berechnungsressource. 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, z.B. im Entwurf von effizienten Approximationsalgorithmen für verschiedene kombinatorische und algebraische Zähl- und Optimierungsprobleme. Lösungen zu solchen Problemen haben einen breiten Anwendungsbereich, der von Algorithmen über Schaltkreisentwurf und Codierungstheorie bis hin zur statistischen Mechanik und Quantentheorie reicht.

Die einzelnen Forschungsthemen sind:

• Entwurf effizienter Algorithmen
• Berechnungskomplexität
• Randomisierte und approximative Algorithmen
• Parallele und verteilte Computerarchitekturen
• Schaltkreis-Theorie
  
• VLSI-Design und Algorithmen
  
• Internet Algorithmen
  
• Kombinatorische Optimierung
• Effiziente Approximationsalgorithmen
  
• Algorithmen in Molekularer Bioinformatik
• Algorithmische Lerntheorie
  

Hinweis: Sollten Sie Fehler bemerken, wenden Sie sich bitte per Email an:  webmaster@theory.cs.uni-bonn.de

Letzte Änderung: 25.08.2003

[ Universität Bonn | Informatik | Abteilung V | english version ]