알고리즘, 유한 한 단계로 질문에 대한 답 또는 문제의 해결책을 생성하는 체계적인 절차. 이 이름은 9 세기 무슬림 수학자 알-카와 리즈 미 (Al-Khwarizmi)의 산술 논문“알코와 리즈 미 (Al-Khwarizmi of Reckoning)에 관한 알-카와 리즈 미 (Al-Khwarizmi)”의 라틴어 번역 인 Algoritmi de numero Indorum에서 유래 한 것이다.
컴퓨터 과학: 알고리즘과 복잡성
알고리즘은 잘 정의 된 계산 문제를 해결하기위한 특정 절차입니다. 알고리즘의 개발 및 분석은 기본
유한 한 사례 또는 값 집합에 대한 질문이나 문제의 경우 알고리즘은 항상 존재합니다 (적어도 원칙적으로는). 답의 값 표로 구성됩니다. 일반적으로 "천연 수 (1, 2, 3, …)는 소수입니까?"와 같이 무한한 수의 사례 또는 값을 갖는 질문이나 문제에 답하는 것은 그리 간단한 절차가 아닙니다. 또는 "자연수 a와 b의 최대 공약수는 무엇입니까?" 이러한 질문 중 첫 번째 질문은 결정 가능한 클래스에 속합니다. 예 또는 아니오 응답을 생성하는 알고리즘을 결정 절차라고합니다. 두 번째 질문은 계산 가능한 클래스에 속합니다. 특정 숫자 답변으로 이어지는 알고리즘을 계산 절차라고합니다.
알고리즘은 그러한 많은 종류의 질문에 대해 존재합니다. 기원전 300 년경에 출판 된 유클리드의 원소는 두 자연수의 최대 공약수를 구하기위한 것입니다. 모든 초등학생은 "분할 a와 다른 자연수 b를 나누면 몫과 나머지는 무엇입니까?"라는 질문에 대한 알고리즘 인 긴 구분으로 드릴됩니다. 이 계산 절차를 사용하면“b가 a를 나누는가?”라는 결정 가능한 질문에 대한 답이됩니다. (나머지가 0이면 대답은 '예'입니다). 이러한 알고리즘을 반복적으로 적용하면 결국“소소한가?”라는 결정 가능한 질문에 대한 답을 얻을 수 있습니다. (a가 1 이외의 더 작은 자연수로 나눌 수 있으면 대답은 아니오입니다).
때로는 허용되는 방법에 대해 추가적인 제한이있을 때 무한한 종류의 문제를 해결하기위한 알고리즘이 존재할 수없는 경우가 있습니다. 예를 들어, 유클리드 시대에는 나침반과 직선 (표시되지 않은 눈금자) 만 사용해야하는 두 가지 문제 (각도를 자르고 주어진 원과 같은 면적을 가진 사각형을 만드는 것)가 불가능 해지기 전에 수 세기 동안 추구되었습니다.. 20 세기 초, 영향력있는 독일 수학자 데이비드 힐버트 (David Hilbert)는 다음 세기에 수학자들이 해결해야 할 23 가지 문제를 제안했습니다. 그의 목록에있는 두 번째 문제는 산술 공리의 일관성에 대한 조사를 요구했다. 대부분의 수학자들은 1931 년까지 오스트리아 태생의 논리 학자 커트 고델 (Kurt Gödel)이 입증하거나 반증 할 수없는 산술적 제안 (또는 질문)이 존재해야한다는 놀라운 결과를 보여 주었을 때까지이 목표의 최종 달성에 대해 거의 의심하지 않았다. 본질적으로, 그러한 제안은 결코 끝나지 않는 결정 절차로 이어집니다 (정지 문제라고 알려진 상태). 어느 제안이 해결할 수 없는지 확인하기위한 실패한 노력으로 영국의 수학자이자 논리학자인 Alan Turing은 이해하기 어려운 알고리즘 개념을 엄격하게 정의했습니다. Turing은 결정 불가능한 제안이 있어야한다는 것을 입증했지만, 범용 알고리즘 머신 또는 Turing 머신의 필수 기능에 대한 그의 설명은 컴퓨터 과학의 기초가되었습니다. 오늘날 결정 성과 계산 문제는 특별한 유형의 알고리즘 인 컴퓨터 프로그램 설계의 핵심입니다.
