Diskrete Mathematik und Anwendungen
Leiter der Arbeitsstelle: Prof. Dr. Jens Vygen
Anschrift:
Forschungsinstitut für Diskrete Mathematik Universität Bonn
Lennéstr. 2
53113 Bonn
Telefon: 02 28 / 73 87 70
Telefax: 02 28 / 73 87 71
E-Mail: dm@or.uni-bonn.de
Internet: http://www.or.uni-bonn.de
Das Projekt "Diskrete Mathematik und Anwendungen" wird durch Beschluss der Konferenz der deutschen Akademien der Wissenschaften ab 1. Januar 1996 als langfristiges Akademievorhaben gefördert. Zuvor hatte die Staatskanzlei Düsseldorf eine Anschubfinanzierung zur Verfügung gestellt.
Die Diskrete Mathematik beschäftigt sich im wesentlichen mit endlichen (oder abzählbar unendlichen) Strukturen. Sie ist als eigenständige Disziplin in der zweiten Hälfte des 19. Jahrhunderts entstanden, wo zunächst gewisse Gebiete der Graphentheorie und der enumerativen Kombinatorik entwickelt wurden. In den letzten Jahrzehnten hat die Diskrete Mathematik besonders durch ihre Anwendungen in den Ingenieur- und Naturwissenschaften eine sehr starke Entwicklung erfahren. Das ging Hand in Hand mit der Entwicklung sehr leistungsfähiger Computer, denn jede mathematische Anwendung, die einen Computer benutzt, ist notwendigerweise diskret.
Es ist im allgemeinen nicht bekannt, dass viele Entwicklungen, Struktur- und Theoriebildungen in der Mathematik durch Anwendungsprobleme oder durch Realphänomene in anderen Wissenschaften angeregt worden sind. So ist zum Beispiel der Calculus mit dem für viele Entwicklungen in der Mathematik zentralen Grenzwertbegriff primär aus den Bedürfnissen der Physik entstanden. Newton, der zusammen mit Leibniz die Differenzialrechnung in ihren Anfängen entwickelt hat, war in erster Linie Physiker. Es ging in der Tat darum, neue physikalische Begriffe wie Geschwindigkeit und Beschleunigung adäquat und mathematisch korrekt zu beschreiben. Diese empirische Fundierung des Calculus hat dann ausgereicht, um in einem Zeitraum von mehr als drei Jahrhunderten tiefe und grundlegende methodische Entwicklungen in der Mathematik anzuregen und zu beeinflussen.
Mit diesem historischen Beispiel sollte lediglich demonstriert werden, dass – wesentlich stärker als man üblicherweise glaubt – mathematische Entwicklungen ihre grundlegende Anregung aus Realphänomenen erhalten. Das ist auch und gerade in den letzten Jahren besonders stark für die Diskrete Mathematik der Fall. Durch vielfältige Anwendungen sind zahlreiche neue diskrete und kombinatorische Strukturen entstanden und weiterentwickelt worden, die der Diskreten Mathematik ein solides und breites Fundament geben und die Prognose gestatten, dass diese noch junge Disziplin in nächster Zeit zahlreiche und relevante Forschungs- und Anwendungsprobleme haben wird.
Sehr interessante – auch effizient lösbare – Anwendungsprobleme hat die Diskrete Mathematik in letzter Zeit gerade in den Ingenieurwissenschaften, aber auch in den klassischen Naturwissenschaften gehabt. Hier seien genannt: Transport- und Flussprobleme, Reihenfolgeprobleme, allgemeine Schedulingprobleme, Produktions-, Produktionsplanungs- und Produktionsvorbereitungsprobleme, Steuerung von Werkzeugmaschinen und Robotern, diskrete Strukturen bei Modellen der theoretischen Physik (Computational Physics), diskrete Strukturen in der Chemie, zum Beispiel Modelle zur Beschreibung von Valenzen und Bindungsenergien, verschiedene Standortprobleme, z.B. im Mobilfunk, aber auch Seriationsprobleme in der Archäologie, Strukturmodelle in der Genetik und Klassifikationsprobleme in der Linguistik.
Prozesse der Chemietechnik, zum Beispiel Crack-Verfahren in der Mineralölindustrie, werden laufend mit Methoden der Diskreten Optimierung gesteuert. Fluggesellschaften können ihre Flugnetze ebenfalls nicht mehr ohne Methoden der Diskreten Mathematik betreiben. Verschnittprobleme, zum Beispiel bei der Stahlerzeugung, können minimiert werden. Komplexe Fließbandsteuerungen und Fertigungssysteme sind ohne Diskrete Optimierung nicht denkbar. In der Mikroelektronik kann die Diskrete Optimierung zu wesentlich leistungsfähigeren Computern beitragen. Aber auch bei der Logistik komplexer ökologischer Entsorgungsprobleme, ja selbst beim Management von Blutbanken sind Methoden der Diskreten Mathematik von Bedeutung.
Auch das Design höchstintegrierter mikroelektronischer Schaltungen (VLSI-Chips) ist ohne Diskrete Mathematik nicht mehr vorstellbar. Vereinfacht ausgedrückt, muss man sehr komplexe logische Funktionen optimal durch Schaltkreise auf einem Chip realisieren. Dies schließt die Platzierung von vielen Millionen (und in wenigen Jahren Milliarden) Transistoren auf einer rund daumennagelgroßen Chipfläche ebenso mit ein wie deren Verdrahtung auf rund zehn Ebenen. Dabei müssen zahlreiche technologische Nebenbedingungen (z.B. Abstandsregeln) eingehalten werden. Ziel ist die Maximierung der Taktfrequenz bei minimalem Stromverbrauch und kleinstmöglicher Chipfläche. Es handelt es also um endliche, aber sehr große Optimierungsprobleme.
Dieser sehr komplexe Problemkreis stellt die Diskrete Mathematik vor große - und aufgrund immer weiterer technologischer Fortschritte - ständig neue Herausforderungen. In den letzten Jahren sind jedoch - gerade auch im Rahmen dieses Akademieprojekts - wesentliche theoretische Ergebnisse erzielt worden, die bereits zu vielen besseren (schnelleren, billigeren, stromsparenderen) Chips geführt haben. Dies gelang durch eine enge Wechselwirkung zwischen theoretischer Forschung, der Entwicklung von Algorithmen und Software und deren Anwendung beim Chip-Design. So führen neue Probleme der Praxis - die aufgrund der rasanten Entwicklung dauernd auftreten - direkt zu neuen theoretischen Fragestellungen, und deren Lösung führt zu besseren Algorithmen und damit sehr schnell zu besseren Chips.
Dabei konzentriert sich das Akademieprojekt weniger auf die beim Design aktueller Chips auftretenden Probleme, sondern vielmehr auf grundlegende Fragestellungen, die auch noch in vielen Jahren und - wegen ihrer allgemeinen Natur - in ganz anderen, teilweise unvorhergesehenen Anwendungsbereichen eine wesentliche Rolle spielen. Eine solche Wechselwirkung zwischen theoretischer Grundlagenforschung und Anwendung - und das in einer Schlüsseltechnologie - ist der seltene Idealfall.