Jakie części algebry liniowej są używane w informatyce?

15

Czytam Algebrę liniową i jej aplikacje, aby pomóc w zrozumieniu materiałów informatycznych (głównie uczenia maszynowego), ale martwię się, że wiele informacji nie jest użytecznych dla CS. Na przykład wiedza o tym, jak skutecznie rozwiązywać układy równań liniowych, nie wydaje się bardzo przydatna, chyba że próbujesz zaprogramować nowy układ równań. Dodatkowo, książka dużo mówiła o rozpiętości, liniowej zależności i niezależności, kiedy macierz ma odwrotność, i relacjach między nimi, ale nie mogę wymyślić żadnego zastosowania tego w CS. Jakie części algebry liniowej są używane w CS?

— Kelmikra
źródło

2

Czy prosisz o własne korzyści, czy jesteś nauczycielem poszukującym strategii motywowania uczniów?

— Raphael

Algebra liniowa jest przydatna w wielu częściach grafiki komputerowej (można znaleźć wiele powiązanych informacji w Google).

— Juho

Rozwiązywanie układów równań liniowych jest niezwykle przydatne w informatyce. Na przykład: en.m.wikipedia.org/wiki/Combinatorial_optimization

— Ant P

1

Matryce są szeroko stosowane w tworzeniu gier, IE do projekcji, rotacji i matematyki czwartorzędu.

— Paul

@Paulpro Pytanie dotyczy zastosowań algebry liniowej (bryły pracy), a nie macierzy (zestawu obiektów).

— Raphael

11

Wspomniane części są podstawowymi pojęciami algebry liniowej. Nie można zrozumieć bardziej zaawansowanych pojęć (na przykład wartości własnych i wektorów własnych) przed pierwszym zrozumieniem podstawowych pojęć. W matematyce nie ma skrótów. Bez intuicyjnego zrozumienia pojęć zakresu i niezależności liniowej nie zajdziesz daleko w algebrze liniowej.

Niektóre algorytmy działają tylko z macierzami pełnej rangi - czy wiesz, co to oznacza? Czy wiesz, co może sprawić, że matryca nie będzie pełna? Jak sobie z tym poradzić? Nie będziesz miał pojęcia, jeśli nie wiesz, czym jest liniowa niezależność.

Algorytm eliminacji Gaussa, który jest używany do rozwiązywania równań liniowych, może być niestabilny numerycznie, jeśli zostanie nieprawidłowo zaimplementowany, i w niektórych przypadkach możesz się martwić. Bez zrozumienia algorytmu nie wiadomo, skąd pochodzi problem i czy można coś z tym zrobić - nie na poziomie algorytmów rozwiązywania równań liniowych, ale na poziomie wymyślania poprawnych równań liniowych do rozwiązania.

Krótko mówiąc, nie bądź leniwy i wierz, że te rzeczy są przydatne.

— Yuval Filmus
źródło

5

„wierzcie, że te rzeczy są przydatne” - cóż, czy nie wszyscy znamy nauczycieli, którzy ładują swoje wykłady swoimi ulubieńcami, nie dbając o ogólną użyteczność? Uczniowie tak naprawdę nie potrafią odróżnić, ale nie powinni też ślepo ufać. „Do czego będę tego potrzebować?” jest uczciwym pytaniem, ale „To tylko dla treningu umysłu” jest również uczciwą odpowiedzią.

— Raphael

9

„nie bądź leniwy” nadaje ton niekonstruktywny. Cudownie dociekliwi, zaangażowani i wcale nie leniwi studenci zadają mi to właśnie pytanie. Myślę, że duża populacja studentów CS uważa, że tradycyjna klasa Algebry Liniowej to światy poza tym, co ich zdaniem potrzebują. Ich zainteresowania to informatyka i programowanie, a niekoniecznie matematyka. Potrzebowanie kontekstu i motywacji nie jest oznaką lenistwa. Nie malujmy tego jako takiego.

— Logan Mayfield

@Raphael, Logan Mayfield, czy wiecie, jak uczenie maszynowe odnosi się do algebry liniowej? Chociaż jest trochę konkretny, Yuval jest bardzo trafny w przykłady, o których wspomniał. Na pytanie PO nie można w pełni odpowiedzieć w jednym poście internetowym.

— musicliftsme

7

Algebra liniowa jest czasem niezwykle przydatna i wydajna w algorytmach graficznych. Za pomocą twierdzenia o macierzy-drzewie możesz skutecznie policzyć liczbę drzew rozpinających na wykresie (musisz zrozumieć wartości własne). Bardziej wymagającym zastosowaniem, w którym potrzebujesz jeszcze mocniejszego zrozumienia algebry liniowej, jest algorytm FKT do obliczania liczby idealnych dopasowań na wykresie planarnym w czasie wielomianowym.

Istnieje wiele innych ekscytujących przykładów zastosowań algebry liniowej w teorii grafów algebraicznych i teorii grafów spektralnych . Algorytmy, które powstają, służą nie tylko do liczenia problemów, jak dwa przykłady, które podałem. Możesz na przykład sprawdzić łączność lub obliczyć średnicę wykresu .

— Juho
źródło

Zastanawia się, dlaczego kiedykolwiek chciałby policzyć liczbę drzew łączących lub idealnie dopasowanych. Do czego to służy? Czy masz na myśli aplikację w świecie rzeczywistym?

— Yuval Filmus

@YuvalFilmus Nie wiem i na początek może być trudniej wymyślić aplikacje z liczeniem problemów. Myślę, że oba są interesujące głównie z teoretycznego punktu widzenia, chociaż wpis FKT na wiki daje pewną historię i motywację. W każdym razie głównym punktem jest to, że algebra liniowa jest przydatna do opracowywania algorytmów grafowych, a zatem ma zastosowanie w informatyce.

— Juho

6

Jednym z najbardziej znanych zastosowań algebry liniowej jest algorytm Google Pagerank :

Wartości PageRank są wpisami dominującego lewego wektora własnego zmodyfikowanej macierzy przylegania.

— Robert S. Barnes
źródło

3

Niemal wszystko, co obejmuje grafikę komputerową, animację, wizję komputerową, przetwarzanie obrazu, obliczenia naukowe lub symulację zjawisk fizycznych, będzie wymagało szerokiego zastosowania wektorów i matryc (algebry liniowej) od prostych rzeczy, takich jak reprezentacja przekształceń przestrzennych i orientacji, po bardzo złożone algorytmy. Te rzeczy były kiedyś domeną superkomputerów, ale teraz te same pola są rdzeniem wszystkich najfajniejszych aplikacji na komputerze, telefonach i wszędzie indziej, od gier wideo przez fotografię komputerową po samochody samobieżne. Algebra liniowa jest wszędzie.

— Larry Gritz
źródło

2

Istnieje wiele algorytmów i technik opartych na algebrze macierzowej. I to świetnie. Analiza głównego składnika jest przykładem dość użytej stosowanej algebry liniowej. To samo można powiedzieć o analizie Fouriera, która ma również swoje korzenie w ortogonalności i produktach wewnętrznych. Istnieją więc bezpośrednie aplikacje.

ALE , co jeszcze ważniejsze, uczenie się algebry liniowej jest cenne, ponieważ uczy, jak myśleć w określony sposób. Większość dobrych klas algebry liniowej kładzie nacisk na uogólnienie, logikę i dowody. Czy coś jest prawdą ogólnie, czy tylko w niektórych konkretnych, powszechnych przypadkach? Jak możesz być pewien? Możliwość pomyślenia, jak udowodnić swoje założenia, jest dobra, ponieważ pomaga powstrzymać się od robienia złych założeń i pisania kodu, który nie jest generalny w sposób, w jaki zakładasz. Pomaga również zastanowić się, jak uogólnić rzeczy, które w innym przypadku mogłyby być trudne do uogólnienia, i które pozwalają rozwiązać większe problemy.

Podsumowując, należy pamiętać, że algebra liniowa jest dobra, ponieważ podnosi ciężar części mózgu, która jest przydatna w informatyce.

— Psy
źródło

0

Rozwiązywanie układu równań liniowych (które można wykonać metodą eliminacji Gaussa), programowanie liniowe (które można rozwiązać metodą simpleks), najmniejszych kwadratów i detekcja skompresowana (patrz artykuł z Wikipedii) to praktyczne problemy, które pojawiają się w wielu obszary zastosowania. Algebra liniowa pomaga w opracowaniu poprawnych i wydajnych algorytmów dla tych problemów.

Zobacz tekst [Cormen, Leiserson, Rivest i Stein, „Wprowadzenie do algorytmów, wydanie trzecie”], w którym rozdział 28 dotyczy operacji na macierzach, a rozdział 29 dotyczy programowania liniowego.

— Ashwin Ganesan
źródło