Tip:
Highlight text to annotate it
X
모두 안녕하세요. 우리는 오늘 알고리즘을 다룰 겁니다,
그리고 우리는 recurrence를 풀기 위한
마스터 정리 같은 지난 시간에 했던
간단한 수학을 많이 사용할 것입니다.
우리는 이것을 많이 사용할 것입니다.
우리가 오늘 재귀 알고리즘에 대해 이야기할 것이기 때문입니다.
그리고 우리는 마스터 정리를 이용하여
그것들의 러닝 타임을 알아낼 것입니다.
이것은 지난 시간에 했던 것과 같습니다,
제가 실수를 하지 않는다면요. 몇 가지 상기해야 할 것들이 있습니다.
여러분은 금요일에 모든 설명을 들을 것입니다.
그것이 요구됩니다. 만약 여러분이 원한다면,
여러분은 일요일에 숙제 연구실로 갈 수 있습니다.
그것은 여러분이 실제로 여러분의 문제 세트를 몇 시간 일찍 할 수 있는 좋은 구실이 될 수 있습니다.
자, 사실, 그것은 수요일까지 입니다
그러니까 여러분은 시간이 많은 셈이죠.
그리고 월요일에는 수업이 없습니다.
학생 휴일이라는 휴일이지요,
그래서 오지 않습니다. 오늘 우리는
분할 정복이라는 것을 다뤄볼 것입니다.
분할 정복(divide and rule) 또는 라틴어를 아는 사람이라면
divide et impera 라고 알려진 것인데,
이것은 땅을 구역을 나눠서 정복하는 방법입니다.
그것은 정치적인 당파, 다른 무엇들과는 다를 것입니다.
그리고 나서 그것들을 더 이상 서로 좋아하지 않게 만드는 것입니다.
가정 불화의 시작이 항상 좋은 메소드인 것처럼 말이죠.
여러분은 이것을 여러분의 퀴즈에서 기억해야 합니다.
농담입니다. 그리고 여러분이 이 큰 구조를 작은 구조로 분리한다면
여러분은 각각의 작은 구조를 제거할 수 있고
그것들을 모두 개별적으로 정복할 수 있습니다,
여러분이 그것들이 함께 돌아오지 않는다는
것을 확신하는 한요. 그것은 British에서
divide and conquer 입니다.
그러나 우리는 오늘 Cormen, Leiserson, Rivest, Stein, 또는 다른 모든 알고리즘 교재에서
다뤄진 대로 해볼 것입니다.
이것은 매우 기본적이고
강력한 알고리즘 설계 기술입니다.
그래서, 이것은 우리의 첫 번째 실제 알고리즘 설계 경험이 될 것입니다.
우리는 여전히 대부분 모든 분석 모드에 있습니다,
그러나 우리는 실제 설계를 해 볼 것입니다.
우리는 아마 3 또는 4 개의 주요한 설계 기술을 다룰 것입니다.
이 번에 다룰 것도 그들 중 하나 입니다,
그래서 매우 중요합니다. 그리고 그것은 모든 종류의
재귀로 이어집니다, 그래서 우리는
지난 시간에 했던 모든 것들을 사용해야 할 것입니다 그리고 그것이 왜 유용한지 보게 될 것입니다.
여러분이 예상한 바 대로, 분할 정복에서
첫 번째 단계는 분할이고, 두 번째 단계는 정복입니다.
그러나 여러분은 세 단계가 있다는 것을 예상하지 못할 수도 있습니다.
그리고 저는 여기 빈 공간을 남겨 두었습니다. 그리고 저는 여기 빈 공간을 남겨 두었습니다.
분할 정복은 알고리즘적인 기술입니다.
여러분은 여러분이 풀길 원하는 어떤 큰 문제가 주어졌습니다,
여러분은 그것을 효과적인 방법으로 푸는 방법을 정말 알지 못합니다,
그래서 여러분은 그것을 하위 문제들로 쪼갤 것입니다.
이것이 분할 입니다.
여러분은 그 문제를 분할할 것입니다,
더 정확히는 그 문제의 사례를요, 여러분이 가진 문제의 특정한 사례를
하위 문제로 분할할 것입니다.
그리고 그 하위 문제들은 어떤 면에서는 더 작아야 합니다.
그리고 더 작다는 것은 보통 N의 값이 원래 문제에서의 값 보다 더 작아야 한다는 의미입니다.
그래서, 여러분은 어떤 진전을 만들었습니다.
이제 여러분은 여러분이 풀어야 할 하나의,
또는 몇 가지의 하위 문제들을 가지고 있습니다.
그것들 각각은 더 작습니다. 그래서, 여러분은 각 하위문제를 재귀적으로 풉니다.
이것은 정복 단계 입니다.
여러분은 각 하위 문제를 재귀적으로 정복합니다.
그리고 나서 다소 여러분은 이 문제들을 전체 문제를 위한
해결책으로 결합합니다.
그래서, 이것은 일반적인 분할 정복 패러다임입니다.
그리고 많은 알고리즘들이 그것에 맞습니다.
여러분은 이미 이 패러다임에 맞는 한 알고리즘을 보았습니다, 여러분이 기억할 수 있다면요.
합병 정렬 입니다, 좋아요. 와우, 여러분은 모두 깨어있었군요.
감동적이네요. 그래서, 우리는 합병 정렬을 보았습니다.
그리고, 제가 현명하다면, 저는 그것을 이 공간에 맞출 수 있습니다.
물론이죠. 현명해집시다.
합병 정렬에 대해 간단히 복습해 봅시다. 이 1, 2, 3 메소드가 있습니다.
첫 번째 단계는 여러분의 배열을 두 개로 나누는 것입니다.
이것은 정말 아무 의미도 없습니다
왜냐하면 여러분이 그렇게 생각하니까요, 오,
저는 제 배열이 둘로 나눠진 척 할 것입니다.
여기서 아무 작동도 하지 않습니다. 이것은 0번 입니다.
여러분의 배열을 보세요. 여기 여러분의 배열이 있습니다.
저는 아마 여러분이 n/2를 계산하고 춤을 춘다고 생각되네요.
그것은 정수 번 합니다. 그리고 여러분은 좋아,
나는 내 배열이 이제 왼쪽 부분과 오른쪽 부분으로 나눠지는 척을 할거야 라고 말합니다.
그리고 나서 흥미로운 부분은
여러분이 각각을 재귀적으로 푼다는 것입니다.
그것이 정복입니다. 우리는 재귀적으로 각 하위 배열을 정렬합니다.
그리고 나서 세 번째 단계는 이 답들을 결합하는 것입니다.
그리고 여기서 우리는 이것이 무엇을 의미하는지 보게 됩니다.
우리는 이제 도입에 의한 이 배열의 정렬된 버전을 가집니다.
우리는 도입에 의한 이 배열의 정렬된 버전을 가집니다.
우리는 이제 전체 배열의 정렬된 버전을 원합니다.
그리고 우리는 그것이 합병 문제라는 것을 보았습니다,
그것은 두 정렬된 배열을 합병하는 것이지요.
그리고 우리는 선형 시간에, 오더 n 시간에 하는 방법을 보았습니다.
저는 그것을 반복하지 않을 겁니다, 그러나 핵심은 그것이 그 골격에
맞는다는 것입니다. 저는 러닝 타임과 재귀로써
합병 정렬을 쓰고 싶습니다.
여러분은 이미 재귀를 보았습니다, 여러분은 이미 답을 들었습니다,
그러나 이제 우리는 실제로 그것을 푸는 방법을 알게 될 것입니다.
그리고, 더 나아가,
분할 정복 패러다임을 따르는 모든 알고리즘은
같은 형태의 재귀를 가질 것입니다.
우리의 친구 마스터 메소드와 같은 것을요.
우리가 이미 답을 알고 연습한 합병 정렬을 위해
그것을 해 봅시다.
이것은 합병 정렬 재귀입니다.
여러분은 이 재귀를 알고 사랑해야 합니다
왜냐하면 그것은 모든 곳에서 일어나거든요. 이 값(running time)은 일반적인 방법으로부터
여러분이 푸는 하위 문제의 크기가 얼마인지 그리고 얼마나 많은지
여러분이 할 일이 얼마나 남았는지를 통해 알 수 있습니다.
여러분은 여기서 하위 문제의 크기를 가집니다.
여기서 모든 하위 문제들이
대략적으로 같은 크기를 가집니다.
여기에서 사실은 ⌊n/2⌋+⌈n/2⌉이 되어야 하기 때문에
이런 식으로 찝찝한 부분이 있긴 합니다.
그래도 여러분이 금요일에 설명을 들을 때 여러분은 왜 그것이 괜찮은지 알게 될 것입니다.
바닥(⌊┤⌋)과 천장(⌈┤⌉)을 적용시키지 않아도 된다는 거죠.
그렇게 해도 충분하다는 것을 여러분이 증명할 수 있는 정리가 있습니다.
여러분은 N이 2의 제곱이라는 것을 가정할 수 있습니다,
그러나 우리는 지금은 그것을 그냥 가정할 것입니다. 우리는 n/2 사이즈인
두 문제가 있습니다. 이 2는 하위 문제들의
수 입니다.
그리고 이 오더 n은 우리가 하는 모든 여분의 일입니다.
이제, 남은 일들은 잠재적으로 무엇입니까?
자, 정복하는 것은 항상 재귀입니다.
이를 제외하고 아무 것도 작동하지 않습니다.
이 경우에서 분할은 사소합니다, 그러나 일반적으로
그것은 어떤 일을 포함할지도 모릅니다. 그리고 여기서 결합하는 것은 선형적인 일을
포함합니다. 그래서, 이것은
분할 정복 러닝 타임입니다.
그래서, 이것은 재귀적이지 않은 일입니다.
그리고 그것은 일반적으로 여러분이 분할 정복 알고리즘을 재귀로
변환하는 방법입니다. 그것은 정말 쉽고
여러분은 마스터 메소드를 보통 적용합니다.
여기서 우리는 케이스 2에 있습니다. 매우 좋아요.
이것은 케이스 2 입니다. 그리고 k는 여기서 0 입니다.
그리고 재귀 트리에서, 모든 비용은 대략 같습니다.
그것들은 n 로그 b의 a 입니다.
여기서 n 로그 2의 2는 n 입니다.
그래서 이것들은 같습니다.
우리는 남은 로그 인자를 얻습니다 재귀 트리에서 레벨의 수 때문입니다.
마스터 메소드 뒤의 직관을 기억하세요
이것은 n log n 입니다,
그리고 그것은 좋습니다. 합병 정렬은 빠른 정렬 알고리즘입니다.
삽입 정렬은 n 제곱 입니다. 어떤 면에서,
n log n 은 여러분이 할 수 있는 최상입니다.
우리는 지금으로부터 두 강의에 걸쳐 그것을 다룰 것이지만,
이것은 전조입니다. 오늘 우리는
다른 분할 정복 알고리즘을 해볼 것입니다.
정렬은 한 문제입니다. 우리가 풀고 싶어하는
모든 문제들이 있습니다. 그것은 여러분이 분할 정복을 적용할 수 있는
많은 것으로 드러났습니다. 모든 문제는 아닙니다.
아침에 일어나는 방법 같은 것은
분할 정복을 풀기 쉽지 않습니다,
그것이 좋은 문제 세트이더라도요.
우리가 볼 다음 분할 정복 알고리즘은
정렬 보다 더 간단하고, 합병 정렬보다도 더 간단합니다,
그러나 그것은 여러분이 오직 하나의 문제 세트를 가진 경우에만 그렇습니다.
얼마나 많은 학생들이 전에 이진 검색을 보았나요?
아무도 없나요?
한 명 있군요, 좋아요. 저는 그러면 매우 빠르게 해볼 것입니다.
여러분은 인자 X를 가집니다. 여러분은 정렬된 배열에서 X를 찾길 원합니다.
얼마나 많은 학생들이 수업 전에
그것을 보지 못했나요?
아무도 없군요, 네. 좋아요.
여러분은 그것을 아마 6.001 또는
다른 수업에서 보았을 겁니다. 매우 좋아요.
여러분은 선행 강의를 수강했습니다. 네.
저는 그것을 분할 정복이라고 하고 싶군요 왜냐하면 여러분은 그것을 보통 그 방법으로 보지 않기 때문입니다.
분할 단계는 여러분이 X를 여러분의 배열의 중간 인자와
비교하는 것 입니다.
그리고 정복 단계입니다. 여기 여러분의 배열이 있습니다.
여기 중간 인자가 있습니다.
X가 여러분의 배열에서 중간 인자 보다 더 작다고 해봅시다 여러분은 X와 이것(왼쪽)을 비교합니다.
여러분은 X가 왼쪽의 절반이라는 것을 압니다
왜냐하면 그것은 정렬되었거든요, 거기 좋은 변함 없는 루프 입니다.
그러나 재귀적으로 이 하위 배열에서 X를 찾는 문제를 제가 풀 때
우리는 이것에 대해 생각해 보아야 합니다.
우리는 하나의 하위 배열에서 순환합니다, 우리가 두 개의 재귀를 가지고 있는 합병 정렬과 달리요.
그리고 나서 결합된 단계에서 우리는
아무 것도 하지 않습니다. 여러분이 여기서 X를 찾으면
여러분은 전체 배열에서 X를 찾을 수 있습니다.
정말 아무 것도 다시 오지 않습니다.
그래서, 이것은 분할 정복 패러다임에서 이진 검색을 표현하고 있습니다.
그것은 사소한 예이지만,
여러분이 한편으로 재귀할 필요가 있는 많은 환경들이 있습니다.
그리고 하나의 재귀 대 두 개의 재귀의 차이가
얼마나 큰지를 보는 것은 중요합니다.
이것은 이진 검색을 위한 재귀입니다.
우리는 n 사이즈 문제에서 시작합니다.
우리는 그것을 1로 줄입니다. 여기 함축적인 1 인자가 있습니다.
대략적으로 하위 문제의 사이즈는 2 분의 n 입니다.
다시, 바닥(⌊┤⌋)과 천장(⌈┤⌉)중요하지 않습니다.
X와 중간 인자를 비교하는 상수를 더합니다,
그래서 그것은 사실 하나의 비교와 같습니다.
이것은 답을 가지고 있습니다, log n 입니다.
그리고 여러분은 이진 검색의 러닝 타임을 모두 알고 있습니다,
그러나 여기서 그것은 재귀를 푸는 것 입니다.
여기에 몇 가지 차이점들이 있습니다.
우리는 추가적인 오더 n 항을 가지지 않습니다.
만약 우리가 가지고 있다면, 그것은 선형의, 러닝 타임일 것입니다.
n log n 보다 더 낫지요.
그래서, 우리는 2를 제거할 것입니다, 그것을 1로 줄이고,
n을 가져와서 그것을 1로 내릴 것입니다.
그것은 러닝 타임과 n의 전체 인자를 많이 빠르게 만듭니다.
거기서는 크게 놀랄 일이 아닙니다.
좀 더 흥미로운 알고리즘들을 해봅시다.
수를 제곱하는 문제를 다뤄봅시다. 여러분에게 X라는 수를 주어졌습니다.
저는 그것을 실제의 수 또는 정수 또는 무엇이든 그렇게 주었습니다.
그리고 정수 n을 주어졌는데,
이 수는 0보다 크거나 같습니다. 여기에서 X의 n제곱을 계산하려고 합니다.
그래서, 그것은 매우 간단한 문제입니다.
어떤 면에서 그것은 이 모든 것 보다 더 쉽습니다.
그러나 여기에 있습니다. 그리고 분할 정복은 옳은 것들의
정렬입니다. 그래서, 소박한 알고리즘은 매우 간단합니다.
여러분은 X의 n제곱을 어떻게 계산합니까?
자, X의 n제곱의 정의는
제가 X를 가지고 X를 n번 곱하는 것입니다.
그래서, 저는 X 곱하기 X 곱하기 X 곱하기 X를 합니다 전체적으로
X가 n개일 때 까지요. 그리고 그것은 X의 n 입니다.
크게 놀랄 일이 아니지요. 그것은 n번 곱셈,
또는 n 마이너스 1 곱셈, θ(n)입니다.
그러나 그것은 이 문제를 위해 여러분이 할 수 있는 최선이 아닙니다.
우리가 분할 정복을 사용하여 무엇을 하는지에 대한 제안 있나요?
여러분 중 이 알고리즘을 전에 본 학생 있나요?
몇 명 있군요, 네.
나머지 학생들은요? 창의성을 시험해 봅시다,
그것은 매우 어렵지만, 저는 항상 도전을 좋아합니다.
저는 무작위의 생각들을 의미합니다. 우리가 선형 시간 보다 적게
이 문제를 풀기 위해 할 수 있는 가능한 일이 무엇이지요?
분할 정복 문제의 이 정렬은 어떻죠?
우리는 입력, X와 n을 가지고 있습니다.
네? 우리는 X로 나눌 수 있습니다.
그것은 약간 어렵습니다. 그것은 어떤 수 입니다.
또는, 우리는 n에서 나눌 수 있습니다.
어떤가요? 이것을 보세요,
매우 좋아요. 그것은 분할 정복 알고리즘의
정확한 생각입니다.
우리는 X의 2 분의 n을 보고 싶습니다.
이것은 약간 까다로울 것입니다.
이제 우리는 바닥(⌊┤⌋)과 천장(⌈┤⌉) 연산에 주의해야 합니다.
제가 말하고 싶은 것은
X의 n이 다음과 같다는 것입니다.
그리고 이것은 n이 짝수이면 맞습니다. 만약 홀수이면 저는 좀 더 255 00:16:07,758 --> 00:16:11,265 신중해야 할 필요가 있습니다. 그러나 왜 이것이
좋은 분할 정복 알고리즘인지 직관에 대하여 생각해 봅시다.
우리는 사이즈 n의 문제를 가지고 있습니다.
우리는 그것을 변환합니다, 그것은 사이즈 2 분의 n인 하위 문제들이지요,
그러나 사실 그것들은 같은 하위 문제들 입니다.
그래서, 저는 그것들 중
하나만 풀면 됩니다.
네, 저는 X의 2 분의 n을 알고 있습니다. 그래서, 전환성의 호출이 있습니다,
사이즈 2 분의 n의 문제 입니다, 그리고 저는 그 수를 나눕니다.
그리고 그것은 한 번의 계산입니다. 그래서, 이진 검색으로써
정확히 같은 재귀입니다, log n 시간은 n 보다 훨씬 더 낫습니다.
좋아요. 저는 또한 홀수 케이스를 풀려고 할 것입니다.
그래서, n은 홀수입니다.
저는 2 분의 n 마이너스 1을 볼 것입니다.
n 마이너스 1은 짝수입니다. 그리고 저는 X의 또 다른 인자를 놓치고 있습니다.
n이 홀수이면,
저는 한 번의 재귀 호출과 두 곱셈을 해야 합니다.
같은 재귀 입니다.
사이즈 2 분의 n 플러스 정수 시간의 재귀 문제 입니다.
여기서 분할 작업은 2로 나누는 것이고
결합 작업은 1번 또는 가능하면 2번 곱셈하는 것입니다.
그리고 이것은 lg n 입니다. 그리고 여러분이 하도록
허락 받은 모든 것은 수들을 곱셈하는 것입니다, lg n은 여러분이 할 수 있는 최상입니다.
좋아요. 간단하지만 강력합니다.
여러분이 수의 제곱을 계산하길 원할 때면 언제든,
이제 여러분은 무엇을 해야 하는지 알고 있습니다.
여러분 중 피보나치 수열의 정의를 모르는 학생 있나요?
그것을 기꺼이 허용해도 되겠죠? 좋아요, 그래서 이것은 좋은 오래된 친구입니다.
저는 상기시키기 위해 정의를 써 볼 것입니다.
그리고, 특히,
기본적인 경우에서요.
피보나치 수열은 매우 중요합니다.
왜냐하면 그것은 자연을 통해 나타나기 때문입니다.
여러분은 어떤 과일을 봅니다, 여러분은 피보나치 순서를 볼 수 있습니다.
만약 여러분이 반지 요철을 본다면요.
여러분이 해변의 모래를 볼 때 그리고 파도가 어떻게 그것을 칠 때도,
그것은 피보나치 수열입니다.
여러분이 보는 모든 곳에서, 피보나치 수열이 있습니다.
자연은 어떻게 피보나치 수열을 계산할까요?
자, 그것은 다른 분야이구요.
그러나 우리는 어떻게 가능한 빨리 피보나치 수열을 계산할 수 있을까요?
여러분은 두 알고리즘을 아마 보았을 겁니다.
가장 소박한 알고리즘은
재귀 알고리즘입니다.
N의 f 에서요. 만약 n이 0이면,
0을 리턴합니다. 만약 n이 1이면, 1을 리턴합니다.
만약 그렇지않으면, 재귀적으로 n-1의 f와 n-2의 f를 계산하고,
그것들을 함께 더합니다. 이것을 전에 본 학생들은,
이 알고리즘이 얼마나 시간이 걸리는지 아나요?
이것은 명백하게 알 수 없습니다.
이것은 정확하지 않거든요.
네. 그리고 얼마나 많은 학생들이 이 알고리즘을
전에 보고 분석해 보았나요?
절반 정도 되는군요, 좋아요. 그래서 러닝 타임은 얼마죠?
정말, 정말로 깁니다, 매우 좋아요.
더 정확한 답은 뭘까요? 무엇입니까?
네, 기하급수적입니다.
그것은 또한 맞고 더 정확한 표현입니다.
저는 더 정확해질 것입니다. 아마 여러분은 이 분석을 전에 보지 못했을 수도 있습니다.
파이는 황금률입니다.
다시, 황금률은 수학의 세계에서
나타납니다.
이것은 아마 이 수업에서 유일한 시간입니다,
저는 두렵지만, 해봅시다. 그것은 카메오로 만들었으니까 우리는 행복합니다.
이것은 지수적인(기하급수적인) 시간이라고 불립니다.
이것은 1 보다 큽니다,
그것은 여러분이 알아야 할 모든 것입니다. 이것은 지수적인 시간입니다.
지수적인 시간이라는 것의 의미는 기본적으로 어떤 정수의 n제곱입니다.
지수적인 시간은 매우 긴 시간입니다.
그것은 나쁩니다.
다항의 시간은 좋습니다. 이것은 우리가 원하는 것,
다항 시간 알고리즘입니다.
이 수업은 기본적으로 다항 시간 알고리즘에 대한 수업입니다.
질문 있나요?
오, 알고리즘이 무엇을 하는지 다시 말해봅시다.
N의 피보나치 함수를 정의하나요? 저는 기본적인 경우를 검사합니다.
그렇지 않으면, 저는 재귀적으로 n – 1의 피보나치를 호출합니다.
저는 재귀적으로 n – 2의 피보나치를 호출하고 두 수를 함께 더합니다.
그래서 여러분은 이 트리를 얻게 됩니다.
여러분은 거의 같은 사이즈의
두 하위 문제들을 풀게 됩니다.
여러분은 문제 사이즈를 거의 전혀 줄이지 않습니다,
그래서 그것은 직관적으로 그것이 지수적인 이유입니다.
여러분은 재귀 트리를 그릴 수 있고
여러분은 그것이 얼마나 커지는지 얼마나 빠르게 커지는지 볼 수 있습니다.
n/2단계에서, 여러분은
n에서 n/2까지 한 문제에서 사이즈를 줄이면 됩니다.
다른 하나에서, 아마 여러분은 n에서 1까지 합니다,
그러나 2 분의 n 단계 후에는 아무 것도 멈추지 않습니다.
여러분은 적어도 2의 2분의 n제곱을 가지고 있습니다,
그것은 2의 n제곱의 루트와 같습니다,
그것은 파이 n과 점점 가까워집니다.
그래서, 이것은 분명히 지수적입니다.
그리고 지수적인 것은 나쁩니다. 우리는 다항식을 원합니다.
N 제곱, n 세제곱, log n 이 좋습니다.
다항식에 의한 것은 좋습니다.
이것은 오래된 생각입니다. 그것은 다항식이 좋다고 말한 주요한 인물들 중 한 사람인
Jack Edmonds으로 거슬러 올라가는데,
그는 결합 최적화 세계에서 유명합니다.
그는 한편으로 제 학문적 할아버지입니다.
그는 매우 흥미로운 사람이었어요.
네, 그래서 그것은 나쁜 알고리즘입니다.
여러분은 아마 다소 나은 알고리즘을 보았을 것입니다,
그것은 여러분이 그 재귀 알고리즘의 세부적인 데서 출발하는 이식으로
생각할 수도 있습니다.
또는, 여러분이 n 피보나치 수열을 위한 재귀 트리를 구축했다면,
여러분은 여러분이 시간을 낭비하고 있는 많은
일반적인 하위 트리들을 볼 수도 있습니다.
여러분이 n-1 피보나치를 풀 때, 그것은 n-2의 피보나치를
다시 풉니다. 그것은 왜 두 번 풀까요?
여러분은 오직 한 번만 그것을 풀 필요가 있습니다. 그래서, 여러분이 그것을 세부적인 데서부터
하는 것은 정말 쉽습니다. 그러나 여러분은 또한 그것을 여러분이 이미 계산한 캐쉬로
재귀적으로 할 수도 있습니다.
그래서, 크게 놀랄만한 것은 아닙니다.
여러분은 피보나치 수열을 순서대로 계산합니다.
그리고 여러분이 n의 피보나치 수열을 계산한 각 시간에,
여러분은 이미 이전의 둘을 계산한 것입니다.
여러분은 그것들 둘을 더합니다,
그것은 정수 시간이 걸립니다.
그래서, 여기 러닝 타임은 선형입니다, 우리의 입력에서요.
좋아요. 그것이 우리가 할 수 있는 최상인가요?
아닙니다. 우리가 n의 피보나치를 선형 시간 보다
더 빨리 계산 할 수 있는 방법에 대한 생각이 있나요?
이제 우리는 이미 여러분이 본 것으로부터 갈라져야 합니다.
여러분이 이미 본 기술들을 사용하는 어떤 생각을
가지고 있나요? 네?
네. 우리는 파이(Φ)와 프사이(Ψ)의 n제곱의 수학적인 트릭을
사용해야 합니다.
사실, 여러분은 파이, 파이, pi, pho, phum 등과 같은
그리스 철자를 사용할 수 있습니다.
좋아요. 여기는 수학적인 트릭입니다.
그리고, 정말로, 이것은 속임수입니다,
여러분이 말했듯이요. 이것은 좋지 않습니다.
우리는 그것을 소박한 recursive squaring 이라고 부를 것입니다,
우리는 recursive squaring을 알고 있습니다.
recursive squaring은 log n 시간이 걸립니다.
recursive squaring을 사용해봅시다. 그리고 여러분이 피보나치 수열의
많은 속성들을 알게 되면, 여러분은 할 필요가 없습니다,
그러나 여기는 그것들 중 하나 입니다. 여러분이 파이(Φ)n 을 루트 5로 나누고,
그것을 가장 가까운 정수로 반올림하면
그것이 n 번째 피보나치 수 입니다.
이것은 매우 좋아요. N의 피보나치는 기본적으로 파이 n 입니다.
우리는 log n 시간에 파이 n을 계산하는
recursive squaring을 적용할 수 있습니다.
우리의 컴퓨터가 가장 가까운 정수를
반올림 연산을 한다고 가정하면,
우리는 한 것입니다. 그것은 많은 다른 이유들을 위해 동작하지 않습니다.
실제 기계에서, 409 00:25:22,051 --> 00:25:26,788 아마 여러분은 파이와 루트 5를 실수로 표현할 것입니다
그것은 약간 수정된 정확한 수 입니다
그리고 만약 여러분이 이 계산을 한다면, 여러분은 중요한 것을 잃을 것입니다.
그리고 여러분이 가장 가까운 정수를 반올림할 때
여러분은 옳은 답을 얻지 못할 것입니다.
그래서, 실수 반올림은 여러분을 실수 점 기계에서 죽일 것입니다.
우리가 마술적으로 수들을 가지는 이론적인 기계에서
그것은 이와 같은 미친 짓을 할 수 있습니다,
그것은 곱셈 당 정수 시간 보다 정말 더 많은 시간이 걸립니다.
그래서, 우리는 다른 모델에 있습니다.
여러분은 정수 시간에서 파이 곱하기 파이를 할 수 없습니다.
그것은 이 수업의 범위를 넘는 것입니다,
그러나 그것은 이것을 하는 방법이지요.
사실, 일반적인 기계에서, 여러분은 지수적인 시간에 어떤 문제들을 풀 수 있습니다.
여러분이 실제 수를 곱하고
그것들을 가장 가까운 정수로 반올림하는 기계에서,
여러분은 그것을 다항의 시간에 풀 수 있습니다.
그래서, 그것은 모델을 정말 깨는 것입니다. 여러분이 이것을 하도록 허락되었다면
여러분은 미친 짓을 할 수 있습니다. 그것은 허용되지 않습니다.
그리고 저는 세 수업 정도를 미리 앞서 말하고 있는데,
저는 더 이상 그것에 대해 말하면 안될 것 같습니다.
그러나 우리가 피보나치 수열의 다른 속성을 사용한다면
우리는 다른 방법에서
recursive squaring을 사용할 수 있습니다.
그리고 우리는 정수를 붙일 것이고 모든 것은 행복해질 겁니다.
설명을 듣는 것을 잊지 마세요
그리고 여러분이 원한다면 숙제 연구실로 오시고요.
월요일엔 수업이 없습니다.
이것은 옳은 recursive squaring 알고리즘 입니다.
그리고 이것은 여러분이 이미 알고 있는지 추측하기 어렵군요.
그러니까 지금 알려드릴게요. 저는 이것을 정리라고 부를 것입니다.
제가 이 수업에서 정리라는 단어를 처음 사용하고 있습니다.
n 번째 피보나치 수는
이 행렬의 n 제곱입니다.
좋아요. 여러분이 이것을 보면 여러분은
오, 물론이야 라고 말할 것입니다.
그리고 우리는 이 정리를 곧 보게 될 것입니다.
그리나 우리가 한 번 이 정리를 가지면, 우리는 이 행렬의 n제곱을 계산함으로써
f의 n을 계산할 수 있습니다.
이것은 2 곱하기 2 행렬입니다. 여러분은 2 곱하기 2 행렬을 함께 곱합니다,
여러분은 2 곱하기 2 행렬을 얻습니다.
그래서 그것은 정수 사이즈이고, 네 수를 가집니다.
우리가 네 수를 다룰 수 있는 셈이죠. 우리는 실수에서처럼
미친 정밀함의 문제를 가지지 않습니다.
우리는 오직 네 수만 다루면 되니까요.
행렬은 커지지 않을 것입니다. 그래서, 이 분할 정복 알고리즘의
러닝 타임은 여전이 log n 일 것입니다.
왜냐하면 이것은 2 곱하기 2 행렬 곱셈 당
정수 시간이 걸리기 때문입니다. 네?
오, 네. 고마워요.
제가 타이핑을 잘못 했군요. 미안해요.
Fn은 정말 위의 왼쪽에 있습니다.
저는 검사하는게 좋을 것 같군요.
그것은 위의 오른쪽 코너에 있습니다.
이것이 여러분이 말한 것입니다.
저는 공간이 더 필요합니다.
미안해요. 저는 2 곱하기 2 행렬을
저기 왼쪽 면에 두어야 합니다.
고마워요. 그래서, 저는 이 행렬의 n 제곱을 log n 시간에 계산합니다,
저는 위의 오른쪽 코너 또는
아래의 왼쪽 코너를 가집니다, 어떤 거든 상관없습니다.
그것은 n 번째 피보나치 수 입니다.
이것은 지난 두 개의 이진 검색과 recursive squaring 알고리즘으로써
같은 재귀로 오더 log n 시간을 함축합니다.
그것은 log n 더하기 상수입니다,
그래서 log n 입니다. 그 정리를 증명해 봅시다.
이 정리를 증명하기 위해 우리가 사용해야 하는
어떤 기술에 대한 생각 있나요?
귀납법, 매우 좋아요.
제가 그 질문을 할 때마다, 답은 항상 귀납법입니다.
이 수업의 향후 내용를 위한
힌트입니다.
제 친구 중 한 명은 그가 분석 수업을 들을 때,
교수가 질문을 할 때 마다,
이 질문의 답은 항상 0이었습니다.
여러분이 분석 수업을 들었다면 재미있겠네요.
아마 저는 우리의 즐거움을 위해 답이 0인 질문을
하려고 노력할 것입니다.
우리는 n에 대해 귀납법을 적용시킬 건데요. 그것은 매우 당연한 일이에요.
그러나 우리는 귀납법의 base단계에서 몇 가지 케이스를 검사해야 합니다.
그래서, 기본적인 경우는 우리가 이것의 첫 번째 제곱을 가진다는 것입니다.
그리고 그것은 [(1, 1), (1, 0)] 입니다.
그리고 저는 n이 적어도 1이라는 것을 말해야 했습니다.
그리고 여러분은 검사할 수 있습니다.
이것은 F_2, F_1, F_1, F_0 이어야 합니다.
그리고 여러분은 그것을 검사할 수 있습니다. F_0은 0이고, F_1은 0이고, F_2는 1 입니다.
좋아요.
Base단계가 맞아떨어지네요. step단계도 흥미진진하겠군요.
그러나 여러분은 여러분의 알고리즘이 동작하는지 증명해야 합니다.
이것이 우리가 계산하길 원하는 것이라고 가정해 보세요.
자, 제가 이것을 할 수 있는 많은 방법들이 있습니다.
저는 그것을 빠른 방법으로 할 것입니다
왜냐하면 그것을 그리 흥미로운 것이 아니거든요.
어떤 방향이죠? 이 방향으로 해 봅시다.
저는 n에 대해 귀납법을 사용하고 싶습니다. 만약 n에 대해 귀납법을 사용하고 싶으면,
아마도 저는 제가 이미 알고 있는 것을 사용해야 합니다
만약 제가 n을 1로 감소 시키면, 저는 이 속성을 가집니다,
그것은 [(1, 1), (1, 0)] 의 n-1 제곱입니다.
귀납법의 가설에 의하여,
저는 이미 알고 있습니다.
그래서, 아마 저는 그것을 어떤 방법으로 사용해야 합니다.
이 등식은 아직 맞지 않습니다,
여러분은 아마 알아 차렸을 거에요. 그래서, 저는 무엇을 더해야 합니다.
제가 무엇을 더해야 맞을까요?
자, 또 다른 [(1, 1), (1, 0)]인자입니다.
제가 이 증명을 발전시키는 방법은 어떤 면에서,
그것이 가능한 유일한 방법입니다. 여러분이 그것의 도입을 알면,
이것은 여러분이 할 수 있는 모든 것입니다. 그리고 나서 여러분은 검사합니다.
정말로, 이 등식은 계속 유지됩니다.
예를 들어, F_(n plus 1)는 이 두 개의 곱입니다.
이것은 이 행과 이 열의 곱입니다.
그래서, 그것은 F_n 곱하기 1 더하기 F_(n minus 1) 곱하기 1 입니다,
그것은 F_(n plus 1)의 정의입니다.
그리고 여러분은 4개의 입력을 검사할 수 있습니다.
이것은 참입니다.
좋아요. 그것이 참이면
저는 이것들을 함께 둘 수 있습니다.
그것은 [(1, 1), (1, 0)] n 마이너스 1 곱하기 [(1, 1), (1, 0)] 입니다,
그것은 [(1, 1), (1, 0)] 의 n 입니다.
매우 간단한 증명이지만,
여러분은 이 알고리즘이 정말로 작동하는지 알기 위해 그것을 해야 합니다.
좋아요.
질문 있나요? 오, 네.
고마워요. 아래 오른쪽에서,
우리는 F_(n minus 1) 를 해야 합니다. 이것은 여러분이
여러분의 증명을 정말로 검사해야 하는 이유입니다.
우리는 제가 그것을 검사할 때 이것이 그 열 곱하기 그 행이라는 것을 알아 냈습니다.
그러나 그것은 여러분이 제 버그를 고치기 위해 여기 있는 이유입니다.
퀴즈 대신에 여기 있는 것은 훌륭한 일이지요.
그러나 사소한 실수입니다.
여러분은 그것을 위해 많이 잃지는 않을 것입니다.
좋아요. 분할 정복 알고리즘을 좀 더 다뤄봅시다.
여전히, 우리는 상대적으로 간단한 것을 지금까지 해왔습니다.
사실, 가장 멋진 것은 합병 정렬 입니다,
우리는 이것을 이미 보았지요.
그래서, 그것은 그리 흥미로운 것이 아닙니다. 남은 것은 모두 log n 시간을 가집니다.
Log n의 세계에서 나와봅시다.
자, 여러분은 암기된 마스터 메소드를 모두 가지고 있습니다,
네, 그래서 저는 그것을 지울 것입니다.
좋아요. 이것은 좋은 테스트 입니다.
다음 문제는 행렬 곱셈입니다,
이 2 곱하기 2 행렬 곱셈의 오른쪽에 있습니다.
우리가 n 곱하기 n 행렬 곱셈을 어떻게 계산할 수 있는지 봅시다.
개요를 말하자면,
여러분은 행렬 곱셈하는 방법을 알아야 하지만, 여기는
정의이고 그래서 우리는 그것을 알고리즘으로 바꿀 수 있습니다.
여러분은 A와 B라는 두 행렬을 가집니다,
그것은 주요한 단계입니다. ij 번째 입력입니다.
I 번째 열과, j 번째 행은 a_ij 또는 b_ij 라고 불립니다.
그리고 여러분의 목표는 이 행렬들의 곱을 계산하는 것 입니다.
저는 아마 i와 j의 범위가 1부터 n까지라고 말해야 합니다.
그래서, 그것들은 정사각형 행렬입니다.
출력은 A와 B의 곱인 입력 c_ij을 가지는 C를 계산하는 것입니다.
그리고, 개요를 말하자면, 곱의 ij 번째 입력은
A의 I 번째 열과 B의 j 번째 행의 곱입니다.
그러나 여러분은 그것을 합처럼 쓸 수 있습니다.
우리는 이것을 모든 i와 j에 대하여 계산하고 싶습니다.
이것을 하는 분명한 알고리즘은 무엇이죠?
자, 모든 i와 j에 대하여 여러분은 합을 계산합니다.
여러분은 모든 곱을 계산합니다.
여러분은 합을 계산합니다. 그래서, 그것은 여기서 대략적으로 n 연산을 합니다.
저는 2n-1과 같은 것을 의미했어요.
그것은 오더 n 연산입니다.
제가 계산해야 하는 C의 n^2 입력들이 있습니다,
그것들을 n^3 입니다. 저는 이것을 프로그래머들을 위하여 마음 속으로 써 보겠습니다.
여기 이것은 수도 코드입니다.
제가 수도 코드를 쓰는 것은 드문 일일 것이에요.
그리고 이것은 제가 그것을 자세하게 쓸 수 있는 충분히 간단한 알고리즘입니다.
그러나 그것은 여러분이 프로그램을 하고 싶다면 여러분에게
이 분석을 위한 어떤 기초를 제공해 줍니다.
그것은 for문이 3중첩된 루프입니다.
그리고 저는 코딩 에러를 했었군요. 희망적으로 여러분은 그것을 아직 쓰지 않았습니다.
c_ij는 0으로 초기화될 필요가 있습니다.
그리고 저는 c_ij에 적절한 곱
a_ik, b_kj 를 더할 것입니다.
그것이 알고리즘입니다. 그리고 핵심은 여러분이
1부터 n까지 중첩 루프를 가진다는 것입니다.
그것은 n^3을 가집니다 왜냐하면 이것은 상수이고
저것도 상수이기 때문입니다. 매우 간단하지요,
n^3 입니다. 더 나은 것을 해 봅시다.
그리고, 물론, 우리는 분할 정복을
사용할 것입니다.
이제, 어떻게 우리가 행렬을 분할할 것인가요?
행렬 안에 많은 수들이 있습니다, 각각에서 그것들의 n^2 입니다.
여러분이 분할할 수 있는 모든 방법들이 있습니다.
지금까지 우리가 했던 모든 분할 정복들은 사이즈 n의 문제를
사이즈 2 분의 n의 문제로 하는 것이었습니다.
저는 사이즈 n 곱하기 n인 행렬으로 시작해 보겠습니다.
저는 그것을 n/2 곱하기 n/2 같은 것으로 전환하고 싶습니다.
제가 그것을 어떻게 하는지 생각 있나요?
네?
블락 형태 매트릭스 입니다.
옳은 답이에요. 그래서, 이것은 첫 번째 분할 정복 알고리즘입니다.
이것은 작동하지 않을 것입니다,
그러나 그것은 우리가 원하는 첫 번째 생각을 가지고 있습니다.
우리는 n 곱하기 n 행렬을 가지고 있습니다. 우리는 그것을 볼 수 있습니다.
이 등식은 여러분이 생각하는 그 이상입니다.
그것은 이 2 곱하기 2 행렬에서 각 입력이
n/2 곱하기 n/2 하위 행렬의 블락인
2 곱하기 2 블락 행렬입니다.
저는 C를 3 부분으로 나누어서 생각할 것입니다,
r, s, t 그리고 u. 제가 그것들을 소문자로
쓴다고 하더라고 그것들은 실제의 행렬입니다.
각각은 n/2 곱하기 n/2 행렬입니다. 그리고 A를 저는 a, b, c, d로 나누고요.
곱하기 B로 나눌 것입니다. B는 e, f, g, h 로 나눌 것입니다.
왜 안되나요?
이것은 확실히 맞습니다. 그리고 여러분이 선형 대수를 본다면,
이것은 기본적으로 여러분이 행렬로 할 수 있는 것입니다.
이제 저는 이것들이 2 곱하기 2 행렬인척 할 수 있고
이 소문자들이 행렬들이라는 것을 잊어버릴 수 있습니다,
r이 이 행과 이 열의 내부 곱셈이라고 할 수도 있습니다.
그것은 ae 곱하기 bg 입니다. 저는 속이지 않았습니다
그렇지 않으면 그것은 너무 쉽습니다. r=ae+bg, s=af+bh,
t=ce+dh 그리고 u=cf+dg. 그것은 여러분 스스로 너무 힘들게 만드는 것입니다.
네, 그것을 올바르게 해 봅시다.
좋아요. 이것은 여러분이 이 곱을
확장하는 방법에 대한 사실입니다.
그리고 이제 여러분은 재귀 알고리즘을 가지고 있습니다.
사실, 우리는 분할 정복 알고리즘을 가지고 있습니다.
우리는 우리의 n 곱하기 n 행렬로 시작할 것입니다.
자, 우리는 사실 그것들 두 개를 가지고 있습니다.
우리는 그것을 8 개의 작은 부분들로 나눌 것입니다.
a, b, c, d, e, f, g, h.
그리고 우리는 이것들을 계산하고 그것은 우리에게 C를 줄 것입니다,
그것들을 같이 붙여서요.
이제, 우리는 어떻게 이것들을 계산하나요?
자, 이 순진하게 보이는 이 소문자 사이의 곱들은 사실
재귀 행렬 곱셈입니다.
각 소문자들이 n/2 곱하기 n/2 행렬이기 때문에 저는
재귀적으로 곱을 계산해야 합니다.
n/2 곱하기 n/2 행렬의 8 개의 재귀 곱셈 같은 것이 있습니다.
그것은 우리에게 악영향을 미치는 것입니다.
그리고 나서 4 개의 덧셈이 있습니다, 이것들을 함께 붙이는 것들이지요.
두 행렬들을 함께 붙이는데 얼마나 시간이
걸릴까요? N^2 입니다.
이것은 매우 쉽죠. 이것은 단지 n^2의 시간이 걸립니다.
기억하세요, 우리가 우리의 행렬 곱셈을 위해 n^3을 이기려고 노력한다는 것을 것을요.
덧셈은 정말 쉬운 문제입니다.
여러분은 모든 수를 더해야 합니다.
여러분은 n^2 보다 더 나은 것을 할 수 있는 방법이 없습니다.
그래서, 그것은 재귀가 아닙니다.
그것은 좋은 것이에요. 그러나 나쁜 것은
우리가 이 재귀를 8개 가지고 있다는 것입니다.
우리는 T(n)=8T(n/2)+θ(n^2) 를 가지고 있습니다. 그리고 저는 마스터 메소드를 지웠습니다,
그러나 여러분은 모두 그것을 암기해야 합니다.
이 재귀의 답은 무엇입니까?
θ(n^3) 입니다. 그것은 짜증 나는 것입니다.
좋아요. A는 8이고, b는 2이고
log 2의 8은 3입니다. 모든 컴퓨터 과학자들은 그것을 알아야 합니다.
n^log_b(a)=n^3 입니다.
그것은 다항적으로 n^2 보다 큽니다, 여기까지 케이스 1이었습니다.
고맙습니다. 그것들을 해 봅시다.
이것은 n^3 입니다, 우리의 이전 알고리즘 보다 좋지 않습니다.
별로에요.
그리고 이제 분할의 영감이 옵니다.
여기서 계속해 봅시다.
여러분이 조금 전에 있었던 곳이 이 피보나치 알고리즘 같은 알고리즘들이 있습니다,
그것은 큰 문제가 아닙니다.
여러분은 그것을 알아 낼 수 있습니다. 그 행렬을 보는 것은 현명하고
모든 것은 문제없이 작동됩니다.
그것은 명백하지 않지만 놀라울 정도로 현명한 것은 아닙니다.
이것은 놀라울 정도로 현명한 알고리즘입니다.
여러분은 그것을 전에 가로챈 것을 보았을 것입니다,
그러나 그것은 여전이 정말, 정말 좋습니다
그래서 여러분은 그것을 다시 보기 행복해야 합니다. 그리고 어떻게 Strassen이 이 알고리즘을 떠올렸을까요?
그는 매우 현명한 사람이었음에 틀림 없습니다.
그 생각은 우리가 이 곱셈들을 제거해야 하는 것입니다.
저는 100 덧셈을 할 수 있습니다. 그 비용은 단지 θ(n^2) 입니다.
저는 이 8을 더 작은 것으로 줄어야 합니다.
만약 여러분이 행렬을 3 곱하기 3 또는 다른 것으로 쪼개면,
그것은 여러분에게 도움이 되지 않습니다.
여러분은 같은 문제를 가지게 됩니다.
왜냐하면 우리는 근본적으로 같은 알고리즘을
다른 순서로 사용하고 있기 때문 입니다.
우리는 곱셈의 상수를 줄여야 합니다.
우리는 그것을 7로 줄일 것입니다.
우리가 2 곱하기 2 행렬을 가지면 우리는 7번의 곱셈을 이용해서 그것들의 곱을 가질 수 있습니다.
만약 그것이 맞으면,
우리는 8을 7로 줄이고 아마 그것들을 빠르게 돌아갈 것입니다.
우리는 곧 얼마나 빠른지 보게 될 것입니다.
여러분은 머리 속에서 계산할 수 있습니다.
여러분이 지루하고 정수 아닌 로그를
계산하는 것을 좋아한다면 계속 하세요.
좋아요. 해 봅시다.
이 알고리즘은 불행히도 다소 깁니다, 그러나
그것은 7번의 곱셈일 뿐입니다.
이 P들의 각각은 덧셈 또는 뺄셈 같은
두 개의 곱입니다.
이것들을 7 번의 곱셈입니다.
그리고 저는 7T(n/2)에서 그것들을 계산할 수 있습니다.
오, 정말 그렇군요. 6은 틀렸습니다.
6과 7은 같습니다, 매우 좋아요.
여러분은 무엇을 복사하는 것이 그리 도전적인 일이 아니라고 생각할 수도 있습니다.
그러나 여러분이 저와 같이 건망증이 심한 교수가 되면
여러분은 그것이 얼마나 쉬운지 알게 될 것입니다.
좋아요.
우리는 그것들을 모두 맞게 했습니다.
계속해봅시다. 그것들은 충분하지 않습니다.
물론 우리는 7 가지를 가지고 있었습니다. 명백히 우리는 이것을 4개로
줄여야 합니다, C의 인자로요.
여기에 C, r, s, t, u가 있습니다.
r=P_5+P_4-P_2+P_6 입니다.
물론이죠. 여러분은 모두 보지 않았나요?
저는 이것이 매우 쉽다고 생각해요,
s=P_1+P2. t=P_3+P_4.
그것은 명백히 그것들이 어떻게 선택되었는지 입니다.
그리고 u는 또 다른 까다로운 것입니다, u=P_5+P_1-P_3-P_7 입니다.
네. 이제, 여러분은 이것들 중 하나를 제가 검사하길 바라나요?
너무 착한 척하지 마세요.
S는 어떤가요? 저는 x가 옳다는 것을 여러분에게 보여줄 것입니다.
어떤 선호하는 것 있나요? u 이군요.
오, 안돼요, 에러가 있습니다.
네. 계속해봅시다. 이것이 정말 작동한다는 주장은 여러분이 그것들의 4개를
모두 검사해야 한다는 것입니다.
그리고 저는 그것을 제 노트에서 했습니다. u=P_5.
P_5=(ae + ah + de + dh). 그것은 P_5 입니다.
검사해보세요.
(af - ah) = P_1 입니다.
P_3은 앞에서 마이너스 기호를 가집니다, 그래서 그것은 (ce + de) 입니다.
그리고 나서 우리는 마이너스 P_7를 가집니다, 그것은 큰 것입니다,
(ae + af - ce - cf) 이에요. 네.
이제 저는 영화처럼 평행으로 그것들을 지우길 바랍니다,
네?
ah, de, af, ce, ae를 소거할 수 있네요. 고마워요,
그리고 이것들은 희망적으로 살아남았습니다. Dh 마이너스 마이너스 cf 입니다.
그리고, 만약 우리가 운이 좋다면, 그것은 정확히 우리가 여기 쓴 것입니다,
반대 순서를 제외하고요.
마술 같죠, 네? Strassen이 이것을 어디서 얻었을까요?
여러분은 신중해져야 합니다.
플러스가 잘못된 순서로 있는 것은 괜찮습니다
왜냐하면 플러스는 순서에 상관 없이 결과가 동일하니까요, 그러나 곱셈은 잘못된 순서이지 않는 것이 좋습니다
왜냐하면 행렬 곱셈은 순서에 따라 결과가 다르니까요.
저는 cf, dh를 검사합니다,
그것들은 제대로 된 순서에 있습니다.
저는 다른 세 가지는 검사하지 않을 것입니다.
그것은 정사각형이 아닌 행렬 곱셈입니다. 재귀를 써 봅시다.
T(n)은 이제 7 입니다.
아마 저는 알고리즘을 재미로 써야 할 것입니다.
왜 아니죠? 제가 시간을 가진다고 가정해보세요.
많은 시간을요.
저는 지난 시간에 10분 일찍 끝냈습니다.
사과 드려요. 저는 그것이 정말 여러분을 화나게 만든다는 것을 알고 있습니다.
그리고 저는 수업이 언제 끝나야 하는지 몰랐습니다.
그래서, 오늘은 제가 십분 늦게 갈 것입니다.
좋아요.
저는 여러분이 모두 동의해 주니 기쁩니다.
농담이에요. 걱정하지 마세요.
알고리즘입니다.
이것은 Strassen 입니다.
먼저 우리는 분할하고, 정복하고 결합합니다.
보통, 저는 그것을 여기서 쓰지 않습니다.
좋아요. A와 B를 분할합니다.
이것은 사소한 것입니다. 그리고 항들을 계산합니다.
이것은 우리가 P의 모든 것을 계산할 준비가 되었다는 것을 의미합니다.
우리는 a+b,
c+d, g-e, a+d, e+h 등을 계산합니다.
여기서 나타나는 모든 항들은, 우리가 계산합니다.
그것은 n^2의 시간이 걸립니다. 왜냐하면 그것은 많은 덧셈과 뺄셈이 있습니다.
큰 문제는 아닙니다.
그것들의 상수 개 입니다. 그리고 우리는 모든 P_i 들의 것을 재귀적으로 계산함으로써 정복합니다.
그것은 그것들의 7개의 곱셈입니다.
우리는 P_1, P_2 에서 P_7까지 가집니다.
그리고, 마지막으로, 우리는 결합합니다,
그것은 r, s, t, u를 계산하는 것입니다.
그리고 그것들은 다시 덧셈과 뺄셈입니다,
그래서 그것들은 n^2의 시간이 걸립니다.
그래서, 여기서 우리는 마지막으로 분할에서도 결합에서도 사소하지 않은 알고리즘을 얻습니다.
재귀는 항상 재귀이지만,
이제 우리는 흥미로운 단계 1과 3이 있습니다.
재귀는 T(n)이 개의 재귀적인 하위 문제들을 가지는 것입니다,
각각은 n/2 더하기 오더 n^2 사이즈 입니다, 이 모든 덧셈 작업을 하기 위해서요.
이제 우리는 이 재귀를 풀 필요가 있습니다.
우리는 n^log_b(a)를 계산합니다,
그것은 여기서 nlog_2(7) 입니다. 그리고 우리는 로그 2의 8이 3이라는 것을 알고 있습니다.
로그 2의 7은 3 보다 약간 작을 것이지만
여전히 2 보다는 큽니다 로그 2의 4가 2 이니까요.
그래서, 그것은 n^2 보다
다항적으로 크지만 n^3 보다 다항적으로 작습니다.
우리는 다시 케이스 1에 있습니다. 그리고 이것은 n 로그 2의 7, nlg7을
쓰는 속이는 방법입니다.
Lg는 로그의 지수 2를 말합니다. 여러분은 그것을 알아야 합니다.
그것은 교재 전반에 있고 우리 문제 세트에도 있습니다.
그리고 특히,
저는 여기서 계산기를 가지고 있습니다. 이것은 좋은 오래된 계산기 입니다.
아니네요, 그것은 잘못 되었습니다.
미안해요. 그것은 엄격하게 2.81 보다 작습니다.
그것은 엄격하게 2.81 보다 작습니다. 좋아요.
그것은 다항적으로 n^3 보다 낫습니다.
N^2인 덧셈 보다는 여전히 좋지 않지만요.
그것을 일반적으로 믿어집니다, 비록 우리가 여러분이 행렬을 위해 분할을 할 수 있는 한
가장 빠르게 곱셈을 하는지 모른다고 하더라도요.
우리는 여러분이 n^2를 얻을 수 없다고 생각합니다, 그러면 누가 알죠?
그것은 여전히 일어날 수 있습니다. lower bound 가 없습니다
이것은 행렬 곱셈을 위한 최고의 알고리즘이 아닙니다.
그것을 n^3를 이기는 가장 단순한 것입니다.
지금까지 최고는 n^2.376와 같은 것입니다.
2와 가까워지는 것이지요. 여러분은 이 수들이
이상하다고 생각할 수도 있습니다. 아마 여기서 정수들은
여러분이 지수에서 만큼의 개선을 제거합니다.
지수를 개선하는 것은 큰 문제가 아닙니다.
N이 커져감에 따라 지수는 정말 여러분을 이깁니다.
그래서, n^3은 매우 큰 값의 n에 대하여 매우 실용적이지 않습니다.
그리고 우리는 n이 충분히 크다면
Strassen이 보통의 행렬 곱셈을 이길 것이라는 것을 압니다
대략적으로 32에 대하여
또는 이미 여러분이 얻는 진보에서,
또 따른 이유들을 위하여, 지수가 나아지지 않기 때문에,
여러분은 계속 합니다. 그래서 이것은 매우 좋습니다.
이것은 완전히 실용적이지 않습니다,
그래서 이 알고리즘이 무엇이든 사용하지 마세요.
저는 참고도서가 없지만
그것은 이론적인 개선을 얻으려고 합니다.
와우, 시간이 많이 남았네요.
질문 있나요? 우리는 아직 다 하지 않았지만
우리가 행렬 곱셈으로 계속 가기 전에 질문 있나요?
좋아요.
저는 하나의 문제를 더 가집니다.
분할 정복은 매우 일반적인 생각입니다.
여러분은 그것을 나라를 정복하기 위해 사용할 수 있습니다.
여러분은 그것을 행렬을 곱하기 위해 사용할 수 있습니다.
누가 생각해 본 적 있나요? 여러분이 분할 정복으로 풀 수 있는
매우 다른 유형의 문제들이 여기 있습니다.
이것은 정확히는 알고리즘 문제가 아닙니다,
어떤 사람들은 컴퓨터 과학이라고 하더라고요.
그것은 명백합니다 이것은 매우 큰 범위의 통합입니다.
칩들은 매우 큰 스케일로 통합된 것입니다.
아마 이 날들보다 더 그럴 것이지만,
그것은 캐치프레이즈입니다. 여기 문제가 있습니다
그것은 VLSI 레이아웃에서 그렇습니다 우리는 왜 그런지 너무 자세히는 얻지 않을 것이지만,
여러분은 어떤 회로를 가집니다.
그리고 여기서 저는 회로가 이진 트리라고 가정할 것입니다.
이것은 회로의 일부입니다.
지금 여기서는 그것이 완벽한 이진 트리라고 가정하세요.
완벽한 이진 트리는 이와 같습니다.
제 모든 강의에서, 저는 이 그림을 최대한 그립니다.
그것은 제가 가장 좋아하는 그림입니다,
높이 4의 완벽한 이진 트리 입니다.
네, 이것입니다. 저는 어떤 높이의 트리를 가지고 있습니다.
저는 그것을 어떤 칩에 이식하고 싶습니다.
그것이 n 개의 잎을 가지고 있다고 말해봅시다.
저는 그것을 최소 범위의 그리드 안에 이식하고 싶습니다.
이것은 매우 귀여운 문제이고 그것은 정말 여러분에게 분할 정복이 유용하고
강력한 도구라는 것을 보여주는 또 다른 방법입니다.
그래서, 저는 이 트리를 가집니다. 저는 그것을 이런 방법으로 그리고 싶습니다.
저는 그것을 그리드에서 그리고 싶습니다.
그것이 의미하는 것은 꼭지점이 그리드에서 점으로 넣어져야 한다는 것입니다,
그리고 저는 정사각형 그리드에 대해 이야기할 것입니다.
그것은 그리드의 꼭지점으로 가야 합니다.
그리고 이 가장자리들은 이 점과 다른 점 사이에서 직각의 길로써 보내져야 합니다,
그래서 그것은 가장자리여야 합니다.
이 문제를 푸는
명확한 방법이 있고
옳은 방법이 있습니다.
그것들 모두에 대해 이야기해 봅시다.
그것들은 모두 특별히 명확하지는 않지만, 분할 정복은
여러분에게 옳은 방향에서 힌트를 줍니다.
소박한 이식입니다. 저는 여기서 소박한 이라는 단어를
쓰고 있군요.
저는 이것을 아래로 그릴 것입니다. 왜냐하면 그것이 더 쉽기 때문입니다.
그래서 세 그리드 선을 남기고 그리기 시작할 것입니다.
저는 그것이 얼마나 커질지 모릅니다.
여기 우리 트리의 아랫부분이 있습니다. 이것은 저기서 작은 세 노드들과 같습니다.
그리고 저는 빈 열을 남길 것입니다.
저는 사실 여기 빈 열들을 남기는 것이 필요하지 않지만,
그것은 더 보기 좋은 형태가 되겠네요. 889 00:58:25,414 --> 00:58:30,000 그리고 우리는 우리의 방법으로 할 것입니다.
트리가 있습니다, 그것은 그리드에서 일직선이어야 합니다.
대각선은 안됩니다.
모든 것은 완벽하네요. 그것이 얼마나 많은 공간을 차지하죠?
공간에 의해, 아 공간이라는 건 가장자리 박스를 의미합니다.
그래서, 저는 제가 그것을 사용하지 않더라도 이 빈 공간을 셀 수 있고
제가 그것을 사용하지 않더라도 저는 이 모든 빈 공간을 셀 수 있습니다.
저는 높이를 보고 싶습니다. 이것을 H(n) 이라고 합니다.
그리고 넓이를 보기 위해, 그것은 제가 W(n) 이라고 하겠습니다.
이제, H(n)이 log n 과 같고 W(n)이 n 또는 다른 것과 같다는 것은 아마 매우 명백합니다.
그러나 저는 그것을 재귀로써 쓰고 싶습니다.
왜냐하면 그것은 우리에게 맞는 방향으로 가도록 영감을 주기 때문 입니다.
H(n) 입니다.
자, 만약 여러분이 이것을, 어떤 면에서, 재귀 트리로 생각한다면요.
우리는 큰 트리로 시작하겠습니다.
우리는 그것을 두 부분으로 나누겠습니다. 사이즈가 n/2인 두 개의 하위 트리로요.
왜냐하면 우리는 잎을 셀 것입니다. 그것은 각 면이 정확히 n/2 입니다.
그리고 높이를 위해 그것들은 평행하고 그것은 큰 문제가 아닙니다.
높이는 단지 이것의 높이입니다,
이 하위 문제들의 1 더하기 1입니다.
넓이는, 여러분이 두 넓이를 함께 더하고,
또한 1을 더해야 합니다.
여러분은 여기서 1을 더할 필요가 없지만, 그것은 중요하지 않습니다. 그것은 확실히 많아 봐야 1 입니다.
H(n) = H(n/2) + θ(1) 이고, 여러분은 저기서 1을 더해야 합니다.
그리고 W(n) = 2W(n/2) + O(1) 입니다. 보통의 기본적인 경우입니다.
우리가 알고 사랑해야 하는 재귀들도 있습니다.
이것은 log n 입니다, 저는 이미 답을 주었습니다,
그리고 이것은 선형인 것이 좋습니다.
이것은 다시 케이스 1입니다. 그리고 로그 2의 2는 n입니다,
그것이 답입니다, 1보다 훨씬 큽니다.
그리고 여기서 n의 로그 2의 1은 n의 0제곱이고,
그것은 1입니다, 그것은 같고 우리는 lg n을 얻습니다.
범위는 n log n 입니다, 그러나 여러분이 칩들을 만들길 원한다면
여러분은 가능한 한 작은 범위를 원해서 여러분이 거기서 좋은 것에 맞을 수 있기를 원합니다.
그래서, 우리는 n 보다 나은 범위를
확실히 할 수 없습니다.
여러분은 잎들을 어딘가에 두어야 합니다,
그러나 이것은 이미 좋습니다.
그것은 로그 인자 입니다, 그러나 우리는 n을 목표로 합니다.
우리가 어떻게 n을 구할 수 있나요? 이 레이아웃에 무엇이 바뀌어야 하는지 않아요?
어떻게 하는지가 아닙니다 왜냐하면
그것은 명확하지 않거든요, 그러나 높이와 넓이의 관점에서
우리는 무엇을 해야 합니까? Log n 보다 작은 높이를 구하는 것은
매우 어렵습니다.
왜냐하면 이것은 트리이기 때문입니다. 그것은 정말로 넓이를 log n 보다 작게 할 수 없습니다.
우리가 곱을 선형으로 하기 위해 무엇을 할 수 있나요?
아무 생각이라도 좋아요.
곱이 n인 두 함수는 무엇인가요?
루트 n과 루트 n.
그것은 좋은 선택입니다. 다른 제안 있나요?
N 곱하기 정수. 네, n 곱하기 정수도 좋습니다.
그러나 저는 여러분이 이것들을 모두 정수보다
작게 해야 한다고 말하고 싶습니다.
여러분은 log n 분의 n 나누기 log n을 목표로 할 수 있습니다, 그것은 더 그럴 듯 하지만,
저는 이것이 거의 불가능하다고 생각합니다.
루트 n 나누기 루트 n은 옳은 답입니다. 그래서 그것을 가지고 해 봅시다,
루트 n 나누기 루트 n을 가지고요. 우리는 답이 루트 n인 어떤 재귀도 보지 못했지만,
그것들은 저기 확실히 있습니다.
목표는 W(n) = Theta(root of n) 을 구하고 H(n) = Theta(root of n) 을
구하는 것입니다.
우리가 괜찮다면, 곱은 선형이기 때문입니다.
어떻죠? 답이 루트 n인 보통의 마스터 메소드 형태에서
있는 재귀는 무엇인가요?
여러분은 그것을 그 방법으로 생각할 수 있습니다.
재귀는 약간 까다롭습니다. 그러나 n^log_b(a) 에 대해 생각해 봅시다.
언제 로그 b의 a ½ 인가요?
n^log_b(a)이 루트 n이기 때문입니다.
그리고 제가 루트 n의 답을 구할 수 있으리라는 희망이 있습니다.
이것은 그것이 분할 정복이라는 것을 앎으로써 설계되었고,
그러므로 그것은 이와 같은 것이 되어야 합니다.
여러분이 한 번 접근법을 알게 된다면 그것은 쉽습니다.
여러분은 그것을 가지고 이 접근법을 시도 할 수 있습니다.
언제 로그 b의 a ½ 인가요?
많은 답들이 있습니다.
4와 2, 좋은 답이에요. 저는 이것을 옳게 하는 것이 좋겠네요.
로그 4의 2는 ½ 입니다. 왜냐하면 4의 제곱근이 2이니까요.
그래서, 이를 목표로 해 봅시다. 왜 안되나요?
우리가 로그 4의 2를 언제 얻을 수 있죠?
이것은 b이고, 이것은 a 입니다, 그래서 그것은 2T(n/4) 더하기 무엇이 되어야 합니다.
그리고 만약 제가 n^log_b(a) 가 제거하길 원한다면,
그것은 다항적으로 루트 n 보다 작아야 합니다.
그래서, 이것은 n^1/2-ε이 되어야 합니다.
그러나 그것은 더 작을 수 있습니다.
그것은 1일 수 있습니다. 0도 좋습니다,
그러나 그것은 아마 너무 많이 바란 것 같군요.
그래서, 더 작은 것, 엄격하게 다항적으로 루트 n 보다 작은 것입니다.
그것이 우리의 목표입니다.
그리고 이제 마법이 일어납니다. 만약 여러분이 이것을 가지고 잠시 놀고 싶다면
여러분은 이 점에서, 그것을 찾을 것입니다.
여러분이 사이즈 n/4인 두 하위 문제들을 가지고 사이즈 n인
이 문제를 풀 때 여러분은 무엇을 할 수 있나요?
자, 만약 여러분이 이것을 정사각형으로 생각하기 시작한다면,
이것은 자연스러운 것입니다.
이것은 H 레이아웃이라는 것입니다. 여러분은 이유를 상상할 수 있습니다.
제가 격자판, 그래프 보드 같은 것을 가지고 있다면
훨씬 그리기 쉬울 것입니다
이것은 재귀 레이아웃 입니다. 저는 몇 가지 연산자를 그릴 것이지만,
희망적으로 여러분은 일반화를
상상할 수 있습니다.
저는 4개의 H를 가집니다, 좋은 계획입니다 제가
사이즈 n/4의 문제를 원하니까요. 이것은 n/4 잎들을 가집니다.
이것은 n/4 잎들을 가집니다. 그런데, 이것은 중간에서 루트입니다.
이것은 n/4 잎들을 가집니다.
이것은 n/4 잎들을 가집니다. 그래서, 저는 사이즈 n/4의 4개의 문제를 가집니다.
저는 그것을 둘로 해야 합니다.
고맙게도, 제가 높이를 보면 또는 넓이를 보면,
중요한 것은 두 가지 입니다.
그리고 이 두 가지는 중요하고 이 두 가지는 같이 있습니다.
그것들은 평행입니다, 우리가 여기서 높이를 가지고 했던 것처럼요.
그러나 저는 높이와 넓이를 둘 다 얻을 것입니다.
제가 측정한다면,
자, 이제 그것들은 같습니다, 그래서 저는 그것들을 길이라고 부를 것입니다.
우리는 L(n) 곱하기 L(n) 을 가집니다.
그리고 제가 계산을 하면, L(n)이 무엇이죠?
저는 여기 L(n)을 가지고 있습니다
. 왜냐하면 이것 또는 저것에 4분의 1의 잎이 있기 때문입니다.
저는 정수 θ(1)을 가지고 있습니다, 큰 문제는 아닙니다, 그리고 다시 L(n/4)을 가지고 있습니다.
그래서, 저는 제가 원했던 재귀를 얻습니다.
L(n) = 2L(n/4) + θ(1) 입니다. 그리고 그것은 n 제곱근의 답을 가집니다,
우리가 전에 주장했던 것처럼요. 다시, 우리는 마스터 메소드의 케이스 1에 있습니다.
좋죠?
이것은 더욱 압축적인 레이아웃입니다.
찰스, 이 레이아웃을 도입했었나요?
아니군요. 그러나 저는 그것이 당신의 박사 학위 논문에 나타난다는 것을 알고 있습니다
당신은 그것을 다양한 방향으로 연장했습니다.
그래서, 이것은 일종의 고전적인 트리 레이아웃이고
분할 정복의 또 다른 응용입니다.
저는 이것이 알고리즘에 대하여 직접적으로 특별히 유용한 것이 아니라고 생각합니다.
이것은 VLSI 레이아웃에 대하여 직접적으로 유용합니다.
그러나 그것은 여러분에게 여러분이 생각해야 하는 방법에 대한 느낌을 더욱 줍니다.
만약 여러분이 퀴즈의 문제 세트에서처럼 여러분이 목표로 하는 러닝 타임이 얼마인지 안다면,
여기서 우리는 종종 여러분이 가져야 하는 러닝 타임에 대해 말합니다.
여러분이 저기서 얻는 재귀에 대해 생각해보세요.
그리고 그것은 여러분에게 영감을 줄 수 있습니다.
금요일에 수업이 있습니다.
일요일엔 숙제 실험실이 열립니다. 월요일엔 수업이 없습니다.
수요일에 봅시다.