Quelles parties de l'algèbre linéaire sont utilisées en informatique?

15

J'ai lu l'algèbre linéaire et ses applications pour aider à comprendre le matériel informatique (principalement l'apprentissage automatique), mais je crains que beaucoup d'informations ne soient pas utiles à CS. Par exemple, savoir comment résoudre efficacement des systèmes d'équations linéaires ne semble pas très utile, sauf si vous essayez de programmer un nouveau solveur d'équations. De plus, le livre a beaucoup parlé de la durée, de la dépendance linéaire et de l'indépendance, lorsqu'une matrice a un inverse, et des relations entre ceux-ci, mais je ne peux penser à aucune application de cela dans CS. Alors, quelles parties de l'algèbre linéaire sont utilisées dans CS?

Kelmikra
la source
2
Demandez-vous votre propre avantage ou êtes-vous un enseignant à la recherche de stratégies pour motiver vos élèves?
Raphael
L'algèbre linéaire est utile dans de nombreuses parties de l'infographie (vous pouvez trouver beaucoup d'informations connexes sur Google).
Juho
La résolution de systèmes d'équations linéaires est extrêmement utile en informatique. Par exemple: en.m.wikipedia.org/wiki/Combinatorial_optimization
Ant P
1
Les matrices sont largement utilisées dans le développement de jeux, IE pour les projections, les rotations et les mathématiques du quaternion.
Paul
@Paulpro La question concerne les applications de l'algèbre linéaire (un ensemble d'œuvres), et non des matrices (un ensemble d'objets).
Raphael

Réponses:

11

Les parties que vous avez mentionnées sont des concepts de base de l'algèbre linéaire. Vous ne pouvez pas comprendre les concepts les plus avancés (par exemple, les valeurs propres et les vecteurs propres) avant d'avoir d'abord compris les concepts de base. Il n'y a pas de raccourcis en mathématiques. Sans une compréhension intuitive des concepts de durée et d'indépendance linéaire, vous n'irez pas loin en algèbre linéaire.

Certains algorithmes ne fonctionnent qu'avec des matrices de rang complet - Savez-vous ce que cela signifie? Savez-vous ce qui peut rendre une matrice non complète? Comment gérer ça? Vous n'aurez aucune idée si vous ne savez pas ce qu'est l'indépendance linéaire.

L'algorithme d'élimination gaussien utilisé pour résoudre les équations linéaires peut en fait être numériquement instable s'il n'est pas mis en œuvre correctement, et c'est quelque chose dont vous pourriez avoir à vous soucier dans certains cas. Sans comprendre l'algorithme, vous ne saurez pas d'où vient le problème et si vous pouvez y faire quelque chose - pas au niveau des algorithmes pour résoudre les équations linéaires, mais au niveau de trouver les équations linéaires correctes à résoudre.

En bref, ne soyez pas paresseux et croyez que ces choses sont utiles.

Yuval Filmus
la source
5
"croyez que ces choses sont utiles" - eh bien, ne connaissons-nous pas tous des enseignants qui chargent leurs cours avec leurs chéris sans se soucier de l'utilité générale? Les étudiants ne peuvent pas vraiment faire la différence, mais ils ne devraient pas non plus faire confiance aveuglément. "De quoi aurai-je besoin?" est une bonne question, mais "c'est juste pour former votre esprit" est aussi une bonne réponse.
Raphael
9
"ne soyez pas paresseux" donne un ton qui n'est pas constructif. J'ai eu des étudiants merveilleusement curieux, engagés et pas du tout paresseux qui me posent cette question. Je pense qu'une grande population d'étudiants CS trouve que la classe d'algèbre linéaire traditionnelle est un monde en dehors de ce dont ils pensent avoir besoin. Leurs intérêts sont l'informatique et la programmation et pas nécessairement les mathématiques. Avoir besoin ou vouloir un peu de contexte et de motivation n'est pas un signe de paresse. Ne le peignons pas comme tel.
Logan Mayfield
@Raphael, Logan Mayfield, savez-vous même comment l'apprentissage automatique est lié à l'algèbre linéaire? Bien qu'un peu précis, Yuval est assez précis sur les exemples qu'il a mentionnés. Il n'est pas possible de répondre pleinement à la question du PO dans un seul message Internet.
musicliftsme
7

L'algèbre linéaire est parfois extrêmement utile et puissante dans les algorithmes de graphes. Avec le théorème de l'arbre matriciel, vous pouvez compter efficacement le nombre d'arbres couvrant un graphique (vous devez comprendre les valeurs propres). Une application plus difficile, où vous avez besoin d'une compréhension encore plus ferme de l'algèbre linéaire est l' algorithme FKT pour calculer le nombre de correspondances parfaites dans un graphe planaire en temps polynomial.

Il existe de nombreux autres exemples passionnants d'utilisations de l'algèbre linéaire dans la théorie des graphes algébriques et la théorie des graphes spectraux . Les algorithmes qui se posent ne sont pas seulement pour compter des problèmes comme les deux exemples que j'ai donnés. Par exemple, vous pouvez également vérifier la connectivité ou calculer le diamètre d'un graphique .

Juho
la source
On se demande pourquoi on voudrait jamais compter le nombre de travées ou de correspondances parfaites. À quoi cela sert-il? Vous avez une application concrète en tête?
Yuval Filmus
@YuvalFilmus non, et il est peut-être plus difficile de trouver des applications de problèmes de comptage pour commencer. Je pense que les deux sont intéressants principalement d'un point de vue théorique, bien que l' entrée wiki de FKT donne un peu d'histoire et de motivation. Quoi qu'il en soit, le point principal est que l'algèbre linéaire est utile pour développer des algorithmes de graphes, et a donc des applications en informatique.
Juho
6

L'une des utilisations les plus connues de l'algèbre linéaire est dans l' algorithme Pagerank de Google :

Les valeurs du PageRank sont les entrées du vecteur propre gauche dominant de la matrice d'adjacence modifiée.

Robert S. Barnes
la source
3

Presque tout ce qui concerne l'infographie, l'animation, la vision par ordinateur, le traitement d'image, le calcul scientifique ou la simulation de phénomènes physiques impliquera une utilisation intensive de vecteurs et de matrices (algèbre linéaire) allant de choses simples comme la représentation de transformations et d'orientations spatiales à des algorithmes très complexes. Ces choses étaient autrefois le domaine du calcul intensif, mais maintenant ces mêmes domaines sont au cœur de toutes les applications les plus cool sur votre bureau, vos téléphones et partout ailleurs, des jeux vidéo à la photographie informatique en passant par les voitures autonomes. L'algèbre linéaire est partout.

Larry Gritz
la source
2

Il existe de nombreux algorithmes et techniques basés sur l'algèbre matricielle. Et c'est super. L'analyse en composantes principales est un exemple d'algèbre linéaire appliquée assez utile. On peut en dire autant de l'analyse de Fourier, qui trouve également ses racines dans l'orthogonalité et les produits internes. Il y a donc des applications directes.

MAIS , plus important encore, prendre un cours d'algèbre linéaire est précieux car il vous apprend à penser d'une certaine manière. La plupart des bonnes classes d'algèbre linéaire mettent l'accent sur la généralisation, la logique et les preuves. Y a-t-il quelque chose de vrai en général, ou seulement certains cas spécifiques spécifiques? Comment pouvez-vous en être certain? Pouvoir réfléchir à la façon de prouver vos hypothèses est bon car cela vous aide à ne pas faire de mauvaises hypothèses et à écrire du code qui ne se généralise pas comme vous le supposez. Cela vous aide également à réfléchir à la façon de généraliser des choses qui pourraient autrement être difficiles à généraliser, et cela vous permet de résoudre des problèmes plus importants.

En résumé, il est bon de garder à l'esprit que l'algèbre linéaire est bonne, car c'est l'haltérophilie pour la partie de votre cerveau qui est utile en informatique.

Chiens
la source
0

La résolution d'un système d'équations linéaires (ce qui peut être fait avec la méthode d'élimination gaussienne), la programmation linéaire (qui peut être résolue avec la méthode simplex), les moindres carrés et la détection compressée (voir l'article Wikipedia) sont des problèmes pratiques qui se posent dans de nombreux zone d'application. L'algèbre linéaire aide à développer des algorithmes corrects et efficaces pour ces problèmes.

Voir le texte [Cormen, Leiserson, Rivest et Stein, "Introduction to Algorithms, Third Edition"], où le chapitre 28 est consacré aux opérations matricielles et le chapitre 29 à la programmation linéaire.

Ashwin Ganesan
la source