결정론적 알고리즘
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
결정론적 알고리즘은 초기 상태 이후의 모든 상태가 미리 결정되어 있는 알고리즘을 의미하며, 상태 기계로 엄밀하게 정의할 수 있다. 이러한 알고리즘은 외부 상태의 영향을 받지 않고, 입력에 따라 항상 동일한 결과를 반환한다. 결정론적 알고리즘은 프로그래밍 언어에서 비결정성을 최소화하는 방향으로 사용되며, 함수형 프로그래밍 언어에서 순수 함수와 유사한 개념으로 간주되기도 한다. 그러나 소수 판별, NP-완전 문제와 같이 결정론적 알고리즘을 찾기 어렵거나 효율성이 떨어지는 문제도 존재하며, 온라인 게임의 화투 패 섞기나 암호 이론에서의 키 생성과 같이 예측 불가능성이 요구되는 경우도 있다. 머큐리, 하스켈, ML 계열 언어, 자바 등 다양한 프로그래밍 언어는 결정론적 알고리즘의 개념을 지원하기 위한 기능을 제공한다.
더 읽어볼만한 페이지
| 결정론적 알고리즘 | |
|---|---|
| 결정론적 알고리즘 | |
 | |
| 분야 | 컴퓨터 과학 |
| 첫 번째 고안자 | 에곤 뵐거 |
| 고안 년도 | 1953년 |
| 속성 | |
| 결정론 | 알고리즘은 동일한 입력이 주어지면 항상 동일한 출력을 생성한다. |
| 예측 가능성 | 알고리즘의 각 단계는 정확하게 예측 가능하다. |
| 유한성 | 알고리즘은 유한한 시간 안에 종료된다. |
| 예시 | |
| 검색 알고리즘 | 이진 탐색 |
| 정렬 알고리즘 | 병합 정렬, 삽입 정렬, 힙 정렬 |
| 암호화 알고리즘 | AES, DES |
| 관련 개념 | |
| 반대 개념 | 비결정론적 알고리즘 |
| 관련 개념 | 결정론적 튜링 기계 |
2. 엄밀한 정의
결정론적 알고리즘은 상태 머신의 관점에서 정의될 수 있다. ''상태''는 특정 시점에서 기계가 무엇을 하고 있는지 설명한다. 상태 머신은 한 상태에서 다른 상태로 이산적인 방식으로 이동한다. 기계가 결정론적이라면, 현재 상태가 다음 상태를 결정하며, 상태 집합을 통과하는 과정은 미리 결정된다. 기계가 결정론적이어도 멈추거나 완료되지 않아 결과를 제공하지 못할 수도 있다.[13]
형식적으로, 결정적 알고리즘은 유한 상태 기계로 정의된다. "상태"는 어떤 시점에서 그 기계가 무엇을 하고 있는지를 나타낸다. 유한 상태 기계는 어떤 상태에서 다른 상태로 엄밀하게 전이한다. 유한 상태 기계가 결정적이라는 것은, 어떤 입력을 주었을 때 그 기계가 거치는 상태 전이의 경로가 항상 같다는 것을 의미한다.
2. 1. 상태 기계
결정론적 알고리즘은 상태 기계로 엄밀하게 정의할 수 있다. '상태'라는 것은 특정한 시각에 기계가 어떤 동작을 하는지 설명한다. 상태 기계는 한 상태에서 다른 상태로 차례대로 넘어가면서 동작한다. 처음 입력값을 넣으면, 기계는 '초기 상태' 혹은 '시작 상태'가 된다. 만약 기계가 결정론적이면, 초기 상태 이후로 현재 상태가 앞으로 어떤 상태가 될지 결정하며 어떤 상태를 거쳐서 동작할지 미리 결정된다. 어떤 기계가 결정론적이라고 해도 완료 상태에 도달하지 못하거나 멈추지 않을 수도 있다.[13]결정론적인 성질을 가지는 추상 기계의 예에는 결정론적 튜링 기계와 결정론적 유한 자동 장치가 있다.
2. 2. 추상 기계
결정론적인 성질을 가지는 추상 기계의 예로는 결정론적 튜링 기계와 결정론적 유한 자동 장치가 있다.[13]3. 비결정론적 알고리즘
알고리즘이 비결정론적으로 작동하게 하는 데는 여러 방법이 있다.[14] 입력 이외의 외부 상태를 적용하거나, 알고리즘이 시간에 민감하게 동작하게 하거나,[15] 하드웨어 오류를 이용해 예측할 수 없는 방식으로 변화를 줄 수 있다.
실제 프로그램은 순수하게 결정론적인 경우가 드물지만, 결정론적이라고 생각하는 것이 편리하다. 이러한 이유로 프로그래밍 언어, 특히 함수형 언어는 지정된 경우가 아니면 이러한 상황을 최대한 피하려고 한다.
3. 1. 비결정성 요인
알고리즘이 비결정론적으로 작동하게 하는 요인에는 여러 가지가 있다.[14]- 입력 이외의 외부 상태를 알고리즘에 적용하는 경우
- 알고리즘이 시간에 민감하게 동작하는 경우[15]
- 하드웨어 오류를 이용하여 알고리즘 진행 과정을 예측할 수 없는 방식으로 변화시키는 경우
알고리즘이 결정론적이지 않거나 비결정론적으로 동작하게 만드는 다양한 요인은 다음과 같다.
- 사용자 입력, 전역 변수, 하드웨어 타이머 값, 난수, 저장된 디스크 데이터 등 입력 외의 외부 상태를 사용하는 경우.
- 시간에 민감하게 작동하는 경우. (예: 여러 프로세서가 동시에 동일한 데이터에 쓰는 경우, 각 프로세서가 데이터를 쓰는 정확한 순서가 결과에 영향을 미침)
- 하드웨어 오류로 인해 상태가 예측하지 못한 방식으로 변경되는 경우.
멀티 코어 프로세서의 보급으로 병렬 프로그래밍에서의 결정론에 대한 관심이 높아졌으며 비결정론의 문제점들이 잘 기록되어 있다.[1][2] 교착 상태 및 경쟁 상태 문제를 해결하기 위한 많은 도구들이 제안되었다.[3][4][5][6]
비결정적 알고리즘을 구성하는 요인은 다음과 같다.
- 입력 이외의 외부 상태를 사용하는 경우. (예: 사용자 입력, 전역 변수, 하드웨어 타이머 값, 디스크상의 데이터 등)
- 타이밍에 의존하는 처리를 하는 경우. (예: 복수의 프로세서가 동시에 같은 주소에 데이터를 쓰는 경우, 실제 정확한 쓰기 순서에 따라 최종적인 결과가 달라짐)
- 하드웨어 고장 등의 요인으로 예측하지 못한 동작을 하는 경우.
3. 2. 프로그래밍 언어와 비결정성
대부분의 프로그래밍 언어, 특히 함수형 언어는 제어된 상황 외에는 비결정성을 최소화하려고 노력한다. 실제 프로그램은 순수하게 결정론적인 경우가 드물지만, 결정론적인 프로그램이 사람과 다른 프로그램이 추론하기 더 쉽기 때문이다. 이러한 이유로 결정론적 알고리즘을 순수함수라고 부르기도 한다.[14]멀티 코어 프로세서의 보급으로 병렬 프로그래밍에서의 결정론에 대한 관심이 높아졌으며, 비결정론의 문제점들이 잘 기록되어 있다.[1][2] 교착 상태 및 경쟁 상태 문제를 해결하기 위한 많은 도구들이 제안되었다.[3][4][5][6]
4. 결정론적 알고리즘의 문제점
어떤 문제들은 결정론적 알고리즘을 찾기 어렵거나 비효율적이다. 소수 판별 문제, NP-완전 문제, 예측 불가능성이 요구되는 경우가 이에 해당한다.
P=NP 문제에 대한 부정적인 답변이 비결정적 출력을 가진 프로그램이 결정적 출력을 가진 프로그램보다 이론적으로 더 강력하다는 것을 의미하지는 않는다. NP (복잡도) 복잡도 클래스는 검증기 기반 정의를 사용하여 비결정성에 대한 언급 없이 정의될 수 있다.
4. 1. 소수 판별 문제
어떤 수가 소수인지 아닌지 판별하는 단순하고 효율적인 확률적 알고리즘이 존재하며, 판정을 잘못할 가능성은 극히 작다(밀러-라빈 소수 판별법). 그러한 알고리즘은 1970년대부터 알려져 있지만, 동일한 문제에 대한 결정론적 알고리즘은 그것에 비하면 너무 많은 시간이 소요된다.[12]4. 2. NP-완전 문제
NP-완전 문제는 비결정론적 튜링 기계라는 가상의 병렬 기계를 이용하면 쉽게 풀 수 있지만, 아직까지 이러한 기계를 실제로 구현하지 못하고 있다.[12] 따라서 현재는 NP-완전 문제의 근사해(approximate solution)를 구하거나 특별한 경우의 해를 구하는 정도이다. 실생활에서 중요한 의미를 가지는 많은 문제들이 NP-완전에 속한다.4. 3. 예측 불가능성
온라인 고스톱, 블랙잭과 같은 온라인 게임에서는 결과값 예측을 막기 위해 의도적인 비결정성이 요구된다. 예를 들어, 블랙잭 게임에서 사용되는 카드 섞기 프로그램의 동작은 소스 코드가 공개되어도 플레이어가 예측할 수 없어야 한다. 의사 난수 생성기만으로는 플레이어가 섞기 결과를 예측하는 것을 막기에 충분하지 않을 수 있다. 실제로, Reliable Software Technologies의 Software Security Group은 ASF Software, Inc.의 포커 게임에서 의사 난수 생성기의 취약점을 이용하여 핸드의 결과를 예측할 수 있었다.[7][12]암호 이론에서도 비밀 키 생성 등에 의사 난수가 사용되는데, 예측 불가능성을 확보하기 위해 암호학적으로 안전한 의사 난수 생성기(CSPRNG)를 사용한다. 또한, CSPRNG를 초기화하기 위한 예측 불가능한 난수 시드가 필요하며, 이를 위해 하드웨어 난수 생성기와 같은 비결정성의 소스가 사용된다.
5. 프로그래밍 언어에서의 결정론
여러 프로그래밍 언어에서 결정론 또는 비결정론을 다루기 위한 기능을 제공한다.
- 머큐리는 술어 모드에 대해 서로 다른 결정론 범주를 설정한다.[8][9]
- 하스켈은 `Maybe` 및 `Either` 타입을 통해 결과에 성공 또는 실패 개념을 포함시키거나, Monad 클래스의 `fail` 메서드를 사용하여 실패를 알릴 수 있다.[10] 또한, `MonadPlus` 모나드를 통해 다중 결과 계산의 가능한 모든 결과를 얻을 수 있다.[11]
- 스탠다드 ML, OCaml, 스칼라에서는 ''option'' 타입을 사용하여 성공/실패 개념을 표현한다.
- 자바에서 ''null'' 참조 값은 실패한 결과를 나타낼 수 있다.
5. 1. Mercury
머큐리 논리-함수형 프로그래밍 언어는 참고 자료에서 설명된 대로 술어 모드에 대해 서로 다른 결정론 범주를 설정한다.[8][9]5. 2. Haskell
하스켈은 여러 메커니즘을 제공한다.- 비결정성 또는 실패의 개념
- `Maybe` 및 `Either` 타입은 결과에 성공의 개념을 포함한다.
- Monad 클래스의 `fail` 메서드는 예외로 `fail`을 신호하는 데 사용될 수 있다.[10]
- `Maybe` 모나드와 `MaybeT` 모나드 변환기는 실패한 계산을 제공한다(계산 시퀀스를 중지하고 `Nothing`을 반환).[10]
- 여러 해답을 가진 비결정성/비결정론
- 결과 유형을 `MonadPlus` 모나드로 래핑하여 다중 결과 계산의 가능한 모든 결과를 검색할 수 있다. (`mzero` 메서드는 결과가 실패하도록 하고 `mplus`는 성공적인 결과를 수집한다).[11]
5. 3. ML 계열 (Standard ML, OCaml, Scala)
스탠다드 ML, OCaml, 스칼라에서는 ''option'' 타입을 사용하여 성공/실패 개념을 표현한다.5. 4. Java
자바에서 ''null'' 참조 값은 실패한 (범위를 벗어난) 결과를 나타낼 수 있다.참조
[1]
웹사이트
The Problem with Threads
http://www.eecs.berk[...]
2009-05-29
[2]
간행물
Parallel Programming Must Be Deterministic by Default
https://www.usenix.o[...]
[3]
웹사이트
Intel Parallel Inspector Thread Checker
http://software.inte[...]
2009-05-29
[4]
웹사이트
Data Race and Deadlock Detection with Sun Studio Thread Analyzer
http://developers.su[...]
2009-05-29
[5]
웹사이트
Intel Parallel Inspector
http://software.inte[...]
2009-05-29
[6]
웹사이트
Intel addresses development life cycle with Parallel Studio
https://web.archive.[...]
2009-05-26
[7]
웹사이트
Make your software behave: Playing the numbers: How to cheat in online gambling.
https://web.archive.[...]
2007-07-02
[8]
웹사이트
Determinism categories in the Mercury programming language
https://web.archive.[...]
2013-02-23
[9]
웹사이트
Mercury predicate modes
https://web.archive.[...]
2013-02-25
[10]
웹사이트
Representing failure using the Maybe monad
http://www.haskell.o[...]
[11]
웹사이트
The class MonadPlus
http://www.haskell.o[...]
[12]
문서
Make your software behave: Playing the numbers: How to cheat in online gambling.
http://www.ibm.com/d[...]
[13]
문서
어떤 상태를 거쳐서 어떤 다음 상태에 도달하는지 미리 알 수 있어도, 완료상태에 도달하지 못하거나 멈추지 않는 경우가 있을 수 있기 때문이다.
[14]
문서
예: 사용자의 입력, 전역변수, 하드웨어 타이머 값, 난수등을 알고리즘 진행과정에 입력으로 넣는 방법
[15]
문서
예: 여러 개의 프로세서가 동시에 같은 메모리에 값을 쓰려고 하는 경우, 각 프로세서가 어떤 순서로 썼는지에 따라 결과값이 달라진다.
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com