위키백과

결정론적 알고리즘: 두 판 사이의 차이

입체적으로 역사 찾아보기
← 이전 편집다음 편집 →
내용 삭제됨 내용 추가됨
시각위키텍스트
Chobot (토론 | 기여)
봇
487,764 편집
잔글 robot Adding: es
Crypto~kowiki (토론 | 기여)
2,628 편집
17번째 줄:
 
== 결정론적 알고리즘의 문제점 ==
어떤 문제는 결정론적 알고리즘을 찾기 어렵다. 예를 들어, 어떤 수가 소수인지 아닌지 판별하는 [[확률론적확률적 알고리즘]]은 1970년대에 발견했다.(예: [[페르마 소수판별법]]) 확률론적 알고리즘은 아주 작은 확률로 틀릴 가능성이 있기는 하지만, 효율적인 알고리즘이다. 그 이후로 30년동안 연구한 끝에 소수인지 판별하는 결정론적 알고리즘을 찾아냈으나, 실행시간은 비교할 수도 없이 오랜 걸린다.
 
또 다른 예로 [[NP-완전]] 문제가 있다. 실생활에서 중요한 의미를 가지는 많은 문제들이 NP-완전인데, 이 문제들은 [[비결정비결정론적 튜링 기계]]라는 엄청난 능력을 가진 가상의 병렬 기계를 이용하면 쉽게 풀 수 있으나, 아직까지 이런 기계를 실제로 구현하지 못하고 있다. 기껏해야 NP-완전 문제의 근사해(approximate solution)를 구하거나 특별한 경우의 해를 구하는 정도이다.
 
특별한 경우에는 알고리즘의 결과값을 예측하지 못하도록 하고자 할 때도 있는데, 이런 경우에 비결정 알고리즘이 필요하다. 예를 들어, 온라인 고스톱 게임에서 화투패를 섞을 때 [[의사난수발생기]]를 사용하면 악의적인 사용자가 화투패가 어떻게 섞였는지 알아내서 상대방을 속일 위험이 있다. 마찬가지 이유로 암호학에서도 확률적 알고리즘이 필요하다. ([[암호학적으로 안전한 의사난수발생기]] 참고)
원본 주소 "https://ko.wikipedia.org/wiki/결정론적_알고리즘"