결정론적 알고리즘
결정론적 알고리즘(deterministic algorithm)은 예측한 그대로 동작하는 알고리즘이다. 어떤 특정한 입력이 들어오면 언제나 똑같은 과정을 거쳐서 언제나 똑같은 결과를 내놓는다. 결정론적 알고리즘은 실제 기계에서 돌릴 수 있는 효율적인 알고리즘일 뿐 아니라, 가장 오랫동안 연구되었으며 가장 친숙한 알고리즘이다.
결정론적 알고리즘을 가장 단순한 형태로 생각하면 수학 함수라고 볼 수 있다. 함수에 특정한 입력이 들어오면 언제나 동일한 결과를 거쳐서 동일한 결과값이 나오는데, 결정론적 알고리즘도 마찬가지이다. (물론, 알고리즘에서는 실제로 어떻게 구하는지 상세한 과정이 명시되어 있지만, 함수에서는 상세한 과정이 생략되는 경우가 많다.)
엄밀한 정의
편집결정론적 알고리즘은 상태 기계로 엄밀하게 정의할 수 있다. '상태'라는 것은 특정한 시각에 기계가 어떤 동작을 하는지 설명한다. 상태기계는 한 상태에서 다른 상태로 차례대로 넘어가면서 동작한다. 처음 입력값을 넣으면, 기계는 '초기상태' 혹은 '시작상태'가 된다. 만약 기계가 결정론적이면, 초기상태 이후로 현재 상태가 앞으로 어떤 상태가 될지 결정하며 어떤 상태를 거쳐서 동작할지 미리 결정된다. 어떤 기계가 결정론적이라고 해도 완료상태에 도달하지 못하거나 멈추지 않을 수도 있다.[1]
결정론적인 성질을 가지는 추상기계의 예에는 결정론적 튜링 기계와 결정론적 유한 자동장치가 있다.
비결정론적 알고리즘 만들기
편집어떤 알고리즘이 비결정론적으로 작동하게 하는 데는 여러 방법이 있다.
실제 프로그램에서는 순수하게 결정론적인 경우가 드물지만, 순수하게 결정론적이라고 생각하는 것이 여러모로 편리하다. 이런 이유로 프로그래밍 언어, 특히 함수형 언어의 경우, 미리 지정된 경우가 아니면 위와 같은 상황을 최대한 피해야 한다. 이런 이유로, 결정론적 알고리즘을 가끔 순수함수(purely functional)라고 부르기도 한다.
결정론적 알고리즘의 문제점
편집어떤 문제는 결정론적 알고리즘을 찾기 어렵다. 예를 들어, 어떤 수가 소수인지 아닌지 판별하는 확률적 알고리즘은 1970년대에 발견했다.(예: 페르마 소수판별법) 확률론적 알고리즘은 아주 작은 확률로 틀릴 가능성이 있기는 하지만, 효율적인 알고리즘이다. 그 이후로 30년동안 연구한 끝에 소수인지 판별하는 결정론적 알고리즘을 찾아냈으나, 실행시간은 비교할 수도 없이 오랜 걸린다.
또 다른 예로 NP-완전 문제가 있다. 실생활에서 중요한 의미를 가지는 많은 문제들이 NP-완전인데, 이 문제들은 비결정론적 튜링 기계라는 엄청난 능력을 가진 가상의 병렬 기계를 이용하면 쉽게 풀 수 있으나, 아직까지 이런 기계를 실제로 구현하지 못하고 있다. 기껏해야 NP-완전 문제의 근사해(approximate solution)를 구하거나 특별한 경우의 해를 구하는 정도이다.
특별한 경우에는 알고리즘의 결과값을 예측하지 못하도록 하고자 할 때도 있는데, 이런 경우에 비결정 알고리즘이 필요하다. 예를 들어, 온라인 고스톱 게임에서 화투 패를 섞을 때 의사난수 발생기를 사용하면 악의적인 사용자가 화투패가 어떻게 섞였는지 알아내서 상대방을 속일 위험이 있다. 마찬가지 이유로 암호학에서도 확률적 알고리즘이 필요하다.