idw – Informationsdienst Wissenschaft
Nachrichten, Termine, Experten
Nachrichten, Termine, Experten
Effiziente Algorithmen in Wirtschaft und Technologie - Industrietag zum Abschluss des nationalen DFG-Schwerpunktprogramms
am 27. November 2000 (von 9.30 bis 21.30 Uhr)
in der Universität Karlsruhe, Allgemeines Verfügungsgebäude (Gebäude-Nr. 50.41), Adenauerring 20
Tischvorlage zum Pressegespräch
Ohne die Unterstützung durch effiziente Algorithmen wären hochkomplexe Steuerungssysteme nicht realisierbar, wie sie zum Beispiel im Verkehr, bei der Telekommunikation, in Robotik und Fertigung, bei der Planung von Produktions-prozessen, im Schaltkreisentwurf oder Computer-Aided Design (CAD) auftreten. Ein Algorithmus ist eine Rechenvorschrift, z.B. zur Optimierung industrieller Entwürfe. Qualitätsmerkmale von Algorithmen sind die Güte des von ihnen berechneten Ergebnisses - z.B. ein möglichst kleiner Luftwiderstand einer Autokarrosserie - und ihre Schnelligkeit (Effizienz). Während sich die Schnelligkeit von Rechnern in den letzten zwanzig Jahren mehrere tausendfach erhöhte, stieg die Effizienz zentraler Algorithmen in dieser Zeit millionenfach. Schnelle Algorithmen sind also ein Kern des informationstechnischen Fortschritts.
Sechs Jahre lang haben Wissenschaftler mehrerer Universitäten und Forschungszentren in ganz Deutschland - Informatiker, Mathematiker und Ingenieure - zu dem Thema "Effiziente Algorithmen für diskrete Probleme und ihren Anwendungen'' gearbeitet und interdisziplinäre Lösungsansätze gefunden. Das Ziel war dabei, die vielfältigen Methoden und Ergebnisse aus der Grundlagenforschung in Informatik und Angewandter Mathematik praktischen Anwendungen in Wirtschaft und Technologie zugänglich zu machen. Die Deutsche Forschungsgemeinschaft (DFG) förderte die Forschungen in einem nationalen Schwerpunktprogramms.
Die im Schwerpunktprogramm geförderten Forschungsvorhaben behandelten sogenannte diskrete Probleme. Unter diesem Begriff fasst man Probleme zusammen, die mithilfe mathematischer Strukturen modelliert werden können, welche auf endlichen und abzählbaren Mengen - und hier insbesondere den ganzen Zahlen - basieren. Modellierungen von Problemen mithilfe reeller Zahlen gelten nicht als diskret. Die Konstruktion effizienter Algorithmen für diskrete Problemmodellierungen spielen in vielen Bereichen der angewandten Informatik eine zentrale Rolle. Die Klasse der diskreten Probleme ist dabei sehr reichhaltig. Sie reicht von sehr theoretischen bis zu betont anwendungsbezogenen Fragen. In diesem Schwer-punkt-programm realisierten die Wissenschaftler ausschließlich Forschungsvorhaben mit konkretem Anwendungsbezug.
In einem zweitägigen Seminar am Institut für Prozessrechentechnik, Automation und Robotik an der Universität Karlsruhe stellen die Forscher nun ihre Leistungen der vergangenen sechs Jahre vor. Zu einem Industrietag am 27. November sind Industrie- und Dienstleistungsunternehmen eingeladen, zu denen zahlreiche Partnerschaften geknüpft werden konnten. Ziel dabei ist es, einen Einblick in die innovative Zusammenarbeit universitärer Forschung mit Industrie und Wirtschaft zu geben und einen offenen Gedankenaustausch zu ermöglichen. In Vorträgen, Poster- und Softwaredemonstrationen präsentieren Wissenschaftler und Industrievertreter ihre Resultate .
Aus den im Schwerpunktprogramm entworfenen Algorithmen entwickelten Firmen bereits mehrere kommerzielle Programmsysteme, etwa zum automatischen Zeichnen komplexer Diagramme, zur textilen Schnittmusterberechnung, zur Standortplanung, zur kollisionsfreien Bahnplanung von Industrierobotern und zum Medikamentenentwurf.
Hier einige ausgewählte Projekte aus dem Schwerpunktprogramm. Das große Spektrum diskreter Probleme spiegelt sich in der Vielzahl der Anwen-dungs--gebiete wider, aus denen die geförderten Projekte stammen.
Automatisches Zeichnen von Graphen und Diagrammen
In diesem Projekt wurde die AGD-Software implementiert, die mit Hilfe im Schwerpunkt neu entwickelter Algorithmen Diagramme auf vielfältige Weise übersichtlich zeichnet. Eine kommerzielle Version von AGD wurde von führenden Softwareunternehmen gekauft und findet Einsatz in der Visualisierung großer Netzwerke, Datenbankstrukturen sowie im Software Engineering und Reengineering. Das Projekt wird von der DFG-Ideenwerkstatt als eines von zehn Projekten mit besonders hohem Transferpotential besonders gefördert. Frau Prof. Petra Mutzel wurde für ihre Arbeiten auf dem Gebiet des Automatischen Zeichnens von Graphen im Oktober 2000 mit dem ALCATEL-SEL-Preis Technische Kommunikation ausgezeichnet. (Prof. Dr. Michael Jünger, Universität zu Köln)
Generierung von Hexaedernetzen für Simulationen in der Medizin und im CAD
In der Arbeitsgruppe "Kombinatorische Optimierung und Graphenalgorithmen'' an der Technischen Universität Berlin (Prof. Dr. Rolf H. Möhring, Dr. Matthias Müller-Hannemann) wurden neue kombinatorische Algorithmen zur Vierecks- und Hexaedernetzgenerierung für Finite-Elemente-Verfahren entwickelt. Es geht dabei darum, möglichst genaue aber auch möglichst vom Computer gut verarbeitbare Repräsentationen von Oberflächen, etwa von Werkstücken, zu berechnen. Das viel-fältige Anwendungsspektrum der entwickelten Verfahren reicht von der Automobilindustrie bis zu Simu-la-tionen in der Biomedizin. (Prof. Dr. Rolf H. Möhring, Technische Universität Berlin)
Computeralgebra und Entwurf analoger elektronischer Schaltkreise
Im Rahmen dieses Projektes wurden neue Algorithmen und Software für symbolische Rechnungen mit Anwendungen in der Mikroelektronik, Kodierungstheorie, Robotik, Molekularbiologie, Glasschmelze und Medizin entwickelt. (Prof. Dr. Gert-Martin Greuel, Universität Kaiserslautern)
Effiziente Erstellung von Schnittbildern in der textil- und blechverarbeitenden Industrie
Auf dem Gebiet der Verschnitt- und Packungsprobleme entwarfen Prof. Dr. Thomas Lengauer, Ph.D., Dr. Ralf Heckmann, Mike Schäfer, Onno Garms im Institut für Algorithmen und Wissenschaftliches Rechnen der GMD in Sankt Augustin Algorithmen zur Erstellung hochqualitativer Schnittbilder auf Textilien und Blechen. Die Verfahren erstellen binnen kurzer Zeit Lösungen, die mit von Experten erstellten Schnittbildern konkurrieren können. Zudem wurde ein Verfahren entwickelt, das Angaben über den mindestens notwendigen Verschnitt machen kann. Dadurch ist es erstmals möglich, Qualitätsgarantien für erstellte Schnittbilder zu geben. Die entwickelte Software zeichnet sich durch ihre uneingeschränkte praktische Anwendbarkeit aus. Es gibt derzeit keine andere Software auf dem Markt, die eine vergleichbare Qualität oder einen vergleichbaren Funktionsumfang bietet. Die Software setzen weltweit namhafte Firmen im Produktionsbetrieb eing. (Prof. Dr. Thomas Lengauer, Ph.D., GMD - Forschungszentrum Informationstechnik, Sankt Augustin)
Selektive Suche zur Strategiebildung mit Anwendungen beim Schachspiel
In diesem Projekt wurden neue Wege bei der Auswertung von Strategien beschritten, wie sie bei vielen komplexen Planungs- und Entscheidungssituationen auftreten. Als Demonstrationsbeispiel dient das Schachspiel. Die neu entwickelten Methoden werden im parallelen Schachprogramm P.ConNerS eingesetzt, das im Juli 2000 das 10. Lippstädter Großmeisterturnier gewinnen konnte. Damit hat zum ersten Mal weltweit ein Computerprogramm ein offizielles FIDE Großmeisterturnier gewonnen. P.ConNerS erspielte dabei eine ELO-Zahl von 2660 und gewann mit 6 Siegen, 3 Unentschieden und 2 Niederlagen vor dem 'besten Menschen' des Turniers Großmeister Hracek. (Prof. Dr. Burkhard Monien, Universität Paderborn)
Selbstlokalisation autonomer mobiler Roboter in realistischen Umgebungen
Untersucht wurde die Lokalisation und Navigation für autonome Roboter in Produktions- und Serviceumge-bun-gen mittels Laser-Radar (oder kurz: Lokalisation und Navigation mittels Ladar). Bei der Lokalisation und Navigation geht es um die selbständige Standortbestimmung eines mit einem Laser-Entfernungsmessers ausgestatteten Roboters in einem Gebäude. Wir haben Lösungsverfahren mit diversen Nebenbedingungen entwickelt und stellen ein umfangreiches, modulares Programmpaket RoLoPro für diese Problemstellungen zur Verfügung. (Prof. Dr. Hartmut Noltemeier, Universität Würzburg)
Realzeit-Algorithmen zur Darstellung großer dreidimensionaler Szenen
Das Projekt beschäftigt sich mit der Entwicklung von Realzeit-Algorithmen zur Darstellung großer dreidimensionaler Szenen. Der Besuch virtueller Umgebungen mit einem Computer kommt in vielen Bereichen wie Architektur, Erziehung, Unterhaltung und Planung zur Anwendung. Ein virtueller Rundgang in Echtzeit ist nur bei Szenen möglich, die nicht allzu groß sind. In dem Projekt wurden Algorithmen und Datenstrukturen entwickelt, die einen Durchgang durch sehr große Szenen erlauben, die mit einfachen Methoden nicht darzustellen sind. Grundlage ist die Implementierung eines verteilten Systems zum Durchlaufen einer Szene, bei dem die Szene auf mehrere Rechner verteilt ist. (Prof. Dr. Friedhelm Meyer auf der Heide, Universität Paderborn)
Automatisches Zeichnen von Graphen zur Visualisierung komplexer Strukturen
Das an der Universität Passau am Lehrstuhl von Prof. Dr. Franz J. Brandenburg entwickelte Graphlet System ermöglicht dem Anwender das Editieren und automatische Zeichnen von Diagrammen, Plänen, Netzen oder Graphen. Graphlet wird weltweit in Lehre und Forschung und in der Industrie zur Visualisierung von Diagrammen für Telekommunikationsnetze, Klassendiagrammen oder biochemischen Reaktionsnetzen eingesetzt. (Prof. Dr. Franz J. Brandenburg, Universität Passau)
Evolution von Genen
Das Projekt befasste sich mit der Entwicklung von Algorithmen zur Rekonstruktion der evolutionären Entwicklung von Genfamilien. Die DNA- oder Proteinsequenz der Gene heute existierender Organismen erlaubt Rückschlüsse auf deren Abstammung und auf mögliche Gensequenzen in ausgestorbenen Organismen. Schwerpunkt der Arbeit war hierbei die Integration von Verfahren zum Vergleich von Sequenzen mit Methoden zur Berechnung von Stammbäumen. In der Folge konnte eine neue Methode zum Durchsuchen einer Gendatenbank nach evolutionär verwandten Sequenzen entwickelt werden. (Dr. Martin Vingron, Deutsches Krebsforschungszentrum Heidelberg)
Oberflächen- und Volumenrekonstruktion
Bei der industriellen Produktentwicklung tritt oftmals das Problem auf, dass ein bereits vorhandenes Produkt mittels CAD/CAM-Techniken weiter bearbeitet werden soll, ohne dass verlässliche CAD-Daten des Objektes vorhanden sind. Diese Situation liegt z.B. dann vor, wenn ein handwerklich erzeugter oder manipulierter Prototyp als Grundlage der Konstruktion dient. Im Projekte zur Oberflächen- und Volumenrekonstruktion wurden effiziente Algorithmen zur teilautomatischen Generierung von CAD-Modellen aus digitalisierten Objekten entwickelt. Diese Methoden zielen ab auf die Vermeidung aufwendiger Neukonstruktionen und dienen damit der Einsparung von Ressourcen bei der Produktentwicklung. (Prof. Dr.-Ing. Guido Brunnett, Technische Universität Chemnitz)
Gröbnerbasen und Computeralgebra
Gröbnerbasen stellen einen universellen algorithmischen Lösungsansatz für ein breites Spektrum von Problemen der Computeralgebra dar. Im Projekte wurden zum einen beweisbar optimale Algorithmen zur Berechnung von Gröbnerbasen von Polynomidealen entwickelt, zum anderen wurden verschiedene damit strukturelle Fragestellungen bei Gröbnerbasen untersucht (Prof. Dr. Ernst W. Mayr, Technische Universität München)
Algorithmen für die Erzeugung von Roboterbahnen
Das Institut für Prozessrechentechnik, Automation und Robotik der Universität Karlsruhe entwickelte Algorithmen für die Erzeugung von Roboterbahnen. Auf Basis eines gegebenen 3D-Umweltmodells der Robo-ter-zelle berechnen die Algorithmen kürzeste kollisionsfreie Pfade zwischen anzufahrenden Punkten. In Kooperation mit Industrieunternehmen werden diese Algorithmen mit dem Ziel der Vermarktung derzeit erfolgreich in ein Robotersimulationssystem sowie in eine Robotersteuerung integriert. Damit können in der Simulation als auch direkt vor Ort am realen Roboter automatisch optimierte kollisionsfreie Bahnen und Roboterprogramme erzeugt werden. Dies reduziert drastisch die heute üblichen Programmier- und Anlagen-still-stands-zeiten. (Prof. Dr.-Ing. Heinz Wörn, Universität Karlsruhe)
Eine CD bietet vertiefende Informationen zu den Projekten des Schwerpunktprogramms. Die CD kann bei den unten genannten Ansprechpartnern angefordert werden. Diese Informationen finden Sie auch im World Wide Web unter den unten angegebenen Adressen.
Ansprechpartner
Prof. Dr. Thomas Lengauer, Ph.D. (Koordinator des Schwerpunktprogramms)
GMD-SCAI, Schloss Birlinghoven, 53754 Sankt Augustin
Telefon: 02241/14-2777 (-2776: Sekretariat), Fax: 02241/14-2656
E-Mail: lengauer@gmd.de
Prof. Dr.-Ing. Heinz Wörn (Veranstalter des Seminars)
Universität Karlsruhe, IPR, Engler-Bunte-Ring 8, 76131 Karlsruhe
Telefon: 0721/608-4006, Fax: 0721/608-7141
E-Mail: woern@ira.uka.de
Web-Adressen für weitere Informationen
http://www.gmd.de/SCAI/dfg (Projektübersicht, Projektinhalte, Ansprechpartner, Adressen)
http://wwwipr.ira.uka.de/~spp2000 (Seminarprogramm, Vortragsinhalte)
http://www.gmd.de/SCAI/dfg
http://wwwipr.ira.uka.de/~spp2000
Merkmale dieser Pressemitteilung:
Biologie, Informationstechnik, Maschinenbau, Mathematik, Physik / Astronomie
überregional
Buntes aus der Wissenschaft, Forschungsergebnisse, Wissenschaftliche Tagungen
Deutsch
Sie können Suchbegriffe mit und, oder und / oder nicht verknüpfen, z. B. Philo nicht logie.
Verknüpfungen können Sie mit Klammern voneinander trennen, z. B. (Philo nicht logie) oder (Psycho und logie).
Zusammenhängende Worte werden als Wortgruppe gesucht, wenn Sie sie in Anführungsstriche setzen, z. B. „Bundesrepublik Deutschland“.
Die Erweiterte Suche können Sie auch nutzen, ohne Suchbegriffe einzugeben. Sie orientiert sich dann an den Kriterien, die Sie ausgewählt haben (z. B. nach dem Land oder dem Sachgebiet).
Haben Sie in einer Kategorie kein Kriterium ausgewählt, wird die gesamte Kategorie durchsucht (z.B. alle Sachgebiete oder alle Länder).
