13

TAOCP Volume 1 を読み始めたばかりで、スタイルを理解するのに苦労しています。

Knuth は計算方法を 4 倍 (Q,I, Omega, f) であると述べていますが、これらのそれぞれが何を意図しているのかを理解するのに苦労しています。彼の最初の例は理解できるが、2 番目の例は理解できない

私は第 3 版の 8 ページを見ています。

章の終わり近くに、文字列のセットについて説明するアルゴリズムがあります。

（ギリシャ語の変数を入力しやすいものに置き換えました-申し訳ありません）

A を文字の有限集合とし、A* を A 上のすべての文字列の集合とします。この考え方は、計算の状態をエンコードして、A* の文字列で表すようにすることです。

Q = (s,j) where s is in A* and j is an integer, 0 <= j <= N 
I = subset of Q with j = 0
Omega = subset with j = N
f = function below

(p と w は文字列であることに注意してください) と s が A* の文字列である場合、s が文字列 p と w に対して pTw の形式を持っている場合、T が s に出現すると言います。

f(s,j) = (s,a j ) T jが s に出現しない場合。
f(s,j) = (pY j w,b j ) p が s = pY j wを満たす最短の文字列の場合
f(s,N) = (s,N)

文字列のセットを作成するという概念は理解できますが、彼がここで言おうとしていることはすべて理解できません。なぜ Q、I、オメガが必要なのですか? f は実際に何を説明していますか (なぜ f に 3 つの関数が必要なのですか?)??

誰かが光を当てるのを助けることができますか?

4

5 に答える 5

16
于 2015-02-22T15:36:33.873 に答える
15

Q= 状態のセット(つまり、ある時点での(s, j)状態を表す) = 初期状態 (したがって、という要件) = 最終状態 (したがって、という要件) = 遷移関数sj
Ij == 0
Omegaj == N
f

また、名前fが付けられた 3 つの関数はありませんがf、3 つの方程式によって区分的に定義されています。

于 2009-02-19T18:35:12.360 に答える
1

アルゴリズムではなく「計算方法」を定義していることを思い出してください。単純に計算方法とは何ですか?

有限性を欠いている可能性があることを除いて、アルゴリズムのすべての特性を備えた「手順」は、計算方法と呼ばれることがあります。

簡単に言えば、Q は計算方法です。

Q = {all possible states of computations, I, Ω}
I = {all possible inputs}
Ω = {all possible outputs}
f = computational rule

f は Q からそれ自体への関数です。

f: Q  --->  Q
  [I]      [Ω]

f は Ω を点ごとに固定したままにする必要があります。つまり、次のことを意味します。

f(q) = q, ∀ q ∈ Ω 注: 異なる関数ではなく、同じ計算規則が Ω で区切られているだけです</p>

これで、プロシージャにはシーケンスが含まれます。そして明らかに、計算方法にもシーケンスが必要です。したがって、

セット I の各入力 x は、次のように計算シーケンス x 0、 x 1、 x 2、... を定義します: k ≥ 0 の場合、 x 0 = x および x k+1 = f(x k )。

どのように x 0 = x? 入力 x がシーケンスであることを忘れないでください。したがって、最初の入力シーケンスは x 0になります。シーケンスを扱っているとき、および「k」状態について懸念している場合、シーケンス内の要素の順序と位置が重要です。したがって、計算規則 f は、k番目の要素の位置またはより正確には「状態」という単語が k+1番目の状態になるようなものです。そうすれば、新しい状態ごとに関数を個別に適用して、次の状態を取得できます。

x k+1が Ω にない場合、関数の定義から意味がありません。したがって、クヌートの言葉遣い。

k が x kが Ωにある最小の整数である場合、計算シーケンスは k ステップで終了すると言われ、この場合、x から出力 x kを生成すると言われます。

したがって、これは計算方法の定義です。計算規則はアルゴリズムです。

于 2016-11-01T12:31:56.417 に答える
1

100%確かではありませんが、Q は 0 <= J <= N の順序付けられたすべてのペア (s, j) のセットのようです。これがドメインになります。これは、いくつかの N と文字列 s が与えられた場合のすべての可能な状態のセットです。

I は、すべての順序対が J=0 を含む Q のサブセット、または初期状態です。オメガは、すべての順序対が J=N を含む Q のサブセット、または最終状態です。

f はドメイン Q 上の実際の関数です。

編集

関数定義は 1 つの関数に沿ったものであると考えてください。ただし、与えられた入力によってケースが異なります。言語で書く関数を考えてみてください。元：

tuple f(string s, int i)
{
    if (Tj not in s)
        (s, aj)
    else if ( p is shortest possible length such that s = pYjw)
        (pYjw,bj)
    else if ( i == N )
        (s, N)
}

もう 1 つの例は、フィボナッチ関数の定義です。それがどのように定義されているか見てください。わかる？

于 2009-02-19T18:35:59.910 に答える
1

彼が本で以前に述べたユークリッドの gcd アルゴリズムを経験したとしたら。アイデアは、各反復の開始を初期段階としてマークし、ループの 1 回の反復で発生する状態の数 (つまり N) を定義することです。ここで、m を n で割った剰余がゼロに等しくなったときに、答えを受け入れて計算を停止したことを思い出してください。つまり、文字列 Yj の特定のオカレンスを検索していました。計算がループの最終段階に到達すると、停止または反復することになります。

于 2011-06-14T11:12:13.790 に答える