알고리즘.

Algorithm
"알고리즘"은 여기서 리디렉션된다. 컴퓨터 과학의 하위 필드에 대해서는 알고리즘 분석을 참조하십시오.
다른 용도는 알고리즘(동음이의)을 참조하십시오.
A와 B라는 위치에서 두 숫자 a와 b 중 가장 큰 공통점(예: c.d.)을 계산하기 위한 알고리즘(유클리드 알고리즘)의 흐름도. 알고리즘은 다음 두 루프의 연속적인 감산에 의해 진행된다. 만약 시험 B ≥ A가 "yes" 또는 "true"를 산출한다면(더 정확히 말하면, 위치 B의 숫자b가 위치 A의 숫자a보다 크거나 같음) 알고리즘은 B - B - A를 지정한다(숫자 b - a가 이전 b를 대체한다는 의미). 마찬가지로 IF A > B, A ← A - B. 이 과정은 (B의 내용물이) 0일 때 종료되며, A.에서 G.c.d.를 산출한다(Scott 2009:13에서 파생된 Algorithm; Tausworthe 1977에서 기호와 그리기 스타일).
최초의 컴퓨터 알고리즘인 "노트 G"에서 나온 에이다 러브레이스의 도표

수학 및 컴퓨터 과학에서 알고리즘(/ˈllrrəəmm/ About this sound(듣기))은 잘 정의된 명령의 유한한 시퀀스로, 일반적으로 특정 문제의 클래스를 풀거나 계산을 수행하는 데 사용된다.[1] 알고리즘은 계산, 데이터 처리, 자동화된 추론, 자동화된 의사결정 및 기타 작업을 수행하기 위한 사양으로 사용된다. 이와는 대조적으로 휴리스틱은 특히 정확하거나 최적의 결과가 잘 정의되지 않은 문제 영역에서는 완전하게 명시되지 않거나 정확하거나 최적의 결과를 보장하지 않을 수 있는 문제 해결 접근법이다.[2]

효과적인 방법으로서 알고리즘은 한정된 공간과 시간의 양 내에서,[3] 그리고 함수 계산을 위해 잘 정의된 공식 언어로[4] 표현될 수 있다.[5] 초기 상태와 초기 입력(아마도 비어 있을 것이다)[6]에서 시작하여, 명령어는 실행될 때, 잘 정의된 한정된 수의[7] 연속적인 상태를 통해 진행되어 결국 "출력"[8]을 생성하고 최종 종료 상태에서 종료하는 계산을 기술한다. 한 상태에서 다음 상태로의 전환이 반드시 결정론적인 것은 아니다. 임의화된 알고리즘으로 알려진 일부 알고리즘은 무작위 입력을 통합한다.[9]

역사

알고리즘의 개념은 고대부터 존재해왔다. 분할 알고리즘과 같은 산술 알고리즘은 고대 바빌로니아 수학자 c. 2500 BC와 이집트 수학자 c. 1550 BC에 의해 사용되었다.[10] 이후 그리스 수학자들은 에라토스테네스의 체에 있는 240 BC의 알고리즘을 소수점 찾기에 사용했고, 유클리드 알고리즘은 두 숫자의 최대 공통점 찾기에 사용하였다.[11] 9세기 알 킨디 같은 아랍 수학자들은 주파수 분석을 바탕으로 암호 알고리즘을 코드 해독에 사용했다.[12]

알고리즘이라는 단어는 9세기 페르시아 수학자 무함마드 이븐 무사 알-크화리츠므의 이름에서 유래되었는데, 그의 nisba(Khwarazm 출신이라고 확인)는 알고리트미(Algoritmi, 페르시아어 اخوار c c c c c.780–850)로 라틴어화되었다.[13][14]

무함마드 이븐 무샤 알-크화리츠므는 바그다드 지혜의 집의 수학자, 천문학자, 지리학자, 학자로, 그의 이름은 '크화라젬의 고향'이라는 뜻으로 이란 대이란에 속하고 현재 우즈베키스탄에 있는 지역이다.[15][16] 약 825년경, 알-크와리즈미는 힌두-아랍어 수체계에 대한 아랍어 논문을 썼는데, 12세기 동안 라틴어로 번역되었다. 원고는 Dixit Algorizmi(Thus spake Alkharizmi)'라는 문구로 시작되는데, 여기서 "Algorizmi"는 번역자의 알-Kharizmi의 이름 라틴어였다.[17] 알-크와리즈미는 중세 말기에 유럽에서 가장 널리 읽힌 수학자로, 주로 그의 또 다른 저서인 대수학을 통해서였다.[18] 중세 말기의 라틴어, 알고리즘, 영어의 '알고리즘', 그의 이름의 부패는 단순히 '십진수제'를 의미했다.[19] 15세기에는 그리스어 ἀρμμό(arithmos)의 영향으로 '숫자'(cf)가 되었다. '산술'), 라틴어 '알고리즘'은 알고리즘으로 바뀌었고, 이에 상응하는 영어 용어 '알고리즘'은 17세기에 처음으로 증명되었다; 현대적 감각은 19세기에 도입되었다.[20]

영어에서는 약 1230년에 처음 사용되었고 그 후 1391년에 초서에 의해 사용되었다. 영어는 프랑스어 용어를 채택했지만, 19세기 후반이 되어서야 '알고리즘'이 현대 영어에서 가지는 의미를 그대로 받아들였다.[21]

이 단어의 또 다른 초기 용어는 1240년 알렉산드르 드 빌레디외가 작곡한 카르멘 드 알고리스모라는 제목의 매뉴얼에 수록된 것이다. 시작은 다음과 같다.

헥 알고리스무스는 퀘아 / 탈리버스 인디오룸 과일 비스 퀸케 조형물에서 드시쿠르를 칭찬한다.

이는 다음과 같은 의미로 해석된다.

알고리즘은 현재 우리가 그 인도의 수치를 사용하는 기술인데, 그 숫자는 2 곱하기 5이다.

이 시는 수백 줄의 길이로, 새로운 스타일의 인도 주사위(탈리 인도르름), 즉 힌두교의 숫자로 계산하는 기술을 요약하고 있다.[22]

현대 알고리즘 개념의 부분적인 공식화는 1928년 데이비드 힐버트가 제기한 엔치등스프로블럼(결정문제)을 해결하려는 시도로 시작되었다. 이후 공식화는 "유효한 계산가능성"[23] 또는 "유효한 방법"[24]을 정의하기 위한 시도로 틀에 박혔다. 공식화에는 1930, 1934, 1935년의 괴델-헤르브란트-클레인 재귀 기능, 1936년의 알론조 교회의 람다 미적분, 1936년의 에밀 포스트의 공식화 1 그리고 1936-37년과 1939년의 앨런 튜링 기계가 포함되었다.

비공식적 정의

"알고리즘"의 정의에 대한 다양한 관점에 대한 자세한 설명은 알고리즘 특성화를 참조하십시오.

비공식적인 정의는 모든 컴퓨터 프로그램(숫자 계산을 수행하지 않는 프로그램 포함)과 (예를 들어) 규정된 관료 절차 또는[26] 요리책 레시피를 포함하는 "운영 순서를 정확하게 정의하는 일련의 규칙"[25][need quotation to verify]이 될 수 있다.[27]

일반적으로 프로그램은 무한 루프(무한 루프)가 때로는 바람직하다고 증명될 수 있지만 결국[28] 중단되는 경우 알고리즘일 뿐이다.

알고리즘의 프로토타입 예는 유클리드 알고리즘으로, 두 정수의 최대 공통분위를 결정하는 데 사용된다. 예시(다른 것이 있음)는 위의 흐름도로 설명되며, 이후 섹션의 예로서 설명된다.

Boolos, Jeffrey & 1974년, 1999년 는 다음 인용구에서 "알고리즘"이라는 단어의 비공식적인 의미를 제공한다.

어떤 인간도 충분히, 또는 충분히 길거나, 충분히 작을 수 없다. 분자, 원자, 전자에 차례로 이름을 적음으로써 열거할 수 없을 정도로 무한한 집합의 모든 구성원을 열거하기 위해 분자, 원자, 전자에 제한 없이 쓸 수 있다. 그러나 인간은 열거할 수 없을 정도로 무한한 집합의 경우에 똑같이 유용한 일을 할 수 있다. 임의 유한 n에 대해 집합의 n번째 멤버를 결정하기 위한 명시적 지침을 제공할 수 있다. 그러한 지침은 컴퓨터 기계가 따를 수 있는 형태 또는 기호에 대한 매우 기본적인 조작만 수행할 수 있는 인간에 의해 상당히 명확하게 제공되어야 한다.[29]

"무한한 집합"은 정수와 일대일 대응으로 요소를 넣을 수 있는 집합이다. 따라서 Boolos와 Jeffrey는 알고리즘이 이론적으로 임의로 클 수 있는 임의의 "입력" 정수나 정수의 정수를 "생성"하는 과정에 대한 지침을 내포하고 있다고 말하고 있다. 예를 들어 알고리즘은 y = m + n(즉 출력 y를 생성하는 임의의 두 "입력 변수" m과 n)과 같은 대수 방정식이 될 수 있지만, 개념을 정의하려는 다양한 저자의 시도는 단어가 이것보다 훨씬 더 많이 함축되어 있음을 나타낸다(추가 예시 등).

정확한 지침은, 디코딩을 찾기 위해"컴퓨터"(기계나 인간, 필요한 내부적으로 포함된 정보와 역량을 갖춘)[32]의"움직임"을 지정하는 빠르고 효율적이고" 좋은"[31일]절차에 대한 다음 임의의 입력 integers/symbols m와 엔, 기호+및=조사 분류합니다(언어"컴퓨터"에 의해 이해가에서)[30].…과``effe"ctripty"[33]는 지정된 장소에서 지정된 형식으로 출력-표시 y를 생성한다.[34]

알고리즘의 개념은 결정성의 개념을 정의하는 데에도 사용된다. 결정성의 개념은 어떻게 공식적인 시스템이 작은 공리와 규칙의 집합에서 시작하게 되는지 설명하는 데 중심적인 개념이다. 논리학에서는 알고리즘이 완료해야 하는 시간은 통상적인 물리적 차원과 명백히 관련되지 않기 때문에 측정할 수 없다. 이러한 불확실성으로부터 진행 중인 작업의 특성을 나타내는 것은 구체적(어떤 의미에서는)과 추상적인 용어 사용에 모두 적합한 알고리즘의 정의를 사용할 수 없게 된다.

대부분의 알고리즘은 컴퓨터 프로그램으로 구현되도록 되어 있다. 그러나 알고리즘은 생물학적 신경망(예: 인간의 두뇌가 산수나 먹이를 찾는 곤충을 구현하는 것), 전기회로나 기계장치에서와 같은 다른 방법으로도 구현된다.

공식화

알고리즘은 컴퓨터가 데이터를 처리하는 방식에 필수적이다. 많은 컴퓨터 프로그램에는 직원들의 급여를 계산하거나 학생들의 성적표를 인쇄하는 것과 같은 특정 작업을 수행하기 위해 컴퓨터가 수행해야 하는 특정 지시사항을 특정 순서대로 상세히 기술하는 알고리즘이 포함되어 있다. 따라서 알고리즘은 튜링 완료 시스템에 의해 시뮬레이션될 수 있는 모든 작동 시퀀스로 간주될 수 있다. 이 논문을 주장하는 작가로는 민스키(1967), 새비지(1987), 구레비치(2000) 등이 있다.

민스키: "하지만 우리는 튜링과 함께 자연적으로 "자연적으로" 효과적인 절차라고 불릴 수 있는 어떤 절차도 실제로 (단순한) 기계에 의해 실현될 수 있다는 것을 유지할 것이다. 비록 이것이 극단적으로 보일지라도, 그것에 유리한 주장은 반박하기 어렵다"고 말했다.[35] 구레비치: "… 그의 논문에 찬성하는 튜링의 비공식적인 주장은 더 강력한 논제를 정당화한다: 모든 알고리즘은 새비지[1987]에 따르면 튜링 기계에 의해 시뮬레이션될 수 있다. 알고리즘은 튜링 기계에 의해 정의된 계산 과정이다."[36]

튜링 머신은 종료되지 않는 연산 프로세스를 정의할 수 있다. 일반적으로 알고리즘의 비공식적인 정의는 알고리즘이 항상 종료되어야 한다고 요구한다. 이 요건은 정지 문제로 알려진 계산가능성 이론의 주요한 정리 때문에 일반적인 경우에서 정식 절차가 불가능한지 여부를 결정하는 과제를 렌더링한다.

일반적으로 알고리즘이 정보 처리와 연관되어 있을 때, 데이터는 입력 소스에서 읽을 수 있고 출력 장치에 기록되어 추가 처리를 위해 저장될 수 있다. 저장된 데이터는 알고리즘을 수행하는 기업의 내부 상태의 일부로 간주된다. 실제로 상태는 하나 이상의 데이터 구조에 저장된다.

이러한 계산 프로세스의 일부에 대해서는 알고리즘을 엄격하게 정의해야 한다. 알고리즘이 발생할 수 있는 모든 가능한 상황에 적용되는 방식으로 명시해야 한다. 이는 모든 조건부 단계를 사례별로 체계적으로 처리해야 한다는 것을 의미한다. 각 사례에 대한 기준은 명확해야 한다(그리고 계산 가능해야 한다).

알고리즘은 정확한 단계의 정확한 목록이기 때문에 계산 순서는 항상 알고리즘의 기능에 중요하다. 지시사항은 일반적으로 명시적으로 나열되는 것으로 가정하며, "위에서 "아래로" 시작하는 것으로 설명된다. 즉, 통제의 흐름에 의해 보다 공식적으로 기술되는 개념이다.

지금까지 알고리즘의 공식화에 관한 논의는 명령적 프로그래밍의 전제를 상정해 왔다. 이것은 가장 일반적인 개념이다. 즉, 작업을 별개의 "기계적"의 의미로 설명하려고 시도하는 개념이다. 이러한 정형화된 알고리즘의 개념에는 변수의 값을 설정하는 할당 작업이 유일하다. 스크래치패드로서의 「기억」의 직감에서 유래한다. 그러한 과제의 예는 아래에서 찾을 수 있다.

알고리즘을 구성하는 요소에 대한 몇 가지 대체 개념은 기능 프로그래밍 및 로직 프로그래밍을 참조하십시오.

알고리즘 표현

알고리즘은 자연어, 유사코드, 플로우차트, 드래콘차트, 프로그래밍 언어 또는 제어표(통역사에 의해 처리됨)를 포함한 다양한 종류의 표기법으로 표현할 수 있다. 알고리즘의 자연어 표현은 장황하고 모호한 경향이 있으며, 복잡하거나 기술적인 알고리즘에는 거의 사용되지 않는다. 유사코드, 플로우차트, 드래콘차트, 제어표는 자연어를 바탕으로 문장에서 공통적으로 나타나는 많은 모호성을 피하는 알고리즘을 표현하는 구조적인 방법이다. 프로그래밍 언어는 주로 컴퓨터에 의해 실행될 수 있는 형태로 알고리즘을 표현하는 것을 목적으로 하지만, 알고리즘을 정의하거나 문서화하는 방법으로도 자주 사용된다.

다양한 표현이 가능하며, 주어진 튜링 머신 프로그램을 기계 테이블의 시퀀스(자세한 내용은 유한 상태 기계, 상태 전환 테이블 및 제어 테이블 참조), 플로우차트 및 드래콘차트(자세한 내용은 상태 다이어그램 참조), 또는 "세트"라고 하는 기본적인 기계 코드 또는 조립 코드의 형태로 표현할 수 있다. 4배" (자세한 내용은 튜링 기계 참조).

알고리즘 표시는 다음과 같이 허용되는 튜링 기계 설명의 세 가지 수준으로 분류할 수 있다.[37]

1 고차 설명
"…실행 세부사항을 무시한 채 알고리즘을 설명해야 한다. 이 정도 수준에서는 기계가 테이프나 헤드를 어떻게 관리하는지 언급할 필요가 없다고 말했다.
2 구현 설명
"…투어링 기계가 머리를 사용하는 방식과 테이프에 데이터를 저장하는 방식을 정의하는 데 사용되는 프로스. 이 정도 수준에서는 상태나 전환 기능에 대한 세부 사항은 밝히지 않는다."
3 형식적 설명
가장 상세하고 "가장 낮은 수준"은 튜링 기계의 "상태표"를 제공한다.

세 가지 레벨 모두에 설명된 간단한 알고리즘 "Add m+n"의 예는 알고리즘#예제를 참조하십시오.

디자인

참고 항목: 알고리즘 § 설계 패러다임별

알고리즘 설계란 문제해결 및 공학적 알고리즘을 위한 방법이나 수학적 과정을 말한다. 알고리즘의 설계는 동적 프로그래밍과 분할-컨커밍과 같은 운영 연구의 많은 솔루션 이론의 일부다. 알고리즘 설계 및 구현 기법을 알고리즘 설계 패턴이라고도 하며,[38] 템플릿 방법 패턴과 장식자 패턴을 예로 들 수 있다.

알고리즘 설계의 가장 중요한 측면 중 하나는 자원(런타임, 메모리 사용) 효율성이다. 빅 O 표기법은 입력 크기가 증가함에 따라 알고리즘의 런타임 증가를 설명하는데 사용된다.

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

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

컴퓨터 알고리즘

7400 칩에 전자적으로 구현된 논리적 NAND 알고리즘
표준 Böhm-Jacopini 구조의 플로우차트 예: SEQUENCE(페이지 아래로 직사각형), WID-DO 및 IF-THEN-ELSE. 3개의 구조는 원시 조건부 GOTO로 되어 있다.IF test THEN GOTO step xxx, 다이아몬드로 표시), 무조건적인 GOTO(직각), 다양한 할당 연산자(직각), HALT(직각)이다. 이러한 구조를 할당 블록 내부에 내포하면 복잡한 다이어그램(cf)이 생성된다. Tausworthe 1977:100, 114).

컴퓨터 시스템에서 알고리즘은 기본적으로 소프트웨어 개발자가 소프트웨어로 작성한 로직의 한 예로서, 의도된 "대상" 컴퓨터가 주어진 (아마도 null) 입력으로부터 출력을 생성하는데 효과적이다. 구형 하드웨어에서도 실행되는 최적의 알고리즘은 동일한 목적을 위한 비최적(고시간 복잡성) 알고리즘보다 더 빠른 결과를 낼 수 있으며, 이는 컴퓨터 하드웨어와 같은 알고리즘이 기술로 간주되는 이유다.

"Elegant" (콤팩트) 프로그램, "좋은" (패스트) 프로그램: "단순하고 우아함"이라는 개념은 크누스에서 비공식적으로 나타나며 정확히 Chaitin에서 나타난다.

크누스: " … 우리는 느슨하게 정의되는 미적 감각의 좋은 알고리즘을 원한다. 한 가지 기준은 알고리즘을 수행하는 데 걸리는 시간이다. 다른 기준으로는 알고리즘의 컴퓨터 적응성, 단순성, 우아성 등이 있다.[39]
Chaitin: "… 프로그램은 '우아한' 프로그램인데, 내 말은, 프로그램은 그것이 하는 결과를 생산할 수 있는 가장 작은 프로그램이라는 뜻이야."[40]

Chaitin은 "프로그램이 '독자적'이라는 것을 증명할 수 없다는 것을 보여줄 것이다"라고 그의 정의를 미리 내세운다. 그런 증거가 Halting 문제를 해결할 것이다.

알고리즘 대 알고리즘으로 계산할 수 있는 함수: 주어진 기능에는 여러 알고리즘이 존재할 수 있다. 프로그래머가 사용할 수 있는 사용 가능한 명령어 세트를 확장하지 않더라도 이것은 사실이다. 로저스는 "그것은... 알고리즘의 개념, 즉 절차와 알고리즘에 의해 계산 가능한 함수의 개념, 즉 절차에 의해 산출되는 매핑을 구별하는 데 중요하다. 동일한 기능에는 여러 가지 다른 알고리즘이 있을 수 있다."[41]

불행히도 선함(속도)과 우아함(비교) 사이에 트레이드오프가 있을 수 있다. 우아한 프로그램은 한 단계 덜 우아함보다 더 많은 단계를 거쳐 연산을 완료할 수 있다. 유클리드 알고리즘을 사용하는 예는 아래와 같다.

컴퓨터(및 컴퓨터), 계산 모델: 컴퓨터(또는 인간 "컴퓨터")[42]는 제한된 유형의 기계로, 맹목적으로 그 지시를 따르는 "분리 결정론적 기계 장치"[43]이다.[44] 멜작과 람벡의 원시 모델은[45] 이 개념을 (i) 이산, 구별 가능한 위치, (ii) 이산, 구별할 수 없는 카운터[46] (iii) 에이전트, (iv) 에이전트의 능력에 비례하여 효과적인 명령의 목록 등 네 가지 요소로 축소시켰다.[47]

민스키는 그의 "계산성에 대한 매우 간단한 기초"에서 람베크의 "아바쿠스" 모델의 보다 적절한 변형을 묘사하고 있다.[48] 민스키의 기계는 조건부 IF-DEN GOTO나 무조건 GOTO가 프로그램 흐름을 순서에서 벗어나지 않는 한 5가지(또는 6가지, 계산 방법에 따라) 지시를 통해 순차적으로 진행한다. STORT 외에 민스키의 기계는 ZERO(예: 위치의 내용 0: L ← 0으로 대체), SEACHER (예: L ← L+1) 및 DEVENT (예: L ← L - 1)의 세 가지 할당(교체, 대체)[49] 작업을 포함한다.[50] 프로그래머가 그러한 제한된 명령 집합으로 "코드"를 작성해야 하는 경우는 드물다. 그러나 민스키는 그의 기계가 조건부 GOTO, 무조건 GOTO, 할당/교체/대체, STOR의 네 가지 일반적인 유형의 명령만으로 튜링 완료되었음을 (멜작과 람벡처럼) 보여준다. 그러나 튜링-완전성에는 몇 가지 다른 할당 지침(예: 민스키 기계에 대한 DEWNT, Increment 및 ZERO/CLEAR/EMENTY)도 필요하다. 정확한 사양은 설계자에게 다소 달려 있다. 무조건적인 GOTO는 편리하다. 전용 위치를 0으로 초기화하여 구성할 수 있다(예: "Z ← 0 "). 그 이후에는 명령 IF Z=0 THE GOTO xxx는 무조건이다.

알고리즘 시뮬레이션: 컴퓨터(컴퓨터) 언어: 크누스는 독자들에게 "알고리즘을 배우는 가장 좋은 방법은 그것을 시도하는 것이다. 즉시 펜과 종이를 가지고 예를 통해 작업하는 것"이라고 충고한다.[51] 하지만 실제의 시뮬레이션이나 실행은 어떨까? 프로그래머는 시뮬레이터/컴퓨터/컴퓨터가 효과적으로 실행할 수 있는 언어로 알고리즘을 번역해야 한다. 스톤은 이를 예로 들 수 있다: 이차 방정식의 뿌리를 계산할 때 계산자는 제곱근을 취하는 방법을 알아야 한다. 그렇지 않으면 알고리즘이 유효하려면 제곱근을 추출하기 위한 규칙 집합을 제공해야 한다.[52]

이는 프로그래머가 대상 컴퓨팅 에이전트(컴퓨터/컴퓨터)에 비해 효과적인 "언어"를 알아야 한다는 것을 의미한다.

그러나 시뮬레이션을 위해 어떤 모델을 사용해야 하는가? Van Emde Boas는 "우리가 복잡한 이론을 콘크리트 기계 대신에 추상적인 것에 기초하더라도, 모델의 선택에 대한 재정적인 중요성은 남아 있다"고 말한다. 시뮬레이션의 개념이 들어가는 것은 바로 이 시점이다"[53]라고 말했다. 속도를 측정할 때 명령 집합이 중요하다. 예를 들어, 나머지를 계산하기 위한 유클리드 알고리즘의 하위 프로그램은 프로그래머가 단순한 뺄셈(혹은 더 나쁜: 민스키의 "감소"만 하는 것이 아니라 이용 가능한 "계량" 명령을 가지고 있다면 훨씬 더 빨리 실행될 것이다.

구조화된 프로그래밍, 표준 구조: Church-Turing 논문에 따르면 어떤 알고리즘도 Turing complete로 알려진 모델로 계산할 수 있으며, Minsky의 데모에 따르면 Turing complete는 조건부 GOTO, 무조건 GOTO, assignment, HALT의 네 가지 명령 유형만 필요로 한다. 케메니와 쿠르츠는 무조건적인 GOTO와 조건부 IF-THEN GOTO를 "단련되지 않은" 사용은 "스파게티 코드"를 야기할 수 있지만 프로그래머는 이러한 명령만을 사용하여 구조화된 프로그램을 작성할 수 있고, 다른 한편으로는 "구조화된 언어로 잘못 구성된 프로그램을 작성하는 것도 가능하며 그리 어렵지 않다"[54]고 본다. Tausworthe는 세 가지 Böm-Jacopini 표준 구조(SEQUENT, IF-THEN-ELSE, WID-DO)[55]를 확장하며, DO-WHING과 CASE를 두 개 더 추가한다.[56] 구조화된 프로그램의 또 다른 장점은 수학적 유도를 사용하여 정확성을 증명하는 것에 자신을 빌려준다는 것이다.[57]

표준 흐름도 기호[58]: 플로우차트라고 불리는 그래픽 보좌관은 알고리즘을 설명하고 문서화하는 방법을 제공한다. 민스키 기계의 프로그램 흐름처럼 플로우차트는 항상 페이지 맨 위에서 시작해서 아래로 내려간다. 기본 기호는 프로그램 흐름을 보여주는 방향 화살표, 사각형(SEQUENCE, GOTO), 다이아몬드(IF-TEN-ELSE), 도트(OR-tie) 4개뿐이다. Böhm-Jacopini의 표준 구조는 이러한 원시적인 모양으로 만들어진다. 하부 구조는 직사각형에서 "둥지"를 수 있지만, 상부 구조에서 하나의 출구가 발생하는 경우에만 가능하다. 기호와 표준 구조물을 만드는 용도는 도표에 나타나 있다.

예

추가 정보: 알고리즘 목록

알고리즘 예제

가장 간단한 알고리즘 중 하나는 무작위 순서 목록에서 가장 많은 숫자를 찾는 것이다. 해결책을 찾으려면 목록의 모든 숫자를 살펴봐야 한다. 여기서부터 간단한 알고리즘을 따르며, 이 알고리즘은 영어 산문에서는 높은 수준의 설명으로 다음과 같이 기술할 수 있다.

높은 수준의 설명:

  1. 만약 세트에 숫자가 없다면, 가장 높은 숫자는 없다.
  2. 집합에서 첫 번째 숫자가 집합에서 가장 큰 숫자라고 가정하십시오.
  3. 집합에 남아 있는 각 숫자에 대해: 이 숫자가 현재 가장 큰 숫자보다 큰 경우 이 숫자를 집합에서 가장 큰 숫자로 간주하십시오.
  4. 세트에 반복할 숫자가 남아 있지 않으면 현재 가장 큰 숫자를 세트의 가장 큰 숫자로 간주하십시오.

(Quasi-)형식 설명: 산문으로 쓰이지만 컴퓨터 프로그램의 높은 수준의 언어에 훨씬 더 가까운 다음 사항은 알고리즘을 유사코드 또는 피지닌 코드로 더 공식적인 코드화한다. 

알고리즘 MigNumber 입력: 숫자 L 목록.   출력: L 목록에서 가장 큰 숫자. 
 L.size = 0이면 L의 각 항목에 대해 null 최대값 L[0]을 반환하고, 항목 > 가장 크면 최대값으로 반환한다.
  • "직접"은 할당을 의미한다. 예를 들어, "가장 큰 ←항목"은 가장 큰 값이 항목의 가치를 변화시킨다는 것을 의미한다.
  • "return"은 알고리즘을 종료하고 다음 값을 출력한다.

유클리드 알고리즘

추가 정보: 유클리드 알고리즘

수학에서 유클리드 알고리즘, 즉 유클리드 알고리즘은 두 정수(숫자)의 가장 큰 공통분할기(GCD)를 계산하는 효율적인 방법인데, 이 두 정수(숫자)를 나머지 없이 모두 나누는 수가 가장 많다. 고대 그리스 수학자 유클리드(Eucleid)의 이름을 따서 지은 것인데, 그는 이것을 그의 원소(C. 300 BC)에서 처음 기술했다.[59] 그것은 공통적으로 사용되는 가장 오래된 알고리즘 중 하나이다. 분수를 가장 단순한 형태로 줄이는 데 사용할 수 있으며, 다른 많은 숫자-이론적 및 암호 계산의 일부분이다.

T.L의 유클리드 알고리즘 예제 다이어그램. 히스(1908년), 자세한 내용 추가. 유클리드(유클리드)는 제3의 측정치를 넘지 않으며 수치적인 예를 제시하지 않는다. 니코마쿠스는 49와 21의 예를 들며 "나는 큰 것에서 작은 것을 뺐다, 28이 남는다, 그리고 다시 같은 21이 남는다, 7이 남는다, 14가 남는다, 21에서 이것을 뺐다, 나는 다시 7을 뺐다, 7이 남는다, 그러나 7은 7에서 뺄 수 없다."라고 말한다. 히스는 말했다. "마지막 구절호기심도 있지만, '하나의 같은 숫자로' 끝맺는다는 구절의 의미도 마찬가지로 그 의미는 충분히 명백하다."(Heath 1908:300)

유클리드는 이렇게 문제를 제기한다: "서로 맞지 않는 두 개의 숫자를 주어, 그들의 가장 큰 공통의 척도를 찾아라." 그는 "단위들로 구성된 숫자[될 수 있는] 집합"을 정의한다: 계산 숫자, 0을 포함하지 않는 양의 정수. "측정"은 남은 부분 r이 짧은 길이 s보다 작을 때까지 긴 길이 l를 따라 연속적으로 (q배) 짧은 측정 길이를 배치하는 것이다.[60] 현대어로, 나머지 r = l - q×s, q는 인수가 되거나, 나머지 r은 분할 후 남은 정수-수축 부분인 "modulus"이다.[61]

유클리드 방법이 성공하려면 출발 길이는 두 가지 요건을 충족해야 한다: (i) 길이가 0이 아니어야 하며, (ii) 뺄셈은 "적절한" 것이어야 한다. 즉, 시험은 두 숫자 중 작은 숫자를 큰 숫자에서 빼야 한다(또는 둘의 뺄셈이 0이 되도록 같을 수 있다).

유클리드의 원래 증거는 세 번째 요건을 추가했다: 두 길이가 서로 프라임이어서는 안 된다. 유클리드는 이를 명기하여 두 숫자의 공통 척도가 사실 가장 크다는 불합리한 증거를 만들 수 있도록 했다.[62] 니코마쿠스의 알고리즘은 유클리드 알고리즘과 같은 반면, 숫자가 서로 프라임일 때는 공통 측정치인 "1"을 산출한다. 정확히 말하자면, 다음은 정말로 니코마쿠스의 알고리즘이다.

1599년과 650년 동안 가장 큰 공통점을 찾기 위한 유클리드 알고리즘의 그래픽 표현. 
 1599 = 650×2 + 299  650 = 299×2 + 52  299 = 52×5 + 39  52 = 39×1 + 13  39 = 13×3 + 0

유클리드 알고리즘의 컴퓨터 언어

유클리드 알고리즘을 실행하려면 몇 가지 명령 유형만 필요하다. 일부 논리 테스트(조건부 GOTO), 무조건 GOTO, 할당(교체) 및 뺄셈.

  • 위치는 대문자로 상징된다(예: S, A 등).
  • 위치의 다양한 수량(숫자)은 위치 이름과 관련된 소문자와 (일반적으로) 소문자로 작성된다. 예를 들어, 시작점에서 위치 L은 숫자 l = 3009를 포함할 수 있다.

유클리드 알고리즘에 대한 비굴한 프로그램

"Inelegant"는 Knuth의 알고리즘 버전을 분업(또는 "modulus" 명령)을 대체하는 뺄셈 기반 잔여 루프를 사용하여 번역한 것이다. Knuth 1973:2–4에서 파생됨. 두 숫자에 따라 "Enelegant"는 "Elegant"보다 적은 단계로 g.c.d를 계산할 수 있다.

다음 알고리즘은 크누스의 4단계 버전인 유클리드·니코마코스'로 액자에 들어가지만, 나머지를 찾기 위해 분열을 사용하기보다는 나머지 길이 r에서 r이 s보다 작을 때까지 짧은 길이의 s를 연속적으로 소급하는 것을 사용한다. 굵은 글씨로 표시된 높은 수준의 설명은 Knuth 1973:2–4에서 채택되었다.

입력: 

1 [두 위치 L과 S에 두 길이를 나타내는 숫자 l과 s를 삽입]:   입력 L, S 2 [초기화 R: 나머지 길이를 시작/초기화/입력 길이 l]: R ← L

E0: [R ≥ s.를 확인하십시오.] 

3 [두 숫자 중 작은 숫자가 S에 있고 큰 숫자가 R에 있다는 것을 확인하라]: IF R > S에 있는 L의 내용이 큰 숫자인지 확인하라. 따라서 교환 단계 4, 5, 6을 건너뛰고, 기타 GOTO 단계 7 R과 S. 4 L ← R의 내용을 교환한다(이 첫 번째 단계는 중복이지만 나중에 논의하는데 유용하다). 5 R ← S 6 S ← L

E1: [남은 항목 찾기]: R의 나머지 길이 r이 S의 짧은 길이 s보다 작을 때까지, R의 나머지 길이 r에서 S의 측정 숫자 s를 반복적으로 뺀다. 

7 IF S > R 그 다음 다시 측정하여 8 R 10 R - S 9 [제거기-루프]: GOTO 7을 측정하였다.

E2: [남은 것이 0인가?]: 둘 중 하나 (i) 마지막 측정치가 정확했고, R의 나머지가 0이며, 프로그램을 중지할 수 있고, 또는 (ii) 알고리즘이 계속되어야 한다. 마지막 측정치는 S의 측정 숫자보다 R에 나머지를 남겨두었다. 

10 R = 0이면 GOTO 15단계를 수행하고 그렇지 않으면 11단계를 계속한다.

E3: [교체 s 및 r]: 유클리드 알고리즘의 너트. 나머지 r을 사용하여 이전에 더 적은 수의 s를 측정하십시오. L은 임시 위치 역할을 한다. 

11 L ← R 12 R ← S 13 S ← L 14 [측정 공정 반복]: GOTO 7

출력: 

15 [완료. S에 가장 큰 공통점 포함]:PRINT S

완료: 

16 정지, 종료, 정지.

유클리드 알고리즘을 위한 우아한 프로그램

다음 버전의 유클리드 알고리즘은 "Inelegant"에 의해 요구되는 것을 하기 위해 6개의 핵심 지침만 필요로 한다. 더 나쁜 것은 "Inelegant"는 더 많은 종류의 지시사항을 필요로 한다.[clarify] "Elegant"의 흐름도는 이 글의 상단에 있다. (구조화되지 않은) 기본 언어에서는 단계 번호가 매겨지고, 지시 사항도 매겨진다. LET [] = [] ←으로 상징되는 과제지침이다. 

  5 최대공통분할기에 대한 REM 유클리드 알고리즘   6 프린트 "0보다 큰 정수 2개 입력"   10 입력 A,B   20 IF B=0 그럼 에 가다 80   30 IF A > B 그럼 에 가다 60   40 LET B=B-A   50 에 가다 20   60 LET A=A-B   70 에 가다 20   80 프린트 A   90 끝

"Elegant" 작동 방식: 외부 "유클리드 루프" 대신에 "Elegant"는 두 개의 "co-loops"와 A ← A - B를 계산하는 A > B 루프, B b B - A를 계산하는 B loop A 루프 사이에서 앞뒤로 이동한다. 이것은, 마침내 미니언드 M이 서브트라헨드 S(차이 = 미니언드 - 서브트라헨드)보다 작거나 같을 때, 미니언드가 s(새로운 측정 길이)가 될 수 있고, 서브라헨드가 새로운 r(측정할 길이)이 될 수 있기 때문에, 즉, 감산역전의 "감각"이 작용한다.

다음 버전은 C-family의 프로그래밍 언어와 함께 사용할 수 있다. 

// 유클리드 알고리즘 최대공통점 인트로 유클리드알고리즘 (인트로 A, 인트로 B){      A=복근(A);      B=복근(B);      하는 동안에 (B!=0){           하는 동안에 (A>B) A=A-B;           B=B-A;      }      돌아오다 A; }

유클리드 알고리즘 테스트

알고리즘은 저자가 원하는 것을 하는 것일까? 몇 가지 테스트 사례에서는 일반적으로 핵심 기능에 대한 신뢰도를 어느 정도 제공한다. 하지만 테스트로는 충분하지 않다. 테스트 사례의 경우, 하나의 출처가[63] 3009와 884를 사용한다. 크누스는 40902, 24140을 제안했다. 또 다른 흥미로운 사례는 비교적 소수인 14157과 5950이라는 것이다.

그러나 "예외적 사례"[64]를 식별하고 테스트해야 한다. R > S, S > R, R = S? Ditto for "Elegant": B > A, A > B, A = B? (모두 예)가 제대로 수행될 것인가? 한 숫자가 0이면 두 숫자가 모두 0이면 어떻게 되는가?("Inelegant"는 모든 경우에 영구적으로 계산되며, "Elegant"는 A = 0일 때 영구적으로 계산된다. 음수를 입력하면 어떻게 되는가? 분수? 만일 입력 번호, 즉 알고리즘/프로그램에 의해 계산된 함수의 도메인이 0을 포함한 양의 정수만을 포함한다면, 0에서의 고장은 알고리즘(및 알고리즘을 인스턴스화하는 프로그램)이 총함수가 아닌 부분함수임을 나타낸다. 예외로 인한 눈에 띄는 실패는 아리안 5편 501호 로켓 실패(1996년 6월 4일)이다.

수학적 유도를 이용한 프로그램 정확성 증명: 크누스는 유클리드 알고리즘의 "확장" 버전에 수학적 유도를 적용하는 것을 증명하며, 그는 "어떤 알고리즘의 유효성을 증명하는 데 적용되는 일반적인 방법"[65]을 제안한다. Tausworthe는 프로그램의 복잡성에 대한 측도가 정확성 입증의 길이일 것을 제안한다.[66]

유클리드 알고리즘 측정 및 개선

우아함(콤팩트함) 대 선량함(속도): 핵심지시가 6개밖에 되지 않는 상황에서 13개지시에 있는 '이레건트'와 비교하면 '이레건트'가 확실한 승자다. 그러나 "Inelegant"는 더 빠르다(SHIRT에 더 적은 단계로 도착함). 알고리즘 분석은[67] 왜 이런지를 보여준다: "Elegant"는 모든 감산 루프에서 두 가지 조건부 테스트를 하는 반면, "Enelegant"는 한 가지 조건부 테스트를 한다. 알고리즘(보통)은 많은 루프스루(loop-through)를 요구하기 때문에, 평균적으로 많은 시간이 나머지를 계산한 후에만 필요한 "B = 0?" 테스트를 하는 데 낭비된다.

알고리즘을 개선할 수 있는가?: 프로그래머가 프로그램을 "적합"하고 "효과적" 즉, 프로그램 작성자가 의도한 기능을 계산하는 것으로 판단하면, 문제는 개선될 수 있는가?

5단계를 없애면 '귀족'의 콤팩트함을 개선할 수 있다. 그러나 Chaitin은 알고리즘의 압축은 일반화된 알고리즘에 의해서만 자동화될 수 없다는 것을 증명했다;[68] 오히려 그것은 경험적으로, 시행착오, 영리함, 통찰력, 귀납 추론의 적용 등에 의해서만 행해질 수 있다. 4, 5, 6단계가 11, 12 및 13단계에서 반복되는지 관찰하십시오. "Elegant"와의 비교는 이러한 단계들이 2단계와 3단계와 함께 제거될 수 있다는 암시를 준다. 이를 통해 핵심지시는 13개에서 8개로 줄어 9단계로 'Elegant'보다 '고상하다'는 느낌을 준다.

"Elegant"의 속도는 "B=0?" 테스트를 두 개의 뺄셈 루프 밖으로 이동함으로써 향상될 수 있다. 이 변경은 세 가지 지침(B = 0?, A = 0?, GOTO)을 추가해야 한다. 이제 "Elegant"는 예-숫자를 더 빨리 계산한다; 이것이 주어진 A, B, R에 항상 해당되는 것이든, S는 상세한 분석이 필요할 것이다.

알고리즘 분석

주요 기사: 알고리즘 분석

주어진 알고리즘에 대해 이론적으로 어느 정도의 특정 자원(시간이나 저장)이 필요한지 아는 것이 자주 중요하다. 그러한 정량적 답변(추정)을 얻기 위한 알고리즘 분석을 위한 방법이 개발되었다. 예를 들어, n개의 숫자 목록의 요소를 추가하는 알고리즘은 큰 O 표기법을 사용하여 O(n)의 시간 요건을 가질 것이다. 항상 알고리즘은 지금까지 모든 요소의 합과 입력 목록의 현재 위치라는 두 가지 값만 기억하면 된다. 따라서 입력 번호를 저장하는 데 필요한 공간을 계산하지 않으면 O(1)의 공간 요구 조건을, 계산된 경우에는 O(n)의 공간 요구 조건을 가지고 있다고 한다.

다른 알고리즘은 다른 알고리즘보다 더 작거나 더 많은 시간, 공간 또는 '이퍼트(effort)'로 다른 명령 집합으로 동일한 작업을 완료할 수 있다. 예를 들어, 바이너리 검색 알고리즘(비용 O(log n)은 정렬된 목록이나 배열의 테이블 검색에 사용될 때 순차 검색(비용 O(n) )을 능가한다.

형식 대 실증적

주요 기사: 경험적 알고리즘, 프로파일링(컴퓨터 프로그래밍) 및 프로그램 최적화

알고리즘의 분석과 연구는 컴퓨터 과학의 한 분야로, 특정 프로그래밍 언어나 구현을 사용하지 않고 추상적으로 실행되는 경우가 많다. 이러한 의미에서 알고리즘 분석은 특정 구현의 구체적 내용이 아니라 알고리즘의 기초적 특성에 초점을 맞춘다는 점에서 다른 수학 분야와 유사하다. 일반적으로 가성형은 가장 단순하고 일반적인 표현이기 때문에 분석에 사용된다. 그러나 궁극적으로 대부분의 알고리즘은 대개 특정 하드웨어/소프트웨어 플랫폼에서 구현되며 알고리즘 효율성은 결국 실제 코드를 사용하여 시험한다. "일회성" 문제의 해결책의 경우, 특정 알고리즘의 효율성은 유의미한 결과를 가져오지 않을 수 있지만(n이 극히 큰 경우는 제외), 빠른 쌍방향, 상업적 또는 장수명 과학적 사용을 위해 설계된 알고리즘의 경우 그것은 중요할 수 있다. 작은 n에서 큰 n으로 확장하는 것은 종종 그렇지 않으면 양성인 비효율적인 알고리즘을 노출시킨다.

경험적 시험은 성능에 영향을 미치는 예기치 않은 상호작용을 발견할 수 있기 때문에 유용하다. 벤치마크를 사용하여 프로그램 최적화 후 알고리즘의 잠재적 개선 전후를 비교할 수 있다. 그러나 경험적 테스트는 형식적 분석을 대체할 수 없으며 공정하게 수행하기에 사소한 것이 아니다.[69]

실행효율

주요 기사: 알고리즘 효율

잘 확립된 알고리즘에서도 가능한 잠재적 개선을 설명하기 위해, FFT 알고리즘(이미지 처리 분야에서 많이 사용됨)과 관련된 최근의 중요한 혁신은 의료 영상과 같은 애플리케이션의 처리 시간을 최대 1,000배까지 줄일 수 있다.[70] 일반적으로 속도 향상은 문제의 특수 속성에 따라 달라지는데, 실제 적용에서는 매우 일반적이다.[71] 이 정도의 속도를 높이면 디지털 카메라나 의료 장비와 같은 이미지 처리를 광범위하게 사용하는 컴퓨터 장치가 전력을 덜 소비할 수 있다.

분류

알고리즘을 분류하는 방법에는 제각기 장점이 있다.

구현별

알고리즘을 분류하는 한 가지 방법은 구현 수단이다. 

인트로 gcd(인트로 A, 인트로 B) {     만일 (B == 0)         돌아오다 A;     다른 만일 (A > B)         돌아오다 gcd(A-B,B);     다른         돌아오다 gcd(A,B-A); }
위 흐름도에서 유클리드 알고리즘의 반복 C 구현
재귀
재귀 알고리즘은 기능 프로그래밍에 공통적인 방법인 특정 조건(종료 조건이라고도 함)이 일치할 때까지 반복적으로 자신을 호출( 참조)하는 알고리즘이다. 반복 알고리즘은 루프와 같은 반복적인 구조와 때로는 주어진 문제를 해결하기 위해 스택과 같은 추가 데이터 구조를 사용한다. 어떤 문제들은 자연스럽게 한 가지 이행에 적합하다. 예를 들어, 하노이의 탑들은 재귀적 구현을 사용하여 잘 이해된다. 모든 재귀 버전은 동등(그러나 다소 복잡할 수 있음) 반복 버전을 가지고 있으며, 그 반대의 경우도 마찬가지다.
논리적인
알고리즘은 통제된 논리적 추론이라고 볼 수 있다. 이 개념은 알고리즘 = 논리 + 제어로 표현될 수 있다.[72] 논리 구성요소는 계산에 사용될 수 있는 공리를 표현하고 제어 구성요소는 공리에 공리가 적용되는 방식을 결정한다. 이것이 논리 프로그래밍 패러다임의 기본이다. 순수 로직 프로그래밍 언어에서는 제어 컴포넌트가 고정되고 로직 컴포넌트만 공급하여 알고리즘을 지정한다. 이 접근방식의 매력은 우아한 의미론이다: 공리의 변화는 알고리즘에 잘 정의된 변화를 일으킨다.
직렬, 병렬 또는 분산
알고리즘은 보통 컴퓨터가 한 번에 하나의 알고리즘 명령을 실행한다는 가정으로 논의된다. 그 컴퓨터들은 때때로 직렬 컴퓨터라고 불린다. 그러한 환경을 위해 설계된 알고리즘을 병렬 알고리즘이나 분산 알고리즘과는 반대로 직렬 알고리즘이라고 한다. 병렬 알고리즘은 여러 프로세서가 동시에 문제를 해결할 수 있는 컴퓨터 아키텍처를 활용하는 반면 분산 알고리즘은 컴퓨터 네트워크와 연결된 여러 기계를 활용한다. 병렬 또는 분산 알고리즘은 문제를 더 대칭적이거나 비대칭적인 하위 문제로 나누고 결과를 함께 수집한다. 그러한 알고리즘의 리소스 소비는 각 프로세서의 프로세서 사이클일 뿐만 아니라 프로세서 간의 통신 오버헤드도 포함한다. 일부 정렬 알고리즘은 효율적으로 병렬화할 수 있지만 통신 오버헤드는 비싸다. 반복 알고리즘은 일반적으로 병렬로 사용할 수 있다. 어떤 문제들은 병렬 알고리즘이 없으며 본질적으로 직렬 문제라고 불린다.
결정론적 또는 비결정론적
결정론적 알고리즘은 알고리즘의 모든 단계에서 정확한 결정으로 문제를 해결하는 반면 비결정론적 알고리즘은 경험적 접근법을 사용하여 일반적인 추측이 더 정확하지만 추측을 통해 문제를 해결한다.
정확하거나 근사함
많은 알고리즘이 정확한 솔루션에 도달하는 동안, 근사 알고리즘은 실제 솔루션에 더 가까운 근사치를 추구한다. 근사치는 결정론적 또는 무작위 전략을 사용하여 도달할 수 있다. 그러한 알고리즘은 많은 어려운 문제들에 대한 실질적인 가치를 가지고 있다. 대략적인 알고리즘의 예 중 하나는 주어진 일련의 항목이 있는 배낭 문제다. 그것의 목표는 배낭을 싸서 최대 총값을 얻는 것이다. 각 품목은 어느 정도 무게와 가치가 있다. 운반할 수 있는 총 중량은 일부 고정 숫자 X에 지나지 않는다. 따라서 해결책은 항목의 가중치와 그 가치를 고려해야 한다.[73]
양자 알고리즘
그것들은 양자 계산의 현실적인 모델에서 작동한다. 이 용어는 본질적으로 양자처럼 보이거나 양자 중첩이나 양자 얽힘과 같은 양자 컴퓨팅의 필수적인 특징을 사용하는 알고리즘에 주로 사용된다.

디자인 패러다임별

알고리즘을 분류하는 또 다른 방법은 설계 방법론이나 패러다임에 의해 이루어진다. 각각 다른 패러다임들이 일정하게 존재한다. 또한 이러한 각 범주는 다양한 유형의 알고리즘을 포함한다. 몇 가지 일반적인 패러다임은 다음과 같다.

완충력 또는 철저한 검색
이것은 어떤 것이 최선인지 보기 위해 가능한 모든 해결책을 시도하는 순진한 방법이다.[74]
분열시켜 정복하다.
분할 및 정복 알고리즘은 문제가 쉽게 해결될 수 있을 정도로 작을 때까지 한 가지 이상의 작은 문제(일반적으로 반복적으로)로 문제의 인스턴스를 감소시킨다. 그러한 분열과 정복의 한 예는 병합 정렬이다. 데이터를 세그먼트로 나눈 후 데이터의 각 세그먼트에 대해 정렬할 수 있으며, 세그먼트를 병합하여 정복 단계에서 전체 데이터를 정렬할 수 있다. 더 단순한 분열과 정복의 변형을 감소와 정복 알고리즘이라고 하는데, 이 알고리즘은 동일한 하위 문제를 해결하고 이 하위 문제의 해결책을 사용하여 더 큰 문제를 해결한다. 분할 정복은 문제를 여러 하위 문제로 나누기 때문에 정복 단계는 감소하고 알고리즘을 정복하는 것보다 더 복잡하다. 감소와 정복 알고리즘의 예는 바이너리 검색 알고리즘이다.
검색 및 열거
많은 문제(장기놀이 등)는 그래프 상의 문제로 모델링할 수 있다. 그래프 탐색 알고리즘은 그래프 주위로 이동하는 규칙을 지정하며 이러한 문제에 유용하다. 이 범주에는 검색 알고리즘, 분기 및 바인딩 열거 및 역추적도 포함된다.
랜덤화 알고리즘
그러한 알고리즘은 무작위로(또는 사이비 무작위로) 어떤 선택을 한다. 정확한 해결책을 찾는 것이 비실용적일 수 있는 문제에 대한 대략적인 해결책을 찾는 데 매우 유용할 수 있다(아래 경험적 접근법 참조). 이러한 문제들 중 일부의 경우, 가장 빠른 근사치에는 어떤 무작위성이 수반되어야 한다고 알려져 있다.[75] 다항식 시간 복잡성을 가진 무작위화된 알고리즘이 일부 문제에 대한 가장 빠른 알고리즘이 될 수 있는지는 P 대 NP 문제로 알려진 개방형 질문이다. 그러한 알고리즘에는 크게 두 가지 등급이 있다.
  1. 몬테카를로 알고리즘은 높은 확률로 정답을 돌려준다. 예: RP는 다항식 시간에 실행되는 이들의 하위 클래스다.
  2. 라스베이거스 알고리즘은 항상 정답을 반환하지만, 이들의 실행 시간은 ZPP와 같이 확률적으로만 구속되어 있다.
복잡성 감소
이 기법은 어려운 문제를 우리가 점증적으로 최적의 알고리즘을 가지고 있는 더 잘 알려진 문제로 변형시킴으로써 해결하는 것을 포함한다. 목표는 복잡성이 결과적으로 감소된 알고리즘에 의해 지배되지 않는 축소 알고리즘을 찾는 것이다. 예를 들어, 정렬되지 않은 리스트에서 중위수를 찾기 위한 하나의 선택 알고리즘은 먼저 리스트를 분류한 다음 정렬된 리스트에서 중간 요소(싼 부분)를 꺼내는 것을 포함한다. 이 기술은 변형과 정복으로도 알려져 있다.
백 트래킹
이 접근법에서는 복수의 솔루션이 증분적으로 구축되어 유효한 풀 솔루션으로 이어질 수 없다고 판단될 때 폐기한다.

최적화 문제

최적화 문제의 경우 알고리즘의 보다 구체적인 분류가 있다. 이러한 문제에 대한 알고리즘은 위에서 설명한 하나 이상의 일반 범주 및 다음 중 하나에 포함될 수 있다.

선형 프로그래밍
선형적 평등과 불평등 제약에 묶인 선형함수에 대한 최적의 해결책을 찾을 때, 문제의 제약조건은 최적의 해결책을 도출하는 데 직접적으로 사용될 수 있다. 인기 있는 심플렉스 알고리즘처럼 이 카테고리의 어떤 문제도 해결할 수 있는 알고리즘이 있다.[76] 선형 프로그래밍으로 해결할 수 있는 문제에는 지시된 그래프의 최대 흐름 문제가 포함된다. 문제가 하나 이상의 무명 중 하나 이상이 정수여야 한다고 추가로 요구하는 경우 정수 프로그래밍으로 분류된다. 선형 프로그래밍 알고리즘은 정수 값에 대한 모든 제한이 표면적이라는 것이 증명될 수 있다면, 즉, 해결책이 어쨌든 이러한 제한을 충족시킨다면 그러한 문제를 해결할 수 있다. 일반적인 경우에는 문제의 난이도에 따라 대략적인 해결책을 찾아내는 전문 알고리즘이나 알고리즘이 사용된다.
동적 프로그래밍
문제에 대한 최적의 해결책이 최적의 해결책에서 하위 문제에 이르기까지 구성될 수 있다는 것을 의미하는 최적의 하위 구조와 동일한 하위 문제가 여러 가지 다른 문제 사례를 해결하기 위해 사용된다는 것을 의미하는 중복 하위 문제를 보여주는 경우 동적 프로그래밍이라는 보다 빠른 접근방식은 이미 해결된 해결책의 재구성을 피할 수 있다. 계산된 예를 들어, 가중 그래프에서 정점에서 목표에 이르는 최단 경로인 플로이드-워셸 알고리즘은 인접한 모든 정점에서 목표에 이르는 최단 경로를 사용하여 찾을 수 있다. 동적 프로그래밍과 메모화가 함께 한다. 동적 프로그래밍과 분열과 정복의 주요 차이점은 하위문제들이 분할과 정복에서 다소 독립적이긴 하지만, 하위문제들은 동적 프로그래밍에서 겹친다는 것이다. 동적 프로그래밍과 간단한 재귀의 차이는 재귀 호출의 캐싱 또는 메모화에 있다. 하위 문제가 독립적이고 반복이 없을 때, 메모는 도움이 되지 않는다. 따라서 동적 프로그래밍은 모든 복잡한 문제에 대한 해결책이 아니다. 메모화를 사용하거나 이미 해결된 하위 문제의 표를 유지함으로써 동적 프로그래밍은 많은 문제의 기하급수적인 성격을 다항식 복잡성으로 감소시킨다.
탐욕스러운 방법
탐욕스러운 알고리즘은 하위구조를 조사하여 작동한다는 점에서 동적 프로그래밍 알고리즘과 유사하며, 이 경우 문제가 아니라 주어진 해결책의 경우도 있다. 그러한 알고리즘은 어떤 방법으로 주어지거나 구성되었을 수 있는 어떤 해결책에서 시작하여 작은 수정으로 개선한다. 어떤 문제에서는 최적의 솔루션을 찾을 수 있고, 다른 문제에서는 알고리즘으로 개선할 수 없지만 최적은 아닌 해결책에서 국소 최적화에 그칠 수 있다. 탐욕스러운 알고리즘의 가장 일반적인 사용은 이 방법으로 최적의 해결책을 찾을 수 있는 최소한의 신장 트리를 찾는 것이다. 허프먼 트리, 크러스칼, 프림, 솔린은 이 최적화 문제를 해결할 수 있는 탐욕스러운 알고리즘이다.
휴리스틱 방식
최적화 문제에서 경험적 알고리즘을 사용하여 최적의 솔루션을 찾는 것이 비실용적인 경우 최적 솔루션에 가까운 솔루션을 찾을 수 있다. 이러한 알고리즘은 진행함에 따라 최적의 솔루션에 점점 더 가까워짐으로써 작동한다. 원칙적으로 무한정 달릴 경우 최적의 솔루션을 찾게 된다. 이들의 장점은 비교적 짧은 시간 안에 최적의 솔루션에 매우 가까운 솔루션을 찾을 수 있다는 점이다. 그러한 알고리즘에는 국부 검색, 타부 검색, 시뮬레이션 어닐링 및 유전 알고리즘이 포함된다. 시뮬레이션된 어닐링과 같은 일부는 비결정론적 알고리즘인 반면 타부 검색과 같은 일부는 결정론적 알고리즘이다. 최적화되지 않은 용액의 오류에 대한 한계를 알게 되면 알고리즘은 근사 알고리즘으로 더욱 분류된다.

연구분야별

참고 항목: 알고리즘 목록

과학의 모든 분야에는 나름대로의 문제가 있고 효율적인 알고리즘이 필요하다. 한 분야의 관련 문제들이 함께 연구되는 경우가 많다. 검색 알고리즘, 정렬 알고리즘, 병합 알고리즘, 숫자 알고리즘, 그래프 알고리즘, 문자열 알고리즘, 계산 기하 알고리즘, 결합 알고리즘, 의료 알고리즘, 기계 학습, 암호화 알고리즘, 데이터 압축 알고리즘 및 파싱 기법이 몇 가지 예다.

필드는 서로 중복되는 경향이 있으며, 한 필드의 알고리즘 진보는 때로는 완전히 관련이 없는 다른 필드의 필드를 개선할 수 있다. 예를 들어, 동적 프로그래밍은 산업에서 자원 소비의 최적화를 위해 발명되었지만 지금은 많은 분야에서 광범위한 문제를 해결하는 데 사용되고 있다.

복잡성별

참고 항목: 복잡성 등급 및 매개 변수화된 복잡성

알고리즘은 입력 크기에 비해 완료해야 하는 시간에 따라 분류할 수 있다.

  • 일정 시간: 입력 크기에 관계없이 알고리즘에 필요한 시간이 동일한 경우 예: 배열 요소에 대한 액세스.
  • 로그 시간: 입력 크기의 로그 함수인 경우. 예: 바이너리 검색 알고리즘.
  • 선형 시간: 시간이 입력 크기에 비례하는 경우 예: 목록의 이동
  • 다항식 시간: 시간이 입력 크기의 검정력인 경우 예를 들어 버블 정렬 알고리즘은 2차 시간 복잡성을 가지고 있다.
  • 지수 시간: 시간이 입력 크기의 지수 함수인 경우. 예: 브루트 포스 검색.

어떤 문제들은 서로 다른 복잡성의 다중 알고리즘을 가질 수 있는 반면, 다른 문제들은 알고리즘이 없거나 알려진 효율적인 알고리즘이 없을 수 있다. 일부 문제에서 다른 문제로의 매핑도 있다. 이 때문에, 알고리즘 대신 문제 자체를 가능한 최선의 알고리즘의 복잡성에 근거해 동등성 등급으로 분류하는 것이 더 적합하다는 것이 밝혀졌다.

연속 알고리즘

"알고리즘"이라는 단어에 적용할 때 "연속적"이라는 형용사는 다음을 의미할 수 있다.

  • 이 데이터가 이산 근사치로 표현되더라도 연속적인 양을 나타내는 데이터에 대해 작동하는 알고리즘 - 이러한 알고리즘은 수치 분석에서 연구된다.
  • 아날로그 컴퓨터에서 실행되는 데이터에서 연속적으로 작동하는 미분 방정식의 형태의 알고리즘.[77]

법적 문제

참고 항목: 소프트웨어 특허

알고리즘 자체는 보통 특허를 얻을 수 없다. 미국에서는 추상적인 개념, 숫자 또는 신호의 단순한 조작만으로 구성된 주장이 "프로세스"(USPTO 2006)를 구성하지 않으며, 따라서 알고리즘은 특허를 얻을 수 없다(Gottschalk v. Benson). 그러나 알고리즘의 실용적인 적용은 때때로 특허를 얻을 수 있다. 예를 들어 Diamond v. Diehr에서는 합성고무의 양생에 도움이 되는 간단한 피드백 알고리즘의 적용이 특허를 얻을 수 있는 것으로 간주되었다. 소프트웨어 특허는 논란이 심한데, 특히 유니시스의 LZW 특허와 같은 알고리즘을 포함한 비판적인 특허가 있다.

또한 일부 암호 알고리즘에는 내보내기 제한이 있다(암호화 내보내기 참조).

역사: "알고리즘" 개념의 발전

고대 근동

알고리즘의 초기 증거는 고대 메소포타미아(현대 이라크)의 바빌로니아 수학에서 찾을 수 있다. 바그다드 인근 슈루팍에서 발견된 기원전 2500년 경의 수메르 점토판은 최초의 분할 알고리즘을 설명했다.[10] 기원전 1800~1600년 경의 함무라비 왕조 동안에 바빌로니아 점토판은 공식을 계산하는 알고리즘을 기술했다.[78] 알고리즘은 바빌로니아 천문학에서도 사용되었다. 바빌로니아 점토판은 중요한 천문학적 사건의 시간과 장소를 계산하기 위한 알고리즘 절차를 기술하고 사용한다.[79]

산수를 위한 알고리즘은 기원전 1550년 경의 라인드 수학 파피루스(Rhind Mathematical Papyrus)로 거슬러 올라가는 고대 이집트 수학에서도 발견된다.[10] 알고리즘은 후에 고대 헬레니즘 수학에서 사용되었다. 니코마쿠스의 산술 입문서에 기술된 에라토스테네스의 체와 [80][11]: Ch 9.2 유클리드 원소(c. 300 BC)에서 처음 기술한 유클리드 알고리즘이 두 가지 예다.[11]: Ch 9.1

구분 가능한 불연속 기호

집계 표시: 그들의 양 떼와 곡식 자루와 돈을 기록하기 위해 옛 사람들은 집계를 했다: 막대기에 긁힌 돌이나 자국을 쌓거나 점토로 분리된 상징물을 만드는 것. 바빌로니아와 이집트의 마크와 상징의 사용을 통해 결국 로마 숫자와 주판이 진화했다(Dilson, 페이지 16–41) Turing 기계와 Post-Turing 기계 계산에 사용된 단수 계통 산술에서 집산 마크는 두드러지게 나타난다.

숫자에 대한 "위치 홀더"로서 기호 조작: 대수

페르시아의 수학자인 무하메드 이븐 무사 알-크와리츠므는 9세기에 알자브르를 썼다. 알고리즘(algorism)과 알고리즘(algorithm)이라는 용어는 알-크와리즈름(algorithm)이라는 이름에서 유래한 것이고, 알제브라(algebra)라는 용어는 알자브르(aljabr)라는 책에서 유래한 것이다. 유럽에서 '알고리즘'이라는 단어는 원래 알-크화리즈미가 대수 방정식을 풀기 위해 사용하는 규칙과 기법의 집합을 가리키는 데 사용되었고, 후에 어떤 규칙이나 기법을 지칭하기 위해 일반화되었다.[81] 이것은 결국 라이프니츠의 미적분 래티오시네이터(ca 1680년) 개념에서 절정에 이르렀다.

시대를 반년 앞선 좋은 세기였던 라이프니즈는 논리 대수, 즉 일반 대수학에서 숫자를 조작하는 규칙을 규정하는 방식으로 논리 개념을 조작하는 규칙을 명기하는 대수학을 제안했다.[82]

암호 알고리즘

암호화된 코드를 해독하기 위한 최초의 암호 알고리즘은 9세기 아랍 수학자인 알 킨디가 암호 메시지 해독에 관한 원고에서 개발했다. 그는 최초의 암호 해독 알고리즘인 주파수 분석에 의한 암호 분석에 대한 첫 번째 설명을 했다.[12]

이산 상태에서의 기계적 경쟁

시계: 볼터는 무게로 움직이는 시계의 발명을 "중세의 [유럽의] 핵심 발명품"으로, 특히 기계 시계의 틱과 틱을 우리에게 제공하는 위기[83] 탈출로 간주한다. "정확한 자동 기계"[84]는 즉시 13세기에 시작하여 마침내 "컴퓨터 기계" 즉 찰스 배비지와 에이다 러브레이스 백작 부인의 차이 엔진과 분석 엔진으로 이어졌다.[85] 러블레이스는 컴퓨터에 가공하기 위한 알고리즘을 최초로 만든 것으로 인정받고 있다. 배비지의 분석 엔진, 단순한 계산기 대신 실제 튜링-완전한 컴퓨터로 간주되는 첫 번째 장치, 그리고 배비지의 두 번째 장치를 완전히 구현하는 것은 아니지만, 그 결과 "역사 최초의 프로그래머"라고 불릴 때도 있다. 생후 수십 년까지 실현되다

논리 기계 1870 – Stanley Jevons의 "논리적 주판" 및 "논리적 기계": 기술적 문제는 현재 Karnaugh 지도라고 알려진 것과 유사한 형태로 제시될 때 부울 방정식을 줄이는 것이었다. Jevons(1880)는 먼저 [논리적] 조합의 어떤 부분이나 종류를 기계적으로 선택할 수 있도록 고안된 "핀으로 제공된 나무의 미끄러짐"의 간단한 "어바쿠스"를 설명한다. 그러나 보다 최근에는 시스템을 완전히 기계적인 형태로 축소하여 논리 기계라고 할 수 있는 것에 대한 추론의 간접적인 과정 전체를 구현했다."그의 기계에는 "확실히 움직이는 나무 막대"와 "발에는 피아노와 같은 21개의 열쇠가 달려 있다. 이 기계로 그는 마취할 수 있었다."논리주의 또는 기타 간단한 논리적인 주장"[86]을 얼버무리다.

그가 1870년에 전시한 이 기계는 왕립학회 회원들 앞에서 전시되었다.[87] 그러나 또 다른 논리학자 존 벤은 1881년 심볼 로직에서 "나는 때때로 논리 기계라고 불리는 것에 대한 관심이나 중요성에 대해 높은 평가를 받지 못하고 있다... 나는 현재 알려져 있거나 발견될 가능성이 있는 어떤 경쟁도 논리 기계라는 이름을 가질 자격이 있다고 생각하지 않는다."; 자세한 내용은 알고리즘 특성화를 참조하십시오. 그러나 그에 뒤지지 않기 위해 그는 "나는 교수에게 다소 유사한 계획을 제시했다. 제본의 주판... [그리고] [a]gain, 교수에 해당된다. Jevons의 논리 기계, 다음과 같은 비교가 설명될 수 있다. 나는 그것을 단지 논리 다이어그램 기계라고 부르고 싶지만, 나는 그것이 논리적인 기계에 합리적으로 기대되는 모든 것을 완전히 할 수 있을 것이라고 생각한다."[88]

Jaccard room, Hollerith 펀치 카드, 전신 및 전화 – 전자기계 계전기: Bell과 Newell(1971)은 Jaccard room (1801), Hollerith 카드의 전조 (펀치 카드, 1887), "전화 교환 기술"이 첫 번째 컴퓨터의 발전을 이끄는 나무의 뿌리였음을 나타낸다.[89] 19세기 중반까지 전화의 전구체인 전신은 전세계에서 사용되고 있었는데, 그 불연속적이고 구별이 가능한 부호화 문자는 "점점과 대시"라는 공통적인 소리였다. 19세기 후반에 이르러서는 1890년 미국 인구조사에서 홀러리스 카드가 사용된 것과 마찬가지로 티커 테이프(ca 1870년대)가 사용되었다. 그 후, 테이프에 Baudot 코드를 펀치한 종이로 사용한 텔레프린터 (ca. 1910년)가 등장했다.

전자 기계식 계전기(invented 1835)의 전화 교환 네트워크는 디지털 추가 장치의 발명가 조지 스티비츠(1937년)의 작품 뒤에 있었다. 벨 연구소에서 일하면서, 그는 기어와 함께 기계식 계산기를 사용하는 "버든섬"을 관찰했다. "그는 1937년 어느 날 저녁, 자신의 생각을 시험해 볼 생각으로 집으로 돌아갔다... 팅커링이 끝나자 스티비츠는 바이너리 추가 장치를 만들었다."[90]

데이비스(2000년)는 전자기계 계전기("이진 상태"를 열고 닫은 상태에서)의 특별한 중요성을 관찰한다.

1930년대부터 전기 계전기를 이용한 전자기계 계산기가 개발되면서 배비지가 구상한 범위를 가지고 기계가 만들어지게 되었다."[91]

19세기에서 20세기 중반까지의 수학

기호 및 규칙: 빠르게 연속해서 조지 불(1847년, 1854년), 고틀롭 프레게(1879년), 주세페 페아노(1888년–1889년)의 수학은 산수를 규칙으로 조작한 일련의 기호들로 줄였다. 새로운 방법(1888)이 제시한 페아노의 산술 원리는 "수학을 상징적인 언어로 공리화하려는 첫 시도"[92]였다.

그러나 하이제노르트는 프레게(1879)에게 다음과 같은 쿠도를 준다. 프레지는 "아마도 논리로 쓰여진 가장 중요한 단 하나의 작품일 것이다. 그 작품에서 우리는 '포뮬라 언어'를 볼 수 있다. 그것은 언어의 특성, 특별한 상징을 가지고 쓰여진 언어, 즉 "순수한 사고를 위한" 언어, 즉 수사학적 장식이 없는 언어, 즉 명확한 규칙에 따라 조작되는 특정한 기호들로 구성된 것이다."[93] 프레지의 작품은 알프레드 노스 화이트헤드와 버트랜드 러셀에 의해 그들의 프린키마티카 (1910–1913)에서 더욱 단순화되고 증폭되었다.

역설: 그와 동시에 문학에는 특히 부랄리-포르티 역설(1897), 러셀 역설(1902-03), 리처드 패러독스 등이 다수 등장하였다.[94] 그 결과 커트 괴델의 논문(1931년)은, 특히 거짓말쟁이의 역설을 인용하여, 재귀의 규칙을 숫자로 완전히 축소시켰다.

유효 계산성: 1928년 힐베르트가 정확히 정의한 엔체시둥스프로문제를 해결하기 위한 노력에서 수학자들은 먼저 "유효한 방법"이나 "유효한 계산" 또는 "유효한 계산"(즉, 성공할 계산)이 의미하는 바를 정의하기 시작했다. 연속적으로 다음과 같은 것이 나타났다. Alonzo Church, Stephen Kleene and J.B. 로서의 λ-미적분학은[95] 괴델이 자크 헤르브란트(cf)의 제안에 따라 행동하는 작품에서 나온 "일반적인 재귀"의 정교하게 연마된 정의다. 괴델의 1934년 프린스턴 강의)와 그에 따른 클레네의 단순화.[96] Entscheidungsprororoblem이 풀릴 수 없다는 Church의 증명[97], Emil Post의 노동자로서의 효과적인 계산가능성에 대한 정의는 일련의 방들을 통해 왼쪽이나 오른쪽으로 움직이는 지시들의 목록을 부주의하게 따르고, 거기에 표시나 지우기, 종이를 관찰하거나 다음 지시들에 대해 예스 노(Yes-No) 결정을 한다.[98] Entscheidungsprobroblem이 그의 "a-[자동] 기계"[99]를 사용함으로써 해결할 수 없다는 앨런 튜링의 증거는 사실상 Post의 "형식", J. Barkley Rosser의 "유효한 방법" 정의와 거의 일치한다.[100] 클린이 '합성 1호'라고 부른 '교회 논문'의 전구체를 제안했고,[101] 몇 년 뒤 클린이 자신의 논문을 '교회 논문'[102]으로 개명하고 '튜링 논문'을 제안했다는 것이다.[103]

에밀 포스트 (1936)와 앨런 튜링 (1936–37, 1939)

에밀 포스트(1936년)는 「컴퓨터」(인간)의 행동을 다음과 같이 기술했다.

"...문제에서 답으로 이어지는 작업을 수행하는 기호 공간과 변경할 수 없는 고정된 일련의 방향이라는 두 가지 개념이 관련되어 있다.

그의 상징적인 공간은

"공간이나 상자의 양방향 무한 시퀀스... 문제는 해결사나 노동자가 이 상징적인 공간에서 움직이고 일하는 것이다. 한 번에 한 박스씩 한 박스 안에서만 작동한다. 상자는 두 가지 조건만 인정하는 것이다. 즉, 빈 칸이거나 표지가 없는 칸이며, 그 안에 하나의 표시가 있는 칸은 세로 획이라고 한다.
"한 박스를 선별하여 출발점이라 한다.....특정 문제는 한정된 수의 박스[즉, 입력]가 스트로크로 표시됨으로써 상징적인 형태로 주어지는 것이다. 마찬가지로, [즉, OUTPUT]의 답은 그러한 마크 박스의 구성에 의해 상징적인 형태로 주어진다.
"일반적인 문제에 적용할 수 있는 일련의 방향은 각각의 특정 문제에 적용할 때 결정론적 과정을 설정한다. 이 프로세스는 유형(C )[즉, STOP]"[104]의 방향에 관해서만 종료된다. Post-Turing 기계에서 자세히 보기
블렛클리 공원에 있는 앨런 튜링의 동상

앨런 튜링의 작품은[105] 스티비츠(1937년)의 작품보다 앞서 있는데, 스티비츠가 튜링의 작품을 알았는지는 알 수 없다. 튜링의 전기 작가는 튜링이 젊은 시절의 관심에서 파생된 타자기와 같은 모델을 사용했다고 믿었다: "앨런은 어렸을 때 타이프라이터를 발명하는 꿈을 꾸었다; 미세스. 튜링은 타이프라이터를 가지고 있었고, 타이프라이터를 '기계적'[106]이라고 부르는 것이 무엇을 의미하는지 스스로에게 물어보는 것으로 시작할 수 있었을 것이다. 모스 부호와 전보, 티커 테이프 기계, 텔레타이프 작성기가 널리 보급되어 있는 것을 보면, 우리는[who?] 모든 것이 영향을 미쳤다고 추측할 수 있을 것이다.

튜링—그의 연산 모델은 현재 튜링 머신(Turing Machine)이라고 불리는데, 포스트가 그러했듯이, 간단한 기본 동작과 "마음 상태"로 요약한 인간 컴퓨터를 분석한 것이다. 그러나 그는 한 걸음 더 나아가서 숫자 계산의 모델로서 기계를 만든다.[107]

"컴퓨팅은 보통 종이에 특정 기호를 적어서 한다. 우리는 이 논문이 아이의 산수책처럼 정사각형으로 나뉘어져 있다고 생각할지도 모른다...그 때 나는 계산이 1차원 종이, 즉 정사각형으로 나뉜 테이프에서 수행된다고 가정한다. 또한 인쇄할 수 있는 기호의 수가 한정되어 있다고 가정할 것이다...
"어느 순간 컴퓨터의 행동은 그가 관찰하고 있는 기호, 그리고 그 순간의 그의 '정신 상태'에 의해 결정된다. 우리는 컴퓨터가 한 순간에 관찰할 수 있는 기호나 정사각형의 수에 B가 있다고 가정할 수 있다. 만약 그가 더 관찰하고 싶다면, 그는 연속적인 관찰을 사용해야 한다. 우리는 또한 고려해야 할 정신상태의 수가 한정되어 있다고 가정할 것이다...
"컴퓨터가 수행하는 작업이 너무 초보적이어서 더 이상 분단된 상상이 쉽지 않은 '단순 작업'으로 나눠진다고 상상해보자."[108]

튜링의 감소는 다음을 산출한다.

"따라서 간단한 운영에는 다음 사항이 포함되어야 한다.
"(a) 관측된 사각형 중 하나의 기호 변경
"(b) 이전에 관측된 정사각형 중 하나의 L 제곱 내에서 다른 정사각형으로 관측된 정사각형의 변경.

"이러한 변화들 중 일부는 필연적으로 정신상태의 변화를 불러일으킬지도 모른다. 따라서 가장 일반적인 단일 작동은 다음 중 하나로 간주해야 한다.

"(가) 심경의 변화 가능성과 함께 (가) 기호의 변화 가능성.
"(나) 관찰된 정사각형의 가능한 변화 (b)와 함께 가능한 정신 상태 변화"
"우리는 이제 이 컴퓨터의 일을 할 수 있는 기계를 만들지도 모른다."[108]

몇 년 후 튜링은 다음과 같은 강력한 표현으로 분석(합성, 정의)을 확대했다.

"함수는 어떤 순수하게 기계적인 과정에 의해 그 값이 발견될 수 있다면 "효과적으로 계산할 수 있다"고 한다. 이 생각을 직관적으로 이해하는 것은 꽤 쉽지만, 그럼에도 불구하고 좀 더 확실하고 수학적 표현 가능한 정의를 갖는 것은 바람직하다... [그는 괴델, 헤르브란트, 클레네, 처치, 튜링, 포스트에 관하여 위에서 제시한 정의의 역사를 상당히 논하고 있다] ... 우리는 기계에 의해 수행될 수 있는 순수하게 기계적인 과정으로 이해하면서 이 진술을 문자 그대로 받아들일 수 있다. 이러한 기계의 구조에 대한 수학적인 설명을 어떤 정상적인 형태로 하는 것이 가능하다. 이러한 사상의 발달은 저자의 계산 가능한 함수의 정의로 이어지고, 계산가능성 †의 식별으로 이어지며, 유효 계산가능성을 가지고 있다.
"1987 기계의 계산이 가능한 기능을 의미하기 위해 "계산 가능한 기능"이라는 표현을 사용해야 하며, "효과적으로 계산 가능한" 것은 이러한 정의 중 하나로 특별히 식별하지 않고 직관적인 아이디어를 가리킨다."[109]

J.B. 로서(1939년)와 SC. 클레네(1943)

J. 바클리 로서는 다음과 같은 방식으로 '유효한 [수학적] 방법'을 정의했다(활력화 추가).

'유효한 방법'은 여기에서 각 단계가 정밀하게 결정되고 유한한 수의 단계로 답을 산출할 것이 확실한 방법의 다소 특별한 의미로 사용된다. 이 특별한 의미와 함께, 지금까지 세 가지 다른 정확한 정의가 주어졌다. [그의 각주 #5; 바로 아래 토론을 참조하라]. 이것들 중 가장 간단한 것은 (Post and Turing 때문에) 본질적으로 어떤 문제를 해결하는 효과적인 방법이 존재한다고 말한다. 만약 어떤 사람이 기계를 만들 수 있다면, 질문을 삽입하고 답을 읽는 것 이상으로 사람이 개입하지 않고 문제를 해결할 수 있을 것이다. 세 가지 정의는 모두 동일하므로 어떤 정의가 사용되든 상관없다. 더욱이 세 가지 모두 등가라는 사실은 어느 한 가지에 대한 정확성에 대한 매우 강력한 주장이다.(Rosser 1939:225–226)

Rosser's footnote No. 5 references the work of (1) Church and Kleene and their definition of λ-definability, in particular Church's use of it in his An Unsolvable Problem of Elementary Number Theory (1936); (2) Herbrand and Gödel and their use of recursion in particular Gödel's use in his famous paper On Formally Undecidable Propositions of Principia Mathematica and Related Systems I(1931) 및 (3) Post(1936) 및 Turing(1936–37)의 연산 메커니즘 모델.

스티븐 C. 클레인은 Church-Turing 논문으로 알려진 현재 유명한 "Ethrogency I"로 정의했다. 그러나 그는 다음과 같은 맥락에서 이렇게 했다(원래로 볼드페이스).

"12. 알고리즘 이론... 완전한 알고리즘 이론을 설정할 때, 우리가 하는 일은 독립 변수의 각 값 집합에 대해 수행 가능한 절차를 설명하는 것이다. 어떤 절차는 반드시 종료되며, 그 결과로부터 "예" 또는 "아니오"라는 질문에 대한 명확한 답을 읽을 수 있는 방식으로, "예" 또는 "아니오"라는 질문을 하는 것이다."" (Kleene 1943:273)

1950년 이후의 역사

'알고리즘'의 정의를 더욱 정교하게 다듬기 위해 많은 노력을 기울였으며, 특히 수학의 기초(특히 교회-튜링 논문)와 정신 철학(특히 인공지능에 대한 주장)을 둘러싼 이슈 때문에 활동이 진행 중이다. 자세한 내용은 알고리즘 특성을 참조하십시오.

참고 항목

메모들

  1. ^ "Definition of ALGORITHM". Merriam-Webster Online Dictionary. Archived from the original on February 14, 2020. Retrieved November 14, 2019.
  2. ^ 데이비드 A. 그로스만, 오피르 프리더, 정보 검색: 알고리즘 및 휴리스틱스, 제2판, 2004, ISBN 1402030045
  3. ^ "예를 들어 모든 고전적인 수학 알고리즘은 한정된 수의 영어 단어로 설명할 수 있다."(로저스 1987:2)
  4. ^ 알고리즘을 실행하는 에이전트와 관련하여 잘 정의되어 있다: "명령에 반응하여 계산을 수행할 수 있는 컴퓨팅 에이전트가 대개 인간이다."(로거 1987:2)
  5. ^ "알고리즘은 함수를 계산하는 절차다. (정수에 대해 선택된 표기법 관련) ... 이 제한은 일반성의 손실을 초래하지 않는다." (로저스 1987:1)
  6. ^ "알고리즘은 0개 이상의 입력, 즉 알고리즘이 시작되기 전에 처음 주어진 양을 가지고 있다."(Knuth 1973:5)
  7. ^ "정밀성이 결여되었을 가능성이 있는 경우를 제외하고 알고리즘의 모든 특성을 갖는 절차를 '계산법'(Knuth 1973:5)이라고 할 수 있다.
  8. ^ "알고리즘에는 하나 이상의 출력물, 즉 입력과 관련된 특정 수량이 있다."(Knuth 1973:5)
  9. ^ 무작위 내부 프로세스가 있는 프로세스가 알고리즘인지 아닌지는 논쟁의 여지가 있다. 로저스는 다음과 같이 주장한다. "연속적인 방법이나 아날로그 장치를 사용하지 않고 개별적인 단계적 방식으로 연산이 수행된다... 무작위적인 방법이나 장치(예: 주사위)에 의존하지 않고 결정적으로 진행되었다"(로저스 1987:2)
  10. ^ a b c Chabert, Jean-Luc (2012). A History of Algorithms: From the Pebble to the Microchip. Springer Science & Business Media. pp. 7–8. ISBN 9783642181924.
  11. ^ a b c Cooke, Roger L. (2005). The History of Mathematics: A Brief Course. John Wiley & Sons. ISBN 978-1-118-46029-0.
  12. ^ a b Dooley, John F. (2013). A Brief History of Cryptology and Cryptographic Algorithms. Springer Science & Business Media. pp. 12–3. ISBN 9783319016283.
  13. ^ "Al-Khwarizmi biography". www-history.mcs.st-andrews.ac.uk. Archived from the original on August 2, 2019. Retrieved May 3, 2017.
  14. ^ "Etymology of algorithm". Chambers Dictionary. Archived from the original on March 31, 2019. Retrieved December 13, 2016.
  15. ^ Hogendijk, Jan P. (1998). "al-Khwarzimi". Pythagoras. 38 (2): 4–5. Archived from the original on April 12, 2009.
  16. ^ Oaks, Jeffrey A. "Was al-Khwarizmi an applied algebraist?". University of Indianapolis. Archived from the original on July 18, 2011. Retrieved May 30, 2008.
  17. ^ Brezina, Corona (2006). Al-Khwarizmi: The Inventor Of Algebra. The Rosen Publishing Group. ISBN 978-1-4042-0513-0.
  18. ^ Carl B에 따르면 역사상 가장 중요한 수학 문헌들이 2011년 6월 9일 웨이백 기계에 보관되어 있다고 한다. 보이어.
  19. ^ "algorismic", The Free Dictionary, archived from the original on December 21, 2019, retrieved November 14, 2019
  20. ^ 옥스포드 영어사전, 2012년 3월호
  21. ^ Mehri, Bahman (2017). "From Al-Khwarizmi to Algorithm". Olympiads in Informatics. 11 (2): 71–74. doi:10.15388/ioi.2017.special.11.
  22. ^ "Abu Jafar Muhammad ibn Musa al-Khwarizmi". members.peak.org. Archived from the original on August 21, 2019. Retrieved November 14, 2019.
  23. ^ 1965년 데이비스 주의 클레인 1943:274
  24. ^ 1965년 데이비스의 로서 1939년 2월 25일
  25. ^ 스톤 1973:4
  26. ^ Simanowski, Roberto (2018). The Death Algorithm and Other Digital Dilemmas. Untimely Meditations. 14. Translated by Chase, Jefferson. Cambridge, Massachusetts: MIT Press. p. 147. ISBN 9780262536370. Archived from the original on December 22, 2019. Retrieved May 27, 2019. [...] the next level of abstraction of central bureaucracy: globally operating algorithms.
  27. ^ Dietrich, Eric (1999). "Algorithm". In Wilson, Robert Andrew; Keil, Frank C. (eds.). The MIT Encyclopedia of the Cognitive Sciences. MIT Cognet library. Cambridge, Massachusetts: MIT Press (published 2001). p. 11. ISBN 9780262731447. Retrieved July 22, 2020. An algorithm is a recipe, method, or technique for doing something.
  28. ^ 스톤은 단순히 "제한된 수의 스텝으로 종료되어야 한다"고 요구한다(Stone 1973:7–8).
  29. ^ 볼로스와 제프리 1974,1999:199
  30. ^ cf 스톤 1972:5
  31. ^ 크누스 1973:7은 다음과 같다: "실제로 우리는 알고리즘을 원할 뿐만 아니라, 좋은 알고리즘을 원한다... 선의 한 가지 기준은 알고리즘을 수행하는 데 걸리는 시간이다... 다른 기준은 컴퓨터에 대한 알고리즘의 적응성, 단순성, 우아성 등이다.
  32. ^ cf 스톤 1973:6
  33. ^ 스톤 1973:7–8에 따르면, 로봇[즉, 컴퓨터]이 명령을 따르는 정확한 방법을 결정하기 위해 따를 수 있는 절차가 있어야 한다. 스톤은 이 정의에 공정의 정밀성을 더하고, 명확성(지침에 모호함이 없음)을 더한다.
  34. ^ 크누스, loc. cit
  35. ^ 민스키 1967, 페이지 105
  36. ^ 구레비치 2000:1, 3
  37. ^ 시퍼 2006:157
  38. ^ Goodrich, Michael T.; Tamassia, Roberto (2002), Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley & Sons, Inc., ISBN 978-0-471-38365-9, archived from the original on April 28, 2015, retrieved June 14, 2018
  39. ^ 크누스 1973:7
  40. ^ 차이틴 2005:32
  41. ^ 로저스 1987:1-2
  42. ^ 그의 에세이 "인간과 기계에 의한 계산: 개념 분석" Seig 2002:390은 로빈 간디, cf Wilfred Seig, 등, 2002 Reflections와 수학의 기초에 대한 성찰: 솔로몬 페퍼먼을 기리는 에세이, A.K. Peters Ltd, MA.
  43. ^ cf 간디 1980:126, 로빈 간디 교회가 J. 바와이즈 외 1980년 클라인 심포지엄 북홀랜드 출판사에서 123–148페이지에 등장하는 메커니즘에 대한 논문과 원리.
  44. ^ a "로봇" : "컴퓨터는 명령의 연속이라고 표현할 수 있는 모든 작업을 수행하는 로봇이다."cf 스톤 1972:3
  45. ^ 램벡의 '아바쿠스'는 카운터의 무제한 공급(페블스, 구슬 등)과 함께 "카운터(구멍, 전선 등)가 무한히 많은 곳"이다. 그 장소들은 구별할 수 있고, 카운터는 그렇지 않다." 그 구멍들은 무한정 용량이 있으며, 대기하고 있는 것은 지시사항 목록을 이해하고 수행할 수 있는 요원이다."(람베크 1961:295) 람벡은 자신의 Q-머신을 "무한히 많은 장소 ... 이 장소들 사이에 배포된 무한정 많은 카운터, 프로그램, 그리고 프로그램을 수행하는 유일한 목적이 있는 운영자의 공급"이라고 정의한 멜작(Melzak 1961:283)을 언급한다.B-B-J(Loc. cit)는 이 구멍들이 "홀딩이 가능한"이라는 규정을 덧붙인다.ny ny number of stone" (46 페이지) 멜작과 람베크 둘 다 1961년 9월 제4권 제3호 캐나다 수학 회보에 등장한다.
  46. ^ 혼동이 일어나지 않을 경우 "상담자"라는 단어를 삭제할 수 있으며, 위치에는 "번호"가 한 개 포함되어 있다고 말할 수 있다.
  47. ^ "우리는 로봇이 명령을 준수하는 방법을 정확하게 결정하기 위해 따를 수 있는 절차가 있다면 명령이 효과적이라고 말한다."(스톤 1972:6)
  48. ^ cf Minsky 1967: 11장 "컴퓨터 모델" 및 14장 "계산성에 대한 매우 단순한 기반" 페이지 255–281 특히,
  49. ^ cf 크누스 1973:3.
  50. ^ 그러나 부적절한 뺄셈을 피하기 위해 항상 IF-THEN이 선행한다.
  51. ^ 크누스 1973:4
  52. ^ 돌 1972:5. 뿌리를 추출하는 방법은 사소한 것이 아니다: 제곱근을 계산하는 방법을 참조하십시오.
  53. ^ Leeuwen, Jan (1990). Handbook of Theoretical Computer Science: Algorithms and complexity. Volume A. Elsevier. p. 85. ISBN 978-0-444-88071-0.
  54. ^ 존 G. 케메니와 토마스 E. 커츠 1985년 Back to Basic: Adison-Wesley Publishing Company, Inc. 언어의 역사, 부패, 그리고 미래 리딩, MA, ISBN 0-201-13433-0
  55. ^ 타우스워테 1977:101
  56. ^ 타우스워테 1977:142
  57. ^ Knuth 1973 섹션 1.2.1, 1977년 Tausworthe 100f 및 9.1페이지에서 확장.
  58. ^ cf 타우스워테 1977년
  59. ^ 히스 1908:300; 호킹의 도버 2005판은 히스에서 유래되었다.
  60. ^ 'BF를 재는 CD를 자기보다 적게 FA를 떠나게 하라.' 이것은, 남은 길이 FA가 CD보다 작도록 F 지점에 도달할 때까지 CD와 동일한 BA 연속 길이를 측정한다는 단어의 깔끔한 약어다. 즉, BF를 BA에 포함된 CD의 가장 큰 정확한 배수가 되도록 하라."(Heath 1908:297)
  61. ^ 알고리즘의 분열을 이용한 현대적 치료는 Hardy와 Wright 1979:180, Knuth 1973:2 (Volume 1) 및 Knuth 1969:293–297 (Volume 2)에서 유클리드 알고리즘에 대한 자세한 논의를 참조한다.
  62. ^ 유클리드는 이 문제를 그의 발의안 1에서 다룬다.
  63. ^ "Euclid's Elements, Book VII, Proposition 2". Aleph0.clarku.edu. Archived from the original on May 24, 2012. Retrieved May 20, 2012.
  64. ^ 이 개념은 널리 사용되고 있지만, 정확하게 정의될 수는 없다.
  65. ^ 크누스 1973:13–18. 그는 R. Floyd, Peter Naur, C.A.R. Hoare, H.H. Goldstine, J. von Neumann에게 "주장 및 유도 측면에서 알고리즘 검증의 공식화"를 인정한다. Tausworth 1977은 Knuth의 유클리드 예를 빌리고 9.1 Formal Proofs (pp. 288–298)절에서 Knuth의 방법을 확장한다.
  66. ^ 타우스워테 1997:294
  67. ^ cf Knuth 1973:7 (Vol. I), 그리고 1969:294–313페이지에 대한 그의 자세한 분석(Vol II)
  68. ^ 알고리즘이 스스로 압축을 시도할 때 파괴가 발생한다. 성공은 할팅 문제를 해결할 것이다.
  69. ^ Kriegel, Hans-Peter; Schubert, Erich; Zimek, Arthur (2016). "The (black) art of run-time evaluation: Are we comparing algorithms or implementations?". Knowledge and Information Systems. 52 (2): 341–378. doi:10.1007/s10115-016-1004-2. ISSN 0219-1377. S2CID 40772241.
  70. ^ Gillian Conahan (January 2013). "Better Math Makes Faster Data Networks". discovermagazine.com. Archived from the original on May 13, 2014. Retrieved May 13, 2014.
  71. ^ Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price, "ACM-SIAM 이산 알고리즘 심포지엄(SODA) 2013년 7월 4일 교토 웨이백머신에 보관되었다. 2012년 2월 21일 웨이백 머신에 보관된 sFT 웹 페이지도 참조하십시오.
  72. ^ 코왈스키 1979년
  73. ^ Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Knapsack Problems Hans Kellerer Springer. Springer. doi:10.1007/978-3-540-24777-7. ISBN 978-3-540-40286-2. Archived from the original on October 18, 2017. Retrieved September 19, 2017.
  74. ^ Carroll, Sue; Daughtrey, Taz (July 4, 2007). Fundamental Concepts for the Software Quality Engineer. American Society for Quality. pp. 282 et seq. ISBN 978-0-87389-720-4.
  75. ^ 예를 들어, 볼록 다면체(회원 신탁을 사용하여 묘사했다)의 볼륨 높은 정밀도에 임의 추출된 다항 시간 알고리즘이 아니라 결정론적인 사람에 의해:다이어, 마틴, 프리즈, 앨런, Kannan, 라비(1월 1991년),"A랜덤 Polynomial-time 알고리즘 볼록 사업의 시행 주체별 볼륨 Approximating에", J.ACM, 3할 수 있다.8(1):1–17, CiteSeerX 10.1.1.145.4600, doi:10.1145/102782.102783, S2CID 13268711.
  76. ^ 조지 B. 단치히와 무쿤드 N. 타파. 2003. 선형 프로그래밍 2: 이론과 확장. 스프링거-베를라크.
  77. ^ Tsypkin (1971). Adaptation and learning in automatic systems. Academic Press. p. 54. ISBN 978-0-08-095582-7.
  78. ^ Knuth, Donald E. (1972). "Ancient Babylonian Algorithms" (PDF). Commun. ACM. 15 (7): 671–677. doi:10.1145/361454.361514. ISSN 0001-0782. S2CID 7829945. Archived from the original (PDF) on December 24, 2012.
  79. ^ Aaboe, Asger (2001), Episodes from the Early History of Astronomy, New York: Springer, pp. 40–62, ISBN 978-0-387-95136-2
  80. ^ Ast, Courtney. "Eratosthenes". Wichita State University: Department of Mathematics and Statistics. Archived from the original on February 27, 2015. Retrieved February 27, 2015.
  81. ^ Chabert, Jean-Luc (2012). A History of Algorithms: From the Pebble to the Microchip. Springer Science & Business Media. p. 2. ISBN 9783642181924.
  82. ^ 데이비스 2000:18
  83. ^ 볼터 1984:24
  84. ^ 볼터 1984:26
  85. ^ 볼터 1984:33–34, 204–206.
  86. ^ W. Stanley Jevons 1880의 논리의 모든 인용구: 연역 및 귀납, 맥밀란 및 주식회사, 런던 및 뉴욕. 구글북으로 재출간; cf Jevons 1880:199–201. Louis Couturat 1914년 Logic 대수학, The Open Court 출판사, 시카고와 런던. 구글북으로 재출간; cf Couturat 1914:75–76은 몇 가지 더 자세한 내용을 제공한다; 그는 이것을 피아노뿐만 아니라 타자기와 비교한다. Jevons는 그 계정이 1870년 1월 20일에 발견될 것이라고 말한다.
  87. ^ 제본 1880:199–200
  88. ^ 모든 인용구는 런던 맥밀런과 주식회사 존 벤 1881 심볼 로직에서 인용한 것이다. 구글북으로 재출판. cf Venn 1881:120–125. 관심 있는 독자는 그 페이지에서 더 깊은 설명을 찾을 수 있다.
  89. ^ 벨과 뉴웰 다이어그램 1971:39, cf. 데이비스 2000
  90. ^ * Melina Hill, Valley News 특파원, A Tinkerer Get a Place in History, Valley News West Leven NH, 1983년 3월 31일 목요일, 페이지 13.
  91. ^ 데이비스 2000:14
  92. ^ 반 헤이제노르트 1967:81ff
  93. ^ 반 헤이제노르트의 산술적 언어인 프레게의 베그리프슈크리프트에 대한 해설은 반 헤이제노르트 1967:1의 순수한 사상을 위해 산술적 언어를 모델로 했다.
  94. ^ 딕슨 1906, cf. 클레인 1952:36–40
  95. ^ cf. 데이비스의 알론조 교회 1936a에 각주 1965:90, 데이비스의 1936b에 1965:110
  96. ^ 1935-6년(Davis 1965:237ff), 1943년(Davis 1965:255ff)의 클레네
  97. ^ 1936년 데이비스 주의 교회 1965:88ff
  98. ^ cf. "완료 결합 프로세스 – 제1편", 1965년 데이비스:289–290년 포스트 1936
  99. ^ 1965년 데이비스에서 튜링 1936-37:116f
  100. ^ 1965년 데이비스의 로서 1939:226
  101. ^ 1965년 데이비스 주의 클레인 1943:273–274
  102. ^ 클레네 1952:300, 317
  103. ^ 클레네 1952:376
  104. ^ 1965년 데이비스의 튜링 1936-37:289–290
  105. ^ 1965년 데이비스의 튜링 1936년, 1939년 데이비스의 튜링 1965:160
  106. ^ 호지스 96쪽
  107. ^ 튜링 1936-37:116
  108. ^ a b 1965년 데이비스의 튜링 1936-37:136
  109. ^ 1965년 데이비스의 튜링 1939:160

참고 문헌 목록

추가 읽기

외부 링크

알고리즘 저장소