Que partes da álgebra linear são usadas na ciência da computação?

15

Eu tenho lido a Álgebra Linear e seus Aplicativos para ajudar a entender o material da ciência da computação (principalmente aprendizado de máquina), mas estou preocupado que muitas informações não sejam úteis para o CS. Por exemplo, saber como resolver com eficiência sistemas de equações lineares não parece muito útil, a menos que você esteja tentando programar um novo solucionador de equações. Além disso, o livro falou muito sobre extensão, dependência linear e independência, quando uma matriz tem um inverso e as relações entre eles, mas não consigo pensar em nenhuma aplicação disso no CS. Então, quais partes da álgebra linear são usadas no CS?

Kelmikra
fonte
2
Você está pedindo seu próprio benefício ou é professor procurando estratégias para motivar seus alunos?
Raphael
A álgebra linear é útil em muitas partes da computação gráfica (você pode encontrar muitas informações relacionadas no Google).
Juho 02/02
A resolução de sistemas de equações lineares é incrivelmente útil na ciência da computação. Por exemplo: en.m.wikipedia.org/wiki/Combinatorial_optimization
Ant P
1
Matrizes são muito usadas no desenvolvimento de jogos, IE para projeções, rotações e matemática de quaternário.
Paul
@Paulpro A questão é para aplicações de álgebra linear (um corpo de trabalho), não matrizes (um conjunto de objetos).
Raphael

Respostas:

11

As partes que você mencionou são conceitos básicos de álgebra linear. Você não pode entender os conceitos mais avançados (por exemplo, autovalores e autovetores) antes de entender primeiro os conceitos básicos. Não há atalhos em matemática. Sem uma compreensão intuitiva dos conceitos de extensão e independência linear, você não chegará muito longe na álgebra linear.

Alguns algoritmos funcionam apenas com matrizes de classificação completa - Você sabe o que isso significa? Você sabe o que pode fazer com que uma matriz não seja uma classificação completa? Como lidar com isso? Você não terá idéia se não souber o que é independência linear.

O algoritmo de eliminação gaussiano usado para resolver equações lineares pode ser numericamente instável se implementado incorretamente, e isso é algo com que você pode se preocupar em alguns casos. Sem entender o algoritmo, você não saberá de onde vem o problema e se há algo que possa ser feito - não no nível dos algoritmos para resolver equações lineares, mas no nível de encontrar as equações lineares corretas para resolver.

Em resumo, não seja preguiçoso e acredite que essas coisas são úteis.

Yuval Filmus
fonte
5
"acredite que essas coisas são úteis" - bem, todos nós conhecemos professores que carregam suas palestras com seus queridos sem se preocupar com a utilidade geral? Os alunos não podem realmente dizer a diferença, mas também não devem confiar cegamente. "Para que vou precisar disso?" é uma pergunta justa, mas "É apenas para treinar sua mente" também é uma resposta justa.
Raphael
9
"não seja preguiçoso" define um tom que não é construtivo. Tive alunos maravilhosamente curiosos, engajados e nem um pouco preguiçosos que me fizeram essa pergunta. Eu acho que uma grande população de estudantes de CS considera a aula tradicional de Álgebra Linear um mundo à parte do que eles acham que precisam. Seus interesses são computação e programação e não necessariamente matemática. Necessitar ou desejar algum contexto e motivação não é sinal de preguiça. Não vamos pintar como tal.
Logan Mayfield #
@Raphael, Logan Mayfield, vocês sabem como o aprendizado de máquina se relaciona à álgebra linear? Embora um pouco específico, Yuval é bastante direto aqui nos exemplos que ele mencionou. A pergunta do OP não pode ser totalmente respondida em apenas uma publicação na Internet.
Musicliftsme
7

Álgebra linear às vezes é extremamente útil e poderosa em algoritmos de gráficos. Com o teorema da árvore matricial, é possível contar com eficiência o número de árvores de abrangência que um gráfico possui (é necessário entender os autovalores). Uma aplicação mais desafiadora, onde você precisa de uma compreensão ainda mais firme da álgebra linear é o algoritmo FKT para calcular o número de combinações perfeitas em um gráfico planar em tempo polinomial.

Existem muitos exemplos mais interessantes de usos da álgebra linear na teoria dos grafos algébricos e na teoria dos grafos espectrais . Os algoritmos que surgem não são apenas para contar problemas como os dois exemplos que eu dei. Por exemplo, você também pode verificar a conectividade ou calcular o diâmetro de um gráfico .

Juho
fonte
Alguém se pergunta por que alguém iria querer contar o número de árvores abrangidas ou de combinações perfeitas. Para que serve isso? Você tem uma aplicação do mundo real em mente?
Yuval Filmus 02/03
@YuvalFilmus Eu não, e talvez seja mais difícil criar aplicativos de problemas de contagem para começar. Eu acho que ambos são interessantes principalmente de uma perspectiva teórica, embora a entrada do FKT no wiki dê alguma história e motivação. De qualquer forma, o ponto principal é que a álgebra linear é útil para o desenvolvimento de algoritmos de grafos e, portanto, tem aplicações na ciência da computação.
Juho
6

Um dos usos mais conhecidos da álgebra linear está no algoritmo Pagerank do Google :

Os valores PageRank são as entradas do autovetor esquerdo dominante da matriz de adjacência modificada.

Robert S. Barnes
fonte
3

Quase tudo o que envolve computação gráfica, animação, visão computacional, processamento de imagens, computação científica ou simulação de fenômenos físicos envolverá o uso extensivo de vetores e matrizes (álgebra linear), desde coisas simples como representar transformações e orientações espaciais até algoritmos muito complexos. Essas coisas costumavam ser o domínio da supercomputação, mas agora esses mesmos campos são o núcleo de todos os aplicativos mais legais em seu desktop, telefones e em qualquer outro lugar, de videogames a fotografia computacional e carros autônomos. Álgebra linear está em toda parte.

Larry Gritz
fonte
2

Existem muitos algoritmos e técnicas baseados em álgebra matricial por aí. E isso é ótimo. A análise de componentes principais é um exemplo de uma álgebra linear aplicada bastante útil. O mesmo pode ser dito sobre a análise de Fourier, que também tem raízes na ortogonalidade e nos produtos internos. Portanto, existem aplicativos diretos.

MAS , ainda mais importante, ter uma aula de álgebra linear é valioso porque ensina você a pensar de uma certa maneira. A maioria das boas aulas de álgebra linear enfatiza generalização, lógica e provas. Algo é verdade em geral, ou apenas alguns casos comuns específicos? Como você pode ter certeza? Ser capaz de pensar em como provar suas suposições é bom porque ajuda a evitar suposições ruins e a escrever códigos que não se generalizam da maneira que você supõe. Também ajuda a pensar em como generalizar coisas que, de outra forma, podem ser difíceis de generalizar, e que permitem resolver problemas maiores.

Em resumo, é bom ter em mente que a álgebra linear é boa porque é o levantamento de peso para a parte do cérebro que é útil na ciência da computação.

Cães
fonte
0

Resolver um sistema de equações lineares (que pode ser feito com o método de eliminação gaussiano), programação linear (que pode ser resolvida com o método simplex), mínimos quadrados e detecção compactada (consulte o artigo da Wikipedia) são problemas práticos que surgem em muitos Áreas de aplicação. A álgebra linear ajuda no desenvolvimento de algoritmos corretos e eficientes para esses problemas.

Veja o texto [Cormen, Leiserson, Rivest e Stein, "Introdução aos Algoritmos, Terceira Edição"], em que o Capítulo 28 trata de operações matriciais e o Capítulo 29 trata de programação linear.

Ashwin Ganesan
fonte