1

コンピュータアルゴリズムの設計と分析の私のコピーが本日届きました。最初の章では、著者はチューリングマシンを紹介しました。他に2つのアルゴリズムの教科書、アルゴリズム入門とアルゴリズム設計マニュアルがありますが、アルゴリズムとデータ構造の分野で有名ですが、チューリングマシンについてはどれも説明していません。

チューリングマシンとアルゴリズム/データ構造の関係を理解し​​たい。チューリングマシンを理解してアルゴリズムの専門家になることは本当に重要ですか？

4

2 に答える 2

7

チューリングマシンは、計算を分析するための単なる理論上のツールです。アルゴリムを計算するチューリングマシンを作成することで、アルゴリムを指定できます。それらは、計算可能性の研究、つまり、関数を計算することがまったく可能である場合に非常に役立ちます。チューリングマシンと他のいくつかの形式言語構造は、HopcroftとUllmannによる古典的な本で議論されています。チューリングマシンは、たとえばこの本で、GareyとJohnsonによるNP完全性について議論するときにも表示されます。

本とチューリングマシンはどちらも一般的にかなり理論的です。アカデミックな方法でalgorihhmsに興味があるなら、私はそれらをお勧めします。ただし、実際のコンピューターに実装され、実際のデータで実行されるアルゴリムを実際に理解したい場合は、チューリングマシンを大まかに理解することが重要であると言えます。

于 2011-08-20T19:06:31.213 に答える
6

チューリングマシンがデータ構造とアルゴリズムを説明するときに重要である理由は、チューリングマシンがアルゴリズムとは何かを説明できる数学的モデルを提供するためです。ほとんどの場合、アルゴリズムは高級言語または擬似コードを使用して記述されます。たとえば、次のように配列内の最大値を見つけるアルゴリズムを説明できます。

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.

これは有効なアルゴリズムですか？つまり、「インデックスを推測する」と言って、それが何を意味するのかを厳密に定義できますか？これを許可した場合、これを行うのにどのくらい時間がかかりますか？許可しないのなら、どうしてですか？最初の説明と2番目の説明の違いは何ですか？

アルゴリズムを数学的に厳密に定義するには、コンピューターがどのように機能し、何ができるか、何ができないかについての正式なモデルが必要です。チューリングマシンは、計算を正式に定義する一般的な方法の1つですが、他にも使用できる方法があります（レジスターマシン、文字列書き換えシステム、Churchのラムダ計算など）。計算の数学モデルを定義したら、開始できます。どのような種類のアルゴリズム記述が有効であるか、つまり、計算モデルを使用して実装できる記述について話します。

最新のアルゴリズムの多くは、基礎となる計算モデルのプロパティに大きく依存しています。たとえば、キャッシュを無視するアルゴリズムは、計算モデルに未知のサイズのメモリバッファと2層メモリがあることを前提としています。一部のアルゴリズムでは、基盤となるマシンが二分法である必要があります、つまり、マシンワードのサイズは、問題のサイズを保持するのに少なくとも十分な大きさである必要があります。ランダム化アルゴリズムには、ランダム性の正式な定義と、マシンがランダム値を使用する方法が必要です。非決定論的アルゴリズムには、非決定論的計算を指定する手段が必要です。回路に基づくアルゴリズムは、回路プリミティブが何であるかを知っている必要があり、許可されていません。量子コンピューターは、出力が確率的であるというアルゴリズムの定義が与えられていることに加えて、操作が許可されているものと許可されていないものの正式な定義を必要とします。分散アルゴリズムには、マシン間の通信の正式な定義が必要です。

つまり、アルゴリズムを説明するときに、何が許可され、何が許可されないかを明示することが重要です。ただし、優れたプログラマーになるため、またはアルゴリズムをしっかりと理解するために、チューリングマシンの内外を必ずしも知る必要はありません。また、チューリングマシンを使用して特定の問題をエンコードする方法の具体的な詳細について知る必要もありません。 。ただし、知っておくべきことは、計算モデルで実行できることと実行できないこと、および操作ごとのコストです。このようにして、アルゴリズムがどれほど効率的であるか、それらが使用するさまざまなリソース（時間、空間、メモリ、通信、ランダム性、非決定性など）の量について推論できます。とはいえ、基礎となるモデルを理解していなくても慌てないでください。

計算の基礎となるモデルについて考えるもう1つの理由があります。それは、その制限について説明することです。すべての計算モデルには限界があり、場合によっては、特定のアルゴリズムが特定の問題に対して存在できない可能性があること、または特定の問題を解決するアルゴリズムが必ず特定のリソースをある程度使用する必要があることを証明できます。これがアルゴリズム設計で発生する最も一般的な例は、NP困難の概念です。いくつかの問題は解決するのが非常に「難しい」と推測されますが、この難しさの正式な定義は、チューリングマシンと非決定性チューリングマシンの知識に依存しています。この場合、モデルを理解すると、特定の問題の計算の実現可能性について推論できるため、役立ちます。

お役に立てれば！

于 2011-08-20T21:00:54.437 に答える