|
== 비결정론적 알고리즘 만들기 ==
어떤 알고리즘이 비결정론적으로 작동하게 하는데는 여러가지 방법이 있다.
<!--
* 입력 이외의 외부 상태를 알고리즘에 적용함 (예: 사용자의 입력, 전역변수, 하드웨어 타이머 값, 난수등을 알고리즘 진행과정에 입력으로 넣는 방법)
A variety of factors can cause an algorithm to behave in a way which is not deterministic, or non-deterministic:
* 알고리즘이 시간에 민감하게 동작함 (예: 여러 개의 프로세서가 동시에 같은 메모리에 값을 쓰려고 하는 경우, 각 프로세서가 어떤 순서로 썼는지에 따라 결과값이 달라진다.)
* If it uses external state other than the input, such as user input, a global variable, a hardware timer value, a random value, or stored disk data.
* 하드웨어의 오류를 이용하여 알고리즘 진행과정을 예상할 수 없는 방식으로 변화시키는 방법
* If it operates in a way that is timing-sensitive, for example if it has multiple processors writing to the same data at the same time. In this case, the precise order in which each processor writes its data will affect the result.
* If a hardware error causes its state to change in an unexpected way.
실제 프로그램에서는 순수하게 결정론적인 경우가 드물지만, 순수하게 결정론적이라고 생각하는 것이 여러모로 편리하다. 이런 이유로 [[프로그래밍 언어]], 특히 [[함수형 언어]]의 경우, 미리 지정된 경우가 아니면 위와 같은 상황을 최대한 피해야 한다. 이런 이유로, 결정론적 알고리즘을 가끔 [[순수함수]](purely functional)라고 부르기도 한다.
Although real programs are rarely purely deterministic, it is easier for humans as well as other programs to reason about programs that are. For this reason, most [[programming language]]s and especially [[functional programming]] languages make an effort to prevent the above events from happening except under controlled conditions. Because of the way such restrictions enforce determinism, deterministic algorithms are sometimes called [[purely functional]].
-->
== 결정론적 알고리즘의 문제점 ==
어떤 문제는 결정론적 알고리즘을 찾기 어렵다. 예를 들어, 어떤 수가 소수인지 아닌지 판별하는 [[확률론적 알고리즘]]은 1970년대에 발견했다.(예: [[페르마 소수판별법]]) 확률론적 알고리즘은 아주 작은 확률로 틀릴 가능성이 있기는 하지만, 효율적인 알고리즘이다. 그 이후로 30년동안 연구한 끝에 소수인지 판별하는 결정론적 알고리즘을 찾아냈으나, 실행시간은 비교할 수도 없이 오랜 걸린다.
| 