Algorithm

Original article: w:Algorithm

"Algorithms" redirects here. For the subfield of computer science, see Analysis of algorithms.

For other uses, see Algorithm (disambiguation).

Flowchart of an algorithm (Euclid's algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≥ A yields "yes" or "true" (more accurately, the number b in location B is greater than or equal to the number a in location A) THEN, the algorithm specifies B ← B − A (meaning the number b − a replaces the old b). Similarly, IF A > B, THEN A ← A − B. The process terminates when (the contents of) B is 0, yielding the g.c.d. in A. (Algorithm derived from Scott 2009:13; symbols and drawing style from Tausworthe 1977).

Ada Lovelace's diagram from "note G", the first published computer algorithm

수학(mathematics)과 컴퓨터 과학(computer science)에서, 알고리듬(algorithm, /ˈælɡərɪðəm/ (listen))은 전형적으로 특정 문제(problems)의 클래스를 해결하거나 계산(computation)을 수행하기 위해 사용되는 엄격한(rigorous) 명령의 유한 순서열입니다. 알고리듬은 계산(calculations)과 데이터 처리(data processing)를 수행하는 데 사양으로 사용됩니다. 보다 발전된 알고리듬은 조건(conditionals)을 사용하여 다양한 경로 (자동화된 의사-결정(automated decision-making)이라고 참조됨)를 통해 코드 실행을 전환하고, 유효한 추론(inferences) (자동화된 추리(automated reasoning)이라고 참조됨)을 연역하여, 결국 자동화(automation)를 달성할 수 있습니다. 은유적 방법에서 인간의 특성을 기계의 서술자로 사용한 것은 앨런 튜링(Alan Turing)에 의해 이미 "기억", "검색" 및 "자극"과 같은 용어를 사용하여 실행한 것입니다.

대조적으로, 휴리스틱(heuristic)은 특히 잘-정의된 올바른 또는 최적의 결과가 없는 문제 영역에서 완전히 지정되지 않거나 정확하거나 최적의 결과를 보장하지 않을 수 있는 문제 해결에 대한 접근 방식입니다.

효과적인 방법(effective method)으로, 알고리듬은 유한한 공간과 시간 내에서 표현되고, 함수(function)를 계산하는 데 잘-정의된 형식적 언어로 표현될 수 있습니다. 초기 상태와 초기 입력 (아마도 빈 것)에서 시작하여, 명령은 실행될 때 유한한 숫자의 잘-정의된 연속적인 상태를 통해 진행되어, 결국 "출력"을 생성하고 최종 끝 상태에서 종료되는 계산을 설명합니다. 한 상태에서 다음 상태로의 전환이 반드시 결정론적(deterministic)인 것은 아닙니다; 무작위 알고리듬(randomized algorithms)으로 알려진 일부 알고리듬은 무작위 입력을 통합합니다.

History

알고리듬의 개념은 고대부터 존재해 왔습니다. 나눗셈 알고리듬(division algorithm)과 같은 산술 알고리듬은 기원전 2500년경 고대 바빌로니아 수학자들과 기원전 1550년경 이집트 수학자들에 의해 사용되었습니다. 그리스 수학자들은 나중에 기원전 240년에 소수를 찾는 데 에라토스테네스의 체(sieve of Eratosthenes)에서 알고리듬을 사용했고, 두 숫자의 최대 공통 약수(greatest common divisor)를 찾는 데 유클리드 알고리듬(Euclidean algorithm)을 사용했습니다. 9세기에서 알-킨디(Al-Kindi)와 같은 아랍 수학자들은 빈도 분석(frequency analysis)을 기반으로 암호-해독(code-breaking)을 위해 암호화(cryptographic) 알고리듬을 사용했습니다.

알고리듬(algorithm)이라는 단어는 9세기 페르시아 수학자 무하마드 이븐 무사 알-콰리즈미(Muḥammad ibn Mūsā al-Khwārizmī)의 산술 논문 "Al-Khwarizmi Concerning the Hindu Art of Reckoning"의 라틴어 번역, Algoritmi de numero Indorum에서 파생되었습니다. 알-콰리즈미는 수학자, 천문학자, 및 지리학자로 바그다드에 있는 지혜의 집에서 학자로 활동했으며, 그 이름은 대이란의 일부였고 현재 우즈베키스탄에 있는 지역, "Khwarazm의 원주민"을 의미합니다. 약 825년에, 알-콰리즈미는 힌두-아라비아 숫자-표시 시스템에 관한 아랍어 논문을 썼으며, 이는 12세기 동안 라틴어로 번역되었습니다. 원고는 Dixit Algorizmi ("Thus spoke Al-Khwarizmi")라는 문구로 시작하며, 여기서 "Algorizmi"는 알-콰리즈미의 이름의 번역가의 라틴어화였습니다. 알-콰리즈미는 주로 그의 다른 책, Algebra를 통해 중세 후기에 유럽에서 가장 널리 읽힌 수학자였습니다. 후기 중세 라틴어에서, algorismus, 영어 "algorism", 그의 이름의 타락은 "십진 숫자 시스템"을 의미했습니다. 15세기에, 그리스어 ἀριθμός (arithmos), "숫자" (비고, "산술")의 영향 아래에서, 라틴어 단어는 algorithmus로 바뀌었고, 이에 해당하는 영어 용어 "algorithm"은 17세기에 처음으로 증거가 되었습니다; 현대적 의미는 19세기에 도입되었습니다.

인도 수학은 주로 알고리듬이었습니다. 인도의 수학적 전통을 대표하는 알고리듬은 고대 Śulbasūtrās에서 케랄라 학파의 중세 문헌에 이르기까지 다양합니다.

영어에서, algorithm이라는 단어는 1230년경에 처음 사용되었고 1391년 초서(Chaucer)에 의해 사용되었습니다. 영어는 프랑스어 용어를 채택했지만, 19세기 후반이 되어서야 "algorithm"이 현대 영어에서 가지는 의미를 얻게 되었습니다.

이 단어의 또 다른 초기 사용은 Alexandre de Villedieu에 의해 구성된 Carmen de Algorismo라는 제목의 매뉴얼에서 1240년부터 사용되었습니다. 그것은 음으로 시작합니다:

Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris.

다음으로 번역됩니다:

알고리듬은 현재 우리가 숫자 2 곱하기 5인 인도 수치를 사용하는 기술입니다.

그 시는 길이가 수백 줄이고 새로운 스타일의 인도식 주사위 (Tali Indorum), 또는 힌두 숫자-표시로 계산하는 기술을 요약합니다.

현대 알고리듬 개념의 부분적 형식화는 1928년 다비트 힐베르트(David Hilbert)에 의해 제기된 Entscheidungsproblem (결정 문제)을 해결하려는 시도로 시작되었습니다. 이후의 형식화는 "효과적인 계산-가능성" 또는 "효과적인 방법"을 정의하려는 시도로 짜여졌습니다. 그들 형식화는 1930년, 1934년 및 1935년의 Gödel–Herbrand–Kleene 재귀 함수(recursive functions), 1936년 Alonzo Church의 람다 계산법(lambda calculus), 1936년 Emil Post의 형식화 1, 1936–37 및 1939년의 Alan Turing의 튜링 기계(Turing machines)를 포함합니다.

Informal definition

For a detailed presentation of the various points of view on the definition of "algorithm", see Algorithm characterizations.

비형식적 정의는 모든 컴퓨터 프로그램 (수치 계산을 수행하지 않는 프로그램 포함)과 (예를 들어) 임의의 규정된 관료적인(bureaucratic) 절차 또는 요리책 레시피를 포함하는 "작업의 순서열을 정확하게 정의하는 규칙의 집합"일 수 있습니다.

일반적으로, 프로그램은 궁극적으로 중지되는 경우에만 알고리듬입니다—때때로 무한 루프(infinite loops)가 바람직한 것으로 판명될 수도 있습니다.

알고리듬의 원형적 예제는 두 정수의 최대 공통 약수를 결정하기 위해 사용되는 유클리드 알고리듬(Euclidean algorithm)입니다; 위의 순서도(flowchart)에 예제 (다른 예제가 있음)가 설명되어 있고 이후 섹션에서 예제로 설명됩니다.

Boolos, Jeffrey & 1974, 1999는 다음 인용문에서 "알고리듬"이라는 단어의 비형식적 의미를 제공합니다:

어떤 사람도 어떤 표기법에서 그들의 이름을 차례로 쓺으로써 열거할 수 있는 무한한 집합의 모든 구성원을 나열할 만큼 충분히 빠르거나, 충분히 길거나, 충분히 작게† (†"제한 없이 점점 더 작아집니다... 분자, 원자, 전자에 쓰려고 시도할 것입니다") 쓸 수 없습니다. 그러나 사람은 어떤 열거-가능한 무한 집합의 경우에서 똑같이 유용한 일을 할 수 있습니다: 그들은 임의적인 유한 n에 대해 집합의 n번째 구성원을 결정하는 데 명시적 명령을 제공할 수 있습니다. 그러한 명령은 컴퓨팅 기계, 또는 기호에 대해 매우 기본적인 작업만 수행할 수 있는 사람이 따를 수 있는 형식으로 매우 명시적으로 제공되어야 합니다.

"열거-가능한 무한 집합"은 그 원소가 정수와 일-대-일 대응으로 넣을 수 있는 집합입니다. 따라서 Boolos와 Jeffrey는 알고리듬이 임의적인 "입력" 정수 또는, 이론에서, 임의적으로 클 수 있는 정수로부터 출력 정수를 "생성"하는 프로세스에 대한 지침을 의미한다고 말하고 있습니다. 예를 들어, 알고리듬은 y = m + n (즉, 출력 y를 생성하는 두 개의 임의적인 "입력 변수" m과 n)과 같은 대수적 방정식일 수 있지만, 개념을 정의하기 위한 다양한 저자의 시도는 그 단어는 이것보다 훨씬 더 많은 (추가적인 예제에 대해) 다음 정도의 어떤 것을 의미합니다:

"컴퓨터" (필요한 내부적으로 포함된 정보와 기능을 갖춘 기계 또는 인간)의 "이동"을 지정하는 빠르고, 효율적인, "좋은" 프로세스를 찾고, 디코딩하고, 그런-다음 임의적인 입력/기호 m와 n, 기호 +와 = ...을 처리하고, "합리적인" 시간에서, 지정된 위치와 지정된 형식에서 출력-정수 y를 "효율적으로" 생성하기 위한 (컴퓨터가 이해하는 언어에서) 정확한 지침.

알고리듬의 개념은 역시 결정-가능성(decidability)—공리와 규칙의 작은 집합에서 시작하여 형식적 시스템이 어떻게 발생하는지 설명하는 데 핵심적인 개념을 정의하기 위해 사용됩니다. 논리(logic)에서, 알고리듬이 완료하기 위해 요구되는 시간은 측정될 수 없는데, 왜냐하면 관습적인 물리적 차원과 분명하게 관련되지 않기 때문입니다. 진행 중인 작업을 특징짓는 그러한 불확실성으로 인해, 용어의 (어떤 의미에서) 구체적이고 추상적 사용 모두에 적합한 알고리듬의 정의를 사용할 수 없도록 만듭니다.

대부분의 알고리듬은 컴퓨터 프로그램으로 구현되려고 의도된 것입니다. 어쨌든, 알고리듬은 역시 생물학적 신경망 (예를 들어, 산술을 구현하는 인간의 뇌 또는 음식을 찾는 곤충), 전기 회로, 또는 기계 장치와 같은 다른 수단으로 구현됩니다.

Formalization

알고리듬은 컴퓨터가 데이터를 처리하는 방법에 필수적입니다. 많은 컴퓨터 프로그램은 직원의 월급 계산이나 학생의 성적표 인쇄와 같은 특정 작업을 수행하기 위해—특정 순서로—컴퓨터가 수행해야 하는 특정 지침을 자세히 설명하는 알고리듬을 포함하고 있습니다. 따라서 알고리듬은 튜링-완성(Turing-complete) 시스템에서 시뮬레이션될 수 있는 연산의 임의의 순서열로 고려될 수 있습니다. 이 논문을 주장하는 저자로는 민스키 (1967), 세비지 (1987), 및 구레비치 (2000)를 포함합니다:

민스키: "그러나 우리는 역시 튜링과 함께 ... "자연스럽게" 효과적이라고 불릴 수 있는 임의의 절차가 사실, (단순한) 기계에 의해 실현될 수 있다고 주장할 것입니다. 비록 이것이 극단적으로 보일 수 있지만, 그 주장은 ... 유리하게 반박하는 것이 어렵습니다". 구레비치: "... 그의 논문을 지지하는 튜링의 비형식적 주장은 더 강력한 논문을 정당화합니다: 모든 각 알고리듬은 튜링 기계에 의해 시뮬레이션될 수 있습니다 ... 세비지 [1987]에 따르면, 알고리듬은 튜링 기계에 의해 정의된 계산 과정입니다.".

튜링 기계는 종료하지 않는 계산적 과정을 정의할 수 있습니다. 알고리듬의 비형식적 정의는 일반적으로 알고리듬이 항상 종료하도록 요구합니다. 이 요구 사항은 정지 문제(halting problem)로 알려진 계산-가능성 이론(computability theory)의 주요 정리로 인해 형식적 절차가 일반적인 경우에서 불가능한 알고리듬인지 여부를 결정하는 임무를 렌더링합니다.

전형적으로, 알고리듬이 정보 처리와 관련되어 있을 때, 데이터는 입력 원천에서 읽고 출력 장치에 쓰고 추가 처리를 위해 저장될 수 있습니다. 저장된 데이터는 알고리듬을 수행하는 엔터티의 내부 상태의 일부로 여겨집니다. 실제로, 상태는 하나 이상의 데이터 구조(data structures)에 저장됩니다.

이들 계산적 과정 중 일부에 대해, 알고리듬은 엄격하게 정의되어야 합니다: 그리고 발생될 수 있는 모든 가능한 상황에 적용되는 방법으로 지정되어야 합니다. 이것은 임의의 조건부 단계가 사례별로 시스템적으로 처리되어야 함을 의미합니다; 각 사례에 대한 기준은 명확해야 합니다 (그리고 계산-가능해야 합니다).

알고리듬은 정확한 단계의 정확한 목록이기 때문에, 계산의 순서는 알고리듬의 기능화에 항상 중요합니다. 지침은 보통 명시적으로 나열되는 것으로 가정되고, "위에서" 시작하여 "아래로" 내려가는 것으로 설명됩니다—제어 흐름(flow of control)에 의해 보다 형식적으로 설명되는 아이디어입니다.

지금까지, 알고리듬의 형식화에 대한 논의는 명령형 프로그래밍(imperative programming)의 전제를 가정해 왔습니다. 이것은 임무를 불연속적, "기계적" 수단으로 설명하려고 시도하는 가장 공통적인 개념입니다. 형식화된 알고리듬의 이러한 개념에 고유한 것은 변수의 값을 설정하는 할당 연산(assignment operation)입니다. 그것은 스크래치 패드로서의 "기억(memory)"의 직관에서 파생됩니다. 그러한 할당의 예제는 아래에서 찾을 수 있습니다.

알고리듬을 구성하는 것에 대한 몇 가지 대안적인 개념에 대해, 함수형 프로그래밍(functional programming) 및 논리 프로그래밍(logic programming)을 참조하십시오.

Expressing algorithms

알고리듬은 자연 언어, 유사-코드(pseudocode), 순서도(flowcharts), 드라콘-차트(drakon-charts), 프로그래밍 언어 또는 제어 테이블 (인터프리터에 의해 처리됨)을 포함하여 다양한 종류의 표기법으로 표현될 수 있습니다. 알고리듬의 자연 언어 표현은 장황하고 모호한 경향이 있고, 복잡하거나 기술적인 알고리듬에 거의 사용되지 않습니다. 유사코드, 순서도, 드라콘-차트(drakon-charts) 및 제어 테이블은 자연 언어를 기반으로 하는 문장에서 흔히 발생하는 많은 모호성을 피하는 알고리듬을 표현하는 구조화된 방법입니다. 프로그래밍 언어는 주로 컴퓨터에 의해 실행될 수 있는 형식으로 알고리듬을 표현하기 위한 것이지만, 종종 알고리듬을 정의하거나 문서화하는 방법으로 사용됩니다.

가능한 다양한 표현이 있고 주어진 튜링 기계 프로그램을 일련의 기계 테이블 (자세한 내용에 대해 유한-상태 기계, 상태 전이 테이블 및 제어 테이블을 참조), 순서도와 드라콘-차트 (자세한 내용에 대해 상태 다이어그램을 참조), 또는 "네 겹의 집합"이라고 하는 초보적인 기계 코드 또는 어셈블리 코드 (자세한 내용에 대해 튜링 기계를 참조)의 한 형식으로 표현할 수 있습니다.

알고리듬의 표현은 다음과 같이 세 가지 허용 수준의 튜링 기계 설명으로 분류될 수 있습니다:

1 High-level description

"...구현 세부 사항을 무시하고, 알고리듬을 설명하는 산문입니다. 이 수준에서, 우리는 기계가 테이프나 헤드를 관리하는 방법을 언급할 필요가 없습니다."

2 Implementation description

"...튜링 기계가 헤드를 사용하는 방법과 테이프에 데이터를 저장하는 방법을 정의하기 위해 사용되는 산문입니다. 이 수준에서, 상태 또는 전이 기능에 대한 세부 정보를 제공하지 않습니다."

3 Formal description

가장 상세한 "최저 수준"은 튜링 기계의 "상태 테이블"을 제공합니다.

세 가지 수준 모두에 설명된 간단한 알고리듬 "Add m+n"의 예제에 대해, 아래 예제(Examples)를 참조하십시오.

Design

See also: Algorithm § By design paradigm

알고리듬 설계는 문제-해결과 공학 알고리듬을 위한 방법 또는 수학적 과정을 말합니다. 알고리듬의 설계는 운영 연구(operations research) 내의 분할-과-정복(divide-and-conquer) 또는 동적 프로그래밍(dynamic programming)과 같은 많은 해 이론의 일부입니다. 알고리듬 설계를 설계하고 구현하는 데 기술은 알고리듬 설계 패턴이라고도 하며, 템플릿 방법 패턴과 데코레이터 패턴을 예제로 들 수 있습니다.

알고리듬 설계의 가장 중요한 측면 중 하나는 자원 (실행 시간, 메모리 사용) 효율성입니다: 큰 O 표기법(big O notation)은 예를 들어 입력 크기가 증가함에 따라 알고리듬의 실행 시간이 증가를 설명하기 위해 사용됩니다.

알고리듬 개발에서 전형적인 단계:

1. 문제 정의(Problem definition)
2. 델의 개발(D몯모ㅁ Development of a) model
3. 알고리듬의 사양(Specification of the algorithm)
4. 알고리듬을 설계(Designing an algorithm)
5. 알고리듬의 정확성(correctness)의 확인
6. 알고리듬의 분석(Analysis of algorithm)
7. 알고리듬의 구현(Implementation of algorithm)
8. 프로그램 테스트(Program testing)
9. 문서 준비(Documentation preparation)

Computer algorithms

Logical NAND algorithm implemented electronically in 7400 chip

Flowchart examples of the canonical Böhm-Jacopini structures: the SEQUENCE (rectangles descending the page), the WHILE-DO and the IF-THEN-ELSE. The three structures are made of the primitive conditional GOTO (IF test THEN GOTO step xxx, shown as diamond), the unconditional GOTO (rectangle), various assignment operators (rectangle), and HALT (rectangle). Nesting of these structures inside assignment-blocks results in complex diagrams (cf. Tausworthe 1977:100, 114).

"우아한" (컴팩트) 프로그램, "좋은" (빠른) 프로그램: "단순함과 우아함"이라는 개념은 커누스(Knuth)에서 비형식적으로 나타나고, 카이틴(Chaitin)에서 정확하게 나타납니다:

커누스: " ... 우리는 느슨하게 정의된 미학적 의미에서 좋은 알고리듬을 원합니다. 하나의 기준은 ... 알고리듬을 수행하는 데 걸리는 시간의 길이입니다 .... 다른 기준은 컴퓨터에 대한 알고리듬의 적응성, 그것의 단순성, 및 우아함, 등입니다."

카이틴: "... 프로그램이 '우아하다', 그것에 의해 나는 그것이 하는 것에 출력을 생성하는 데 가장 작은 가능한 프로그램임을 의미합니다."

카이틴은 다음과 같이 자신의 정의를 시작합니다: "프로그램이 '우아하다'는 것을 증명할 수 없음을 보여드리겠습니다"—그러한 증명은 정지 문제(Halting problem)를 해결할 것입니다 (ibid).

알고리듬 대 알고리듬에 의해 계산-가능한 함수: 주어진 함수에 대해, 여러 알고리듬이 존재할 수 있습니다. 이것은 프로그래머가 사용할 수 있는 명령어 집합을 확장하지 않아도 참입니다. 로저스(Rogers)는 "...알고리듬의 개념, 즉 절차와 알고리듬에 의해 계산-가능한 함수의 개념, 즉 절차에 의해 생성된 매핑 사이를 구별하는 것이 중요합니다. 같은 함수는 여러 다른 알고리듬을 가질 수 있습니다."

불행하게도, 좋음 (속도)과 우아함 (컴팩트) 사이에는 상충 관계가 있을 수 있습니다—우아한 프로그램은 덜 우아한 것보다 계산을 완료하기 위해 더 많은 단계를 거칠 수 있습니다. 유클리드의 알고리듬을 사용하는 예제가 아래에 나와 있습니다.

컴퓨터, 계산의 모델: 컴퓨터 (또는 인간 "컴퓨터")는 맹목적으로 명령을 따르는 제한된 유형의 기계, "이산 결정론적 기계 장치"입니다. Melzak과 Lambek의 원시 모델은 이 개념을 네 가지 요소로 축소했습니다: (i) 별개의 구별-가능한 위치, (ii) 별개의, 구별-불가능한 카운터 (iii) 에이전트, 및 (iv) 에이전트의 기능과 관련하여 효과적인 지침의 목록.

민스키는 그의 "Very Simple Bases for Computability"에서 Lambek의 "주판" 모델의 더 적합한 변형을 설명합니다. 민스키의 기계(Minsky's machine)는 조건부 IF-THEN GOTO 또는 무조건부 GOTO가 프로그램 흐름을 순서열에서 변경하지 않은 한 5개 (또는 계산 방법에 따라 6개) 명령을 통해 순차적으로 진행합니다. HALT 외에도, 민스키의 기계는 ZERO (예를 들어, 위치의 내용이 0으로 대체됨: L ← 0), SUCCESSOR (예를 들어, L ← L+1), 및 DECREMENT (예를 들어, L ← L − 1)의 세 가지 할당 (대체, 치환) 연산을 포함합니다. 프로그래머가 이렇게 제한된 명령어 집합으로 "코드"를 작성해야 하는 경우는 드뭅니다. 그러나 민스키는 (Melzak와 Lambek과 마찬가지로) 그의 기계가 조건부 GOTO, 무조건부 GOTO, 할당/대체/치환, 및 HALT의 네 가지 일반적인 유형의 명령만으로 튜링 완전(Turing complete)을 보여줍니다. 어쨌든, 튜링-완전성에는 몇 가지 다른 할당 명령 (예를 들어, 민스키 기계에 대해, DECREMENT, INCREMENT, 및 ZERO/CLEAR/EMPTY)도 필요합니다; 그것들의 정확한 사양은 어느 정도 디자이너에게 달려 있습니다. 무조건부 GOTO가 편리합니다; 그것은 전용 위치를 영, 예를 들어, 명령 " Z ← 0 "으로 초기화함으로써 구성될 수 있습니다; 이후 명령 IF Z=0 THEN GOTO xxx는 무조건부입니다.

알고리듬의 모의실험: 컴퓨터 언어: 커누스는 독자에게 "알고리듬을 배우는 가장 좋은 방법은 그것을 시도하는 것입니다. . . 즉시 펜과 종이를 가지고 예제를 통해 작업하십시오"라고 조언합니다. 그러나 실제의 모의실험이나 실행은 어떻습니까? 프로그래머는 알고리듬을 모의실험/컴퓨터가 효과적으로 실행할 수 있는 언어로 번역해야 합니다. Stone은 이에 대한 예제를 제공합니다: 이차 방정식의 근을 계산할 때, 컴퓨터는 제곱근을 구하는 방법을 알아야 합니다. 만약 그것이 가능하지 않으면, 알고리듬이, 효과적이려면, 제곱근을 추출하기 위한 일련의 규칙을 제공해야 합니다.

이것은 프로그래머가 대상 컴퓨팅 에이전트 (컴퓨터)에 관련하여 효과적인 "언어"를 알아야 한다는 것을 의미합니다.

그러나 모의실험에 어떤 모델을 사용해야 합니까? Van Emde Boas는 "우리가 복잡성 이론(complexity theory)을 구체적인 기계 대신 추상적인 것에 기초하더라도, 모델 선택의 임의성은 남아 있습니다. 이 시점에서 모의실험의 개념이 도입됩니다"라고 말합니다. 속력이 측정될 때, 명령어 집합이 중요합니다. 예를 들어, 나머지를 계산하는 유클리드 알고리듬의 부분-프로그램은 프로그래머가 단순히 뺄셈 (또는 더 나쁘게는 민스키의 "decrement")가 아닌 사용-가능한 "모듈러스(modulus)" 명령을 가졌다면 훨씬 빠르게 실행됩니다.

구조화된 프로그래밍, 정식의 구조: 처치-튜링 논제(Church–Turing thesis)에 따르면, 임의의 알고리듬은 튜링 완전(Turing complete)으로 알려진 모델로 계산될 수 있고, 민스키의 시연에 따르면, 튜링 완전성은 조건부 GOTO, 무조건부 GOTO, 할당, HALT의 4가지 명령 유형만 필요합니다. Kemeny와 Kurtz는 무조건부 GOTO와 조건부 IF-THEN GOTO를 "무분별하게" 사용하면 "스파게티 코드(spaghetti code)"가 될 수 있지만, 프로그래머는 이들 명령만 사용하여 구조화된 프로그램을 작성할 수 있음을 관찰했습니다; 다른 한편으로, "잘못 구조화된 프로그램을 구조화된 언어로 작성하는 것도 가능하지만 그렇게 어렵지는 않습니다". Tausworthe는 세 개의 Böhm-Jacopini canonical structures: SEQUENCE, IF-THEN-ELSE, 및 WHILE-DO를 보강하고, DO-WHILE와 CASE 두 개를 더 추가합니다. 구조화된 프로그램의 추가적인 이점은 수학적 귀납법(mathematical induction)을 사용하여 정확성의 증명(proofs of correctness)에 적합하다는 것입니다.

정식의 순서도 기호: 순서도(flowchart)라고 하는 그래픽 보조 도구는 알고리듬 (및 그에 상응하는 컴퓨터 프로그램)을 설명하고 문서화하는 방법을 제공합니다. 민스키 기계의 프로그램 흐름과 마찬가지로, 순서도는 항상 페이지의 꼭대기에서 시작하고 아래로 진행합니다. 그것의 주요 기호는 프로그램 흐름을 나타내는 방향화된 화살표, 사각형 (SEQUENCE, GOTO), 다이아몬드 (IF-THEN-ELSE), 및 점 (OR-tie)의 4개뿐입니다. Böhm–Jacopini 정식의 구조는 이들 원시 모양으로 만듭니다. 하위-구조는 직사각형에 "중첩"할 수 있지만, 상부-구조에서 단일 출구가 발생하는 경우에만 가능합니다. 정식의 구조를 구축하기 위한 기호와 그것들의 사용이 다이어그램에 표시됩니다.

Examples

Further information: List of algorithms

Algorithm example

가장 간단한 알고리듬 중 하나는 무작위 순서의 숫자 목록에서 가장 큰 숫자를 찾는 것입니다. 해결책을 찾는 것은 목록에서 모든 각 숫자를 살펴봐야 합니다. 이것으로부터 다음과 같이 산문에서 높은-수준 설명에서 말할 수 있는 간단한 알고리듬을 따릅니다:

높은-수준 설명:

1. 만약 집합에 숫자가 없으면, 가장 높은 숫자가 없습니다.
2. 집합에서 첫 번째 숫자가 집합에서 가장 큰 숫자라고 가정합니다.
3. 집합에서 남아있는 각 숫자에 대해: 만약 이 숫자가 현재 가장 큰 숫자보다 크면, 이 숫자를 집합에서 가장 큰 숫자로 생각합니다.
4. 집합에 반복할 남아 있는 숫자가 없을 때, 현재 가장 큰 숫자를 집합에서 가장 큰 숫자로 생각합니다.

(준)형식적 설명: 산문으로 작성되었지만 컴퓨터 프로그램의 높은-수준 언어에 훨씬 더 가까운, 다음은 유사-코드(pseudocode) 또는 피진 코드(pidgin code)에서 알고리듬을 보다 형식적으로 코딩한 것입니다:

Algorithm LargestNumber
Input: A list of numbers L.
Output: The largest number in the list L.

if L.size = 0 return null
largest ← L[0]
for each item in L, do
    if item > largest, then
        largest ← item
return largest

• "←" denotes assignment. For instance, "largest ← item" means that the value of largest changes to the value of item.
• "return" terminates the algorithm and outputs the following value.

Euclid's algorithm

Further information: Euclid's algorithm

수학(mathematics)에서, 유클리드 알고리듬은 두 정수 (숫자)의 최대 공통 약수(greatest common divisor, GCD), 둘을 나머지(remainder) 없이 나누는 가장 큰 숫자를 계산하는 데 효율적인 방법입니다. 그것은 그의 원론(Elements, 기원전 약, 300년)에서 처음으로 그것을 기술한 고대 그리스 수학자 유클리드(Euclid)의 이름을 따서 지어졌습니다. 그것은 공통적으로 사용되는 가장 오래된 알고리듬 중 하나입니다. 그것은 분수(fractions)를 가장 간단한 형식으로 줄이기 위해 사용될 수 있고, 다른 많은 숫자-이론적 및 암호화 계산의 일부입니다.

The example-diagram of Euclid's algorithm from T.L. Heath (1908), with more detail added. Euclid does not go beyond a third measuring and gives no numerical examples. Nicomachus gives the example of 49 and 21: "I subtract the less from the greater; 28 is left; then again I subtract from this the same 21 (for this is possible); 7 is left; I subtract this from 21, 14 is left; from which I again subtract 7 (for this is possible); 7 is left, but 7 cannot be subtracted from 7." Heath comments that "The last phrase is curious, but the meaning of it is obvious enough, as also the meaning of the phrase about ending 'at one and the same number'."(Heath 1908:300).

유클리드는 다음과 같이 문제를 제기합니다: "서로 소수가 아닌 두 개의 숫자가 주어지면, 그것들의 최대 공통 약수를 찾습니다." 그는 "단위로 구성된 배수[가 되는] 숫자": 세는 숫자, 영을 포함하지 않는 양의 정수를 정의합니다. "측정"하는 것은 남아있는 부분 r이 더 짧은 길이 s보다 작을 때까지 더 긴 길이 l을 따라 더 짧은 측정 길이 s를 연속적으로 (q번) 배치하는 것입니다. 현대적인 말로, 나머지 r = l − q×s, q는 몫이거나 나머지 r은 나눗셈 후에 남은 정수-분수적 부분, "모듈러스"입니다.

유클리드의 방법이 성공하려면, 시작 길이가 두 가지 요구 사항을 충족해야 합니다: (i) 길이가 영이 아니어야 합니다, 그리고 (ii) 뺄셈은 "적절"해야 합니다; 즉, 테스트는 두 숫자 중 더 작은 숫자가 더 큰 숫자에서 뺀다는 것을 보장해야 합니다 (또는 두 숫자는 그것들의 뺄셈이 영을 산출하도록 같을 수 있습니다).

유클리드의 원래 증명은 세 번째 요구 사항을 추가합니다: 두 길이는 서로소가 아니어야 합니다. 유클리드는 두 숫자의 공통 측정이 실제로 가장 크다는 귀류법(reductio ad absurdum) 증명을 구성할 수 있도록 이것을 규정했습니다. Nicomachus의 알고리듬은 유클리드의 알고리듬과 같지만, 숫자가 서로소일 때, 그것은 공통 측정으로 숫자 "1"을 생성합니다. 따라서, 정확히 말하면, 다음은 실제로 Nicomachus의 알고리듬입니다.

A graphical expression of Euclid's algorithm to find the greatest common divisor for 1599 and 650

 1599 = 650×2 + 299
 650 = 299×2 + 52
 299 = 52×5 + 39
 52 = 39×1 + 13
 39 = 13×3 + 0

Computer language for Euclid's algorithm

유클리드의 알고리듬을 실행하는 데 필요한 명령어 유형은 일부 논리적 테스트 (조건부 GOTO), 무조건부 GOTO, 할당 (대체), 및 뺄셈입니다.

• 위치는 대문자, 예를 들어, S, A,등에 의해 기호화됩니다. 에스, 에이 등
• 위치에서 변하는 양 (숫자)은 소문자로 작성되고 (보통) 위치 이름과 결합됩니다. 예를 들어, 시작에서 위치 L은 숫자 l = 3009을 포함할 수 있습니다.

An inelegant program for Euclid's algorithm

"Inelegant" is a translation of Knuth's version of the algorithm with a subtraction-based remainder-loop replacing his use of division (or a "modulus" instruction). Derived from Knuth 1973:2–4. Depending on the two numbers "Inelegant" may compute the g.c.d. in fewer steps than "Elegant".

다음 알고리듬은 유클리드와 니코마코스의 알고리듬의 커누스의 4-단계 버전으로 구성되어 있지만, 나눗셈을 사용하여 나머지를 찾는 대신, r이 s보다 작을 때까지 남아있는 길이 r에서 더 짧은 길이 s를 연속적으로 뺍니다. 굵은 글씨로 표시된 높은-수준의 설명은 Knuth 1973:2–4에서 채택되었습니다.

INPUT:

1 [두 위치 L과 S에 두 길이를 나타내는 숫자 l과 s를 넣습니다]:
INPUT L, S
2 [R 초기화: 남아있는 길이 r을 시작/초기/입력 길이 l과 같게 만듭니다]:
R ← L

E0: [Ensure r ≥ s.]

3 [두 숫자 중 작은 것이 S에 있고 큰 것이 R에 있는지 보장합니다]:
IF R > S THEN
L의 내용물이 더 큰 숫자이므로 교환-단계 4, 5 및 6을 건너뜁니다:
GOTO step 7
ELSE
R과 S의 내용물을 교환합니다.
4 L ← R (이 첫 번째 단계는 중복되지만, 나중에 논의할 때 유용합니다).
5 R ← S
6 S ← L

E1: [Find remainder]: R에서 남아있는 길이 r이 S에서 짧은 길이 s보다 작을 때까지 R에서 남아있는 길이 r에서 S에서 측정 숫자 s를 반복해서 뺍니다.

7 IF S > R THEN
따라서 측정을 완료합니다
GOTO 10
ELSE
다시 측정합니다,
8 R ← R − S
9 [Remainder-loop]:
GOTO 7.

E2: [Is the remainder zero?]: 둘 중 하나 (i) 마지막 측정이 정확하고, R에서 나머지가 0이고, 프로그램이 정지될 수 있습니다, 또는 (ii) 알고리듬이 계속되어야 합니다: 마지막 측정이 S에서 측정 숫자보다 작은 R에서 나머지를 남겼습니다.

10 IF R = 0 THEN
따라서 완료합니다
GOTO step 15
ELSE
CONTINUE TO step 11,

E3: [Interchange s and r]: 유클리드 알고리듬의 열매. 나머지 r을 이전에 더 작은 숫자 s였던 것을 측정하기 위해 사용하십시오; L은 임시 위치 역할을 합니다.

11 L ← R
12 R ← S
13 S ← L
14 [측정 과정을 반복하십시오]:
GOTO 7

OUTPUT:

15 [완료합니다. S는 최대 공통 약수(greatest common divisor)를 포함하고 있습니다]:
PRINT S

DONE:

16 HALT, END, STOP.

An elegant program for Euclid's algorithm

유클리드 알고리듬의 다음 버전은 "Inelegant"에 의해 수행하기 위해 요구된 13개가 작업을 수행하기 위해 6개의 핵심 명령만 필요합니다; 더군다나, "Inelegant"에는 더 많은 유형의 명령이 필요합니다. "Elegant"의 순서도는 이 기사의 꼭대기에서 찾을 수 있습니다. (구조화되지 않은) 기본 언어에서, 단계는 번호-매겨지고, 명령어 LET [] = []는 ←에 의해 기호화된 할당 명령어입니다.

  5 REM Euclid's algorithm for greatest common divisor
  6 PRINT "Type two integers greater than 0"
  10 INPUT A,B
  20 IF B=0 THEN GOTO 80
  30 IF A > B THEN GOTO 60
  40 LET B=B-A
  50 GOTO 20
  60 LET A=A-B
  70 GOTO 20
  80 PRINT A
  90 END

"Elegant" 작동 방법: 외부 "Euclid loop" 대신 "Elegant"는 두 개의 "co-loops", A ← A − B를 계산하는 A > B 루프와 B ← B − A를 계산하는 B ≤ A 루프 사이에서 앞뒤로 이동합니다. 이것은 작동하는데 왜냐하면, 마침내 피감수 M이 감수 S보다 작거나 같을 때 (차이 = 피감수 - 감수), 피감수는 s (새로운 측정 길이)가 될 수 있고 감수는 새로운 r (측정될 길이)이 되기 때문입니다; 다시 말해서, 뺄셈의 "의미"가 반전됩니다.

다음 버전은 C-계열에서 프로그래밍 언어와 함께 사용될 수 있습니다:

// Euclid's algorithm for greatest common divisor
int euclidAlgorithm (int A, int B) {
     A = abs(A);
     B = abs(B);
     while (B != 0) {
          while (A > B) {
               A = A-B;
          }
          B = B-A;
     }
     return A;
}

Testing the Euclid algorithms

알고리듬은 저자가 원하는 대로 수행합니까? 몇 가지 테스트 사례는 보통 핵심 기능에 대해 어느 정도 확신을 줍니다. 그러나 테스트만으로는 충분하지 않습니다. 테스트 경우에 대해, 한 출처는 3009와 884를 사용합니다. 커누스는 40902, 24140을 제안했습니다. 또 다른 흥미로운 경우는 두 개의 상대적으로 소수(relatively prime) 14157과 5950입니다.

그러나 "예외적인 경우"가 식별되고 테스트되어야 합니다. R > S, S > R, R = S일 때 "Inelegant"가 제대로 작동합니까? "Elegant"도 마찬가지: B > A, A > B, A = B? (모두 예). 하나의 숫자가 0이고, 두 숫자가 모두 영이면 어떻게 됩니까? ("Inelegant"는 모든 경우에 영원히 계산합니다; "Elegant"는 A = 0일 때 영원히 계산합니다.) 음수를 입력하면 어떻게 됩니까? 분수? 만약 입력 숫자, 즉 알고리듬/프로그램에 의해 계산된 함수의 도메인이 영을 포함하는 양의 정수만 포함하는 것이면, 영에서의 실패는 알고리듬 (및 이를 인스턴스화하는 프로그램)이 전체 함수(total function)가 아니라 부분 함수(partial function)임을 나타냅니다. 예외로 인한 주목할만한 실패는 Ariane 5 Flight 501 로켓 실패 (1996년 6월 4일)입니다.

수학적 귀납법의 사용에 의한 프로그램 정확성의 증명: 커누스는 유클리드 알고리듬의 "확장된" 버전에 대한 수학적 귀납법(mathematical induction)의 적용을 시연하고, 그는 "임의의 알고리듬의 타당성을 증명하는 데 적용할 수 있는 일반적인 방법"을 제안합니다. Tausworthe는 프로그램의 복잡성 측정이 정확성 증명의 길이라고 제안합니다.

Measuring and improving the Euclid algorithms

우아함 (컴팩트) 대 좋음 (속력): 오직 여섯 개의 핵심 명령과 함께, "Elegant"가 13개의 명령이 있는 "Inelegant"와 비교하여 확실한 승자입니다. 어쨌든, "Inelegant"가 더 빠릅니다 (더 적은 단계로 HALT에 도달합니다). 알고리듬 분석(Algorithm analysis)은 이것이 그 경우인 이유를 나타냅니다: "Elegant"는 모든 각 뺄셈 루프에서 두 개의 조건부 테스트를 수행하고, 반면 "Inelegant"는 하나만 수행합니다. 알고리듬은 (보통) 많은 루프-통과를 필요로 하므로, 나머지가 계산된 후에만 필요한 "B = 0?" 테스트를 수행하는 데 평균적으로 많은 시간이 낭비됩니다.

알고리듬을 개선할 수 있습니까?: 프로그래머가 프로그램이 "적합"하고 "효과적"이라고 판단하면—즉, 저자에 의해 의도된 기능을 계산하면—질문은 다음이 됩니다: 그것이 개선될 수 있습니까?

"Inelegant"의 콤팩트함은 5단계의 제거에 의해 개선될 수 있습니다. 그러나 Chaitin은 알고리듬 컴팩트화가 일반화된 알고리듬에 의해 자동화될 수 없음을 증명했습니다; 오히려, 그것은 휴리스틱 방식으로만 수행될 수 있습니다; 즉, 철저한 검색(Busy beaver에서 찾을 수 있는 예제), 시행과 착오, 영리함, 통찰력, 귀납적 추론(inductive reasoning)의 적용, 등에 의해, 4, 5, 및 6단계가 11, 12, 및 13단계에서 반복됨을 관찰하십시오. "Elegant"는 2단계와 3단계와 함께 이들 단계가 제거될 수 있다는 힌트를 제공합니다. 이렇게 하면 핵심 명령어 숫자가 13개에서 8개로 줄어들어, 9단계에서 "Elegant"보다 "more elegant" 됩니다.

"Elegant"의 속력은 "B=0?" 테스트를 두 개의 뺄셈 루프 외부로 이동함으로써 개선될 수 있습니다. 이 변경은 세 가지 명령(B = 0?, A = 0?, GOTO)을 호출합니다. 이제 "Elegant"는 예제-숫자를 더 빠르게 계산합니다; 임의의 주어진 A, B, 및 R, S에 대해 이것이 항상 그 경우인지 여부 자세한 분석이 필요합니다.

Algorithmic analysis

Main article: Analysis of algorithms

주어진 알고리듬에 대해 이론적으로 특정 자원 (예를 들어, 시간 또는 저장공간)이 얼마나 필요한지 아는 것이 자주 중요합니다. 그러한 정량적 답변 (추정)을 얻기 위한 알고리듬의 분석(analysis of algorithms)을 위한 방법이 개발되어 왔습니다; 예를 들어, n개의 숫자 목록의 원소를 더하는 알고리듬은 큰 O 표기법(big O notation)을 사용하여 O(n)의 시간 요구 사항을 가집니다. 항상 알고리듬은 지금까지의 모든 원소의 합과 입력 목록에서 현재 위치의 두 값만 기억하면 됩니다. 그러므로, 입력된 숫자를 저장하는 데 필요한 공간을 세지 않으면 O(1), 또는 세면 O(n)의 공간 요구 사항을 가진다고 말합니다.

다른 알고리듬은 다른 것보다 적거나 더 많은 시간, 공간 또는 '노력(effort)'으로 다른 명령의 집합으로 같은 임무를 완료할 수 있습니다. 예를 들어, 이진 검색(binary search) 알고리듬 (비용 O(log n)을 가짐)은 정렬된 목록 또는 배열에서 테이블 조회(table lookups)에 사용될 때 순차 검색 (비용 O(n) )보다 성능이 뛰어납니다.

Formal versus empirical

Main articles: Empirical algorithmics, Profiling (computer programming), and Program optimization

알고리듬의 분석과 연구는 컴퓨터 과학(computer science)의 한 분야이고, 종종 특정 프로그래밍 언어 또는 구현의 사용 없이 추상적으로 실행됩니다. 이러한 의미에서, 알고리듬 분석은 알고리듬의 놓여 있는 속성에 집중하고 임의의 특정 구현의 세부 사항에 집중하지 않는다는 점에서 다른 수학적 분야와 닮아 있습니다. 보통 유사-코드(pseudocode)는 가장 단순하고 가장 일반적인 표현이기 때문에 분석에 대해 사용됩니다. 어쨌든, 궁극적으로, 대부분의 알고리듬은 보통 특정 하드웨어/소프트웨어 플랫폼에서 구현되고 그것들의 알고리듬 효율성(algorithmic efficiency)은 결국 실제 코드를 사용하여 테스트됩니다. "일회성" 문제의 해결을 위해, 특정 알고리듬의 효율성은 (n이 매우 크지 않은 한) 중요한 결과를 가져오지 않을 수 있지만 빠른 대화형, 상업적 또는 긴 수명의 과학적 사용을 위해 설계된 알고리듬에 대해 그것은 중요할 수 있습니다. 작은 n에서 큰 n으로 크기를 조정하면 자주 그렇지 않으면 무해한 것인 비효율적 알고리듬을 노출합니다.

경험적 테스트는 성능에 영향을 미치는 예기치 않은 상호 작용을 발견할 수 있기 때문에 유용합니다. 벤치마크(Benchmarks)는 프로그램 최적화 후 알고리듬과 잠재적 개선 전/후에 비교하는 데 사용될 수 있습니다. 경험적 테스트는, 어쨌든, 형식적인 분석을 대체 할 수 없고, 공정한 방식으로 수행하기 위해 자명하지 않습니다.

Execution efficiency

Main article: Algorithmic efficiency

잘-확립된 알고리듬에서도 가능한 잠재적 개선을 설명하기 위해, FFT 알고리듬 (이미지 처리 분야에서 몹시 많이 사용됨)과 관련된 최근의 중요한 혁신은 의료 이미징과 같은 응용 분야에 대해 1,000 번까지 처리 시간을 줄일 수 있습니다. 일반적으로, 속력 개선은 실제 응용 분야에서 매우 공통적인 문제의 특수 속성에 따라 다릅니다. 이 규모의 속력을 높이면 전력을 덜 소비하기 위한 이미지 처리 (예를 들어, 디지털 카메라와 의료 장비)를 광범위하게 사용하는 컴퓨팅 장치가 가능합니다.

Classification

각각 고유 한 장점을 갖는 알고리듬을 분류하는 다양한 방법이 있습니다.

By implementation

알고리듬을 분류하기 위한 한 가지 방법은 구현 수단에 의한 것입니다.

int gcd(int A, int B) { if (B == 0) return A; else if (A > B) return gcd(A-B,B); else return gcd(A,B-A); }

Recursive C implementation of Euclid's algorithm from the above flowchart

Recursion

재귀 알고리듬(recursive algorithm)은 특정 조건 (종단 조건이라고도 함)이 일치할 때까지 반복적으로 자체를 호출 (참조를 만듬)을 호출하는 것이며, 이는 함수형 프로그래밍(functional programming)에 공통적인 방법입니다. 반복적 알고리듬은 주어진 문제를 풀기 위해 루프(loops)와 같은 반복적인 구조물과 때로는 스택(stacks)과 같은 추가 데이터 구조를 사용합니다. 일부 문제는 한 구현 또는 다른 구현에 자연스럽게 적합합니다. 예를 들어, 하노이의 탑은 재귀 구현을 사용하여 잘 이해됩니다. 모든 각 재귀 버전은 동등한 (그러나 다소 복잡한) 반복 버전을 가지고, 그 반대도 마찬가지입니다.

Logical

알고리듬은 제어된 논리적 연역(logical deduction)으로 볼 수 있습니다. 이 개념은 알고리듬 = 논리 + 제어로 표현될 수 있습니다. 논리 구성 요소는 계산에 사용될 수 있는 공리를 표현하고 제어 구성 요소는 연역법이 공리에 적용되는 방법을 결정합니다. 이것이 논리적 프로그래밍 패러다임의 기초입니다. 순수한 논리적 프로그래밍 언어에서, 제어 구성 요소가 고정되고 알고리듬은 논리적 구성 요소만 제공함으로써 지정됩니다. 이 접근 방식의 매력은 우아한 의미론(semantics)입니다: 공리에서 변화는 알고리듬에서 잘-정의된 변화를 생성합니다.

Serial, parallel or distributed

알고리듬은 보통 컴퓨터가 한 번에 알고리듬의 하나의 명령을 실행한다는 가정에 대해 논의됩니다. 그것들 컴퓨터는 때때로 직렬 컴퓨터라고 불립니다. 그러한 환경을 위해 설계된 알고리듬은 병렬 알고리듬(parallel algorithms) 또는 분산 알고리듬(distributed algorithms)과 달리 직렬 알고리듬이라고 불립니다. 병렬 알고리듬은 여러 프로세서가 동시에 문제를 해결할 수 있는 컴퓨터 아키텍처의 이점을 취하는 알고리듬입니다. 분산 알고리듬은 컴퓨터 네트워크에 연결된 여러 기계를 사용하는 알고리듬입니다. 병렬 알고리듬과 분산 알고리듬은 문제를 보다 대칭적 또는 비대칭적 하위-문제로 나누고 결과를 다시 수집합니다. 예를 들어, CPU는 병렬 알고리듬의 예제일 것입니다. 그러한 알고리듬의 자원 소비는 각 프로세서에서 프로세서 주기일 뿐만 아니라 프로세서 사이의 통신 오버헤드입니다. 일부 정렬 알고리듬은 효율적으로 병렬화 될 수 있지만, 그것들의 통신 오버헤드는 비쌉니다. 반복 알고리듬은 일반적으로 병렬화-가능하지만, 일부 문제는 병렬 알고리듬을 가지지 않고 본질적으로 직렬 문제라고 불립니다.

Deterministic or non-deterministic

결정론적 알고리듬(Deterministic algorithms)은 알고리듬의 모든 각 단계에서 정확한 결정을 갖는 문제를 해결하고, 반면 비-결정론적 알고리듬(non-deterministic algorithms)은 추측을 통해 문제를 해결하지만 전형적인 추측은 휴리스틱(heuristics)의 사용을 통해 더 정확하게 만듭니다.

Exact or approximate

많은 알고리듬이 정확한 해에 도달하지만, 근사 알고리듬(approximation algorithms)은 실제 해에 가까운 근사를 찾습니다. 근사는 결정론적 또는 확률 전략을 사용하여 도달될 수 있습니다. 그러한 알고리듬은 많은 어려운 문제에 대해 실질적인 가치를 가집니다. 근사적인 알고리듬의 예제 중 하나는 주어진 항목의 집합이 있는 배낭 문제(Knapsack problem)입니다. 그 목표는 최대 전체 값을 얻기 위해 배낭을 포장하는 것입니다. 각 항목은 무게와 어떤 가치를 가집니다. 운반될 수 있는 전체 중량은 어떤 고정된 번호 X에 지나지 않습니다. 따라서, 해는 항목의 무게와 그 가치를 고려해야합니다.

Quantum algorithm

그것들은 양자 계산(quantum computation)의 현실적인 모델로 실행됩니다. 그 용어는 보통 본질적으로 양자로 보이는 알고리듬에 사용되거나, 양자 중첩(quantum superposition) 또는 양자 얽힘(quantum entanglement)과 같은 양자 컴퓨팅(Quantum computing)의 필수 특질을 사용합니다.

By design paradigm

알고리듬을 분류하는 또 다른 방법은 설계 방법론 또는 패러다임(paradigm)에 의한 것입니다. 특정 숫자의 패러다임이 있으며, 각 패러다임은 다른 것과 다릅니다. 더욱이, 이들 각 카테고리는 다양한 유형의 알고리듬이 포함됩니다. 몇 가지 공통적인 패러다임은 다음과 같습니다:

Brute-force or exhaustive search

무차별 대입(Brute Force)은 최적의 해가 발견 될 때까지 모든 각 가능한 선택 사항을 시스템적으로 시도를 포함하는 문제-해결의 방법입니다. 이 접근 방식은 모든 각 가능한 변수의 조합을 거쳐야 하므로 매우 시간 소모적이 될 수 있습니다. 어쨌든, 그것은 종종 다른 방법을 사용할 수 없거나 너무 복잡할 때 사용됩니다. 무차별 대입은 두 지점과 크래킹 암호 사이의 가장 짧은 경로를 찾는 것을 포함하여 다양한 문제를 해결하기 위해 사용될 수 있습니다.

Divide and conquer

분할-과-정복 알고리듬(divide-and-conquer algorithm)은 인스턴스가 쉽게 해결하도록 충분히 작을 때까지 (보통 재귀적으로) 문제의 인스턴스를 같은 문제의 하나 이상의 작은 인스턴스로 반복적으로 줄입니다. 분할과 정복의 그러한 예제 중 하나는 정렬을 병합하는 것입니다. 정렬은 데이터를 세그먼트로 나눈 후 각 데이터 세그먼트에서 정렬을 수행될 수 있고 전체 데이터의 정렬은 세그먼트를 병합함으로써 정복 단계에서 얻을 수 있습니다. 더 간단한 분할과 정복 변형은 감소-와-정복 알고리듬이라고 불리며, 이는 동일한 부분-문제를 해결하고 이 부분문제의 해를 더 큰 문제를 해결하기 위해 사용합니다. 분할과 정복은 문제를 여러 부분문제로 나누고 따라서 정복 단계는 감소와 정복보다 더 복잡합니다. 감소와 정복 알고리듬의 예제는 이진 검색 알고리듬(binary search algorithm)입니다.

Search and enumeration

많은 문제 (예를 들어 체스 게임)는 그래프(graph)의 문제로 모델링될 수 있습니다. 그래프 탐색 알고리듬(graph exploration algorithm)은 그래프 주위로 이동하는 데 규칙을 지정하고 그러한 문제에 대해 유용합니다. 이 카테고리는 역시 검색 알고리듬(search algorithms), 분기와 경계(branch and bound) 열거 및 역-추적(backtracking)을 포함합니다.

Randomized algorithm

그러한 알고리듬은 일부 선택을 무작위로 (또는 유사-무작위로) 만듭니다. 그것들은 정확한 해를 찾는 것이 비현실적이 될 수 있는 문제에 대해 근사적인 해를 찾는 데 매우 유용할 수 있습니다 (아래의 휴리스틱 방법을 참조). 이들 문제 중 일부에 대해, 가장 빠른 근사는 일부 무작위성(randomness)을 포함해야 하는 것으로 알려져 있습니다. 다항식 시간 복잡성(polynomial time complexity)을 갖는 무작위 알고리듬이 일부 문제에 대한 가장 빠른 알고리듬이 될 수 있는지 여부는 P 대 NP 문제(P versus NP problem)로 알려진 열린 질문입니다. 그러한 알고리듬에는 두 가지 큰 클래스가 있습니다:

1. 몬테 카를로 알고리듬(Monte Carlo algorithms)은 높은-확률을 갖는 정답을 반환합니다. 예를 들어 RP은 다항식 시간(polynomial time)에 실행되는 이것들의 부분클래스입니다.
2. 라스 베이거스 알고리듬(Las Vegas algorithms)은 항상 정확한 답을 반환하지만, 그것들의 실행 시간은 확률론적 경계집니다, 예를 들어, ZPP.

Reduction of complexity

이 기술은 우리가 (희망적으로) 점근적으로 최적(asymptotically optimal) 알고리듬을 가지고 있는 더-잘-알려진 문제로 변환함으로써 어려운 문제를 푸는 것을 포함합니다. 목표는 복잡성(complexity)이 결과로의 감소된 알고리듬에 의해 지배되지 않는 감소 알고리듬을 찾는 것입니다. 예를 들어, 분류되지 않은 목록에서 중앙값을 찾기 위한 하나의 선택 알고리듬(selection algorithm)은 먼저 목록 (비싼 부분)을 정렬하고 그런-다음 정렬된 목록 (저렴한 부분)에서 중간 원소를 꺼내는 것을 포함합니다. 이 기술은 변형-과-정복(transform and conquer)이라고도 알려져 있습니다.

Back tracking

이 접근 방식에서, 여러 해는 유효한 전체 해로 이어질 수 없다고 결정될 때 점진적으로 구축되고 포기됩니다.

Optimization problems

최적화 문제(optimization problems)에 대해, 보다 구체적인 알고리듬 분류가 있습니다; 그러한 문제에 대해 알고리듬은 위에서 설명한 일반 카테고리 중 하나 이상과 다음 중 하나에 속할 수 있습니다:

Linear programming

선형 등식과 부등식 제약 조건에 경계진 선형 함수에 대한 최적의 해를 검색할 때, 문제의 제약 조건은 최적의 해를 생성하는 데 직접 사용될 수 있습니다. 인기있는 심플렉스 알고리듬(simplex algorithm)과 같은 이 카테고리에서 임의의 문제를 해결할 수 있는 알고리듬이 있습니다. 선형 프로그래밍으로 해결될 수 있는 문제는 방향화된 그래프의 최대 흐름 문제(maximum flow problem)를 포함합니다. 만약 문제가 추가적으로 미지수 중 하나 이상이 정수여야 함을 요구하면, 그것은 정수 프로그래밍(integer programming)으로 분류됩니다. 선형 프로그래밍 알고리듬은 만약 그것이 정수 값에 대한 모든 제한이 피상적임, 즉, 해가 어쨌든 이들 제약 조건을 만족시킴을 입증할 수 있으면 그러한 문제를 해결할 수 있습니다. 일반적인 경우에서, 문제의 어려움에 따라 근사적 해를 찾는 특수 알고리듬 또는 하나의 알고리듬이 사용됩니다.

Dynamic programming

문제가 최적의 부분-구조(optimal substructures)—문제에 대한 최적의 해가 부분문제에 대한 최적의 해에서 구성될 수 있음을 의미—와 겹치는 부부문제(overlapping subproblems)—같은 부분문제가 많은 다른 문제 인스턴스를 해결하기 위해 사용됨을 의미—를 보일 때, 동적 프로그래밍이라고 불리는 더 빠른 접근 방식은 이미 계산되어진 해를 다시 계산하는 것을 피합니다. 예를 들어, 플로이드-워셜 알고리듬(Floyd-Warshall Algorithm), 가중된 그래프(graph)에서 꼭짓점으로부터 목표로 가장 짧은 경로는 모든 인접한 꼭짓점으로부터 목표로 가장 짧은 경로를 사용함으로써 찾을 수 있습니다. 동적 프로그래밍과 메모이제이션(memoization)이 함께 진행됩니다. 동적 프로그래밍과 분할과 정복의 주요 차이점은 하위-문제는 분할과 정복에서 다소 독립적이고, 반면에 하위-문제는 동적 프로그래밍에서 겹치는 것입니다. 동적 프로그래밍과 간단한 재귀의 차이점은 재귀 호출의 캐싱 또는 메모이제이션에 있습니다. 하위-문제가 독립적이고 반복이 없을 때, 메모이제이션은 도움이 되지 않습니다; 따라서, 동적 프로그래밍은 모든 복잡한 문제에 대한 해가 아닙니다. 메모이제이션을 사용하거나 이미 해결된 하위문제의 테이블(table)을 유지함으로써, 동적 프로그래밍은 다항식 복잡성에 대한 많은 문제의 지수적 본성을 줄입니다.

The greedy method

탐욕 알고리듬(greedy algorithm)은 부분-구조를 검사함으로써 작동한다는 점에서 동적 프로그래밍 알고리듬과 유사하며,.이 경우에서 문제가 아니라 주어진 해입니다. 그러한 알고리듬은 일부 해로 시작하여, 어떤 방법으로든 제공되거나 구성되었을 수 있고, 작은 수정을 만듦으로써 개선합니다. 일부 문제에 대해, 그것들은 최적의 해를 찾을 수 있지만 다른 경우에 대해 그것들은 지역적 최적화(local optima), 즉, 알고리듬에 의해 개선될 수는 없지만 최적이 아닌 해에서 중지합니다. 탐욕 알고리듬의 가장 인기있는 사용은 최적의 해를 찾는 것이 이 방법으로 가능한 최소 스패닝 트리를 찾는 것입니다. Huffman Tree, Kruskal, Prim, Sollin는 이 최적화 문제를 해결할 수 있는 탐욕 알고리듬입니다.

The heuristic method

최적화 문제(optimization problems)에서, 휴리스틱 알고리듬(heuristic algorithms)은 최적의 해를 찾는 것이 실용적이지 않은 경우에서 최적의 해에 가까운 해를 찾기 위해 사용될 수 있습니다. 이들 알고리듬은 진행됨에 따라 최적의 해에 점점 더 가까워짐으로써 작동합니다. 원칙적으로, 만약 무한한 시간 동안 실행되면, 그것들은 최적의 해를 찾을 수 있습니다. 그것들의 장점은 그것들이 상대적으로 짧은 시간 내에 최적의 해에 매우 가까운 해를 찾을 수 있다는 것입니다. 그러한 알고리듬은 지역적 검색(local search), tabu 검색(tabu search), 시뮬레이션된 어닐링(simulated annealing), 및 유전 알고리듬(genetic algorithms)을 포함합니다. 시뮬레이션된 어닐링과 같은 그들 중 일부는 비-결정론적 알고리듬이고, 반면에 tabu 검색과 같은 다른 것들은 결정론적입니다. 비-최적화 해의 오차에 대한 경계가 알려져 있을 때, 그 알고리듬은 근사 알고리듬(approximation algorithm)으로 더 분류됩니다.

By field of study

See also: List of algorithms

모든 각 과학의 분야는 자체의 문제를 가지고 효율적인 알고리듬이 필요합니다. 한 분야에서 관련된 문제는 종종 함께 연구됩니다. 일부 예제 클래스는 검색 알고리듬(search algorithms), 정렬 알고리듬(sorting algorithms), 병합 알고리듬(merge algorithms), 수치 알고리듬(numerical algorithms), 그래프 알고리듬(graph algorithms), 문자열 알고리듬(string algorithms), 계산 기하학적 알고리듬(computational geometric algorithms), 조합론적 알고리듬(combinatorial algorithms), 의료 알고리듬(medical algorithms), 기계 학습(machine learning), 암호화(cryptography), 데이터 압축(data compression) 알고리듬 및 파싱 기술(parsing techniques)입니다.

분야는 서로 겹치는 경향이 있고, 한 분야에서 알고리듬 발전은 다른 분야의 알고리듬 발전은 때때로 전혀 관련없는 다른 분야를 향상시킬 수 있습니다. 예를 들어, 동적 프로그래밍은 산업에서 자원 소비의 최적화를 위해 발명되었지만 현재 많은 분야에서 광범위한 문제를 해결하는 데 사용됩니다.

By complexity

See also: Complexity class and Parameterized complexity

알고리듬은 입력 크기에 비교된 완료해야 할 시간의 총양으로 분류될 수 있습니다:

• 상수 시간: 만약 알고리듬에 의해 필요한 시간이, 입력 크기에 관계없이 같으면, 예를 들어, 배열 원소에 대한 접근.
• 로그 시간: 만약 시간이 입력 크기의 로그 함수이면, 예를 들어, 이진 검색 알고리듬(binary search algorithm).
• 선형 시간: 만약 시간이 입력 크기에 비례적이면, 예를 들어, 목록의 횡단.
• 다항식 시간: 만약 시간이 입력 크기의 거듭제곱이면, 예를 들어 거품 정렬(bubble sort) 알고리듬은 이차 시간 복잡도를 가집니다.
• 지수 시간: 만약 시간이 입력 크기의 지수 함수이면, 예를 들어 무차별-대입 검색(Brute-force search).

일부 문제는 다른 복잡성의 여러 알고리듬을 가질 수 있지만, 다른 문제는 알고리듬을 가지지 않거나 알려진 효율적인 알고리듬을 가지지 않을 수 있습니다. 일부 문제에서 다른 문제로의 매핑도 있습니다. 이로 인해, 문제에 대한 가능한 최선의 알고리듬의 복잡성을 기반으로 알고리듬을 동치 클래스로 분류하는 대신 문제 자체를 분류하는 것이 더 적합한 것으로 나타났습니다.

Continuous algorithms

"계속"이라는 형용사는 "알고리듬"이라는 단어에 적용될 때 다음을 의미할 수 있습니다:

• 이 데이터가 이산 근사로 표현되더라도 연속 수량을 나타내는 데이터에서 작동하는 알고리듬입니다—그러한 알고리듬은 수치 해석학(numerical analysis)에서 연구됩니다; 또는
• 아날로그 컴퓨터(analog computer)에서 실행하는 데이터에서 연속적으로 작동하는 미분 방정식(differential equation)의 형식에서 알고리듬입니다.

Legal issues

See also: Software patent

알고리듬은, 자체에 의해, 보통 특허-가능이 아닙니다. 미국에서, 추상적 개념, 숫자, 또는 신호의 단순한 조작으로만 구성된 청구는 "프로세스"를 구성하지 않고 (USPTO 2006), 따라서 알고리듬은 특허-가능이 아닙니다 (예를 들어, Gottschalk v. Benson에서 그렇습니다). 어쨌든, 알고리듬의 실제 적용은 때때로 특허-가능입니다. 예를 들어, Diamond v. Diehr에서, 합성 고무의 경화를 돕기 위한 간단한 피드백(feedback) 알고리듬의 적용은 특허-가능으로 생각되었습니다. 소프트웨어의 특허화(patenting of software)는 논란의 여지가 많았고, Unisys의 LZW 특허(Unisys' LZW patent)와 같은 알고리듬, 특히 데이터 압축(data compression) 알고리듬과 관련된 특허가 매우 비판적입니다.

추가적으로, 일부 암호화 알고리듬은 수출 제한이 있습니다 (암호화의 수출(export of cryptography)을 참조하십시오).

History: Development of the notion of "algorithm"

Ancient Near East

알고리듬의 가장 초기 증거는 고대 메소포타미아(Mesopotamia, 현대 이라크)의 바빌로니아 수학에서 발견됩니다. 수메르 점토 태블릿은 바그다드 근처의 Shuruppa에서 발견되었고 기원전 2500년경으로 거슬러 올라가는 최초의 나눗셈 알고리듬(division algorithm)을 설명했습니다. 기원전 1800-1600년경 함무라비 왕조(Hammurabi dynasty) 동안, 바빌로니아 점토 태블릿은 공식을 계산하는 데 알고리듬을 설명했습니다. 알고리듬은 바빌로니아 천문학(Babylonian astronomy)에서도 사용되었습니다. 바빌로니아 점토 태블릿은 중요한 천문학적 사건의 시간과 장소를 계산하기 위해 알고리듬 절차를 설명하고 사용합니다.

산술을 위한 알고리듬은 기원전 1550년경 린드 수학적 파피루스(Rhind Mathematical Papyrus)로 거슬러 올라가는 고대 이집트 수학에서도 발견됩니다. 알고리듬은 나중에 고대 헬레니즘 수학(Hellenistic mathematics)에서 사용되었습니다. 두 가지 예제는 니코마코스(Nicomachus)에 의해 Introduction to Arithmetic에 설명된 에라토스테네스의 체(Sieve of Eratosthenes)와, 유클리드의 원론(Euclid's Elements, 기원전 300년경)에서 처음 설명된 유클리드 알고리듬(Euclidean algorithm)입니다.

Discrete and distinguishable symbols

탈리-표식: 고대인들은 가축 떼, 곡식 자루, 돈을 추적하기 위해 탈리를 사용했습니다: 돌이나 막대기에 긁힌 표시를 모으거나 점토에 개별 기호를 만드는 것입니다. 바빌로니아와 이집트가 표식과 기호의 사용을 통해, 결국 로마 숫자-표시(Roman numerals)와 주판(abacus)이 진화했습니다 (Dilson, p. 16–41). 탈리 표식은 튜링 기계(Turing machine) 및 포스트–튜링 기계(Post–Turing machine) 계산에 사용되는 단항 숫자-표시 시스템(unary numeral system) 산술에서 두드러지게 나타납니다.

Manipulation of symbols as "place holders" for numbers: algebra

페르시아의 수학자, 이븐 무사 알-콰리즈미(Muḥammad ibn Mūsā al-Khwārizmī)는 9세기에 Al-jabr를 저술했습니다. "algorism"과 "algorithm"이라는 용어는 al-Khwārizmī라는 이름에서 파생되었고, 반면 "algebra"라는 용어는 Al-jabr이라는 책에서 파생되었습니다. 유럽에서, "algorithm"이라는 단어는 원래 대수적 방정식을 풀기 위해 알-콰리즈미에 의해 사용되었던 규칙과 기법의 집합을 참조하기 위해 사용되었으며, 나중에 규칙이나 기법 임의의 집합을 참조하기 위해 일반화되었습니다. 이것은 결국 calculus ratiocinator (c. 1680)에 대한 라이프니츠의 개념에서 절정에 달했습니다:

그의 시대보다 150년이나 앞서, 라이프니츠는 논리의 대수학, 보통의 대수학이 숫자를 조작하는 데 규칙을 지정하는 방식으로 논리적 개념을 조작하는 데 규칙을 지정하는 대수학을 제안했습니다.

Cryptographic algorithms

암호화된 코드를 해독하기 위한 최초의 암호화(cryptographic) 알고리듬은 9세기 아랍 수학자 알-킨디(Al-Kindi)에 의해 A Manuscript On Deciphering Cryptographic Messages에서 개발되었습니다. 그는 최초의 암호-해독(codebreaking) 알고리듬, 주파수 분석(frequency analysis)에 의한 암호-분석(cryptanalysis)의 설명을 처음으로 제공했습니다.

Mechanical contrivances with discrete states

시계: Bolter는 추-구동 시계의 발명을 "[중세 유럽의] 핵심 발명품", 특히, 우리에게 기계식 시계의 똑딱거리는 소리를 제공하는 verge escapement라고 공인합니다. "정확한 자동 기계"는 즉시 13세기에 시작된 "기계식 자동 장치(automata)"로, 마침내 "계산적 기계"—19세기 중반 Charles Babbage와 Countess Ada Lovelace의 차이 엔진(difference engine)과 해석적 엔진(analytical engines)으로 이어졌습니다. Lovelace는 컴퓨터—Babbage의 해석적 엔진, 단지 계산기가 아닌 실제 튜링-완성(Turing-complete) 컴퓨터로 고려된 최초의 장치—에서 처리하기 위한 알고리듬을 처음으로 만든 것으로 공인되고, 그 결과 때때로 "역사 최초의 프로그래머"라고 불리지만, Babbage의 두 번째 장치의 완전한 구현은 그녀의 생애 후 수십 년이 지나야 실현됩니다.

논리적 기계 1870 – Stanley Jevons의 "논리적 주판" 및 "논리적 기계": 기술적 문제는 현재 Karnaugh map으로 알려진 것과 유사한 형식에서 제시될 때 부울 방정식(Boolean equations)을 줄이는 것이었습니다. Jevons (1880)는 먼저 [논리적] 조합의 어떤 부분이나 클래스도 기계적으로 골라낼 수 있도록 고안된 "핀이 달린 나무 조각의 단순한 "주판"을 설명합니다 ... 보다 최근에, 어쨌든, 시스템을 완전히 기계적인 형태로 축소하여 논리적 기계라고 부를 수 있는 전체 간접 추론 프로세스를 구현했습니다." 그의 기계는 "특정 움직일 수 있는 나무 막대"가 장착되어 있고 "발바닥에는 피아노 [등]와 같은 21개의 건반이 있습니다...". 이 기계와 함께 그는 "삼단논법(syllogism)이나 임의의 다른 간단한 논리적 논증"을 분석할 수 있었습니다.

그는 이 기계를 1870년에 왕립 학회 회원들 앞에 전시했습니다. 또 다른 논리학자 존 벤(John Venn)은, 어쨌든, 1881년 Symbolic Logic에서 이러한 노력에 황달의 눈을 돌렸습니다: "나는 때때로 논리적 기계라고 불리는 것의 관심이나 중요성에 대해 나 자신을 높게 평가하지 않습니다 ... 현재 알려졌거나 발견될 가능성이 있는 어떤 고안물도 실제로 논리적 기계라는 이름을 가질 자격이 있다고 생각하지 않습니다"; 알고리듬 특성화(Algorithm characterizations)에서 자세한 내용을 참조하십시오. 그러나 지나치지 않기 위해 그는 역시 "Jevon 교수의 주판과, 내가 이해했던, 다소 유사한 계획 ... [그리고] 다시 Jevon 교수의 논리 기계에 해당하는, 다음과 같은 고안이 설명될 수 있습니다. 나는 그것을 단지 논리적-다이어그램 기계라고 부르는 것을 선호한다... 그러나 논리적 기계에서 합리적으로 기대할 수 있는 모든 작업을 완벽하게 수행할 수 있다고 생각합니다"라고 제시했습니다.

Jacquard loom, Hollerith 천공 카드, 전신 및 전화 – 전기-기계적 릴레이: Bell과 Newell (1971)은 Jacquard loom (1801), Hollerith cards (천공 카드, 1887)의 전조, 및 "전화 교환 기술"은 최초의 컴퓨터 개발로 이어지는 나무의 뿌리였다고 나타냅니다. 19세기 중반까지 전화의 전조, 전신은 전 세계적으로 사용되었으며, 공통적인 소리 "점과 대시"로 문자를 이산적이고 구별할 수 있게 인코딩합니다. 19세기 후반에는 티커 테이프(ticker tape, 약 1870년대)가 사용되었고, 1890년 미국 인구 조사에서 Hollerith 카드가 사용되었습니다. 그 후에, 테이프에 Baudot 코드(Baudot code)를 천공 종이로 사용하는 텔레프린터(teleprinter, 약 1910년)가 등장했습니다.

전기-기계적 릴레이의 전화-교환 네트워크 (1835년 발명)는 디지털 덧셈 장치의 발명가, George Stibitz (1937)의 연구 배후에 있었습니다. 그가 벨 연구소에서 일하면서, 그는 기어를 갖는 기계식 계산기의 "부담스러운" 사용을 관찰했습니다. "그는 1937년 어느 날 저녁 자신의 아이디어를 테스트하기 위해 집에 갔습니다... 땜질이 끝났을 때, Stibitz는 이진 덧셈 장치를 만들었습니다."

수학자 Martin Davis는 전기-기계적 릴레이 (두 개의 "이진 상태" 열림 및 닫힘을 가짐)의 특별한 중요성을 관찰합니다:

1930년대 시작하여 전기적 릴레이를 사용하는 전기-기계식 계산기가 개발되면서 Babbage가 구상했던 범위의 기계가 만들어졌습니다."

Mathematics during the 19th century up to the mid-20th century

기호 및 규칙: 빠르게 연속적으로, 조지 부울(George Boole, 1847, 1854), 고틀롭 프레게(Gottlob Frege, 1879) 및 주세페 페아노(Giuseppe Peano, 1888–1889)의 수학은 산술을 규칙에 의해 조작되는 기호의 순서열로 축소했습니다. 페아노의 The principles of arithmetic, presented by a new method (1888)는 "기호적 언어(symbolic language)에서 수학을 공리화하려는 최초의 시도"였습니다.

그러나 Heijenoort는 프레게 (1879)에게 다음과 같은 찬사를 보냅니다: 프레게의 연구는 "아마도 논리학에서 쓰인 가장 중요한 단일 연구일 것입니다. ... 여기서 우리는 "'형식 언어', 즉 lingua characterica, "순수한 사고를 위해", 즉 수사학적 장식이 없는 ... 명확한 규칙에 따라 조작되는 특정 기호로 구성되는 특수 기호로 작성된 언어를 봅니다." 프레게의 연구는 Alfred North Whitehead와 Bertrand Russell에 의해 그들의 Principia Mathematica (1910–1913)에서 더욱 단순화되고 증폭되었습니다.

역설: 그와 동시에 많은 불안한 역설, 특히 Burali-Forti paradox (1897), Russell paradox (1902–03), 및 Richard Paradox이 문헌에 등장했습니다. 결과적인 고려 사항은 재귀(recursion) 규칙을 숫자로 완전히 축소한 Kurt Gödel의 논문 (1931)으로 이어졌습니다—그는 구체적으로 거짓말쟁이의 역설을 인용합니다.

효과적인 계산-가능성: 1928년 힐베르트에 의해 정확하게 정의된 Entscheidungsproblem를 해결하기 위한 노력의 일환으로, 수학자들은 먼저 "효과적인 방법" 또는 "효과적인 계산" 또는 "효과적인 계산-가능성" (즉, 성공할 계산)이 의미하는 바를 정의하기 시작했습니다. 빠르게 연속적으로 다음이 나타났습니다: Alonzo Church, Stephen Kleene, 및 J.B. Rosser의 λ-calculus(λ-계산법)은 Jacques Herbrand (1934년 Gödel의 Princeton 강의 참조)와 후속 단순화 클리네의 제안에 따라 작용하는 괴델의 연구에서 "일반적인 재귀"의 정교하게 연마된 정의가 나타났습니다. Entscheidungsproblem는 풀 수 없다는 처치의 증명, 효과적인 계산-가능성의 Emil Post의 정의는 일련의 방을 통해 왼쪽 또는 오른쪽으로 이동하라는 지침 목록을 아무 생각 없이 따르고 종이에 표시하거나 지우거나 종이를 관찰하고 다음 지침에 대해 예-아니오 결정을 내리는 작업자로 정의합니다. Entscheidungsproblem이 풀 수 없다는 앨런 튜링의 증명은 그의 "a- [automatic-] machine"의 사용에 의한 것입니다—사실상 Post의 "형식화"와 J. Barkley Rosser의 "기계" 측면에서 "효과적인 방법"에 대한 정의와 거의 동일합니다. Kleene이 "Thesis I"이라고 부르는 "처치 논문"의 전조 제안과 몇 년 후 Kleene은 자신의 논문 이름을 "Church's Thesis"로 바꾸고 "Turing's Thesis"를 제안했습니다.

Emil Post (1936) and Alan Turing (1936–37, 1939)

Emil Post (1936)는 "컴퓨터" (인간)의 동작을 다음과 같이 설명했습니다:

"...두 가지 개념이 관련되어 있습니다: 즉, 문제에서 답변으로 이어지는 작업이 수행되는 기호 공간(symbol space)의 개념과 고정된 변경할 수 없는 명령의 집합(set of directions)의 개념입니다.

그의 상징 공간은 다음일 것입니다:

"공간 또는 상자의 양방향 무한 순서열... 문제 해결사 또는 작업자는, 그 안에 있을 수 있는 것과, 한 번에 하나의 상자 안에 있고 작동할 수 있는, 이 기호 공간에서 이동하고 작업합니다....하나의 상자는 두 가지 가능한 조건, 즉 빈 것 또는 표시-없는 것과 그 안에 하나의 표시가 있는 것, 말하자면 세로 획을 가지는 것을 인정하는 것입니다.

"하나의 상자를 선택되고 시작하는 점이라고 합니다. ...유한한 수의 상자 [즉, INPUT]가 획으로 표시되어 특정 문제가 기호적 형식으로 제공됩니다. 마찬가지로, 답 [즉, , OUTPUT]은 그러한 표시된 상자의 구성에 의해 기호적인 형식으로 주어지게 되며...

"일반적인 문제에 적용할 수 있는 명령의 집합은 각 특정 문제에 적용할 때 결정론적 과정을 설정합니다. 이 과정은 유형 (C) [즉, STOP]의 명령에 대해서만 종료됩니다." 포스트-튜링 기계(Post–Turing machine)에서 자세히 보십시오.

Alan Turing's statue at Bletchley Park

Alan Turing의 연구는 Stibitz (1937)의 연구보다 이전에 행해졌습니다; Stibitz가 Turing의 연구를 알고 있었는지 여부는 알 수 없습니다. Turing의 전기-작가는 Turing이 타자기와 유사한 모델을 사용한 것이 젊은 시절의 관심에서 비롯되었다고 믿었습니다: "Alan은 어렸을 때 타자기를 발명하는 꿈을 꾸었습니다; Turing 부인은 타자기를 가지고 있었고, 그는 타자기를 '기계적'이라고 부르는 것이 무엇을 의미하는지 스스로에게 질문하는 것으로 시작했을 수 있었습니다." 모스 부호, 전신, 티커 테이프 기계, 전신-타자기의 유행을 감안할 때 모든 것이 튜링이 젊었을 때 영향을 받았을 가능성이 큽니다.

Post가 그랬던 것처럼 튜링은 간단한 기본 동작과 "정신의 상태"로 요약되는 인간 컴퓨터에 대한 분석으로 시작합니다. 그러나 그는 한 걸음 더 나아가 숫자 계산의 모델로 기계를 만듭니다—그의 계산 모델은 이제 Turing machine라고 불립니다.

"연산은 통상적으로 종이에 특정 기호를 쓺으로써 수행됩니다. 우리는 이 종이가 어린이의 산수 책처럼 사각형으로 나누어져 있다고 가정할 수 있습니다...나는 그런-다음 계산은 일-차원 종이, 즉, 사각형으로 분할된 테이프에서 수행된다고 가정합니다. 나는 역시 인쇄될 수 있는 기호의 숫자가 유한하다고 가정하겠습니다...

"언제든지 컴퓨터의 행동은 그가 관찰하고 있는 기호와 그 순간의 "정신의 상태"에 의해 결정됩니다. 우리는 컴퓨터가 한 순간에 관찰할 수 있는 기호나 사각형의 숫자에 경계 B가 있다고 가정할 수 있습니다. 만약 그가 더 관찰하고 싶다면, 그는 연속적인 관찰을 해야 합니다. 우리는 역시 고려해야 할 정신의 상태의 숫자가 유한하다고 가정할 것입니다...

"컴퓨터가 수행하는 작업을 '단순 작업'으로 분리한다고 상상해 보십시오. 이는 너무 기초적이어서 더 세분화하는 것을 상상하기 쉽지 않습니다."

튜링의 감소는 다음을 생성합니다:

"따라서 간단한 작업에는 다음이 포함되어야 합니다:

"(a) 관찰된 사각형 중 하나에 대한 기호의 변경

"(b) 이전에 관찰된 사각형 중 하나의 L 사각형 내에서 또 다른 사각형으로 관찰된 사각형 중 하나의 변경.

"이들 변경 중 일부는 필연적으로 정신의 상태의 변화를 불러일으킬 수 있습니다. 따라서 가장 일반적인 단일 작업은 다음 중 하나로 취해져야 합니다:

"(A) 가능한 정신의 상태 변경과 함께 가능한 기호의 변경 (a).

"(B) 정신의 상태의 가능한 변경과 함께 관찰된 사각형의 가능한 변경 (b)"

"우리는 이제 이 컴퓨터의 작업을 수행할 기계를 만들 수 있습니다."

몇 년 후 튜링은 다음과 같은 강력한 표현으로 자신의 분석 (논문, 정의)을 확장했습니다:

"함수는 만약 그것의 값이 어떤 순수하게 기계적 과정으로 찾을 수 있으면 "효과적으로 계산-가능"이라고 말합니다. 비록 이 아이디어를 직관적으로 파악하는 것은 상당히 쉽지만, 그럼에도 불구하고 보다 명확하고 수학적으로 표현할 수 있는 정의를 갖는 것이 바람직합니다 ... [그는 Gödel, Herbrand, Kleene, Church, Turing 및 Post와 관련하여 위에 제시된 것과 거의 같은 정의의 역사를 논의합니다] ... 우리는 기계에 의해 수행될 수 있는 순수하게 기계적 과정에 의해 이해하면서 이 명제를 문자 그대로 받아들일 수 있습니다. 이들 기계의 구조에 대해 특정한 정규 형식으로 수학적 설명을 제공하는 것이 가능합니다. 이들 아이디어의 발전은 계산-가능한 함수에 대한 저자의 정의와 효과적인 계산-가능성을 갖는 계산-가능성 †의 식별로 이어집니다...

"† 우리는 "계산-가능한 함수"라는 표현을 기계에 의해 계산할 수 있는 함수를 의미하기 위해 사용해야 하고, 우리는 "효과적으로 계산-가능"을 이들 정의 중 어느 것과도 특별히 동일성 없이 직관적인 아이디어를 참조하도록 만듭니다."

J. B. Rosser (1939) and S. C. Kleene (1943)

J. Barkley Rosser는 "효과적인 [수학적] 방법"을 다음과 같은 방식으로 정의했습니다 (이탤릭체 추가):

"'효과적인 방법'은 여기에서 각 단계가 정확하게 결정되고 한정된 수의 단계에서 답을 확실히 생성하는 방법이라는 다소 특별한 의미로 사용됩니다. 이 특별한 의미와 함께, 세 가지 다른 정확한 정의가 현재까지 주어져 왔습니다. [그의 각주 #5; 바로 아래 논의 참조]. 이것들 중 가장 간단한 것은 만약 우리가 질문을 삽입하고 (나중에) 답을 읽는 것 외에 사람의 개입 없이 임의의 문제의 집합을 해결할 기계를 만들 수 있으면 본질적으로 특정 문제의 집합을 해결하는 데 효과적인 방법이 존재한다고 말합니다. 세 가지 정의는 모두 동등하므로, 어느 것을 사용하는지는 중요하지 않습니다. 더욱이, 세 가지 모두 동등하다는 사실은 어떤 것도 옳다는 매우 강력한 논증입니다." (Rosser 1939:225–226)

Rosser의 각주 5번 참조 연구 (1) Church와 Kleene의 연구와 λ-정의가능성의 그들의 정의, 특히 Church가 그의 An Unsolvable Problem of Elementary Number Theory (1936)에서 이를 사용한 것을 참조합니다; (2) Herbrand와 Gödel 및 그들의 재귀 사용, 특히 그의 유명한 논문 On Formally Undecidable Propositions of Principia Mathematica and Related Systems I (1931)에서 Gödel의 사용; 및 (3) Post(1936)와 Turing(1936–37)의 계산 메커니즘 모델.

Stephen C. Kleene은 Church–Turing thesis으로 알려진 그의 현재 유명한 "Thesis I"로 정의했습니다. 그러나 그는 다음과 같은 맥락에서 이 연구를 수행했습니다 (원본에서 볼드체):

"12. 알고리듬 이론... 완전한 알고리듬 이론을 설정할 때, 우리가 하는 일은 독립 변수의 각 값 집합에 대해 수행할 수 있는 절차를 설명하는 것이며, 어떤 절차가 필연적으로 종료되고 결과에서 "술어 값이 참입니까?"라는 질문에 "예" 또는 "아니오"라는 명확한 대답을 읽을 수 있는 방식으로 종료됩니다" (Kleene 1943:273)

History after 1950

"알고리듬"의 정의를 더욱 구체화하기 위한 많은 노력이 있었고, 특히 수학의 토대(foundations of mathematics, 특히 처치-튜링 논문)와 정신의 철학(philosophy of mind, 특히 인공 지능에 대해 논쟁)을 둘러싼 문제로 인해 활동이 계속되고 있습니다. 자세한 내용에 대해 알고리듬 특성화(Algorithm characterizations)를 참조하십시오.

See also

• Abstract machine
• ALGOL
• Algorithm engineering
• Algorithm characterizations
• Algorithmic bias
• Algorithmic composition
• Algorithmic entities
• Algorithmic synthesis
• Algorithmic technique
• Algorithmic topology
• Garbage in, garbage out
• Introduction to Algorithms (textbook)
• Government by algorithm
• List of algorithms
• List of algorithm general topics
• List of important publications in theoretical computer science – Algorithms
• Regulation of algorithms
• Theory of computation
  • Computability theory
  • Computational complexity theory
• Computational mathematics

External links

• "Algorithm", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Algorithms at Curlie
• Weisstein, Eric W. "Algorithm". MathWorld.
• Dictionary of Algorithms and Data Structures – National Institute of Standards and Technology

Algorithm repositories

• The Stony Brook Algorithm Repository – State University of New York at Stony Brook
• Collected Algorithms of the ACM – Association for Computing Machinery
• The Stanford GraphBase – Stanford University