[MIT 6.006] 1. Algorithms and Computation

MIT 6.006 강의 1강 Algorithms and Computation을 보고 정리한 포스트 입니다.

또한 부족한 개념 설명은 Introduction of Algorithms 책을 참고하여 작성하였습니다.

이 수업의 goal은 계산 문제를 해결하고 너의 해결책이 얼마나 정확하고 효율적인지에 대해서 의논할 수 있게 가르킨다.

What is Algorithms?

알고리즘이란 마치 function 함수와 같이 input에 하나의 output이 무조건 대응되게 하는 procedure 절차라고 할 수 있다.

Introduction of Algorithms p.28
Well defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output in a finite amout of time. An algorithm is thus a sequence of computational steps that transform the input into the output.

input : 알고리즘에서 입력으로 쓰이는 데이터는 현재 환경에 국한 되지 않고 변화되는 환경의 데이터도 포함된다

따라서 알고리즘은 이러한 arbitrarly sized input, 임의의 크기의 입력에서 general problem instances의 모든 입력 출력 관계를 나타낼 수 있어야 한다.

Birthday Problem

한 반에 생일이 같은 사람은 몇명이 있을까? 이 문제에 대해서 생각해보자

이 문제를 해결하기 위해서는 다음과 같은 알고리즘을 생각할 수 있다.

1. maintain record : 학생들의 생일을 기록

2. interview students in some order : 일련의 순서로 학생들에게 생일을 질문한다.

3. check if birthday in record : 기록에 해당 생일이 있었는지 확인한다

4. if there is a match, return the pair. if not, add new student in record : 만약 생일이 같은 사람이 있다면 그 쌍을 반환하고, 없다면 새로운 학생의 생일을 기록한다.

5. return None if last student interviewed without success : 만약 마지막 학생까지 생일인 쌍이 없다면 None을 반환한다.

correctness

생일 매칭 문제의 정답성을 수학적 귀납법을 이용해서 증명해보자. k는 기록된 학생들의 숫자이자.

1. Inductive hypothesis (가설) : if first K students contain match algorithms, the algorithms returns a match before interviewing student K+1 
2. Base Case : k = 0 일때, first k 첫번째 학생은 매칭되는 학생이 없으므로 k=1을 매칭한다 것이 없다.
3. Assume for induction hypothesis : k = k'일때랑 k = k'+1일때를 고려해보자
	- k = k' 일때 match가 있던 경우 : k'번째 학생이 이미 기록된 학생 중에 match가 있다면, 가정에 따라 return the match
    - k = k' + 1 일때 match가 있던 경우: k'번째 학생이 이미 기록된 학생 중에 match 가 없다면, k' + 1번째 학생을 인터뷰한다. 이때 k'+1번째 학생의 매칭이 첫 k'번째에 있는지 확인하고 매칭을 반환한다.

이러한 증명방법을 통해 앞으로 많은 알고리즘의 correctness를 증명할 예정이다.

Efficiency

이제는 어떻게 알고리즘의 효율성 (efficiency) 를 증명할 수 있을까?

가장 먼저 떠오르는건 얼마나 빠르게 동작하는가 즉 time 시간을 측정할 수 있다.
다만, 컴퓨터의 사양에 따라 똑같은 알고리즘을 실행한다고 해도 time이 다르게 측정될 수 있다. 그렇기 때문에, 컴퓨터의 사양에 영향을 받지 않는 performance가 효율성의 측정 기준이 된다.

컴퓨터의 사양에 영향을 받지 않으려면 operations(연산량)을 측정하는 것이 적합하다. 연산량은 입력의 크기 n에 종속적이며 보통 n이 클수록 실행시간도 늘어나기 마련이기 때문에 큰 입력 n에 대해서 빠른 실행 시간을 내는 알고리즘이 효율적이다.

Comparing Algorithms efficiency based on their asymptotic performance relative to problem input size, in order to ignore constant factor differences in hadware performance

Asymptotic Notation

그래서 알고리즘의 효율성은 입력의 크기에 따른 점근적 성능을 측정한다.
이때 사용되는 입력 크기 n에 대한 연산량의 크기를 나타내는 notation에 대해 알아보자.

1. O(n) 표기법

• Definition : non-negative function $g(n)$이 $g(n) \geq cf(n)$ 를 만족시키는 $n \geq n_0$ 에서 양의 실수 $c$가 존재할때 $f(n)$은 $g(n)$의 빅오이다.
• 즉, 이 정의에 의해 충분히 큰 입력에 대한 점근적 성장에 대한 상한선을 의미한다.
• 이 상한선은 $g(n)$에 상수배를 하거나 shift를 해도 그래도이다.

2. $\Omega$(n) 표기법

• Definition : non-negative function $g(n)$이 $g(n) \leq cf(n)$ 를 만족시키는 $n \geq n_0$ 에서 양의 실수 $c$가 존재할때 $f(n)$은 $g(n)$의 빅오이다.
• 즉, 이 정의에 의해 big O와는 반대로 하한선을 의미한다.

3. $\Theta$(n)

• Definition : non-negative function $g(n)$이 $g(n) \geq cf(n)$ 를 만족시키는 $n \geq n_0$ 에서 양의 실수 $c$가 존재할때 $f(n)$은 $g(n)$의 빅오이다.
• 즉, 이 정의에 의해 $f(n)$은 $g(n)$의 tight bound이다.

이러한 표기 방법들은 상 factor랑 low order terms들은 무시하고 표현된다.