[이산수학]알고리즘

많은 문제들은 일반적인 문제들의 특별한 경우로 생각하여 풀 수 있다. 예를 들면 다음과 같다.

1. n개의 정수를 담은 튜플이 주어졌을 때, 최소 원소를 찾으시오.
2. n개의 정수를 담은 튜플이 주어졌을 때, 최대 원소를 찾으시오.
3. n개의 정수를 담은 튜플이 주어졌을 때, 짝수 정수를 모두 찾으시오.

이러한 문제들은 정수들 중에서 특정 성질을 만족하는 정수를 찾는 문제의 특별한 형태이다. 일련의 절차를 통해 일반화된 문제를 푸는 방법이 필요하다. 이러한 일련의 절차를 알고리즘이라 한다.

알고리즘은 여러 경우로 일반화할 수 있다.

1. 정수의 서열이 주어졌을 때, 가장 큰 수를 찾으시오.
2. 집합이 주어졌을 때, 모든 부분집합을 나열하시오.
3. 정수의 집합이 주어졌을 때, 점점 커지는 순서대로 원소를 나열하시오. (정렬)

그렇다면 알고리즘은 다음과 같이 정의할 수 있다.

알고리즘이란 일반화된 문제 해결 방법을 기계적 절차로 나열한 것이다.

여기서 기계적 절차란 수학적인 의미다. 이후에 다룰 오토마타에 대한 이야기다.

이 블로그에서는 C++이나 Java와 같은 프로그래밍 언어보다는 의사 코드를 통해 알고리즘을 작성할 것이다. 하지만 의사 코드의 구체적인 동작은 일일이 설명하지 않을 것이다. 따라서 이 부분은 의사 코드를 이해하기 위해 따로 프로그래밍 언어를 직접 공부를 해야할 수 있다는 점, 미리 양해를 바란다.

알고리즘은 절차를 그대로 한국어나 영어를 통해 나열할 수 있지만, 알고리즘의 설명이 복잡해지고 이해하기 어려워질 수 있다.

의사 코드는 자연어와 프로그래밍 언어를 적절히 혼합하여 사용한다. 예를 들어 주어진 수열 중 가장 큰 값을 찾는 알고리즘은 다음과 같이 의사 코드를 통해 작성할 수 있다. 참고로 컴퓨터 과학에서는 함수를 프로시저(procedure)라고 하기도 한다.

 

$\mathrm{procedure}\ max(a_1,\ a_2,\ \cdots,\ a_n:\ \mathrm{Integers})$

$\mathrm{max}\ :=\ a_1$

$\mathrm{for}\ i\ :=\ 2\ to\ n$

$\quad \mathrm{if\ max}\ <\ a_i\ \mathrm{then\ max}\ :=\ a_i$

$\mathrm{return\ max}$

 

알고리즘의 속성

알고리즘은 구체적으로 다음과 같은 속성들을 만족시켜야 한다.

1. 입력(input): 알고리즘은 특정한 집합으로부터 입력값을 받는다.
2. 출력(output): 각각의 입력값의 집합으로부터 알고리즘은 이에 대한 출력값을 내놓는다.
3. 명확성(definiteness): 알고리즘의 각 단계는 명확하게 잘 정의되어 있어야 한다.
4. 정확성(correctness): 알고리즘은 어떤 입력값에 대해서도 항상 그에 적절한 답을 내놓아야 한다.
5. 유한성(finiteness): 알고리즘은 항상 유한한 시간안에 답을 내놓을 수 있어야 한다.
6. 효율성(effectiveness): 구현할 수 있고 실용적이어야 한다.
7. 일반성(generality): 특정한 입력 집합뿐 아니라, 조건을 만족하는 모든 입력에 대해서도 적당한 답을 내놓아야 한다.

 

여러 알고리즘들

---

탐색 알고리즘

선형 탐색(Linear search): 제일 처음 배울 알고리즘이다. 선형 탐색은 순차 탐색이라고도 불리며, 배열이 주어지면 그 배열의 첫 번째부터 끝까지 차례대로 찾으려는 원소 $x$가 어디에 있는지 탐색한다.

 

$\mathrm{procedure}\ linear\ search(x:\ \mathrm{Integer},\ \vec v: \mathrm{n-tuple})$

$\mathrm{for}\ i\ :=\ 1\ \mathrm{to}\ n$

$\quad \mathrm{if\ }v_i=x\ \mathrm{then\ return\ } i$

$\mathrm{return\ }$-1

 

-1은 해당 튜플에서 $x$라는 값을 찾을 수 없는 경우이다.

위 알고리즘은 함수로 보자면 다음과 같다.

$$ \vec v=(v_1, v_2, v_3, \cdots, v_n) \\ f(\vec v,t,i)=\begin{cases} i & \mathrm{if}\ u_i=t\\ -1 & \mathrm{if}\ n<i \\ f(\vec u,t,i+1) & \mathrm{otherwise} \end{cases} \\ LS(\vec v, t)=f(\vec v, t, 1) $$

 

이진 탐색(Binary search): 이진 탐색은 탐색 범위를 반씩 줄이며 탐색하는 알고리즘이다. 정렬된 배열에 대해서만 올바르게 작용한다.

 

procedure binary search$(x:\mathrm{integer},\ \vec v:n-\mathrm{tuple})$

$i$ $:=$ 1

$j$ $:=$ n

while $i < j$

$\quad$m $:=$ $\lfloor (i+j)/2\rfloor$

$\quad$if $x>v_m$ then $i$ $:=$ $m+1$

$\quad$else $j$ $:=$ m

if $x=v_i$ then $location$ := $i$

else $location$ $:=$ -1

return $location$

정렬 알고리즘

버블 정렬(Bubble sort): 버블 정렬은 정렬 알고리즘 중 가장 기초적인 알고리즘이다. 물론 제일 효율적인 알고리즘 아니다. 배열들의 성분이 무작위로 배치됐을 때, 이를 오름차순으로 정렬해주는 알고리즘이다. 서로 인접한 2개의 원소의 대소를 비교하고, 정렬한다.

 

procedure bubble sort$(\vec v:n-\mathrm{tuple})$

for $i\ :=\ 1$ to $n-1$

$\quad$for $j\ :=\ 1$ to $n - 1$

$\quad$$\quad$if $a_j>a_{j+1}$ then

$\quad$$\quad$$\quad$$t\ :=\ a_j$

$\quad$$\quad$$\quad$$a_j\ :=\ a_{j+1}$

$\quad$$\quad$$\quad$$a_{j+1}\ :=\ a_j$

return $\vec v$

 

선택 정렬(Selection sort): 선택 정렬은 가장 작은 원소를 찾아 첫 번째 자리에, 두 번째 최소 원소를 찾아 두 번째 자리, $n$번째 최소 원소를 찾아 $n$번째 자리에 배치하는 방식으로 정렬하는 알고리즘이다.

 

procedure selection sort$(\vec v:n-\mathrm{tuple})$

$\vec u:=(0,0,0,\cdots,0):n-\mathrm{tuple}$

for $i := 1$ to $n$

$\quad$$m:=v_i$

$\quad$for $j := i$ to $n$

$\quad$$\quad$if $v_i<m$ then $m:=v_i$

$\quad$$u_i:=m$

return $\vec u$

 

기초적인 알고리즘은 아직 많이 있지만 컴퓨터 과학에서 중요한 정리를 소개하기 위해 알고리즘은 여기까지 소개하겠다.

 

정지 문제

---

컴퓨터 과학에서 가장 유명한 정리 중 하나이다. 정지 문제는 다음과 같은 문제를 말한다.

알고리즘과 그 알고리즘의 입력이 주어졌을 때, 알고리즘에 입력값을 넣으면 알고리즘이 정지하는지에 대한 알고리즘이 존재하는가?

예를 들어 다음과 같은 함수를 하나 정의하자.

 

procedure f$(x:\mathrm{integer})$

if $x=0$ then return $x$

else

$\quad$for $i:=1$ to $\infty$

$\quad$$\quad$$x:=x+1$

 

위 함수는 입력이 0이면 0을 반환하며, 그 이외에는 무한 루프에 빠진다. 위 함수와 입력 $x$가 주어졌을 때, $x$가 0이 아니면 함수는 정지하지 않는다는 것을 알 수 있다. 이제 이를 임의의 알고리즘(함수) $P$와 그 알고리즘의 입력 $n$으로 일반화하자. 그렇다면 $P(n)$이 정지하는지, 정지하지 않는지에 대한 답을 내놓는 알고리즘이 존재하는가에 대한 문제가 정지 문제다. 결론부터 말하면 존재하지 않는다.

이제부터 이를 증명할 것이다. 증명은 귀류법으로 이루어진다. 때문에 임의의 알고리즘 $P$와 입력 $n$에 대해서 $P(n)$이 정지하는지 결정할 수 있는 함수 $H(P,n)$가 존재한다고 해보자. 함수 $H(P,n)$는 $P(n)$이 정지한다면 True를 반환하고 그렇지 않다면 False를 반환한다. 그렇다면 다음과 같은 함수를 정의할 수 있다.

 

procedure test$(P:\mathrm{procedure})$

if $H(P, P)$ is False then return True

else

$\quad$for $i:=1$ to $\infty$

$\quad$$\quad$$\cdots$

 

함수 $P$가 무한 루프에 빠진다면 함수 $test$는 True를 반환하며, 반대로 무한 루프에 빠지지 않고 정지한다면 함수 $test$는 무한 루프에 빠진다. 여기서 $H(P,P)$가 의아하게 여겨질 수 있지만 자기 자신을 입력으로 받는 것이 가능하다. 함수 $P$는 컴퓨터 내부에서는 결국 이진수 값이기 때문에 입력이 될 수 있다.

 

이제 함수 $test$에 자기 자신을 입력하여 확인해보자. 그러면 함수 $test(test)$가 정지하는 경우와 정지하지 않는 경우, 총 2가지로 나뉜다. 이 2가지를 확인해보자.

 

1. $test(test)$가 정지한다.

$H(test, test)$는 True를 반환할 것이다. 그렇다면 $test(test)$는 무한 루프에 빠진다.

이는 모순이다. $H(test, test)$는 True를 반환, 즉 분명히 정지한다고 답했다.

 

2. $test(test)$가 정지하지 않는다.

$H(test, test)$는 False를 반환할 것이다. 따라서 $test(test)$는 True를 반환할 것이다. 이는 모순이다. $test(test)$는 $H(test, test)$가 False를 반환했기 때문에 어떠한 무한 루프에 빠져야 한다.

 

함수 $test$는 알고리즘의 정확성에 위배되는 알고리즘이다. 때문에 함수 $test$는 알고리즘이 될 수 없다는 결론에 다다르게 된다. 그리고 이는 함수 $H$가 존재한다는 가정 위에 정의된 함수이기 때문에 가정 자체가 모순임을 알 수 있다.

따라서 함수 $H$는 존재하지 않는다.