Comment l'algèbre linéaire est-elle utilisée dans les algorithmes?

un cryptographe vous dirait probablement qu'une compréhension de la théorie des nombres est très importante lors de l'étude des algorithmes. Et il aurait raison...pour son domaine particulier. Les statistiques ont aussi leur utilité:listes de sauts, tables de hachage, etc. L'utilité de la théorie des graphes est encore plus évident.

il n'y a pas de lien inhérent entre l'algèbre linéaire et les algorithmes; il y a un lien inhérent entre mathématiques et des algorithmes.

L'algèbre linéaire est un domaine avec de nombreux les applications et les algorithmes qui s'en inspirent ont donc aussi de nombreuses applications. Vous n'avez pas perdu votre temps à étudier.

Ha, je ne peux pas résister à mettre cela ici (même si les autres réponses sont bonnes):

Le 25 milliards de dollars vecteur propre.

je ne vais pas mentir... Je n'ai même jamais lu en entier... peut-être que je vais maintenant :-).

Je ne sais pas si je dirais que"l'algèbre linéaire est très importante dans l'étude des algorithmes". Je l'avais presque le mettre dans l'autre sens. Beaucoup, beaucoup, beaucoup dans le monde réel, problèmes de vous obliger à résoudre un ensemble d'équations linéaires. Si vous finissez par avoir à s'attaquer à l'un de ces problèmes, vous aurez besoin de connaître quelques-uns des nombreux algorithmes pour traiter les équations linéaires. Beaucoup de ces algorithmes ont été développés quand les ordinateurs étaient un titre de travail, pas une machine. Envisager gaussien l'élimination et les divers algorithmes de décomposition matricielle par exemple. Il y a un beaucoup de théorie très sophistiquée sur la façon de résoudre ces problèmes pour de très grandes matrices par exemple.

les méthodes les plus courantes dans l'apprentissage machine finissent par avoir une étape d'optimisation qui nécessite la résolution d'un ensemble d'équations simultanées. Si vous ne connaissez pas l'algèbre linéaire, vous serez complètement perdu.

de nombreux algorithmes de traitement des signaux sont basés sur des opérations matricielles, par exemple la Transformée de Fourier, la Transformée de Laplace ...

les problèmes D'optimisation se réduisent souvent à la résolution de systèmes d'équations linéaires.

L'algèbre linéaire est également importante dans de nombreux algorithmes de l'algèbre informatique, comme vous pourriez l'avoir deviné. Par exemple, si vous pouvez réduire un problème à dire qu'un polynôme est égal à zéro, où les coefficients du polynôme sont linéaires dans les variables x1, …, xn, vous pouvez résoudre pour quelles valeurs de x1, …, xn faire le polynôme égal à 0 en égalisant le coefficient de chaque x^n terme à 0 et résolution du système linéaire. Cela s'appelle la méthode des coefficients indéterminés, et est utilisé par exemple pour calculer des décompositions partielles de fractions ou pour intégrer des fonctions rationnelles.

pour la théorie des graphes, la chose la plus cool à propos d'une matrice de contiguïté est que si vous prenez la puissance nième D'une matrice de contiguïté pour un graphe non pondéré (chaque entrée est soit 0 ou 1), M^n, puis chaque entrée i,j sera le nombre de chemins à partir du sommet i sommet j longueur n. Et si ce n'est pas juste cool, alors je ne sais pas ce que c'est.

Toutes les réponses ici sont de bons exemples de l'algèbre linéaire dans les algorithmes.

en méta-réponse, j'ajouterai que vous pourriez utiliser l'algèbre linéaire dans vos algorithmes sans le savoir. Les compilateurs qui optimisent avec SSE (2) vectorisent typiquement votre code en ayant de nombreuses valeurs de données manipulées en parallèle. C'est essentiellement de L'al élémentaire.

cela dépend du type d '"algorithmes".

Quelques exemples:

• algorithmes D'apprentissage automatique/statistiques: régressions linéaires (moindres carrés, crête, lasso).
• compression avec perte de signaux et autres traitements (reconnaissance faciale, etc.). Voir Eigenfaces

par exemple, quelles choses intéressantes peut-on faire avec une matrice de connectivité pour un graphique?

beaucoup de propriétés algébriques de la matrice sont invariantes sous des permutations de Sommets (par exemple abs(déterminant)), donc si deux graphiques sont isomorphiques, leurs valeurs seront égales.

C'est une source de bonnes heuristiques pour déterminer si deux graphes isomorphe, car évidemment l'égalité ne garantit pas l'existence d' isomorphisme.

Case théorie algébrique des graphes pour beaucoup d'autres techniques intéressantes.