Die Mathematik der getrennten Dinge#
Diskrete Mathematik ist so viel mehr als nur „die Sprache der Informatik“, wie sie vielfach bezeichnet wird. „Diskret“ im gebräuchlichen Sinn ist sie dabei nicht. #
Foto: https://pixabay.com
Diskrete Mathematik leitet sich vom lateinischen discernere ab, was „trennen“ bedeutet. „Bei der diskreten Mathematik geht es um abgegrenzte bzw. klar voneinander getrennte Objekte – etwa Punkte, Linien, oder Folgen von ganzen Zahlen“, erklärt Oswin Aichholzer, Informatiker an der TU Graz. „Punkte sind ganz besonders diskret“, fügt er mit einem Schmunzeln hinzu. Schmunzelnd deswegen, weil sich der Forschungsbereich diskrete Mathematik darüber hinaus sehr schwer definieren lässt. Bei der diskreten Mathematik geht es um abgegrenzte Betrachtungsgegenstände. Etwa die Zahlenfolge, 1, 2, 3, 4 und so weiter. Bei dieser Folge weiß man immer, welche Zahl auf die letzte folgt – sie ist „abzählbar“. Nicht abzählbar, und deswegen auch nicht diskret, ist es, wenn beispielsweise alle als Kommazahlen darstellbare Zahlen betrachtet werden. Zwischen 1 und 2 liegt 1,5. Zwischen 1,5 und 1,6 liegt 1,51. Zwischen 1,51 und 1,52 liegt 1,511. So liegen zwischen zwei beliebigen Zahlen unendlich viele weitere Zahlen – sie sind „nicht abzählbar“.
Viel besser ist es aber, die diskrete Mathematik als die Summe ihrer Teilbereiche zu sehen, wie auch Bettina Klinz, Leiterin des Instituts für Diskrete Mathematik bestätigt: „Im Grunde gibt es keine klare Definition. Die Grenzen sind schwer zu ziehen – sie können weit oder eng gefasst werden. Viel leichter ist es, die diskrete Mathematik über die behandelten Fragestellungen zu erklären.“ Disziplinen, die zur diskreten Mathematik gezählt werden sind u.a. Kryptografie, Codierungstheorie, Kombinatorik, Graphentheorie, Algebra, Zahlentheorie, Algorithmentheorie und diskrete Optimierung. Einige dieser Gebiete begegnen uns mittlerweile regelmäßig im Alltag, oft allerdings ohne, dass dies der Mehrheit bewusst ist. So sorgt die Kryptografie dafür, dass Daten verschlüsselt und sicher übertragen werden können, was in der digitalen Welt eine immer größere Rolle spielt. Die Codierungstheorie beschäftigt sich mit Codes, deren Eigenschaften und der Erkennung und Korrektur von Fehlern, die bei der Übertragung oder Speicherung von Daten auftreten können. Allgegenwärtige Codes im Alltag sind zum Beispiel Sozialversicherungsnummern, Barcodes im Supermarkt und QR-Codes (die schwarzen und weißen Quadrate codieren die Bits 0 und 1). „QR Codes bleiben bis zu einem gewissen Ausmaß auch noch entschlüsselbar wenn Teile fehlen oder verblasst sind“, erklärt Bettina Klinz.
Diskrete Optimierung#
Ihr eigenes Spezialgebiet ist die diskrete Optimierung, die sich mit Optimierungsaufgaben beschäftigt, die diskrete/ganzzahlige Entscheidungen beinhalten. Zum Beispiel: Soll eine Fabrik an einem Standort erbaut werden oder nicht? Wie viele Fahrzeuge werden benötigt, um alle geplanten Fahrten abzuwickeln? Besonders schätzt die Mathematikerin an ihrem Forschungsgebiet, dass es die Bandbreite zwischen grundlagenorientierter Forschung und konkreter Anwendung abdeckt. Im Bereich der Grundlagen geht es etwa um Fragestellungen zur optimalen Planung von Fahrten auf Basis von diversen Kriterien wie den Kosten, der Fahrtdauer oder der Nachhaltigkeit. Genauso aber auch um möglichst effiziente Routen für Bohrer, die Löcher in Platinen bohren. „Fragestellungen wie diese klingen vielleicht einfach und banal – aber so ein Bohrer muss mitunter 10.000e Löcher am Tag bohren. Da ist es sehr wichtig, dass er effiziente Bewegungsabläufe hat“, erklärt Klinz.
Lange bevor es praktische Optimierungsprobleme, wie die oben genannten, gab, legte der Mathematiker Leonhard Euler im 18. Jahrhundert wesentliche Grundlagen für die diskrete Mathematik: Er formulierte und löste das Königsberger Brückenproblem, bei dem alle sieben Brücken in Königsberg genau einmal überquert werden sollen und am Ende wieder zum Ausgangspunkt zurückzukehren ist. Dieselbe Fragestellung tritt auf wenn man eine vorgegebene geschlossene Figur (zum Beispiel eine Laterne) zeichnen will, ohne dabei den Stift abzusetzen oder eine Linie doppelt zu zeichnen. „Euler hat damals schon erkannt, dass die Aufgabenstellung mit Hilfe eines Modells mit Punkten (Orte) und Linien (Brücken/Strecken) abstrahiert werden kann. So entsteht ein sogenannter Graph mit Knoten (Punkte) und Kanten (Linien). Mit solchen abstrakten Graphen arbeiten Mathematiker*innen noch heute – und nicht nur in der Graphentheorie. „Relevant für die Antwort auf die Frage von Euler sind nur zwei Dinge: Kann man von jedem Punkt jeden anderen Punkt erreichen? Und haben alle Punkte eine gerade Anzahl von Nachbarpunkten?“ Dann und nur dann ist es nämlich möglich, die Route ohne doppelte Wege zu planen. Auf Eulers Überlegungen aufbauende Vorgangsweisen werden auch heute noch in der Routenplanung eingesetzt.
In der Optimierung wird generell neben der Lösungsqualität der Faktor Robustheit immer wichtiger. Das bedeutet, Entscheidungen und Lösungen, etwa gewählte Routen oder einen Produktions- und Transportplan gegenüber Auswirkungen von Datenunsicherheiten abzusichern.“ Wichtig ist, Lösungen zu finden, die möglichst stabil auf veränderliche Rahmenbedingungen reagieren. „Eine Idee ist, die gewählte Lösung gegen das aus heutiger Sicht schlechteste Szenario abzusichern und die Planungen laufend anzupassen. In einem von der FFG geförderten Forschungsprojekt beschäftigen wir uns mit robusten Optimierungsproblemen in der Transportplanung“.
Diskrete Grundlagen der Informatik#
Oswin Aichholzer ist stellvertretender Leiter des Instituts für Softwaretechnologie und nutzt Methoden der diskreten Mathematik, um Grundlagen für Computeranwendungen zu schaffen – er ist also primär in der Grundlagenforschung tätig, befasst sich mit Graphen und Möglichkeiten, diese einem Computer verständlich zu machen. „Beispielsweise arbeiten wir gerade daran, einem Computer Kurven in einem Graph verständlich zu machen. Das ist ein nicht so einfach lösbares Problem, vor allem, wenn nicht alle Informationen vorhanden sind“, erklärt er. Graphen sind etwa in Zug- oder Straßenplänen relevant und bekommen eine besondere Brisanz, wenn Kreuzungen auftreten, wenn zwei vermeintlich parallele Strecken doch um einen kleinen Faktor nicht parallel sind und sich irgendwann schneiden. „Dieses Problem einem Computer beizubringen ist schwer, aber auch in der Realität bei Streckenplanungen äußerst relevant.“
Seine Forschungsinteressen im Bereich diskrete Mathematik und Informatik bezeichnet er selbst als „sehr spezifisch“. Denn: Vieles ist in diesen Bereichen einfach schon bekannt und es muss sehr tief in ein Thema eingetaucht werden, um Neues zu erfahren und entdecken. „Wir schauen uns ein Problem sehr intensiv an und versuchen, es wirklich bis ins kleinste Detail zu verstehen. So können wir immer noch neue, relevante Zusammenhänge darüber finden.“
Algorithmische Topologie#
Michael Kerber, stellvertretender Leiter des Instituts für Geometrie, übernahm im Herbst die Leitung des Doktoratskollegs für Diskrete Mathematik an der TU Graz, einem PhD-Ausbildungsprogramm, das die TU Graz gemeinsam mit der Uni Graz und der Montanuni Leoben seit mehreren Jahren betreibt. Das Kolleg befindet sich in seiner finalen Phase und soll noch bis Mitte 2024 verlängert werden. In Gründung befindet sich gerade die Graz School of Discrete Mathematics, die als Nachfolgestruktur das erfolgreiche Kolleg weiterführen soll.
Michael Kerber beschäftigt sich im Bereich der algorithmischer Topologie hauptsächlich mit Simplizialkomplexen. Diese stellen Erweiterungen von Graphen in höheren Dimensionen dar und machen es möglich, mit topologischen Räumen auch zu rechnen. Diesen Bereich rechnet er der diskreten Mathematik zu. “Wenn man sich im Gegensatz dazu nur die Eigenschaften von toplogischen Räumen anschaut, dann landet man bei der algebraischen Topologie”, definiert Kerber. In seinem aktuellen Forschungsprojekt – gefördert vom Wissenschaftsfond FWF – beschäftigt er sich mit den topologischen Eigenschaften von Objekten auf mehreren Skalen. “Objekte betrachtet man üblicherweise auf einer Skala – ist es weiter weg, dann sieht man weniger Details, ist es näher, dann sieht man mehr Details. Hier entspricht die Skala der Entfernung, aber es gibt noch viel mehr mögliche Skalen”, beschreibt Kerber. Etwa die drei Farbkanäle von RGB-Bilder Rot, Grün und Blau. Kompliziert wird es, wenn mehrere Skalen gleichzeitig betrachtet werden sollen. “Da sind viele Dinge einfach nicht mehr berechenbar und dieses Vorgehen galt lange als zu schwierig und nicht machbar. Aber in den vergangenen Jahren hat das Feld mit der algorithmischen Betrachtung der Mehrparameter wieder an Fahrt aufgenommen.” Einsatzgebiet sind dann etwas das maschinelle Lernen und die Biotechnologie.
Definiertes Feld ohne Definition#
Die diskrete Mathematik wird in vielfältigen Bereichen der Wissenschaft, in der Theorie wie auch in der Anwendung, dringend gebraucht und umfangreich eingesetzt. Eine klare Definition gibt es aber nicht. “Wobei es vielen Mathematiker*innen auch egal ist, wie das Feld heißt, in dem sie arbeiten. Wichtig ist für uns, neue Erkenntnisse und Einsichten zu gewinnen sowie davor ungelöste mathematische Probleme zu lösen und jede Art von Mathematik, die diesem Ziel dient, ist willkommen“ schließt Bettina Klinz ab. Und das ist eigentlich auch eine wunderschöne Zusammenfassung.
Dieses Forschungsprojekt ist im Field of Expertise „Information, Communication & Computing“ verankert, einem von fünf strategischen Schwerpunktfeldern der TU Graz.
Mehr Forschungsnews finden Sie auf Planet research. Monatliche Updates aus der Welt der Wissenschaft an der TU Graz erhalten Sie über den Forschungsnewsletter TU Graz research monthly.
Nähere Informationen online auf der Website des Science Space Styria