Lecture 2: Models of Computation (연산을 위한 모델들)

1. 배우는 것: 

- 알고리즘이란 무엇인가? 시간이란 무엇인가?

- 랜덤 접근 기계 (Random Access Machine)

- 포인터 머신

- 파이썬 모델

- 문서 간 거리 (Document distance): 고찰과 알고리즘

 

 

2. 알고리즘이란 무엇인가?

- 컴퓨터 프로그램의 수학적 추상화

- 문제를 해결하기 위한 computational procedure

 

 

*model of computation은 다음을 명세한다

: 알고리즘이 수행 가능한 연산들, 각 연산의 비용(시간, 공간 등)

 

알고리즘의 비용 = 모든 연산의 비용의 합

 

3. 랜덤 액세스 머신 (Random Access Macine)

- 랜덤 액세스 머신은 큰 배열로 표현될 수 있다.

- 시간복잡도 Θ(1)의 레지스터들 (각 1워드)

- Θ(1) 시간동안, 

 > load word @ r_i into register r_j

 > 더하기, 빼기, 곱하기, 나누기, 논리연산들을 레지스터에서 수행

 > 레지스터 r_j를 메모리 r_i로 적재할 수 있다

- 현실적이고 추상화를 함에 있어 강력하다

 

4. 포인터 머신 (Pointer Machine)

- 동적으로 할당된 객체들 (named tuple)

- 객체들은 O(1)의 필드를 갖고 있다

- 필드(= 워드) 또는 포인터를 object/null에 대응

- 랜덤 액세스 머신보다는 약함

 

5. 문서 간의 거리 측정 (Document Distance Problem) - d(D_1, D_2) 계산하기

문서 간 거리 측정은 유사한 문서를 찾거나 복제나 표절을 감지하는 데에 응용되며 웹 검색에서도 많이 사용된다.

 

몇 개의 정의:

 - Word = 글자와 숫자의 집합

 - Document = 워드의 집합 (스페이스와 문장부호 등은 무시)

 

공유된 워드를 중심으로 문서 간의 유사도를 측정한다.

문서 D를 벡터로 생각해보자. D[w] 를 워드 W의 등장 횟수로 본다면,

 

위와 같은 표현이 가능하다. 

 

처음 드는 생각으로는, 문서 간 거리를 

다음과 같은 식으로 구할 것이라 생각하지만, 이 식의 문제점은 단어의 등장 횟수, 즉 벡터의 길이가 결과값에 그대로 반영된다는 것이다. 이 뜻은, 99%의 단어가 일치하는 긴 문서보다 10%만이 일치하는 두 문서가 더 작은 결과값을 나타낼 수도 있다는 것이다. (실제 문서 간 거리는 전자가 더 가까운 데도 말이다)

 

따라서 이는 등장하는 단어의 수 정규화하는 것으로 해결할 수 있다:

 

|D_i|의 문서의 단어의 개수라 할 떄, 이것의 기하학적 해석은 다음과 같을 것이다.

 

문서 간 거리(유사도)란, 벡터들 간의 사잇각인 것이다. 0도의 각도는 두 문서가 완벽히 일치함을 나타내고, 90도의 각도는 공통된 단어가 하나도 없음을 나타낸다. 

 

6. 문서 간 거리 알고리즘 (Document Distance Algoritm)

1. 각 문서를 단어 단위로 쪼갠다

2. 단어의 빈도를 측정한다

3. 벡터들을 내적한다

 

문서 간 거리 측정을 위한 슈도코드와 복잡도: