アルゴリズムとは?

[ つぎ | うえ ]

アルゴリズムとは?

どのようにタスクが実行するかを明らかにするステップの集まりである。コンピュータ科学の基礎をなす概念である。

たとえば

手品のアルゴリズム

効果: 手品をする者はテーブルに、表を下にしてある標準のカード一組から数枚を並べる。カードをよく切りテーブルに広げる。そして観客が赤か黒かリクエストした時、実行者はその色のカードをひっくり返す。

手順:

ステップ1: 標準のカード一組から赤、黒それぞれ十枚づつ選ぶ。カードの表を上にして色に応じてテーブルに二つの山に分ける。

ステップ2: 何枚か赤と黒のカードを選んだことを観客に伝える。

ステップ3: 赤いカードを取る。小さな組を作る振りをして左手にカードの表を下にして持つ。このとき、右手の親指と人差し指でわずかにカードを湾曲させる。
そして、「その赤いカードがあります。」という時、テーブルに表を下にして赤いカードの組を戻す。

ステップ4: 黒いカードを取る。いわば、ステップ3 と似たようなものでカードを前に少し曲げる。「この山に黒のカードがあります。」という時、表を下にしてテーブルに戻す。

ステップ5: 黒いカードをテーブルに戻したら、すぐに両手で赤と黒のカードを混ぜる(表を下のまま)。テーブルにカードを広げ、完全に切ったことを説明する。

ステップ6: テーブルに表が下になったカードがある間、以下のステップを繰り返し実行する。
                6-1 赤か黒か観客にリクエストする。
                6-2 もし、赤ならくぼんだ表面のカードがあるのでそれをひっくり返すと同時に「ここに赤いカードがあります。」という。
                6-3 もし、黒なら膨らんだ表面のカードがあるのでそれをひっくり返すと同時に「ここに黒いカードがあります。」という。
                6-4 もうリクエストがない場合は、残っているカードをひっくり返して自分の主張を立証する。


ユークリッド(ユーグリッドではない)の互除法

効果: 入力が二つの正の整数である。これら二つの値の最小公倍数と最大公約数をコンピュータで計算する。

手順:

ステップ1: MとNをそれぞれ大きい入力整数、小さい入力整数とする。

ステップ2: NでMを除算し、余りをRとする。

ステップ3: もしRが0でなければ、Nの値をMとし、RをNとする。そして、ステップ2にもどる。0だったら、最大公約数は、一般的にNの値とする。


これらの他に、折り紙の折り方音楽の楽譜などもアルゴリズムを表現したものであるということができる。


まず、アルゴリズムを考えること

アルゴリズムは、考えてもわからないかもしれないが、とにかく理解することが大切である。上のユークリッドの互除法などは、考えても浮かばないかもしれないが、「だれでも」同じ操作で、同じ結果をえることができることに注意しよう。


[ つぎ | うえ ]
yasu@i.hosei.ac.jp