[COSE214] 알고리즘 기초 개념

알고리즘이란 무엇이며, 이가 가지는 특성과 구성요소에 대해 서술하시오. 알고리즘을 통해 모든 computational problem을 solve 할 수 있는가?

Computational problem은 어떠한 input이 주어졌을 때 어떠한 output이 기대되는지를 명확하게 specification 한다. 이 때 computational problem은 여러 가지 형태의 입력 데이터인 instance를 가질 수 있다. 

알고리즘이란 computational problem에서 정확한 output을 계산하기 위해 수행해야 할 작업에 대한 명확한 설명으로, 1) finiteness를 가져 유한한 단계의 수를 가져야 하며, 2) 주어진 문제의 모든 instance에 대해 올바른 output을 계산하기 위한 correctness를 가져야 한다. 

알고리즘을 구성하는 요소로는 number of steps가 결정하는 time complexity, 차지하는 메모리가 결정하는 space complexity가 존재한다. 둘 중 하나가 높으면 하나를 손해봐야 하는데, 이를 trade off situation이라고 한다. space complexity를 위해 time complexity를 희생하는 것을 hash table이라고 하고, time complexity를 위해 space complexity를 희생하는 것을 dynamic programming이라고 한다. 

computational problems는 uncountable하지만, algorithms는 countably infinite 하다. 따라서 이 두 집합은 1:1 대응하지 못하므로, 이는 다르게 말하면 항상 algorithmically unsolvable 한 problems가 존재한다는 것을 의미한다.

 

 

Halting problem이 무엇인지에 대해 설명하고, 이를 증명하시오.

Halting problem이란 “어떤 입력값을 받았을 때 어떤 프로그램이 유한한 단계를 마치고 멈추는지, 아니면 무한 루프 하는지를 판별할 수 있는 알고리즘이 존재하는가?”라는 질문이다. 이러한 halting problem은 solvable 하지 않다는 것을 귀류법을 통해 증명할 수 있다. 무한루프를 검토하는 프로그램을 HALT라고 한 후, HALT를 만드는게 가능하다고 가정한다. 그 후 HALT가 오류를 일으키는 경우를 찾아서, 전제에 모순되므로 HALT를 만드는 것이 불가능하다는 것을 증명한다. 

 

 

Incremental approach로 알고리즘을 디자인 하는 방법에 대해서 서술하시오.

incremental approach는 문제를 subproblems로 분해한 후, subproblems를 순차적으로 해결하여 전체 문제의 해결책을 구축하는 방식이다. incremental approach를 이용해 알고리즘을 디자인 하기 위해서는 먼저 1) 문제를 subproblems들로 분해하고 2) subproblem을 해결하는 알고리즘을 디자인 한 후 3) subproblem의 해결책을 결합하여 전체 해결책을 만든 후 4) 단계적으로 문제를 확장하고 개선한다. 

Incremental approach의 대표적인 예시로는 Insertion sort가 있다. Insertion sort는 배열을 구성하고 있는 숫자를 하나씩 선택하여 앞의 숫자들과 비교해 적절한 위치에 삽입하여 정렬하는 방식이다. 

이 때 time complexity는 두 가지로 나눠서 생각해볼 수 있다. best case는 배열이 이미 정렬되어 있는 경우로, Insertion Sort 시 각 요소를 비교하지만 이동은 발생하지 않는다. 따라서, 최선의 경우에는 시간 복잡도가 O(n)이 된다. Worst case의 경우 배열의 모든 요소에 대해 비교 및 이동이 필요하므로, 1+2+...+(n-1) = n(n-1)/2 번의 비교가 발생하고 시간 복잡도가 O(n2)이 된다. 이는 이중 반복문을 사용하여 배열을 확인하기 때문에 제곱 시간이 소요된다.

 

Asymptotic notations에 대해 설명하고, 다섯 가지 종류에 대해 서술하시오.

Asymptotic notations은 알고리즘의 시간, 공간 복잡도가 무한대로 접근할 때 증가율을 나타내는데 사용되고, 이는 서로 다른 알고리즘의 효율성을 간결하게 비교할 수 있도록 돕는다. 여기에는 다섯 가지 종류인 Big-O notation(O), Big-Omega notation(Ω), Big-Theta notation(Θ), Little O notation(o), Little omega notation(ω)이 존재한다. Big-O notation(O)는 worst case에서의 time complexity를 나타내며 이는 time complexity의 상한선을 의미한다. Big-Omega notation(Ω)은 best case에서의 time complexity를 나타내며 이는 time complexity의 하한선을 의미한다. Big-Theta notation(Θ)은 알고리즘의 시간 복잡도의 상한과 하한을 동시에 나타낸다. Little O notation(o)은 엄격하지 않은 상한을 나타내어, 알고리즘의 time complexity에 대한 상한을 정의하지만 약간의 가변성을 허용한다. Little omega notation(ω)은 엄격하지 않은 하한을 나타내어, 알고리즘의 time complexity에 대한 하한을 정의하지만 약간의 가변성을 허용한다. 

polynomially bounded 하다는 것은 무슨 뜻인가?

nonnegative한 integer d에 대해, polynomial in n of degree d라는 것은 다음 함수 p(n)=i=0daini과 같은 형태를 띤다. (이 때 ad 0 이어야 한다.) 이 때  ad > 0 인 경우 polynomial은 asymptotically positive 하다. 어떤 함수가가 f(n) = O(nk) 라면, 우리는 이를 polynomially bounded라고 하는데 이는 해당 함수의 증가율이 어떤 다항식과 유사한 형태로 제한된다는 것을 의미한다. 

deterministic, nondeterministic algorithm은 무엇인가?

deterministic algorithm은 미리 정의된 규칙을 따라서, 동일한 입력에 대해 항상 동일한 결과를 반환하는 알고리즘을 말한다. 각 단계에서 다음으로 진행할 동작이 명확하게 결정되므로 예측 가능하고 반복 가능한 동작이 수행된다. 반면 non-deterministic algorithm은 여러 가능한 경로를 가질 수 있는 알고리즘으로써, 하나 이상의 다음 동작이 가능하므로 그 중 어떤 동작을 선택할지는 알고리즘 내부에서 결정되는 것이 아니라 외부적인 요인에 의해서 결정된다.