SPP 731:  Effiziente Algorithmen für diskrete Probleme und ihre Anwendungen

• Fachliche Zuordnung: Informatik, System- und Elektrotechnik
• Förderung: Förderung von 1995 bis 2000
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5465944

Das strategische Ziel dieses Schwerpunktprogramms, das im Jahr 2000 auslief, war es, interessante und neue Methoden, welche die Grundlagenforschung der Informatik und diskreten Mathematik in jüngster Zeit hervorgebracht hat, auf Anwendungen in Wissenschaft und Technologie zu erweitern. Projekte, die in diesem Schwerpunktprogramm gefördert wurden, weiteten die algorithmischeGrundlagenforschung der vergangenen Jahre und Jahrzehnte auf spezifische Anwendungen innerhalb und besonders auch außerhalb der Informatik aus.Die von den Projekten untersuchten Probleme entstammen direkt konkreten Anwendungen, z.B. aus den Bereichen Schaltkreisentwurf, computergestützter Entwurf, Konstruktion und Fertigung, Verkehr, Robotik, Chemie, und Biologie. Die Probleme besitzen einen direkten Bezug zu den zugrunde liegenden Anwendungen. In vielen Faellen wurde die Relevanz für eine konkrete Anwendung durch Kooperation oder Kontakt mit Wissenschaftlern oder Firmen der Anwendungsdisziplin belegt.Die entwickelten Lösungsverfahren basieren auf neuesten Fortschrittenim Bereich der diskreten Algorithmen. Relevante Forschungsthemen sind hier Datenstrukturen, Graphenalgorithmen, algorithmische Geometrie, Computeralgebra, kombinatorische Optimierung, randomisierte Algorithmen, parallele und verteilte Algorithmen und Mustererkennung. Die Lösungsverfahren wurden in den Projekten erweitert und nicht nur angewandt.Die entwickelten Algorithmen wurden durch experimentelle Untersuchungen an realen Eingabedaten und theoretische Analysen validiert.

• DFG-Verfahren: Schwerpunktprogramme
• Internationaler Bezug: Österreich

Projekte

• Algorithmen zur Konstruktion, Klassifikation und Visualisierung hochgeordneter räumlicher Strukturen (Antragsteller Dress, Andreas )
• Algorithmen über omega-Automaten und Anwendungen in der Programmkonstruktion und -verifikation (Antragsteller Thomas, Wolfgang )
• CAD-gerechte Oberflächen- und Volumenrekonstruktion komplexer Objekte aus einer Menge von unstrukturierten Oberflächenpunkten (Antragsteller Brunnett, Guido )
• Design, Analyse, Implementierung, Evaluierung und experimentelle Anwendung von Algorithmen zum Zeichnen von Graphen (Antragstellerin Mutzel, Petra )
• Design, Analyse, Implementierung, Evaluierung und experimentelle Anwendung von Algorithmen zum Zeichnen von Graphen (Antragsteller Jünger, Michael )
• Design, Analyse, Implementierung, Evaluierung und experimentelle Anwendung von Algorithmen zum Zeichnen von Graphen (Antragsteller Näher, Stefan )
• Design, Analyse, Implementierung und experimentelle Anwendungen von Algorithmen zum Zeichnen von Graphen (Antragsteller Brandenburg, Franz Josef )
• Dimensionierung analoger Schaltkreise mit Methoden der Computeralgebra (Antragsteller Greuel, Gert-Martin )
• Effiziente Algorithmen für diskrete und diskretisierte Standortprobleme (Antragsteller Hamacher, Horst W. )
• Effiziente Algorithmen zur formalen Verifikation von VLSI-Designs (Antragsteller Prömel, Hans Jürgen )
• Effiziente Algorithmen zur Logiksynthese und Verifikation bei VLSI-Schaltkreisen (Antragsteller Becker, Bernd )
• Effiziente diskrete Algorithmen zur Flächenrückführung und Flächeneinpassung (Antragsteller Müller, Heinrich )
• Entwicklung, Analyse und experimentelle Erprobung von kompetitiven Algorithmen für die Bahnplanung autonomer Systeme (Antragsteller Klein, Rolf )
• Entwicklung effizienter Algorithmen für die Minimierung von Arbeiterlaufzeiten in Flow-Shop-Fertigungssystemen (Antragsteller Wanke, Egon )
• Entwicklung effizienter algorithmischer Verfahren zur Lösung des zweidimensionalen Plazierungsproblems (sog. Nesting-Problem) unter Berücksichtigung der in der textilverarbeitenden Industrie auftretenden Randbedingungen (Antragsteller Lengauer, Thomas )
• Entwicklung und Implementierung von effizienten parallelen Algorithmen für Molekulardynamik-Simulationen von synthetischen Polymeren (Antragsteller Lenhof, Hans-Peter )
• Entwicklung von Algorithmen für den Vergleich und die Rekonstruktion der evolutionären Zusammenhänge von Gen- und Genomsequenzen (Antragsteller Vingron, Martin )
• Entwurf von Analyse von BDD-basierten Datenstrukturen zur Repräsentation und automatischen Bearbeitung sequentieller Schaltkreise und Systeme (Antragsteller Meinel, Christoph )
• Erzeugung von effizientem Ableitungscode durch Knotenelimination im Berechnungsgraphen (Antragsteller Griewank, Andreas )
• Gekoppelte Auswertealgorithmen zur molekularen Strukturerkennung mit GC/MS (Antragsteller Döhler, Hermann )
• Gekoppelte Auswertealgorithmen zur molekularen Strukturerkennung mit GC/MS (Antragsteller Kerber, Adalbert )
• Graphalgorithmen zur Optimierung von Sendernetzen (Antragsteller Lautemann, Clemens )
• Hierarchische Realzeitalgorithmen: Grundlagen und Walk-trough-Animation (Antragsteller Meyer auf der Heide, Friedhelm )
• Kombinatorische Algorithmen zur Vierecks- und Hexaedernetzgenerierung für Finite-Elemente-Verfahren (Antragsteller Möhring, Rolf H. )
• Kombinatorische Idealisierung des Problems der Proteinfaltung und deren Lösung durch effiziente Algorithmen nach dem Greedy-Prinzip (Antragsteller Lengauer, Thomas )
• Lokalisation und Navigation für reale autonome Roboter in Produktions- und Serviceumgebungen mittels Laserradar (Antragsteller Noltemeier, Hartmut )
• Modellierung paralleler Prozesse mittels algebraischer Methoden (Antragsteller Mayr, Ernst W. )
• Partitionierungsalgorithmen für Modelldatenstrukturen zur parallelen compilergesteuerten Logiksimulation (Antragstellerin Rünger, Gudula )
• Praktikable Algorithmen für Datentransport und andere Basisprobleme auf skalierbaren Architekturen (Antragsteller Kunde, Manfred )
• Reduktion der Teilevielfalt auf der Basis einer geometrisch orientierten Ähnlichkeitssuche (Antragsteller Kriegel, Hans-Peter )
• Robuste Algorithmen zur Auswertung, Rekonstruktion und Visualisierung von graphenbasierten Verkehrsdaten (Antragstellerin Wagner, Dorothea )
• Sequentielle und verteilte Algorithmen zur selektiven Auswertung von Min/Max-Bäumen (Antragsteller Monien, Burkhard )
• Skalierbare Algorithmen für die parallele Bewegungsplanung in dynamischen Umgebungen (Antragsteller Wörn, Heinz )
• Vektororientierte und hybride Verschneidungsalgorithmen für Geoinformationssysteme (Antragsteller Hinrichs, Klaus H. )

• Sprecher: Professor Dr. Thomas Lengauer