¿Qué partes del álgebra lineal se usan en informática?

15

He estado leyendo Álgebra lineal y sus aplicaciones para ayudar a comprender el material informático (principalmente el aprendizaje automático), pero me preocupa que mucha de la información no sea útil para CS. Por ejemplo, saber cómo resolver eficientemente sistemas de ecuaciones lineales no parece muy útil a menos que esté tratando de programar un nuevo solucionador de ecuaciones. Además, el libro ha hablado mucho sobre la amplitud, la dependencia lineal y la independencia, cuando una matriz tiene un inverso, y las relaciones entre estos, pero no puedo pensar en ninguna aplicación de esto en CS. Entonces, ¿qué partes del álgebra lineal se usan en CS?

Kelmikra
fuente
2
¿Estás pidiendo tu propio beneficio o eres un maestro que busca estrategias para motivar a tus alumnos?
Raphael
El álgebra lineal es útil en muchas partes de los gráficos de computadora (puede encontrar mucha información relacionada buscando en Google).
Juho
Resolver sistemas de ecuaciones lineales es increíblemente útil en informática. Por ejemplo: en.m.wikipedia.org/wiki/Combinatorial_optimization
Ant P
1
Las matrices se usan mucho en el desarrollo de juegos, IE para proyecciones, rotaciones y matemáticas de cuaterniones.
Paul
@Paulpro La pregunta es para aplicaciones de álgebra lineal (un cuerpo de trabajo), no matrices (un conjunto de objetos).
Raphael

Respuestas:

11

Las partes que mencionó son conceptos básicos de álgebra lineal. No puede comprender los conceptos más avanzados (digamos, valores propios y vectores propios) antes de comprender primero los conceptos básicos. No hay atajos en las matemáticas. Sin una comprensión intuitiva de los conceptos de amplitud e independencia lineal, no llegarás lejos en álgebra lineal.

Algunos algoritmos solo funcionan con matrices de rango completo. ¿Sabes lo que eso significa? ¿Sabes qué puede hacer que una matriz no sea de rango completo? ¿Cómo manejar esto? No tendrá idea si no sabe qué es la independencia lineal.

El algoritmo de eliminación gaussiano que se usa para resolver ecuaciones lineales en realidad puede ser numéricamente inestable si se implementa de manera incorrecta, y esto es algo de lo que puede tener que preocuparse en algunos casos. Sin comprender el algoritmo, no sabrá de dónde viene el problema y si hay algo que pueda hacer al respecto, no a nivel de algoritmos para resolver ecuaciones lineales, sino a nivel de encontrar las ecuaciones lineales correctas para resolver.

En resumen, no seas perezoso, y ten fe en que estas cosas son útiles.

Yuval Filmus
fuente
55
"confía en que estas cosas son útiles", bueno, ¿no conocemos a todos los maestros que cargan sus conferencias con sus seres queridos sin preocuparse por la utilidad general? Los estudiantes realmente no pueden notar la diferencia, pero tampoco deben confiar ciegamente. "¿Para qué necesitaré esto?" es una pregunta justa, pero "Es solo para entrenar tu mente" también es una respuesta justa.
Raphael
99
"No seas perezoso" establece un tono que no es constructivo. He tenido alumnos maravillosamente inquisitivos, comprometidos y nada perezosos que me hagan esta misma pregunta. Creo que una gran población de estudiantes de CS encuentra que la clase tradicional de Álgebra Lineal es un mundo aparte de lo que creen que necesitan. Sus intereses son la informática y la programación y no necesariamente las matemáticas. Necesitar o querer algo de contexto y motivación no es un signo de pereza. No lo pintemos como tal.
Logan Mayfield
@Raphael, Logan Mayfield, ¿saben ustedes cómo el aprendizaje automático se relaciona con el álgebra lineal? Aunque es un poco específico, Yuval es bastante puntual aquí en los ejemplos que ha mencionado. La pregunta del OP no se puede responder completamente en una sola publicación de Internet.
musicliftsme
7

El álgebra lineal a veces es extremadamente útil y potente en algoritmos gráficos. Con el teorema del árbol de la matriz, puede contar eficientemente el número de árboles de expansión que tiene un gráfico (debe comprender los valores propios). Una aplicación más desafiante, donde necesita una comprensión aún más firme del álgebra lineal es el algoritmo FKT para calcular el número de coincidencias perfectas en un gráfico plano en tiempo polinómico.

Hay muchos más ejemplos interesantes de usos del álgebra lineal en la teoría de grafos algebraicos y la teoría de grafos espectrales . Los algoritmos que surgen no son solo para contar problemas como los dos ejemplos que di. Por ejemplo, también puede verificar la conectividad o calcular el diámetro de un gráfico .

Juho
fuente
Uno se pregunta por qué querría contar la cantidad de árboles que se extienden o de combinaciones perfectas. ¿Para qué es bueno esto? ¿Tienes en mente una aplicación del mundo real?
Yuval Filmus
@YuvalFilmus no, y para empezar es quizás más difícil encontrar aplicaciones de problemas de conteo. Creo que ambos son interesantes principalmente desde una perspectiva teórica, aunque la entrada wiki de FKT ofrece algo de historia y motivación. De todos modos, el punto principal es que el álgebra lineal es útil para desarrollar algoritmos gráficos y, por lo tanto, tiene aplicaciones en informática.
Juho
6

Uno de los usos más conocidos del álgebra lineal es el algoritmo Pagerank de Google :

Los valores de PageRank son las entradas del vector propio izquierdo dominante de la matriz de adyacencia modificada.

Robert S. Barnes
fuente
3

Casi todo lo relacionado con gráficos por computadora, animación, visión por computadora, procesamiento de imágenes, computación científica o simulación de fenómenos físicos implicará un uso extensivo de vectores y matrices (álgebra lineal) desde cosas simples como representar transformaciones y orientaciones espaciales, hasta algoritmos muy complejos. Estas cosas solían ser el dominio de la supercomputación, pero ahora estos mismos campos son el núcleo de todas las aplicaciones más geniales en su escritorio, teléfonos y en cualquier otro lugar, desde videojuegos hasta fotografía computacional y autos sin conductor. El álgebra lineal está en todas partes.

Larry Gritz
fuente
2

Existen muchos algoritmos y técnicas basados ​​en álgebra matricial. Y eso es genial. El análisis de componentes principales es un ejemplo de álgebra lineal aplicada bastante útil. Lo mismo puede decirse sobre el análisis de Fourier, que también tiene sus raíces en la ortogonalidad y los productos internos. Entonces hay aplicaciones directas.

PERO , aún más importante, tomar una clase de álgebra lineal es valioso porque te enseña a pensar de cierta manera. La mayoría de las buenas clases de álgebra lineal ponen énfasis en la generalización, la lógica y las pruebas. ¿Es algo cierto en general, o solo ciertos casos específicos y comunes? ¿Cómo puedes estar seguro? Ser capaz de pensar en cómo probar sus suposiciones es bueno porque te ayuda a evitar hacer malas suposiciones y escribir código que no se generalice en la forma en que asumes que lo hace. También le ayuda a pensar en cómo generalizar cosas que de otro modo serían difíciles de generalizar, y eso le permite resolver problemas más grandes.

En resumen, es bueno tener en cuenta que el álgebra lineal es bueno porque el levantamiento de pesas para la parte del cerebro es útil en informática.

Perros
fuente
0

La resolución de un sistema de ecuaciones lineales (que se puede hacer con el método de eliminación gaussiana), la programación lineal (que se puede resolver con el método simplex), los mínimos cuadrados y la detección comprimida (consulte el artículo de Wikipedia) son problemas prácticos que surgen en muchos Áreas de aplicación. El álgebra lineal ayuda a desarrollar algoritmos correctos y eficientes para estos problemas.

Consulte el texto [Cormen, Leiserson, Rivest y Stein, "Introducción a los algoritmos, tercera edición"], donde el Capítulo 28 trata sobre operaciones matriciales y el Capítulo 29 sobre programación lineal.

Ashwin Ganesan
fuente