결정론적 알고리즘

컴퓨터 과학에서 결정론적 알고리즘은 특정 입력이 주어졌을 때 항상 동일한 출력을 생성하며, 기반이 되는 기계가 항상 동일한 상태 순서를 거치는 알고리즘이다. 결정론적 알고리즘은 가장 많이 연구되고 널리 알려진 종류의 알고리즘이며, 실제 기계에서 효율적으로 실행할 수 있어 가장 실용적인 알고리즘 중 하나이기도 하다.

형식적으로, 결정론적 알고리즘은 수학적 함수를 계산한다. 함수는 정의역 내의 모든 입력에 대해 고유한 값을 가지며, 알고리즘은 이 특정 값을 출력으로 생성하는 과정이다.

형식적 정의

결정론적 알고리즘은 상태 기계의 관점에서 정의할 수 있다. 상태는 특정 시점에서 기계가 수행하고 있는 작업을 나타낸다. 상태 기계는 이산적인 방식으로 하나의 상태에서 다른 상태로 전이한다. 입력을 넣은 직후, 기계는 초기 상태 또는 시작 상태에 놓인다. 기계가 결정론적이라면, 이 시점부터 현재 상태가 다음 상태를 결정하며, 상태 집합을 거치는 경로가 미리 정해져 있다는 것을 의미한다. 기계가 결정론적이면서도 멈추지 않거나 완료되지 않아 결과를 산출하지 못할 수 있다는 점에 유의해야 한다.

결정론적인 특정 추상 기계의 예로는 결정론적 튜링 기계와 결정론적 유한 오토마톤이 있다.

비결정론적 알고리즘

다양한 요인이 알고리즘을 비결정론적으로 동작하게 만들 수 있다:

• 사용자 입력, 전역 변수, 하드웨어 타이머 값, 난수 값, 저장된 디스크 데이터 등 입력 이외의 외부 상태를 사용하는 경우.
• 타이밍에 민감한 방식으로 동작하는 경우. 예를 들어, 여러 프로세서가 동시에 같은 데이터에 쓰기를 수행하는 경우이다. 이 경우 각 프로세서가 데이터를 기록하는 정확한 순서가 결과에 영향을 미친다.
• 하드웨어 오류로 인해 상태가 예기치 않게 변경되는 경우.

실제 프로그램이 순수하게 결정론적인 경우는 드물지만, 결정론적인 프로그램은 사람과 다른 프로그램 모두가 추론하기 더 쉽다. 이러한 이유로, 대부분의 프로그래밍 언어, 특히 함수형 프로그래밍 언어는 통제된 조건을 제외하고는 위의 상황이 발생하지 않도록 노력한다.

멀티코어 프로세서의 보급으로 병렬 프로그래밍에서의 결정론에 대한 관심이 급증했으며, 비결정론의 문제점은 잘 문서화되어 있다.[^2][^3] 교착 상태와 경쟁 조건에 대처하기 위해 이러한 문제를 해결하는 데 도움이 되는 다수의 도구가 제안되었다.[^4][^5][^6][^7]

결정론의 단점

프로그램이 비결정적 행동을 보이는 것이 유리한 경우가 있다. 예를 들어, 블랙잭 게임에서 사용되는 카드 셔플링 프로그램의 행동은 프로그램의 소스 코드가 공개되어 있더라도 플레이어가 예측할 수 없어야 한다. 의사 난수 생성기를 사용하는 것만으로는 플레이어가 셔플 결과를 예측할 수 없도록 보장하기에 충분하지 않은 경우가 많다. 영리한 도박꾼은 생성기가 선택할 숫자를 정확히 추측하여 덱의 전체 내용을 미리 파악함으로써 부정행위를 할 수 있다. 예를 들어, Reliable Software Technologies의 소프트웨어 보안 그룹은 ASF Software, Inc가 배포한 텍사스 홀덤 포커 구현에서 이를 실제로 수행하여 핸드의 결과를 사전에 일관되게 예측할 수 있었다.[^8] 이러한 문제는 암호학적으로 안전한 의사 난수 생성기를 사용하여 부분적으로 피할 수 있지만, 생성기를 초기화하기 위해 예측 불가능한 난수 시드를 사용하는 것이 여전히 필요하다. 이를 위해 하드웨어 난수 생성기가 제공하는 것과 같은 비결정성의 원천이 필요하다.

P=NP 문제에 대한 부정적인 답이 비결정적 출력을 가진 프로그램이 결정적 출력을 가진 프로그램보다 이론적으로 더 강력하다는 것을 의미하지는 않는다는 점에 유의해야 한다. 복잡도 클래스 NP(복잡도)는 검증자 기반 정의를 사용하여 비결정성에 대한 어떠한 참조 없이도 정의할 수 있다.

언어별 결정론 범주

Mercury

Mercury 논리-함수형 프로그래밍 언어는 참고 문헌에 설명된 바와 같이 술어 모드에 대해 서로 다른 결정론 범주를 설정한다.[^9][^10]

Haskell

Haskell은 여러 메커니즘을 제공한다:

• 비결정성 또는 실패의 개념 ** Maybe와 Either 타입은 결과에 성공의 개념을 포함한다. ** Monad 클래스의 fail 메서드는 fail을 예외로 신호하는 데 사용될 수 있다. ** Maybe 모나드와 MaybeT 모나드 변환기는 실패한 계산을 제공한다 (계산 시퀀스를 중단하고 Nothing을 반환한다)[^11]
• 다중 해를 가진 비결정성 ** 결과 타입을 MonadPlus 모나드로 감싸면 다중 결과 계산의 모든 가능한 결과를 검색할 수 있다. (그 메서드 mzero는 결과를 실패하게 만들고 mplus는 성공한 결과를 수집한다).[^1]

ML 계열 및 파생 언어

Standard ML, OCaml, Scala에서 볼 수 있듯이

• option 타입은 성공의 개념을 포함한다.

Java

Java에서 null 참조 값은 실패한 (정의역 밖의) 결과를 나타낼 수 있다.

같이 보기

• 무작위 알고리즘

---

참고 문헌

[^1]: MonadPlus 클래스

[^2]: cite web author = Edward A. Lee url = http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-1.pdf access-date = 2009-05-29 title = 스레드의 문제점

[^3]: Bocchino Jr., Robert L.. 병렬 프로그래밍은 기본적으로 결정적이어야 한다

[^4]: cite web url = http://software.intel.com/en-us/videos/intel-parallel-inspector-thread-checker/ access-date = 2009-05-29 title = Intel Parallel Inspector 스레드 검사기

[^5]: cite web author = Yuan Lin url = http://developers.sun.com/sunstudio/documentation/product/sd_west_threadAnalyzer.pdf title = Sun Studio Thread Analyzer를 이용한 데이터 경쟁 및 교착 상태 감지 a

[^6]: cite web author = Intel url = http://software.intel.com/en-us/intel-parallel-inspector access-date = 2009-05-29 title = Intel Parallel Inspector

[^7]: cite web url = http://sdtimes.com/link/33497 title = Intel, Parallel Studio로 개발 생명주기 문제 해결 author = David Worthington access-date = 2009-05-26 archive-url = https://web

[^8]: McGraw, Gary. 소프트웨어를 올바르게 작동시키기: 숫자 게임: 온라인 도박에서 속이는 방법.

[^9]: Mercury 프로그래밍 언어의 결정성 범주

[^10]: Mercury 술어 모드

[^11]: Maybe 모나드를 사용한 실패 표현