결정론적 알고리즘

Deterministic algorithm

컴퓨터 과학에서 결정론적 알고리즘은 특정 입력이 주어졌을 때 항상 동일한 출력을 생성하는 알고리즘이며, 기초 기계는 항상 동일한 일련의 상태를 통과합니다.결정론적 알고리즘은 실제 기계에서 효율적으로 실행될 수 있기 때문에 지금까지 가장 연구되고 친숙한 종류의 알고리즘일 뿐만 아니라 가장 실용적인 알고리즘입니다.

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

형식적 정의

결정론적 알고리즘은 상태 머신의 관점에서 정의할 수 있습니다.상태는 기계가 특정 순간에 무엇을 하고 있는지를 기술합니다.스테이트 머신은, 상태간에 이산적인 방법으로 건네집니다.입력 직후에 기계는 초기 상태 또는 시작 상태가 됩니다.기계가 결정론적인 경우, 이는 이 시점 이후 현재 상태에 따라 다음 상태가 결정된다는 것을 의미합니다. 일련의 상태를 통과하는 경로가 미리 결정됩니다.기계는 결정론적일 수 있으며, 여전히 멈추거나 종료하지 않기 때문에 결과를 제공하지 못합니다.

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

비결정론적 알고리즘

다음과 같은 다양한 요인에 의해 알고리즘이 결정론적이거나 결정론적이지 않은 방식으로 동작할 수 있습니다.

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

비록 실제 프로그램이 순수하게 결정론적인 경우는 드물지만, 다른 프로그램뿐만 아니라 인간들도 그런 프로그램에 대해 추론하는 것이 더 쉽다.이러한 이유로 대부분의 프로그래밍 언어, 특히 기능적인 프로그래밍 언어는 제어된 조건이 아니면 위의 이벤트가 발생하지 않도록 합니다.

멀티코어 프로세서의 보급으로 병렬 프로그래밍의 결정론에 대한 관심이 높아졌고 비결정론의 문제가 [1][2]잘 입증되었습니다.교착상태와 인종상황에 대처하기 위해 도전에 대처하는 데 도움이 되는 많은 도구들이 제안되었다[3][4][5][6].

결정론의 단점

경우에 따라서는 프로그램이 비결정적 행동을 보이는 것이 유리합니다.예를 들어 블랙잭 게임에서 사용되는 카드 셔플링 프로그램의 동작은 프로그램의 소스 코드가 표시되더라도 플레이어가 예측할 수 없어야 합니다.유사 난수 생성기의 사용은 플레이어가 셔플의 결과를 예측할 수 없도록 하기 위해 충분하지 않은 경우가 많습니다.현명한 도박꾼은 제너레이터가 선택하는 숫자를 정확하게 추측하여 덱의 전체 내용을 미리 판단하여 부정행위를 할 수 있습니다.예를 들어 Reliable Software Technologies의 소프트웨어 보안 그룹은 ASF Software, Inc, al.에 의해 배포되는 Texas Hold'em Poker를 구현하기 위해 이를 수행할 수 있었습니다.손의 결과를 [7]미리 일관되게 예측하기 위해 낮춘다.이러한 문제는 부분적으로 암호학적으로 안전한 의사 난수 생성기를 사용함으로써 피할 수 있지만, 여전히 제너레이터 초기화에 예측할 수 없는 랜덤시드를 사용해야 합니다.이를 위해서는 하드웨어 난수 발생기에 의해 제공되는 것과 같은 비결정론의 원천이 필요하다.

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

언어의 결정론 범주

수성.

수은 논리 함수 프로그래밍 언어는 [8][9]참조에서 설명한 바와 같이 술어 모드에 대해 서로 다른 결정론 범주를 설정합니다.

하스켈

Haskell은 몇 가지 메커니즘을 제공합니다.

  • 비결정론 또는 실패의 개념
    • Maybe 및 Both 유형에는 결과에 대한 성공 개념이 포함됩니다.
    • 예외로서 실패 신호를 보내는 데 사용할 수 있습니다.
    • Maybe monad 및 MaybeT monad 변압기가 실패한 계산을 제공합니다(계산 시퀀스를 중지하고 아무것도 반환하지 않음).[10]
  • Neterminism/Non-Detect(복수 솔루션 사용)
    • 다중 결과 계산의 결과 유형을 MonadPlus 모나드로 래핑하여 가능한 모든 결과를 검색할 수 있습니다.(그 메서드 mzero는 결과를 실패시키고 mplus는 성공한 [11]결과를 수집합니다).

ML 패밀리 및 파생 언어

표준 ML, OCaml 및 Scala와 같이

  • 옵션 유형에는 성공 개념이 포함됩니다.

자바

Java의 경우 null 참조 값은 실패한(도메인 외) 결과를 나타낼 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Edward A. Lee. "The Problem with Threads" (PDF). Retrieved 2009-05-29.
  2. ^ Bocchino Jr., Robert L.; Adve, Vikram S.; Adve, Sarita V.; Snir, Marc (2009). Parallel Programming Must Be Deterministic by Default. USENIX Workshop on Hot Topics in Parallelism.
  3. ^ "Intel Parallel Inspector Thread Checker". Retrieved 2009-05-29.
  4. ^ Yuan Lin. "Data Race and Deadlock Detection with Sun Studio Thread Analyzer" (PDF). Retrieved 2009-05-29.
  5. ^ Intel. "Intel Parallel Inspector". Retrieved 2009-05-29.
  6. ^ David Worthington. "Intel addresses development life cycle with Parallel Studio". Archived from the original on 2009-05-28. Retrieved 2009-05-26.
  7. ^ McGraw, Gary; Viega, John. "Make your software behave: Playing the numbers: How to cheat in online gambling". Archived from the original on 2008-03-13. Retrieved 2007-07-02.
  8. ^ "Determinism categories in the Mercury programming language". Archived from the original on 2012-07-03. Retrieved 2013-02-23.
  9. ^ "Mercury predicate modes". Archived from the original on 2012-07-03. Retrieved 2013-02-25.
  10. ^ "Representing failure using the Maybe monad".
  11. ^ "The class MonadPlus".