알고리즘에서 선형 대수는 어떻게 사용됩니까?
https://stackoverflow.com/questions/1085425
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
내 동료 중 일부는 알고리즘을 연구 할 때 "선형 대수"가 매우 중요하다고 언급했습니다. 다양한 알고리즘을 연구하고 몇 가지 선형 대수 코스를 수강했지만 연결이 보이지 않습니다. 그렇다면 선형 대수는 알고리즘에서 어떻게 사용됩니까?
예를 들어 그래프의 연결 행렬을 가진 흥미로운 것들은 무엇입니까?
해결책
세 가지 구체적인 예 :
- 선형 대수는 현대 3D 그래픽의 기초입니다. 이것은 본질적으로 학교에서 배운 것과 동일합니다. 데이터는 2D 표면에 투사되는 3D 공간으로 유지되며 화면에 표시됩니다.
- 대부분의 검색 엔진은 선형 대수를 기반으로합니다. 아이디어는 각 문서를 하이퍼 공간에서 벡터로 표현 하고이 공간에서 벡터가 서로 어떻게 관련되는지 확인하는 것입니다. 이것은 루센 프로젝트, 다른 것 중에서도. 보다 VSM.
- Ogg Vorbis 형식에서 사용하는 것과 같은 일부 최신 압축 알고리즘은 선형 대수 또는 더 구체적으로라는 메소드를 기반으로합니다. 벡터 양자화.
기본적으로 선형 대수는 여러 변수를 다룰 때 매우 강력한 방법이며 알고리즘을 설계 할 때 이론적 기초로 사용하는 데 큰 이점이 있습니다. 많은 경우 에이 기초는 당신이 생각하는 것만 큼 보이지는 않지만 그것이 존재하지 않는다는 의미는 아닙니다. Linalg 없이도 도출하기 어려운 알고리즘을 이미 구현했을 가능성이 있습니다.
다른 팁
암호화 작가는 아마도 알고리즘을 연구 할 때 숫자 이론의 이해가 매우 중요하다고 말할 것입니다. 그리고 그는 그의 특정 분야에서 옳았을 것입니다. 통계에는 스크립 목록, 해시 테이블 등이 너무 사용됩니다. 그래프 이론의 유용성은 훨씬 더 분명합니다.
선형 대수와 알고리즘 사이에는 고유 한 링크가 없습니다. 사이에는 고유 한 링크가 있습니다 수학 및 알고리즘.
선형 대수는 많은 애플리케이션이있는 필드이며,이를 이끌어내는 알고리즘에는 많은 응용 프로그램이 있습니다. 당신은 그것을 공부하는 데 시간을 낭비하지 않았습니다.
하, 나는 이것을 여기에 두는 것을 저항 할 수 없다 (다른 답변이 좋지만) :
나는 거짓말을하지 않을 것입니다 ... 나는 모든 것을 읽지 못했습니다 ... 아마 지금은 :-).
나는 그것을 '알고리즘을 연구 할 때 선형 대수로 매우 중요하다 "고 표현하는지 모르겠다. 나는 거의 다른 방법으로 그것을 넣었다. 많은, 많은, 많은 실제 문제가 당신이 일련의 선형 방정식. 결국 그러한 문제 중 하나를 해결해야한다면 선형 방정식을 다루기위한 많은 알고리즘에 대해 알아야 할 것입니다. 이러한 알고리즘은 컴퓨터가 작업 제목이었을 때 개발되었습니다. 기계. 가우시안 제거 및 다양한 매트릭스 분해 알고리즘을 고려하십시오. 많은 예를 들어 매우 큰 행렬에 대한 문제를 해결하는 방법에 대한 매우 정교한 이론.
머신 러닝에서 가장 일반적인 방법은 동시 방정식 세트를 해결 해야하는 최적화 단계가 있습니다. 선형 대수를 모른다면 완전히 잃어 버릴 것입니다.
많은 신호 처리 알고리즘은 행렬 작업, 예를 들어 푸리에 변환, 라플라스 변환, ...
선형 방정식 시스템을 해결하기 위해 최적화 문제를 줄일 수 있습니다.
선형 대수는 컴퓨터 대수의 많은 알고리즘에서도 중요합니다. 예를 들어, 다항식이 0이라고 말하면 문제를 줄일 수 있다면 다항식의 계수가 변수에서 선형입니다. x1, …, xn, 그런 다음 어떤 가치를 해결할 수 있습니다 x1, …, xn 각각의 계수를 동일함으로써 다항식을 0으로 동일하게 만듭니다. x^n 용어는 0에서 선형 시스템을 해결합니다. 이를 결정되지 않은 계수의 방법이라고하며, 예를 들어 부분 분획 분해를 계산하거나 합리적 기능을 통합하는 데 사용됩니다.
그래프 이론의 경우 인접 행렬에 대한 가장 멋진 점은 비가 중 그래프에 대한 인접 행렬의 N 번째 힘을 취하면 (각 항목이 0 또는 1), M^n, 그런 다음 각 항목 i,j 정점에서 나온 경로 수입니다 i 정점에 j 길이의 n. 그리고 그것이 단지 시원하지 않다면, 나는 무엇인지 모른다.
여기의 모든 답변은 알고리즘에서 선형 대수의 좋은 예입니다.
메타 답변으로, 나는 당신이 알고리즘에 모르고 알고리즘에 선형 대수를 사용할 수 있다고 덧붙입니다. SSE로 최적화하는 컴파일러 (2)는 일반적으로 많은 데이터 값을 병렬로 조작하여 코드를 벡터화합니다. 이것은 본질적으로 원소 LA입니다.
"알고리즘"유형에 따라 다릅니다.
몇 가지 예 :
- 기계 학습/통계 알고리즘 : 선형 회귀 (최소 제곱, 릿지, 라소).
- 신호 및 기타 처리 (얼굴 인식 등)의 손실 압축. 보다 고유
예를 들어 그래프의 연결 행렬을 가진 흥미로운 것들은 무엇입니까?
매트릭스의 많은 대수 특성은 정점의 순열 (예 : ABS (결정자)) 하에서 변하지 않으므로 두 개의 그래프가 동형 인 경우 값이 동일합니다.
이것은 두 개의 그래프가 있는지 여부를 결정하기위한 좋은 휴리스틱의 소스입니다. ~ 아니다 동형은 물론 평등이 동형의 존재를 보장하지 않기 때문입니다.
확인하다 대수 그래프 이론 다른 많은 흥미로운 기술을 위해.
