수학 및 컴퓨터 과학에서 알고리즘은 일반적으로 특정 문제 클래스를 해결하거나 계산을 수행하는 데 사용되는 엄격한 명령의 유한한 시퀀스이다. 알고리즘은 계산이나 데이터 처리를 수행하기 위한 사양으로 사용된다. 고급 알고리즘은 조건식을 사용하여 코드 실행을 다양한 경로(자동화된 의사결정이라고 함)로 우회하여 합리적인 추론(자동화된 추론이라고 함)을 추론하고 최종적으로 자동화를 달성할 수 있다. 인간의 특성을 기계의 설명자로 비유적인 방식으로 사용하는 것은 이미 앨런 튜링이 '기억', '검색', '자극'과 같은 용어를 통해 실천한 바 있다.

이와는 대조적으로, 휴리스틱은 문제 해결에 대한 접근 방식이며, 특히 올바른 결과나 최적의 결과가 명확하게 정의되지 않은 문제 영역에서는 완전히 특정되지 않았거나 올바른 결과나 최적의 결과를 보장하지 못할 수 있다. 예를 들어, 소셜 미디어의 추천 시스템은 21세기의 일반적인 미디어에서 '알고리즘'으로 널리 특징지어지지만, 문제의 특성상 올바른 결과를 제공할 수 없는 방식으로 휴리스틱에 의존하고 있다.

효과적인 방법으로, 알고리즘은 유한한 공간과 시간에서 함수를 계산하기 위해 명확하게 정의된 형식 언어로 표현할 수 있다. 초기 상태와 초기 입력(아마도 비어있는)으로 시작하여, 실행되면 명확하게 정의된 유한한 수의 연속된 상태를 거쳐 최종적으로 '출력'을 생성하고 최종 종료 상태로 종료하는 계산을 명령어로 기술한다. 한 상태에서 다음 상태로의 전환이 반드시 결정론적인 것은 아니며, 무작위 입력이 포함된 알고리즘도 있는데, 이를 랜덤화 알고리즘이라고 한다.

알고리즘 역사

고대의 알고리즘

고대부터 수학 문제를 풀기 위한 단계적 절차가 증명되어 왔다. 바빌로니아 수학(기원전 2500년경), 이집트 수학(기원전 1550년경), 인도 수학(기원전 800년경 이후 슈루바 수트라, 케랄라 학파, 브라흐마슈타시단타 등), 이파의 신탁(기원전 500년경), 그리스 수학(기원전 500년경). 그리스 수학(기원전 240년경. 엘라토스테네스의 체와 유클리드 알고리즘 등), 아랍 수학(9세기, 주파수 분석에 기반한 암호해독 알고리즘 등).

기계적 알고리즘

1928년 데이비드 힐베르트가 제기한 Entscheidungsproblem(결정문제)을 해결하려는 시도로 알고리즘의 현대적 개념이 부분적으로 공식화되기 시작했다. 이후 형식화는 '유효한 계산가능성' 또는 '유효한 방법'을 정의하려는 시도라는 틀에서 이루어졌다. 이러한 형식화에는 1930, 1934, 1935년 게델 헬브란트 크리네의 재귀함수, 1936년 알론조 처치의 람다 계산, 1936년 에밀 포스트의 공식화1, 1936~37년과 1939년 앨런 튜링의 튜링 기계가 포함된다. 포함된다.

#알고리즘의 설계

알고리즘 설계는 문제 해결이나 알고리즘 공학을 위한 방법이나 수학적 과정을 말한다. 알고리즘 설계는 연산 연구의 분할 통치나 동적 계획법 등 많은 해결 이론의 일부이다. 알고리즘 설계를 설계하고 구현하기 위한 기법은 알고리즘 설계 패턴이라고도 하며, 템플릿 메소드 패턴이나 데코레이터 패턴 등이 그 예이다.

알고리즘 설계의 가장 중요한 측면 중 하나는 자원(런타임, 메모리 사용량)의 효율성이다. 예를 들어, Big O 표기법은 입력의 크기가 커짐에 따라 알고리즘이 런타임에 커지는 것을 표현하기 위해 사용된다.

알고리즘 개발의 일반적인 단계

1. 문제 정의
2. 모델 개발
3. 알고리즘의 사양화
4. 알고리즘 설계
5. 알고리즘의 정확성 확인
6. 알고리즘 분석
7. 알고리즘의 구현
8. 프로그램 테스트
9. 문서 작성

컴퓨터 알고리즘

'우아한(컴팩트한) 프로그램, '뛰어난'(빠른) 프로그램: 단순함과 우아함'이라는 개념은 Knuth에서는 비공식적으로, Chaitin에서는 정확하게 등장한다:

Knuth: "...... 우리는 느슨하게 정의된 미적 감각에서 우수한 알고리즘을 추구한다. 한 가지 기준은 ...... 알고리즘을 실행하는 데 걸리는 시간이다 ....... 다른 기준은 알고리즘의 컴퓨터 적응성, 단순성, 우아함 등입니다.". Chaitin: "...... 프로그램은 "우아한"이며, 이는 프로그램이 수행하는 출력을 생성하기 위해 가능한 가장 작은 프로그램이라는 것을 의미한다". Chaitin은 그의 정의를 이렇게 전제한다: "프로그램이 "우아"하다는 것을 증명할 수 없음을 보여주자" - 그러한 증명은 헐팅 문제를 푸는 것이다(같은 책).

알고리즘 대 알고리즘에 의해 계산 가능한 함수: 한 함수에 대해 여러 알고리즘이 존재할 수 있다. Rogers는 "알고리즘, 즉 절차라는 개념과 알고리즘에 의해 계산 가능한 함수, 즉 절차에 의해 얻어지는 매핑이라는 개념을 구분하는 것은 ...... 중요하다"고 말했다. 같은 함수가 여러 가지 다른 알고리즘을 가질 수 있다.".

우아한 프로그램은 그렇지 않은 프로그램보다 계산을 완료하기 위해 더 많은 단계를 필요로 한다. 유클리드의 알고리즘을 사용한 예는 다음과 같다.

컴퓨터(및 계산기), 계산 모델: 컴퓨터(또는 인간의 '컴퓨터')는 제한된 유형의 기계이며, 명령에 맹목적으로 따르는 '이산적 결정론적 기계 장치': (i) 이산적이고 구별 가능한 장소, (ii) 이산적이고 구별할 수 없는 카운터, (iii) 에이전트, 그리고 (iv) 에이전트의 능력에 대해 유효한 지시 목록이다.

민스키의 기계는 조건부 IF-THEN GOTO 또는 무조건 GOTO가 프로그램의 흐름을 순서대로 변경하지 않는 한, 5(또는 6, 계산 방법에 따라 다름)개의 명령을 통해 순차적으로 진행하며, HALT 외에도 민스키의 기계에는 세 가지 대입(대체, 대체) 연산이 있다. ZERO(예를 들어, 0으로 대체된 곳의 내용: L ← 0), SUCCESSOR(예를 들어, L ← L+1), DECREMENT(예를 들어, L ← L - 1)이 있다. 프로그래머가 이런 제한된 명령어 집합으로 '코드'를 작성해야 하는 경우는 드물다. 그러나 Minsky는 (Melzak과 Lambek과 마찬가지로) 그의 기계가 조건부 GOTO, 무조건 GOTO, 대입/대치/대체/대체, HALT의 네 가지 일반적인 유형의 명령어로만 튜링 완전하다는 것을 보여준다. 그러나 몇 가지 다른 대입 명령어(예: DECREMENT, INCREMENT, 민스키 머신의 ZERO/CLEAR/EMPTY)도 튜링 완전성을 위해 필요하다. 무조건 GOTO는 편리하며, 예를 들어 "Z ← 0" 명령어처럼 전용 장소를 0으로 초기화하여 구축할 수 있다. 그러면 IF Z=0 THEN GOTO xxx라는 명령어가 무조건 실행된다.

알고리즘 시뮬레이션: 컴퓨터(계산기) 언어: Knuth는 "알고리즘을 배우는 가장 좋은 방법은 직접 해보는 것이다." ...... 즉시 펜과 종이를 들고 예제를 통해 작업하는 것이다"라고 독자들에게 조언하고 있다. 프로그래머는 알고리즘을 시뮬레이터/컴퓨터/컴퓨터가 효과적으로 실행할 수 있는 언어로 번역해야 한다. 이차 방정식의 근을 계산할 때, 컴퓨터는 제곱근을 구하는 방법을 알고 있어야 한다. 만약 그렇지 않다면, 알고리즘이 효과적이기 위해서는 제곱근을 추출하기 위한 규칙 세트를 제공해야 한다.

즉, 프로그래머는 대상 계산 에이전트(컴퓨터/컴퓨터)에 유효한 '언어'를 알고 있어야 한다.

그렇다면 어떤 모델을 시뮬레이션에 사용해야 할까? 반 엠데 보아스는 "복잡성 이론의 기초를 구체적 기계가 아닌 추상적 기계에 두더라도 모델 선택의 임의성은 남는다"고 말한다. 이 시점에서 시뮬레이션의 개념이 들어간다.". 속도를 측정하는 경우, 명령어 집합이 문제가 된다. 예를 들어, 유클리드 알고리즘에서 여분을 계산하는 서브프로그램은 프로그래머가 단순한 뺄셈(더 나쁜 경우 민스키의 '감소')이 아닌 '모듈러스' 명령어를 사용할 수 있다면 훨씬 더 빠르게 실행할 수 있다.

구조화 프로그래밍, 정적 구조: 처치 튜링 논문에 따르면 모든 알고리즘은 튜링 완전하다고 알려진 모델로 계산할 수 있으며, 민스키의 증명에 따르면 튜링 완전성은 4 가지 명령어 유형 (조건부 GOTO, 무조건 GOTO, 무조건 Kemeny와 Kurtz는 무조건 GOTO와 조건부 IF-THEN GOTO를 '무분별하게' 사용하면 '스파게티 코드'가 될 수 있지만, 프로그래머는 이 명령어들만 사용하여 구조화된 프로그램을 작성할 수 있다고 명시하고 있다. Tausworthe는 SEQUENCE, IF-THEN-ELSE, WHILE-DO의 세 가지 Böhm-Jacopini 정언 구조에 두 가지 구조를 더 추가했다: 구조화된 프로그램의 또 다른 장점은 수학적 귀납법을 이용한 정확성 증명에 적합하다는 것이다. 이다.

정규 순서도 기호: 순서도라는 그래픽 지원은 알고리즘(및 해당 컴퓨터 프로그램)을 기술하고 문서화하는 방법을 제공한다. 민스키 머신의 프로그램 흐름과 마찬가지로 흐름도는 항상 페이지의 맨 위에서 시작하여 아래로 내려간다. 주요 기호는 프로그램의 흐름을 나타내는 방향 화살표, 직사각형(SEQUENCE, GOTO), 마름모꼴(IF-THEN-ELSE), 점(OR-tie) 등 네 가지뿐이다. 베임-야코피니 정량구조는 이러한 원시적인 도형으로 구성되어 있다. 하부구조는 직사각형 안에 '중첩'될 수 있지만, 이는 상부구조에서 나오는 출구가 하나인 경우에만 가능하다. 정기준 구조를 구축하기 위한 기호와 그 사용법을 그림으로 나타낸다.