최상의 답변
이에 대한 답이 없습니다.
이 문제 설명에 대한 답을 찾아 보겠습니다.
Q. 어떤 알고리즘이 더 잘 작동하는지 찾는 방법은 무엇입니까?
A. 알고리즘을 비교하는 가장 일반적인 방법 :
1) 시간 복잡성
2) 공간 복잡성
3) 솔루션 품질 (아마도 문제를 정확히 해결하기 위해 제안하는 경우 적용 가능). 이것은 근사 알고리즘을 말하는 경우 큰 요인이 될 수 있습니다.
4) 구현의 용이성 / 알고리즘의 적응. 일부 알고리즘은 올바르게 구현하는 데 많은 오버 헤드가있을 수 있습니다. 때로는 더 적합한 알고리즘이 있습니다. 예를 들어 병렬 컴퓨팅에서 Bellman-Ford가 작동하는 방식으로 인해 대부분의 사람들은 Bellman-Ford가 Dijkstra의 알고리즘보다 더 유용하다는 것을 알게 될 것입니다.
그러나 시간과 복잡성은
* 항상 * 최대화 할 바람직한 기능 두 가지 예를 제시하겠습니다.
하나는 선형 대수와 미분 방정식의 알고리즘 기능인 “수치 안정성”입니다. 수치 적으로 더 안정적인 알고리즘에 더 많은 알고리즘 시간과 더 많은 알고리즘 복잡성을 모두 소비 할 것입니다. 선형 대수학에서 불안정성은 일반적으로 알고리즘이 0이나 무한대 또는 둘 다에 너무 가까운 숫자를 만날 때 발생합니다. 숫자 해상도의 유한 표현이 손실 될 수 있기 때문입니다. 일반적으로 이것은 매우 약간 다른 숫자를 유발합니다. 서로 다른 몇 개의 엡실론 (여기서 엡실론은 기계에서 하나에 추가 할 수있는 가장 작은 숫자입니다! = 1)에서 큰 차이를 생성합니다. 대답. 예를 들어, 안정적인 알고리즘을 얻기 위해 LU 분해를 “피벗”함으로써 많은 시간과 공간 복잡성을 소비합니다. 피벗없이 LU는 안정적이지 않습니다. 마찬가지로 불안정성을 피하기 위해 “조건”행렬 만 수행하는 알고리즘이 있습니다.
두 번째 예는 “견고성” in입니다. 기술적 통계적 의미. 견고성은 이상 값에 민감하지 * 않는 * 측정 값 또는 알고리즘을 의미합니다. 예를 들어, 점 집합에 최소 제곱 선을 맞추면 선이 매우 큰 단일 값에 의해 심하게 왜곡 될 수 있습니다. 완벽한 45도 선을 형성하는 99 쌍의 숫자가 있더라도 Y 값이 같은 선에 “해야하는”것의 100 배에 해당하는 단일 이상 값 쌍을 추가하면 적합 선이 심각하게됩니다. 45도 선에서 기울어졌습니다. 알고리즘은 하나의 특이점을 더 잘 표현하기 위해 99 점에 대한 완벽한 적합을 “포기”합니다. 이는 강력하지 * 않습니다 *.
강력한 최소 제곱 접근 방식은 해당 선을 사용하여 생성 된 제곱 오차의 합을 최소화하는 선을 찾는 대신 * 중앙값 *을 최소화하는 선을 찾는 것입니다. 그 선을 사용하여 생성 된 제곱 오차. 이 예에서 해당 선은 45도 선이고 제곱 오차의 중앙값은 0이며 이상 값 지점 (실제로 최대 98 개 이상의 이상 값)은 완전히 무시됩니다. 45도 선이 발견됩니다.
통계 곡선을 맞추고, 모양을 찾는 등의 강력한 알고리즘이 있습니다. 그러나 시간이 많이 걸리며 때로는 심각하게 그렇게합니다. 그러나 강력한 통계는 최소 제곱 오차 접근 방식이 아닌 신호의 “노이즈”에 효과적으로 영향을받지 않기 때문에 시간 비용은 그만한 가치가 있습니다. 현실 세계는 노이즈와 이상치로 가득 차 있으며, 그중 일부는 특히 픽셀 화 된 이미지 나 샘플링 된 사운드에서 사람 또는 기계 오류로 인해 발생합니다. 이러한 상황에서 더 많은 시간이 소요되는 강력한 알고리즘은 더 빠른 알고리즘이 노이즈로 인해 손상되어 쓸모 없거나 받아 들여지면 위험 할 수있는 응답을 생성하는 시끄러운 환경에서 신호를 찾을 수 있습니다.
경우에 따라 시간이 그리고 공간 복잡성은 신호의 잡음과 저하에도 불구하고 실제 신호를 모델링 할 가능성이 가장 높은 답을 찾는 것만 큼 중요하지 않습니다.
답변
수학에서 유래 한 알고리즘은 “레시피”입니다. 함수 기반 계산을 수행하기 위해 기계적으로 따를 수 있습니다. 함수 기반 수학적 세계관에서 모든 입력은 계산이 시작될 때 지정되어야하며 이는 닫힌 상자 방식으로 진행됩니다. 알고리즘 설명은 단일 언어 나 형식에 국한되지 않기 때문에 알고리즘의 개념은 본질적으로 비공식적입니다.
가장 오래된 예는 공약수를 찾는 Euclid의 알고리즘 일 것입니다. 알고리즘은 계산이 “효과적”이라는 의미를 포착합니다. 수학적 공식과 마찬가지로 알고리즘은 값을 계산하는 방법을 알려줍니다. 그들과 달리 알고리즘은 우리가 지금 루프 또는 분기라고 부르는 것을 포함 할 수 있습니다.
알고리즘의 역할 : 유한 입력 값 x가 주어지면 알고리즘은이를 출력 값 y로 효과적으로 변환하는 단계를 설명합니다. 여기서 y는 일부 재귀 함수에 대한 f (x) f.
알고리즘은 1950 년대 초기 컴퓨터 과학자들에 의해 채택되었으며, 알고리즘과 Turing Machines (TM, 1936 년까지 거슬러 올라가는 공식적인 계산 모델)를 연결하여 표현력을 동일시했습니다.
Knuth의 유명하고 영향력있는 교과서 인 “The Art of Computer Programming, Vol. 1″은 1960 년대 후반 컴퓨터 과학에서 알고리즘의 중심성을 대중화했습니다. 그의 알고리즘 정의에서 Knuth는 계산 이론의 수학적 함수 기반 기반과 일치했습니다. “효과적인 계산 방법 (예 : TM 사용)의 개념을 공식화하는 본질적으로 동등한 다른 많은 방법이 있습니다.”
Knuth는 알고리즘이 닫혀 있음을 명시 적으로 지정했습니다. 계산이 시작되면 새로운 입력은 허용되지 않습니다. “알고리즘에는 0 개 이상의 입력이 있습니다. 즉, 알고리즘이 시작되기 전에 처음에 주어진 양입니다.” 그는 I / O를 포함 할 수있는 임의의 계산과 알고리즘을 구별했습니다. 그가 알고리즘이 아닌 문제에 대해 제시 한 한 가지 예는 레시피에서 다음과 같은 지시 사항입니다. “혼합물이 부서 질 때까지 가볍게 던지십시오.” 컴퓨터가 혼합 시간을 알 수 없기 때문에이 문제는 알고리즘이 아닙니다. 이는 사전에 확실하게 예측할 수없는 습도와 같이 동적으로 변화하는 하나의 외부 조건에 따라 달라질 수 있습니다.
알고리즘의 정확한 개념에 대한 동의는 없지만 Knuth의 알고리즘 논의는 결정적입니다.
p>
알고리즘을 지정하기 위해 명시 적으로 개발 된 최초의 고급 프로그래밍 언어는 ALGOL (ALGOrithmic Language)입니다. 50 년대 후반에 도입되어 1960 년대까지 개선되어 알고리즘 출판의 표준으로 사용되었습니다. 알고리즘의 함수 기반 개념화에 충실하게, ALGOL은 알고리즘의 문제를 벗어난 이러한 작업을 고려하여 입력 및 출력에 대한 구성을 제공하지 않았습니다. (당연히 이러한 부재로 인해 업계에서 상용 응용 프로그램을 위해 ALGOL을 채택하는 데 방해가되었습니다.)
1960 년대에는 학부 컴퓨터 과학 (CS) 프로그램이 급증했습니다. ACM (Association for Computing Machinery)에 따르면 미국의 CS 프로그램 수는 1964 년 11 개에서 1968 년 92 개로 증가했습니다. 이러한 증가는 학계의 눈에이 새로운 학문의 정당성을 확립하기위한 강렬한 활동을 동반했습니다. 커뮤니티. ACM은이 활동에서 중심적인 역할을했습니다. 1965 년에는 학부 CS 프로그램에 대한 1968 년 권장 사항의 기반이 된 CS의 정당화 및 설명을 원칙으로 발표했습니다.
CS에 대한 ACM의 설명은 정보의 효과적인 변환을 핵심 관심사로 확인했습니다. ” 컴퓨터 과학은 물리학이 에너지와 관련된 것과 거의 같은 의미에서 정보와 관련이 있습니다. 컴퓨터 과학자는 정보를 변환 할 수있는 실용적인 수단을 발견하는 데 관심이 있습니다.” 이 설명은 입력을 출력으로 효과적으로 변환하기위한 “조리법”이기 때문에 알고리즘을 컴퓨터 과학의 중심에 둡니다. 실제로 ACM은 보고서의 다음 문장에서 알고리즘에 중점을 두었습니다.
“이 관심은 정보를 표현하는 효과적인 방법, 정보를 변환하는 효과적인 알고리즘, 표현할 효과적인 언어에 대한 탐구로 이어집니다. 알고리즘 … 그리고 합리적인 비용으로이를 달성 할 수있는 효과적인 방법.”
물리학의 에너지에 대한 관심과 유사한 중앙 알고리즘 관심사는 CS를 합법적 인 학문 분야로 확립하는 데 도움이되었습니다. 물리학. 알고리즘은 오늘날까지 컴퓨터 과학의 중심으로 남아 있습니다.
해결 가능한 문제를 정의하는 비공식 (알고리즘 기반) 및 공식 (TM 기반) 접근 방식의 공존은 오늘날까지 지속되고 있으며 다음에서 찾을 수 있습니다. 알고리즘 또는 계산 가능성에 관한 모든 현대 교과서. 이것은 컴퓨터 과학자들에게 매우 편리하다는 것이 증명되었습니다. 우리가 “의사 코드”를 사용하여 비공식적으로 알고리즘 계산을 설명 할 수있게함으로써 동등한 튜링 머신을 구성 할 수 있다는 것을 알고 있습니다.
− 가능하다면 문제를 해결할 수 있습니다. 알고리즘에 의해 지정됩니다. − Turing Machine이 있으면 문제를 해결할 수 있습니다.
이론가와 교육자들이 CS의 중심에 알고리즘을 배치하기로 한 1960 년의 결정은 초기 학부 교과서에 명확하게 반영되었습니다. 그러나 알고리즘에 대한 명시적인 표준 정의가 없었고 다양한 교과서에서이 용어를 다르게 정의했습니다. Knuth와 같은 일부 교과서는 알고리즘을 함수를 계산하는 것으로 명시 적으로 제한하여 Turing Machines와 동일하지만 대부분의 이론 책은이 제한을 암시하지만 명시하지 않았습니다.
초기 예는 다음과 같습니다. 1969 년의 Hopcroft와 Ullman의 교과서, 이후 버전은 오늘날까지 사용되고 있습니다.“절차는 컴퓨터 프로그램과 같이 기계적으로 수행 할 수있는 유한 한 일련의 명령입니다.항상 종료되는 절차를 알고리즘이라고합니다.”
알고리즘에 대한이 설명은 음식 준비와 같은 비 기능적 계산을 명시 적으로 배제하지 않습니다. 그러나 다양한 문제의 예를 통해 함수 기반 계산 만 고려했음을 분명히 알 수 있습니다. 실제로 그들은 ALGOL을 예제로 사용했는데, 입력과 출력에 대한 구조도 제공하지 않았습니다.
60 년대 후반부터 실제로 사용하고 CS 프로그램에서 가르치는 고급 프로그래밍 언어는 더 이상 사용되지 않았습니다. 초기 ALGOL의 알고리즘 제한에 구속됩니다. 운영 체제, 그래픽 사용자 인터페이스, 자동 차량 및 기타 로봇과 같은 컴퓨팅 전반에 걸쳐 지속적인 방식으로 환경과 상호 작용하는 프로그램을 작성할 수 있습니다.
그에 대한 응답으로 Rice와 같은 현대 프로그래밍 교과서 및 Rice (1969)는 비 기능적 문제를 포함하도록 알고리즘의 개념을 명시 적으로 확장했습니다. 함수 계산에만 국한하지 않고 알고리즘의 중심성을 반영하는이 접근 방식은 비 이론 교과서의 전형이되었습니다. 이 교과서의 주제는 계산 이론이 아닌 프로그래밍 방법론이며, 우리의 계산 모델을 뒷받침하는 수학적 원리는 실용성을 위해 제외되었습니다.
표면적으로 알고리즘의 정의 Rice and Rice 및 기타 교과서의 경우 Hopcroft 및 Ullman과 다르지 않습니다.“알고리즘은 레시피, 지침 집합 또는 작업을 수행하기위한 프로세스의 사양입니다. 그것은 보통 어떤 종류의 문제를 해결하는 것입니다.” 그러나 계산 가능한 문제의 예는 더 이상 함수 기반이 아니며 Knuth가 거부 한 종류의 계산 만 인정합니다. 알고리즘으로 해결할 수있는 두 가지 예는 감자 보드카를 만들고 도랑을 모래로 채우는 것입니다. Knuth는 두 가지 모두를 거부했을 것입니다.
이 교과서는 “알고리즘”에 대해 초월 명상이 동등하다고 주장하지 않았습니다. 그러나 학생들은 이러한 알고리즘 개념이 Knuth의 개념과 다르며 계산 가능한 것으로 간주되는 일련의 문제가 확대되었다는 사실을 인식하지 못했습니다. 알고리즘 (및 따라서 계산 가능한 문제)의 더 광범위하고 실용적인 개념화를 초월 명상으로 매우 계산 가능한 문제를 계산할 수 있다고 주장하는 이론과 결합함으로써 알고리즘 중심의 CS 커리큘럼은 학생들에게이 광범위한 문제 집합이 가능하다는 잘못된 인상을 남겼습니다. 또한 TM에 의해 해결됩니다.
실용적인 컴퓨터 과학자들은 오랫동안 Rice와 Rice의지도를 따르고 함수 계산을 넘어 알고리즘의 개념을 넓혔지만 이론적 인 컴퓨터 과학은 프레임이라는 수학적 세계관을 유지했습니다. 함수 기반으로 계산하고 그에 따라 계산 문제에 대한 개념을 구분합니다. 이것은 적어도 학부 수준에서는 사실입니다. 그 결과 컴퓨터 과학 커뮤니티는 알고리즘을 일반적인 계산 개념 ( “컴퓨터가하는 일”)과 동의어로 생각하면서도 동시에 Turing Machines와 동등하다고 생각하는 이분법입니다.
나는 생각했습니다. 나는 사람들이이 이분법을 알게하기 위해이 긴 답을 써야했다. 처음에 말했듯이 알고리즘의 개념은 비공식적입니다. 우리는 그것을 함수의 계산 (또는 Turing Machines)과 동등하다고 생각할 수도 있고, 운영 체제 나 자동 자동차와 같은 실시간 대화 형 프로그램을 포함하여 프로그램을 작성할 수있는 모든 것으로 생각할 수 있습니다. 그러나 일반적인 혼동에도 불구하고 두 정의는 동일하지 않습니다.