The Design and Analysis of Computer Algorithms 사본이 오늘 도착했습니다. 첫 번째 장에서 저자는 Turing Machines를 소개했습니다. 두 알고리즘의 다른 교과서 인 Introduction to Algorithms과 The Algorithm Design Manual이 있지만 알고리즘과 데이터 구조라는 주제로 유명한 튜링 기계에 대해서는 언급하지 않았습니다.튜링 머신과 관련된 알고리즘 및 데이터 구조는 어떻습니까?
Turing Machine과 Algorithm/Datastructure의 관계는 무엇입니까? 알고리즘에서 전문가가되는 튜링 기계를 이해하는 것이 정말로 중요합니까?
데이터 구조와 알고리즘을 설명 할 때 튜링 기계가 중요한 이유는 알고리즘이 무엇인지 설명 할 수있는 수학적 모델을 제공하기 때문입니다. 대부분의 알고리즘은 고수준 언어 또는 의사 코드를 사용하여 설명됩니다. 이 알고리즘이 어떻게 작동하는지 쉽게 알이 설명에서
Set max = -infinity
For each element in the array:
If that element is greater than max:
Set max equal to that element.
를, 그리고 소스 코드로 번역하기 쉬울 것이다 : 예를 들어,이 같은 배열의 최대 값을 찾기 위해 알고리즘을 설명 할 수 있습니다. 그러나이 설명을 작성했다고 가정 해 보겠습니다.
Guess the index at which the maximum element occurs.
Output the element at that position.
유효한 알고리즘입니까? 즉, 우리는 "색인을 추측하여"그것이 의미하는 바를 엄격하게 정의 할 수 있습니까? 우리가 이것을 허락한다면 얼마나 오래 걸릴까요? 허용하지 않으면 왜 안 되니? 두 번째 설명과 다른 점은 무엇입니까?
알고리즘을 수학적으로 엄격하게 정의하려면 컴퓨터 작동 방식과 수행 할 수있는 기능에 대한 공식 모델이 필요합니다. 튜링 기계는 공식적으로 계산을 정의하는 일반적인 방법 중 하나입니다 (register machines, 문자열 재 작성 시스템, 교회의 lambda calculus 등). 계산의 수학적 모델을 정의하고 나면 유효한 알고리즘 설명의 종류, 즉 우리의 계산 모델을 사용하여 구현할 수있는 알고리즘 설명.
많은 최신 알고리즘은 근본적인 계산 모델의 속성에 크게 의존합니다. 예를 들어 cache-oblivious algorithms은 계산 모델에 알 수없는 크기의 메모리 버퍼와 2 계층 메모리가 있다고 가정합니다. 일부 알고리즘에서는 기본 시스템이 transdichotomous이어야합니다. 즉, 시스템 단어의 크기가 최소한 문제의 크기를 유지할만큼 커야 함을 의미합니다. 무작위 알고리즘은 임의성의 공식 정의와 기계가 임의의 값을 사용하는 방법을 필요로합니다. 비 결정적 알고리즘에는 비 결정적 계산을 지정하는 수단이 필요합니다. 회로에 기반한 알고리즘은 어떤 회로 프리미티브가 허용되는지, 허용되지 않는지를 알아야합니다. 양자 컴퓨터는 어떤 연산이 허용되는지, 허용되지 않는지에 대한 정식 정의가 필요하며, 알고리즘의 정의에는 출력이 확률 적으로 주어집니다.분산 알고리즘에는 여러 컴퓨터에서 공식적인 통신 정의가 필요합니다.
요약하면 알고리즘을 설명 할 때 허용되는 것과 허용되지 않는 것에 대해 명시해야합니다. 그러나 좋은 프로그래머이거나 알고리즘을 확실하게 이해하려면 튜링 기계를 안팎으로 알아야 할 필요가 없으며이를 사용하여 특정 문제를 인코딩하는 방법에 대한 구체적인 세부 사항을 알아야 할 필요가 없습니다 . 당신이 알아야 할 것은 계산의 모델이 할 수 있고 할 수없는 것이고, 작업 당 비용은 무엇인가하는 것입니다. 이렇게하면 얼마나 효율적인 알고리즘인지, 얼마나 많은 다양한 리소스 (시간, 공간, 메모리, 통신, 임의성, 비 결정론 등)를 사용하는지 추론 할 수 있습니다. 그러나 기본 모델을 이해하지 못한다면 당황하지 마십시오.
계산의 기본 모델에 대해 생각해보아야 할 한 가지 이유가 있습니다. 모든 계산 모델에는 한계가 있으며 경우에 따라 특정 알고리즘이 특정 문제에 대해 존재할 수 없거나 일부 문제를 해결하는 알고리즘이 일정량의 특정 리소스를 사용해야한다는 것을 증명할 수 있습니다. 알고리즘 설계에서 NP 경도의 개념이 나오는 가장 일반적인 예입니다. 일부 문제는 해결하기가 극도로 어렵다고 추측되지만이 어려움에 대한 공식적인 정의는 튜링 기계 및 비 결정적 튜링 기계에 대한 지식에 달려 있습니다. 이 모델을 이해하면 특정 문제의 계산 가능성을 추론 할 수 있기 때문에 유용합니다.
희망이 도움이됩니다.
튜링 기계는 계산을 분석하는 이론적 인 도구 일뿐입니다. 우리는 그것을 계산하는 튜링 기계를 만들어서 알고리즘을 지정할 수 있습니다. 그들은 computability의 연구에서, 즉 함수를 계산하는 것이 가능하다면 매우 유용합니다. 튜링 기계 및 기타 여러 공식 언어 구문은 호프 크로프트 (Hopcroft)와 울만 (Ullmann)의 고전 book에서 다루어집니다. 튜링 기계는 Garey와 Johnson의 this 책의 NP 완전성을 논의 할 때도 나타납니다.
책과 튜링 기계는 일반적으로 꽤 이론적입니다. 학술적으로 알고리즘에 관심이 있다면 추천 할 것입니다. 그러나 실제 컴퓨터에서 구현 된 알고리즘을 실제적으로 이해하고 실제 데이터로 실행하려면 튜링 머신을 이해하는 것이 중요합니다.
이 주제에 대한 많은 통찰력을 제공 해주는 또 다른 훌륭한 책은 "Computer Power and Human Reason"입니다. 실제로 Joseph Weizenbaum이 쓴 것입니다! 할아버지는 대학에 갈 때 저에게 그것을줬고 심지어 서면 (1976 년) 이후 30 년이 지났지 만 제게 커다란 시작을주었습니다. 비록 그것이 주제에 관한 첫번째 책으로 따라가는 것이 약간 어려웠다 고 인정되지만, 나는 결국 나중에 되돌아 가야한다고 생각한다. 그래도 내 삶과 컴퓨터를 보는 방식을 바꿔 아름답게 튜링 기계를 설명합니다. – gnomed
튜링 머신은 계산할 수있는 것과 계산할 수없는 것을 설명하는 이론적 인 구성입니다. –
는 http://programmers.stackexchange.com/에 속해 있습니다. 소프트웨어 개발에 관한 전문 토론에 관심있는 전문가 프로그래머를위한 질문과 대답 – Mchl
@ Mchl- 나는 동의하지 않습니다. 이것은 소프트웨어 개발과 관련이 거의 없습니다. – templatetypedef