Welche Teile der linearen Algebra werden in der Informatik verwendet?

15

Ich habe die Lineare Algebra und ihre Anwendungen gelesen , um Informatikmaterial (hauptsächlich maschinelles Lernen) besser zu verstehen, aber ich bin besorgt, dass viele Informationen für CS nicht nützlich sind. Zum Beispiel scheint es nicht sehr nützlich zu sein, zu wissen, wie lineare Gleichungssysteme effizient gelöst werden können, wenn Sie nicht versuchen, einen neuen Gleichungslöser zu programmieren. Darüber hinaus hat das Buch viel über Spannweite, lineare Abhängigkeit und Unabhängigkeit gesprochen, wenn eine Matrix eine Inverse hat, und die Beziehungen zwischen diesen, aber ich kann mir keine Anwendung davon in CS vorstellen. Welche Teile der linearen Algebra werden in CS verwendet?

Kelmikra
quelle
2
Bitten Sie um Ihren eigenen Nutzen oder suchen Sie als Lehrer nach Strategien, um Ihre Schüler zu motivieren?
Raphael
Die lineare Algebra ist in vielen Bereichen der Computergrafik nützlich (Sie können viele verwandte Informationen finden, die googeln).
Juho
Das Lösen linearer Gleichungssysteme ist in der Informatik unglaublich nützlich. Zum Beispiel: en.m.wikipedia.org/wiki/Combinatorial_optimization
Ant P
1
Matrizen werden häufig in der Spieleentwicklung und im Internet Explorer für Projektionen, Rotationen und Quaternion-Mathematik verwendet.
Paul
@Paulpro Die Frage bezieht sich auf Anwendungen der linearen Algebra (eine Menge von Arbeiten), nicht auf Matrizen (eine Menge von Objekten).
Raphael

Antworten:

11

Die Teile, die Sie erwähnt haben, sind grundlegende Konzepte der linearen Algebra. Sie können die fortgeschritteneren Konzepte (z. B. Eigenwerte und Eigenvektoren) nicht verstehen, bevor Sie die Grundkonzepte verstanden haben. In der Mathematik gibt es keine Abkürzungen. Ohne ein intuitives Verständnis der Konzepte von Spanne und linearer Unabhängigkeit kommen Sie in der linearen Algebra nicht weit.

Einige Algorithmen funktionieren nur mit Vollrangmatrizen. Wissen Sie, was das bedeutet? Wissen Sie, was eine Matrix nicht zum vollen Rang machen kann? Wie geht man damit um? Sie werden keine Ahnung haben, wenn Sie nicht wissen, was lineare Unabhängigkeit ist.

Der Gaußsche Eliminierungsalgorithmus, der zum Lösen linearer Gleichungen verwendet wird, kann bei unsachgemäßer Implementierung numerisch instabil sein. In einigen Fällen müssen Sie sich darüber Gedanken machen. Ohne den Algorithmus zu verstehen, werden Sie nicht wissen, woher das Problem kommt und ob Sie etwas dagegen tun können - nicht auf der Ebene der Algorithmen zum Lösen linearer Gleichungen, sondern auf der Ebene, auf der Sie die richtigen linearen Gleichungen finden.

Kurz gesagt, seien Sie nicht faul und glauben Sie, dass diese Dinge nützlich sind.

Yuval Filmus
quelle
5
"Glauben Sie daran, dass diese Dinge nützlich sind" - kennen wir nicht alle Lehrer, die ihre Vorlesungen mit ihren Lieblingen beladen, ohne sich um den allgemeinen Nutzen zu kümmern? Schüler können den Unterschied nicht wirklich erkennen, aber sie sollten auch nicht blind vertrauen. "Wofür brauche ich das?" ist eine faire Frage, aber "Es ist nur zum Trainieren Ihres Geistes" ist auch eine faire Antwort.
Raphael
9
"sei nicht faul" gibt einen Ton an, der nicht konstruktiv ist. Ich hatte wundervoll neugierige, engagierte und überhaupt nicht faule Studenten, die mir genau diese Frage stellten. Ich denke, eine große Anzahl von CS-Schülern findet, dass der traditionelle Kurs für lineare Algebra Welten ist, die nicht das sind, was sie für nötig halten. Ihre Interessen sind Rechnen und Programmieren und nicht unbedingt Mathematik. Kontext und Motivation zu brauchen oder zu wollen, ist kein Zeichen von Faulheit. Lasst es uns nicht so malen.
Logan Mayfield
@Raphael, Logan Mayfield, wisst ihr überhaupt, wie maschinelles Lernen mit linearer Algebra zusammenhängt? Obwohl Yuval ein wenig spezifisch ist, ist er in Bezug auf die Beispiele, die er erwähnt hat, hier ziemlich zutreffend. Die Frage des OP kann nicht vollständig in nur einem Internetbeitrag beantwortet werden.
musicliftsme
7

Lineare Algebra ist in Graph-Algorithmen manchmal äußerst nützlich und leistungsfähig. Mit dem Matrix-Baum-Theorem können Sie die Anzahl der Spannbäume eines Graphen effizient zählen (Sie müssen Eigenwerte verstehen). Eine herausforderndere Anwendung, bei der Sie die lineare Algebra noch besser verstehen müssen, ist der FKT-Algorithmus zur Berechnung der Anzahl perfekter Übereinstimmungen in einem planaren Graphen in Polynomzeit.

Es gibt viele aufregendere Beispiele für die Verwendung der linearen Algebra in der Theorie der algebraischen Graphen und der Theorie der spektralen Graphen . Die Algorithmen, die entstehen, dienen nicht nur zum Zählen von Problemen, wie die beiden Beispiele, die ich gegeben habe. Sie können beispielsweise auch die Konnektivität überprüfen oder den Durchmesser eines Diagramms berechnen .

Juho
quelle
Man fragt sich, warum man jemals die Anzahl der Bäume oder der perfekten Übereinstimmungen zählen möchte. Wofür ist das gut? Haben Sie eine reale Anwendung im Sinn?
Yuval Filmus
@YuvalFilmus Ich nicht, und es ist vielleicht schwieriger, Anwendungen zu finden, bei denen zunächst Probleme beim Zählen auftreten. Ich denke, beide sind hauptsächlich aus theoretischer Sicht interessant, obwohl der Wiki-Eintrag von FKT etwas Geschichte und Motivation vermittelt. Der wichtigste Punkt ist jedoch, dass die lineare Algebra für die Entwicklung von Graphenalgorithmen nützlich ist und daher in der Informatik Anwendung findet.
Juho
6

Eine der bekanntesten Anwendungen der linearen Algebra ist die von Google Pagerank-Algorithmus von :

Die PageRank-Werte sind die Einträge des dominanten linken Eigenvektors der modifizierten Adjazenzmatrix.

Robert S. Barnes
quelle
3

Nahezu alles, was mit Computergrafik, Animation, Computer Vision, Bildverarbeitung, wissenschaftlichem Rechnen oder Simulation physikalischer Phänomene zu tun hat, erfordert die umfassende Verwendung von Vektoren und Matrizen (lineare Algebra), von einfachen Dingen wie der Darstellung räumlicher Transformationen und Orientierungen bis hin zu sehr komplexen Algorithmen. Früher waren diese Dinge die Domäne des Supercomputers, aber jetzt sind genau diese Bereiche der Kern aller coolsten Apps auf Ihrem Desktop, Ihrem Handy und überall sonst, von Videospielen über Computerfotografie bis hin zu selbstfahrenden Autos. Lineare Algebra ist überall.

Larry Gritz
quelle
2

Es gibt viele Algorithmen und Techniken, die auf der Matrixalgebra basieren. Und das ist großartig. Die Hauptkomponentenanalyse ist ein Beispiel für eine recht nützliche angewandte lineare Algebra. Gleiches gilt für die Fourier-Analyse, deren Wurzeln auch in der Orthogonalität und den inneren Produkten liegen. Es gibt also direkte Anwendungen.

ABER noch wichtiger ist, dass eine lineare Algebra-Klasse wertvoll ist, weil sie Ihnen das Denken in einer bestimmten Art und Weise lehrt. Die meisten guten linearen Algebra-Klassen legen Wert auf Generalisierung, Logik und Beweise. Ist etwas im Allgemeinen wahr oder nur bestimmte spezifische, häufige Fälle? Wie können Sie sicher sein? Überlegen zu können, wie Sie Ihre Annahmen beweisen können, ist gut, da Sie sich dadurch davor schützen, schlechte Annahmen zu treffen und Code zu schreiben, der sich nicht so verallgemeinert, wie Sie es annehmen. Es hilft Ihnen auch beim Überlegen, wie Sie Dinge verallgemeinern können, die ansonsten schwierig zu verallgemeinern wären. Auf diese Weise können Sie größere Probleme lösen.

Zusammenfassend ist zu bedenken, dass lineare Algebra gut ist, weil es das Gewichtheben für den Teil Ihres Gehirns ist, der in der Informatik nützlich ist.

Hunde
quelle
0

Das Lösen eines linearen Gleichungssystems (das mit der Gaußschen Eliminierungsmethode durchgeführt werden kann), des linearen Programmierens (das mit der Simplex-Methode gelöst werden kann), der kleinsten Quadrate und der komprimierten Abtastung (siehe Wikipedia-Artikel) sind praktische Probleme, die in vielen Fällen auftreten Anwendungsbereiche. Die lineare Algebra hilft bei der Entwicklung korrekter und effizienter Algorithmen für diese Probleme.

Siehe den Text [Cormen, Leiserson, Rivest und Stein, "Introduction to Algorithms, Third Edition"], in dem sich Kapitel 28 mit Matrixoperationen und Kapitel 29 mit linearer Programmierung befasst.

Ashwin Ganesan
quelle