AlgorithmStudy/CLRS: Difference between revisions

Latest revision as of 15:27, 25 April 2017

25장 읽음
- APSP(All Pairs of Shortest Path) 알고리즘 중 Matrix multiplication 알고리즘에 대해 이야기 함

while m < n-1 {
    L^(2m) = L^(m)*L^(m)
    m = m*2
}

- 이 때 m = n-1이고 n이 짝수이면 m은 홀수인데 어떻게 결과를 얻는가 혼란스러웠는데 m < n-1동안 루프를 반복하는 것이고 마지막 L의 차수는 2^m이므로 항상 짝수임을 알게되었다.
- 구글링한 학습 자료([[3]], [[4]])에는 위 알고리즘이 seidel's algorithm이라고 명명되어 있는데 해당 키워드로 검색이 되지 않았다. 알고보니 seidel은 수학자이고 seidel's algorithm은 정식 명칭이 아니라 [Seidel method]이 정식 명칭인 듯 하다.
다음주: 26.3장 까지 읽기, 문제 풀기
- [[5]]
- [[6]]

@@ Line 41: / Line 41: @@
   }
 ** 이 때 m = n-1이고 n이 짝수이면 m은 홀수인데 어떻게 결과를 얻는가 혼란스러웠는데 m < n-1동안 루프를 반복하는 것이고 마지막 L의 차수는 2^m이므로 항상 짝수임을 알게되었다.
-** 구글링한 학습 자료에는 위 알고리즘이 '''seidel's algorithm이라고''' 명명되어 있는데 해당 키워드로 검색이 되지 않았다. 알고보니 seidel은 수학자이고 seidel's algorithm은 정식 명칭이 아니라 [[https://en.wikipedia.org/wiki/Gauss%E2%80%93Seidel_method|Gauss Seidel method]]이 정식 명칭인 듯 하다.
+** 구글링한 학습 자료([[http://math.mit.edu/~rothvoss/18.304.1PM/Presentations/2-Chandler-slideslect2.pdf|1]], [[https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss12/AdvancedGraphAlgorithms/Slides14.pdf|2]])에는 위 알고리즘이 '''seidel's algorithm이라고''' 명명되어 있는데 해당 키워드로 검색이 되지 않았다. 알고보니 seidel은 수학자이고 seidel's algorithm은 정식 명칭이 아니라 [[https://en.wikipedia.org/wiki/Gauss%E2%80%93Seidel_method|Gauss Seidel method]]이 정식 명칭인 듯 하다.
 * 다음주: '''26.3장''' 까지 읽기, 문제 풀기
 ** [[https://www.acmicpc.net/problem/1014|컨닝]]
 ** [[https://www.acmicpc.net/problem/3640|제독]]