読者です 読者をやめる 読者になる 読者になる

the art of computer programming 1.1 を読む

taocp the_art_of_computer_programming

1.1アルゴリズム

 アルゴリズムは単に特定のタイプの問題を解決するための一連の作業手順を定める有限個の規則という以上に、5種類の重要な特徴をもっている。

(1)有限性

 アルゴリズムは有限回のステップを実行したあと、必ず終了しなければならない。

 以下の4つの特徴を持つが有限性がない、つまり無限回のステップは計算方法とよばれる。

(2)明確性

 アルゴリズムの各ステップは正確に定義されていなければならない。

 人によって異なる解釈ができるものであってはならない。

(3)入力

 アルゴリズムは0個以上の入力を持つ。

(4)出力

 アルゴリズムは1個以上の出力を持つ。

 出力がないアルゴリズムはない。(何らかの処理をしたのにもかかわらず結果を教えてくれないというのは意味が無い)

(5)実効性

 アルゴリズムは一般に実効性を持つことも期待される。

 つまり、有限の時間のうちに処理が終了するということ。

  アルゴリズムは何でもかんでも実用的かと言われるとそうでもない。結果を得るまでに何年も、何十年もかかっていたのでは意味がないので、実用的なアルゴリズムは非常に限られた数のステップで終了しなければならない。

 

 

文字列のやつはWikipediaを見るとわかりやすい

演習問題 (問題難易度はthird editionのもの)

1.[10]

   t ← a

   a ← b

   b ← c

   c ← d

   d ← t

 

2.[15]

   m = qn + r

   であり、rはnより小さいのでn > r。

 ステップE3でm ← n, n ← rを行うので m > n となり、ステップE1では必ず m > n となる。

 

3.[20]

 F1.[剰余を見つける]mをnで割り、余りをmとする。

 F2.[0か?]m=0ならアルゴリズム終了。nが答えである。

 F3.[剰余を見つける]nをmで割り、余りをnとする。

 F4.[0か?]n=0ならアルゴリズム終了。mが答えである。そうでなければF1へ戻る。

 

4.[16]

  m ← 2166, n ← 6099

  m = 0 × 6099 + 2166

  m ← 6099, n ← 2166

  m = 2 × 2166 + 1767

  m ← 2166, n ← 1767

  m = 1 × 1767 + 399

  m ← 1767, n ← 399

  m = 4 × 399 + 171

  m ← 399, n ← 171

  m = 2 × 171 + 57

  m ← 171, n ← 57

  m = 3 × 57 + 0

  2166と6099の最大公約数は57

 

5.[12]

  18.にて「ステップ3に戻ること」と書いてあり、終了しないため有限性がない。

  15.にて「眠る」とあるが、何時間寝るのか書かれておらず曖昧であるため明確性がない

  どれが入力かは分からないが、入力は0個でも良いので入力はある。

  流れ図を見るかぎり、出力がなさそう。

  今までに行く人ものチャレンジャーを闇に葬っている本だと思うので実効性はないと思う。

  よって、有限性、明確性、実効性がない。

    (出力については解答例でも有耶無耶な感じなので・・・)

  アルゴリズムEとの違いは、識別用の文字(Eなど)がない、などなど

 

6.[20]

  n = 5 なので r は0,1,2,3,4のどれかになる。よってこの5通りを試せば良い。

    m = qn + 1 (r = 1) の場合は2回、 m = qn + 2 (r = 2) の場合は3回、m = qn + 3 (r = 3) の場合は4回

    m = qn + 4 (r = 4)の場合は3回、 m = qn (r = 0) の場合は1回E1が実行される。

    よってT5は(2 + 3 + 4 + 3 + 1) / 5 = 2.6回となる。

  ただしqは正整数。

 

7.[M21]

  Tnはnを固定しmは自由に選べる。 Umはmを固定しnは自由に選べる。

  m = 5 とするとTm = 2.6 である。Umは計算すると3.6となる。各計算について1回づつE1の実行回数が増えているのでUm = T m + 1 である。

 

8.[M25]

  j    θ     Φ   b    a

  1  ab    c    1    2         (文字列中にabがある限りcに変換する)

  2  a      b    2    3         (文字列中のaをすべてbに変換する)

  3  c      a    3    4         (文字列中のcをすべてaに変換する)

  4  b      b    1    end     (文字列中のbをbに変換し1へ。bがなければ終了)

感想

入力が0個のアルゴリズムがわからないので、そこは研究課題。