アルゴリズムの正しさ - necoffeeのにっき

　プログラムの勉強をしていると必ずぶつかるのがアルゴリズムという言葉。このアルゴリズムとは一体何なのかというと、問題を解くための手順を定めたものだ。この手順をきちんと定めればコンピュータに問題を解かせることができる(もちろんアルゴリズムはコンピュータに限った話ではないけど)。

ここで、どういうアルゴリズムが正しいアルゴリズムなのかということを知らなくちゃいけない。正しいアルゴリズムの条件とは次のようなものだ

(1)どんな入力データに対しても間違った答を与えないこと、言い換えると、答を与える場合にはその答が正しいこと。
(2)どんな入力データに対しても有限の時間で答を与えること、すなわち、計算を完了すること。

つまり、アルゴリズムが出す答は正しくなければならず、かつそれが本当に答を出すことを保証していなければならない。

アルゴリズムの証明の方法

　プログラムの中の特定の場所で変数の値の間に成立する条件式を表明(assertion)、ループの中で回るたびに常に成立している表明のことをループ不変条件(loop invariant)という。アルゴリズムの正しさを証明する基本的な手法は、ループ不変条件の成立を示すことだ。

例)ユークリッドの互除法
ステップ1：mをnで割って、余りをrとする。
ステップ2：r=0であれば、アルゴリズムは終了する。このときnが最大公約数である。
ステップ3：m<--nとする。次にn<--rとして、ステップ1に戻る。

たとえば、36と14の最大公約数をユークリッドの互除法を用いて求めると下のようになる。これは上のステップを繰り返し適用して求めたものだが、繰り返しの手順を経ても、最大公約数は変化しない。これがループ不変条件。
m    n    商   r
































-















36 / 14 = 2 … 8   <--36と14の最大公約数は2

14 / 8  = 1 … 6   <--14と8の最大公約数は2

8  / 6  = 1 … 2   <--8と6　　　〃

6  / 2  = 3 … 0   <--6と2      〃 