비결정론적 알고리즘 만들기[편집]
어떤 알고리즘이 비결정론적으로 작동하게 하는 데는 여러 방법이 있다.
실제 프로그램에서는 순수하게 결정론적인 경우가 드물지만, 순수하게 결정론적이라고 생각하는 것이 여러모로 편리하다. 이런 이유로 프로그래밍 언어, 특히 함수형 언어의 경우, 미리 지정된 경우가 아니면 위와 같은 상황을 최대한 피해야 한다. 이런 이유로, 결정론적 알고리즘을 가끔 순수함수(purely functional)라고 부르기도 한다.
결정론적 알고리즘의 문제점[편집]
어떤 문제는 결정론적 알고리즘을 찾기 어렵다. 예를 들어, 어떤 수가 소수인지 아닌지 판별하는 확률적 알고리즘은 1970년대에 발견했다.(예: 페르마 소수판별법) 확률론적 알고리즘은 아주 작은 확률로 틀릴 가능성이 있기는 하지만, 효율적인 알고리즘이다. 그 이후로 30년동안 연구한 끝에 소수인지 판별하는 결정론적 알고리즘을 찾아냈으나, 실행시간은 비교할 수도 없이 오랜 걸린다.
또 다른 예로 NP-완전 문제가 있다. 실생활에서 중요한 의미를 가지는 많은 문제들이 NP-완전인데, 이 문제들은 비결정론적 튜링 기계라는 엄청난 능력을 가진 가상의 병렬 기계를 이용하면 쉽게 풀 수 있으나, 아직까지 이런 기계를 실제로 구현하지 못하고 있다. 기껏해야 NP-완전 문제의 근사해(approximate solution)를 구하거나 특별한 경우의 해를 구하는 정도이다.
특별한 경우에는 알고리즘의 결과값을 예측하지 못하도록 하고자 할 때도 있는데, 이런 경우에 비결정 알고리즘이 필요하다. 예를 들어, 온라인 고스톱 게임에서 화투패를 섞을 때 의사난수 발생기를 사용하면 악의적인 사용자가 화투패가 어떻게 섞였는지 알아내서 상대방을 속일 위험이 있다. 마찬가지 이유로 암호학에서도 확률적 알고리즘이 필요하다.
'Computing > Algorythm' 카테고리의 다른 글
해쉬함수란? (0) | 2019.07.19 |
---|---|
합의 알고리즘 (0) | 2019.07.19 |
동적프로그래밍 vs Memoization (0) | 2018.12.18 |
Sequence Alignment Algorithm (0) | 2018.12.18 |
Ford Fulkerson Algorithm (0) | 2018.12.18 |