algorithm - que - ¿Cómo se usa el álgebra lineal en los algoritmos?
para que sirve el algebra lineal (9)
Por ejemplo, ¿qué cosas interesantes puede uno con una matriz de conectividad para un gráfico?
Muchas propiedades algebraicas de la matriz son invariantes bajo permutaciones de vértices (por ejemplo, abs (determinante)), por lo que si dos gráficas son isomorfas, sus valores serán iguales.
Esta es una fuente de buenas heurísticas para determinar si dos gráficos no son isomorfos, ya que, por supuesto, la igualdad no garantiza la existencia del isomorfismo.
Compruebe la teoría de grafos algebraicos para muchas otras técnicas interesantes.
Varios de mis compañeros han mencionado que el "álgebra lineal" es muy importante al estudiar algoritmos. He estudiado una variedad de algoritmos y he tomado algunos cursos de álgebra lineal y no veo la conexión. Entonces, ¿cómo se usa el álgebra lineal en los algoritmos?
Por ejemplo, ¿qué cosas interesantes puede uno con una matriz de conectividad para un gráfico?
Depende de qué tipo de "algoritmos".
Algunos ejemplos:
- Máquina de aprendizaje / algoritmos de estadística: regresiones lineales (mínimos cuadrados, cresta, lazo).
- Compresión con pérdida de señales y otros procesamientos (reconocimiento facial, etc.). Ver Eigenfaces
Ja, no puedo resistirme a poner esto aquí (aunque las otras respuestas son buenas):
El vector propio de $ 25 mil millones .
No voy a mentir ... ni siquiera leí todo ... tal vez ahora lo haga :-).
Muchos algoritmos de procesamiento de señales se basan en operaciones matriciales, por ejemplo, transformada de Fourier, transformada de Laplace, ...
Los problemas de optimización a menudo se pueden reducir para resolver sistemas de ecuaciones lineales.
No sé si lo expresaría como ''álgebra lineal es muy importante al estudiar algoritmos ". Casi lo expresaría al revés. Muchos, muchos, muchos problemas del mundo real requieren que usted resuelva un problema. conjunto de ecuaciones lineales. Si tiene que abordar uno de esos problemas, necesitará conocer algunos de los muchos algoritmos para tratar con ecuaciones lineales. Muchos de esos algoritmos se desarrollaron cuando las computadoras eran un título de trabajo, no un título. máquina. Considere la eliminación gaussiana y los diversos algoritmos de descomposición matricial, por ejemplo. Hay mucha teoría muy sofisticada sobre cómo resolver esos problemas para matrices muy grandes, por ejemplo.
Los métodos más comunes en el aprendizaje automático terminan teniendo un paso de optimización que requiere resolver un conjunto de ecuaciones simultáneas. Si no sabes álgebra lineal estarás completamente perdido.
Todas las respuestas aquí son buenos ejemplos de álgebra lineal en algoritmos.
Como una meta respuesta, agregaré que podría estar usando el álgebra lineal en sus algoritmos sin saberlo. Los compiladores que optimizan con SSE (2) típicamente vectorizan su código al tener muchos valores de datos manipulados en paralelo. Esto es esencialmente elemental LA.
Tres ejemplos concretos:
- El álgebra lineal es el fundamento de los gráficos 3D modernos. Esto es esencialmente lo mismo que has aprendido en la escuela. Los datos se guardan en un espacio 3D que se proyecta en una superficie 2D, que es lo que ve en su pantalla.
- La mayoría de los motores de búsqueda están basados en álgebra lineal. La idea es representar cada documento como un vector en un espacio hiper y ver cómo el vector se relaciona entre sí en este espacio. Esto es utilizado por el proyecto lucene , entre otros. Ver VSM .
- Algunos algoritmos de compresión modernos, como el que utiliza el formato ogg vorbis, se basan en el álgebra lineal o, más específicamente, en un método llamado cuantificación vectorial .
Básicamente, todo se reduce al hecho de que el álgebra lineal es un método muy poderoso cuando se trata de múltiples variables, y hay enormes ventajas al usar esto como una base teórica al diseñar algoritmos. En muchos casos, esta base no es tan aparente como podría pensarse, pero eso no significa que no esté allí. Es muy posible que ya hayas implementado algoritmos que hubieran sido increíblemente difíciles de obtener sin linalg.
Un criptógrafo probablemente te dirá que un conocimiento de la teoría de los números es muy importante cuando estudias algoritmos. Y tendría razón, por su particular campo. Las estadísticas también tienen sus usos: omitir listas, tablas hash, etc. La utilidad de la teoría de gráficos es aún más obvia.
No hay un vínculo inherente entre el álgebra lineal y los algoritmos; Hay un vínculo inherente entre las matemáticas y los algoritmos.
El álgebra lineal es un campo con muchas aplicaciones, y los algoritmos que se basan en él también tienen muchas aplicaciones. No has perdido tu tiempo estudiándolo.
El álgebra lineal también es importante en muchos algoritmos en álgebra de computadora, como habrás adivinado. Por ejemplo, si puede reducir un problema para decir que un polinomio es cero, donde los coeficientes del polinomio son lineales en las variables x1, …, xn , entonces puede resolver para qué valores de x1, …, xn hacer el polinomio igual a 0 al igualar el coeficiente de cada término x^n a 0 y resolver el sistema lineal. Esto se denomina método de coeficientes indeterminados y se usa, por ejemplo, para calcular descomposiciones de fracciones parciales o para integrar funciones racionales.
Para la teoría de los gráficos, lo mejor de una matriz de adyacencia es que si toma la enésima potencia de una Matriz de adyacencia para un gráfico no ponderado (cada entrada es 0 o 1), M^n , entonces cada entrada i,j será el número de trayectos desde el vértice i al vértice j de longitud n . Y si eso no es simplemente bueno, entonces no sé qué es.