Mathematik in der Informatik

Gregor

Hi.

Oft genug stellen sich gerade für Informatikstudenten in den ersten Semestern Fragen wie "Für was brauche ich dieses Mathethema überhaupt?". Und derartige Fragen werden dann auch hier im Forum gestellt. Ich denke mir, da derartige Fragestellungen immer wieder auftreten, sollte es einen Thread geben, in dem zu vielen Informatikbereichen gesagt wird, welche Mathematik man dort benötigt. Deshalb fange ich diesen Thread hier an. Ich werde in diesem Beitrag (und auch in weiteren Beiträgen in den nächsten Tagen) ein bisschen zusammentragen. Da ich natürlich nicht in die gesamte Informatik detaillierte Einblicke habe, hoffe ich, dass sich weitere Nutzer an diesem Thread beteiligen. Auch Verbesserungen zu den Dingen, die ich schreibe, sind gerne gesehen. Wie gesagt: Viele Dinge kenne ich nur sehr oberflächlich und vielleicht habe ich sogar falsche Eindrücke. Zudem habe ich natürlich einen Schwerpunkt innerhalb der Informatik gewählt, der alles andere als repräsentativ ist und auch eine spezielle Mathematik benötigt. Während sich die Informatik in ihrer Gesamtheit eher mit diskrete Strukturen auseinandersetzt, kommen in meiner Schwerpunktsetzung auch viele kontinuierliche Strukturen vor. Dies wird in der Liste weiter unten dazu führen, dass der Einfluss von Analysis überproportional groß ist. Aber die Liste wird ja hoffentlich von weiteren Nutzern erweitert werden.

Noch eine generelle Vorbemerkung: Informatik ist eine Disziplin, die oft vor allem in Verbindung mit einem Anwendungsgebiet einen Sinn ergibt. Wenn dieses Anwendungsgebiet mathematische Formalismen oder mathematische Modelle nutzt, dann müssen Informatiker, die sich damit auseinandersetzen auch mit der entsprechenden Mathematik auskennen. Wenn man das als Informatiker nicht kann, dann werden für derartige Aufgaben eben andere Leute genommen. "Code schreiben kann jeder!" ...oder zumindest meinen viele, dass das nicht besonders herausfordernd ist und schnell erlernt werden kann.

Vorbemerkung 2: Ich werde die Mathematikbereiche nicht bis zum letzten Satz aufschlüsseln, den man benötigen könnte. Wenn jemand genaueres über den Einsatz eines bestimmten Mathematikbereichs in einem Bereich der Informatik wissen möchte, dann empfehle ich demjenigen, sich ein allgemeines Grundlagenbuch zu eben diesem Informatikbereich zu besorgen. Im Allgemeinen wird einem der entsprechende Mathematikeinsatz schon beim Durchblättern so eines Buchs auffallen. Wenn man genauer hinsieht, erfährt man entsprechende Details. Allerdings ist es mit Grundlagenbüchern natürlich so, dass sie nur die Grundlagen vermitteln. Wenn es in speziellere Bereiche geht, wird oft noch mehr Mathematik verwendet.

Ok, los geht's:

Robotik: Roboter haben Sensoren und Aktoren, die fehlerbehaftet funktionieren. Aus diesem Grund kommen in diesem Zusammenhang Methoden der Stochastik zum Einsatz. Zum Beispiel Wahrscheinlichkeitsverteilungen, bedingte Wahrscheinlichkeiten und so weiter. Weiterhin haben Roboter bewegliche Teile. Wenn sich ein Roboterarm auf bestimmte Weise bewegen muss, dann ist das ein Zusammenspiel aus Translationen, Rotationen und so weiter. All das sind lineare oder affine Abbildungen, die im Rahmen der Linearen Algebra behandelt werden. Als Grundlage der Arbeit mit Robotern werden zudem oft physikalische Modelle erstellt. Hierbei geht es vor allem um die Mechanik. Das heißt, dass man es auch mit Analysis zu tun kriegt. Wer sich also mit Robotern beschäftigen möchte, sollte durchaus etwas von Funktionen, Ableitungen, Integralen, Differentialgleichungen und so weiter verstehen.
Mustererkennung: In der Mustererkennung geht es darum, Objekte, die durch gewisse Merkmale gegeben sind, Objektklassen zuzuordnen. Selbstverständlich unterscheiden sich die Objekte alle etwas von einander und Objektinstanzen einer Klasse haben Merkmale, die irgendeiner Wahrscheinlichkeitsverteilung unterliegen. Es kann auch sein, dass man generelle Wahrscheinlichkeiten für das Auftreten von Objekten bestimmter Klassen im Vorfeld weiß. Das führt dann sehr schnell zu einer Modellierung des Sachverhalts mittels bedingter Wahrscheinlichkeiten, wie sie von Bayes angedacht sind. Mit anderen Worten: In der Mustererkennung braucht man jede Menge Stochastik. Im Rahmen derartiger Stochastik-Anwendung wird auch mit Unmengen von Matrizen hantiert. Deshalb ist Lineare Algebra auch eine Grundvoraussetzung für das Arbeiten in diesem Bereich.
Automatentheorie: In der Automatentheorie ist der Zusammenhang zu Graphen sehr offensichtlich. Deswegen wird hier Diskrete Mathematik benötigt.
Model Checking, Nebenläufige Systeme: In diesem Bereich geht es darum, Modelle bestimmter Systeme daraufhin zu überprüfen, ob sie bestimmte Eigenschaften aufweisen. Nebenläufige Systeme modelliert man in diesem Zusammenhang zum Beispiel gerne als Petrinetze. Diese haben, wie praktisch jede Art von Netz, einen sehr direkten Zusammenhang zu Graphen, die aus der Diskrete Mathematik bekannt sind. Da Eigenschaften der Systeme bewiesen werden sollen, werden Modelle dieser Systeme oft in andere, formalere Modellformen übertragen. In diesen können dann auf Basis von Logik bestimmte Eigenschaften nachgewiesen werden.
Eingebettete Systeme: Eingebettete Systeme werden oft eingesetzt, um irgendwelche Vorgänge zu steuern oder zu regeln. "Regeln" ist hierbei im Rahmen der Regelungstechnik zu verstehen und das heißt, dass Analysis und möglicherweise sogar etwas Funktionentheorie benötigt wird. Analysis ist in diesem Zusammenhang auch deshalb wichtig, weil die zu regelnden Vorgänge oft physikalischer Natur sind und deshalb im Rahmen physikalischer Modelle in den Entwurf eines entsprechenden Eingebetteten Systems einfließen.
Systemtheorie: Systemtheorie ist die formale Grundlage für viele Bereiche der Signalverarbeitung. Letztendlich handelt es sich bei Systemtheorie um Fourieranalysis in Reinform. Also ist Analysis eine integrale Grundvoraussetzung für die Beschäftigung mit Systemtheorie und ihren Anwendungen. Signale unterliegen auch statistischen Schwankungen. Deswegen sind Kenntnisse der Stochastik hier auch von Vorteil. Auch das Wissen über Elemente der Funktionentheorie sind für die Systemtheorie von Vorteil.
Wissensverarbeitung: Wissen repräsentiert man in der Informatik mittels unterschiedlicher logischer Systeme. Deswegen sind in diesem Zusammenhang Logik-Kenntnisse unabdingbar. Und zwar viel. Hier werden auch Modallogiken und so weiter genutzt. Im Prinzip geht es in der Wissensrepräsentation darum, eine wirklich passende Repräsentation für die jeweilige Anwendung zu finden. Bei logischen Systemen sind die Ziele Ausdruckskraft und Schlusskraft widersprüchlich. In einer sehr mächtigen Logik kann man zwar alles darstellen, aber man kann in akzeptabler Zeit nur noch wenig aus dem dargestellten Wissen schließen. Weiterhin werden in der Wissensverarbeitung auch gerne Modelldarstellungen von Vorgängen genutzt, die stark an Graphen angelehnt sind. Diskrete Mathematik ist deshalb auch eine wichtige Grundvoraussetzung. Zuletzt sei gesagt, dass auch Wissen und Schlüsse aus Wissen Unsicherheiten unterworfen ist. Aus diesem Grund fließen auch Kenntnisse aus der Stochastik in die Wissensverarbeitung ein.
Sprachverarbeitung: Auf niedriger Ebene ist Sprachverarbeitung Signalverarbeitung (Systemtheorie) und auch Mustererkennung. Deshalb werden auch die Mathematikkenntnisse benötigt, die zu diesen Themenbereichen gehören (siehe oben). Auf höherer Ebene geht die Sprachverarbeitung eher etwas in Richtung Wissensverarbeitung, auch mit den damit Verbundenen Voraussetzungen. Wenn man ein Buch über Sprachverarbeitung liest, wird man auch gerne mit formalen Sprachen konfrontiert. Auch Hidden Markov Models und andere Aspekte der Stochastik werden hier genutzt.
Bildverarbeitung: Ähnlich wie die Sprachverarbeitung ist die Bildverarbeitung auf niedriger Ebene mehrdimensionale Signalverarbeitung bzw. Systemtheorie. Und auch hier wird Mustererkennung betrieben. Wenn es auf einer abstrakteren Ebene Richtung Höhere Bilddeutung geht, in der Szenen interpretiert werden, dann kommt die Bildverarbeitung auch der Wissensverarbeitung näher. Man benötigt natürlich die Mathematik, die in all diesen Bereichen vorkommt (und noch deutlich mehr).
Theorie der Programmiersprachen: In der Theorie der Programmiersprachen geht es darum, Korrektheit von Code zu beweisen. Dazu werden Codestücke in formalere Sprachen (Semantiken) übersetzt, in denen man derartiges besser machen kann. In diese Formalen Semantiken fließt jede Menge Logik ein, die man deshalb beherrschen sollte.
Komplexitätstheorie: Die Komplexitätstheorie ist wohl eines der zentralsten und anspruchsvollsten Gebiete innerhalb der Informatik. Hier macht es aber eigentlich keinen Sinn, darüber zu reden, welche Mathematik Anwendung findet. Stattdessen muss gesagt werden, dass Komplexitätstheorie Mathematik ist. Damit meine ich die Arbeitsweise innerhalb des Bereichs. Es werden diskrete Strukturen definiert und es werden Eigenschaften und Sätze über diese Strukturen formuliert und bewiesen. Im Prinzip stellt Komplexitätstheorie also einen eigenen Zweig der Mathematik dar. Allerdings gibt es an bestimmten Stellen auch Einflüsse aus beliebigen anderen Bereichen der Mathematik.
Kryptographie Im Prinzip ist Kryptographie ein Teilgebiet der Komplexitätstheorie oder zumindest stark von dieser beeinflusst. Der Grundgedanke hinter kryptographischen Systemen ist heute die Nutzung sogenannter One-way functions. Dies sind Funktionen, die zwar effizient berechnet werden können, aber nicht effizient invertiert werden können. Die effiziente Invertierung klappt im Rahmen der Kryptographie praktisch nur dann, wenn man als Empfänger einer Nachricht einen entsprechenden Schlüssel hat, der einem dabei hilft. One-way functions sind also die zentrale Basis der Kryptographie. Die generelle Existenz von One-way functions ist im Rahmen der Komplexitätstheorie allerdings nicht gesichert und hängt mit der Frage zusammen, ob P!=NP gilt.

Gregor

Computergrafik: In der Computergrafik geht es darum, Szenen aus abstrakten Beschreibungen am Bildschirm darzustellen. Dabei muss man andauernd zwischen verschiedenen Koordinatensystemen hin- und hertransformieren, man muss Dinge rotieren, skalieren, oder verschieben. Das sind natürlich alles Vorgänge, die durch Lineare Algebra beschrieben werden. Weiterhin rechne ich einfach mal den Bereich des CAD/CAM der Computergrafik zu, da dort ebenfalls mit 3D-Modellen gearbeitet wird. In dem Zusammenhang ist es zum Beispiel wichtig, Schnitte durch derartige 3D-Modelle korrekt zu berechnen. Und welche Kurven hinterlassen bestimmte Körper eigentlich in gegebenen Schnittebenen. Bei derartigen Fragestellungen wird Differentialgeometrie benötigt, die man durchaus der Analysis zuordnen kann. Auch jenseits dieses speziellen Anwendungsgebiets ist Analysis in der Computergrafik äußerst nützlich.
Diskrete Simulation: Firmen wollen ihre Infrastruktur passend dimensionieren. Zu große Dimensionierung kostet, eine zu kleine Dimensionierung führt hingegen zu Engstellen. Die Frage, wie die passende Dimensionierung aussieht, kann zum Beispiel durch Diskrete Simulation beantwortet werden. Fragestellungen sind hier zum Beispiel, wie lang LKW-Schlangen vor Containerterminals werden und ähnliches. Selbstverständlich sind derartige Fragestellungen mittels Stochastik zu modellieren und zu interpretieren.

Simulation: Durch Computersimulationen versucht man, aus den Natur- und Ingenieurwissenschaften inspirierte Problemstellungen zu lösen. Teilweise wird die Simulation bereits als dritte Säule wissenschaftlicher Arbeit neben Theorie und Experiment angesehen, aber dieser Gedanke ist noch nicht durchgehend akzeptiert. Zentral für Computersimulationen sind die Numerische Mathematik und die Komplexitätstheorie. Die Fragestellungen werden häufig in der Sprache der Analysis formuliert. Durch Diskretisierung überführt man das Problem in den Bereich der Linearen Algebra und versucht die entstehenden Gleichungssysteme mittels Numerischen Algorithmen zu lösen, da exakte Methoden nicht mehr greifen.
Beispiele: Klimaveränderungen, Crashtests, Entwicklung des Kosmos

Gregor

Algorithmen: Gemeint sind hier klassische Algorithmen, wie man sie in den ersten Semestern kennenlernt. Sortieralgorithmen, Graphenalgorithmen und so weiter. Diese Algorithmen arbeiten auf diskreten Strukturen, deswegen wird hier auch Diskrete Mathematik benötigt. Auch zur Komplexitätsanalyse von Algorithmen kann Diskrete Mathematik hilfreich sein, zum Beispiel der Umgang dieses Teilgebiets der Mathematik mit Rekursion.

EDIT: @µ: Schöner Punkt mit den Simulationen. Aber mir ergibt sich eine Frage. Das meiste davon kann ich nachvollziehen, aber ich sehe keinen wirklichen Zusammenhang zur Komplexitätstheorie. Wie ist das gemeint? Hast Du da ein Beispiel oder so?

Gregor schrieb:

Aber mir ergibt sich eine Frage. Das meiste davon kann ich nachvollziehen, aber ich sehe keinen wirklichen Zusammenhang zur Komplexitätstheorie. Wie ist das gemeint? Hast Du da ein Beispiel oder so?

Im Zusammenhang mit Simulationen und Numerik ist die Analytische Komplexitätstheorie gemeint, nicht die Klassische.

Die Analytische Komplexitätstheorie widmet sich dem minimalen Aufwand analytischer Probleme. Das heißt, zum Beispiel, dem minimalen Aufwand zur Berechnung von beliebieg-hoch-dimensionalen Integralen oder (partiellen) Differentialgleichungen mit Hilfe numerischer Verfahren. Also letztendlich mittels Computern und Programmierung.

Die Betrachtung liegt, im Gegensatz zu rein mathematisch und lösungsorientierten Verfahren, tatsächlich auf dem Laufzeitaufwand. Diese Art der Untersuchung wird von Mathematikern bisher wenig beachtet, weshalb es zur Informatik gezählt werden kann und auch nur von der Informatik untersucht wird.

Datenbanken: Nahezu jede größere Software benötigt eine Möglichkeit zur Persistenz, also zur dauerhaften und strukturierten Speicherung und Abfrage von Daten, welche über die Fähigkeit von einfachen Dateien nach individuellem Schema des Programmierers hinausgehen.
Bereits in den 1970er-Jahren hat Edgar F. Codd das mathematisch fundierte Prinzip tabellenorientierter Datenenbanken entwickelt und untersucht. Heute dominieren Reationale Datenbanken weltweit die Datenspeicherung. Theoretische Fundierung erhält dieser Weg durch die Relationale Algebra. Dahinter verbirgt sich ein mathematisch strenger Formalismus, der von einfachen Mengenoperationen bis hin zu komplexen "Joins" untersucht und in den Eigenschaften aller Einzelheiten nachvollzogen und bewiesen werden kann.

(Trotz aller wissenschaftlicher Formalität leidet die Datenspeicherung im Zuge moderner Programmierung unter dem "Object-relational impedance mismatch". Das aktuelle Programmierparadigma ist Objekt-Orientiert und widerspricht relationalen Datenbanken fundamental. An dieser Stelle fehlt eine mathematische Theorie Objekt-Orientierter Datenbanken.)

Die Implementierung Relationaler Datenbanken bedient sich gerne bei Ideen der Algorithmik und Datenstrukturen: Etwa b*-Bäumen. "Bäume" haben bei geschickter Anwendung inhärent logarihtmische Eigenschaften bezüglich der Laufzeit. Hier wird wieder der Kreis zur klassischen Komplexitätstheorie geschlossen und baut auf Mathematik auf.

Christoph

Gregor schrieb:

Automatentheorie: In der Automatentheorie ist der Zusammenhang zu Graphen sehr offensichtlich. Deswegen wird hier Diskrete Mathematik benötigt.

Ich bin in dem Punkt vielleicht anders vorbelastet, aber ich würde eher den Bezug zur Logik aufzeigen:

Automatentheorie: Automatentheorie hat tiefe Bezüge zur mathematischen Logik. Man lernt im Grundstudium schon häufig, dass reguläre Sprachen zu ganz bestimmten Automaten korrespondieren. Diese Automaten korrespondieren aber auch zu einer ganz bestimmten mathematischen Logik. Diese Bezüge gehen so weit, dass man mit logischen Methoden vielleicht irgendwann P = NP beantworten oder andere tiefe Fragen klären kann.