アルゴリズムの検証

質問

基本情報処理を勉強している文系人間です。
ファイル処理-事務処理の基本-コントロールブレイクで
自分なりに取引先コードの集計、商品分類の集計の追加など
擬似言語を使い試してみたのですが
記述がすべてを網羅しているか確証がもてません。

以前仕事でプログラミングをしたときも、
考えられる変化の状況を書き出して、テストしてＯＫにしてしまって、不安がのこっておりました。

変化する要素とその流れをトレース表にまとめて
は見たものの、それ自体がよくわかっていないようです。
なにか検証する良い手法はありませんでしょうか？
また、やさしい参考資料がありましたらお教え下さい。
よろしくお願いします。

回答No.2

xcrOSgS2wY · ベストアンサー

話を混ぜっ返すようで申し訳ないのですが、質問者さんが補足の中で挙げておられる「アルゴリズムが正しいことの証明」に関しては、「一般に、正しいアルゴリズムが存在するとは限らない」という証明が与えられています。

参考：
http://www.itl.dm.u-tokai.ac.jp/~hiroshi/education/dsa/txt/complexity.html

一般化というのは非常に危険なもので、「一般に・・・存在しない」からと言って「ある特定の問題について存在しない」とは限らないわけですが、少なくともアルゴリズムの正しさについて一般的に論じようとすると、この問題は避けて通れません。

ですので逆に、実務的には「避けて通る」、つまり「アルゴリズムの正しさについて一般的に論じることは避ける」ことが無難であろうと、私は思います。

「アルゴリズムの正しさ」や「有限時間停止性の証明」は、何も非常に複雑なアルゴリズム、あるいはまだ知られていないアルゴリズムについて問題とされているものではありません。

その筋では有名な「与えられた自然数について、偶数なら2で割り、奇数なら3倍して1を足すことを繰り返す。1になったら停止。」というアルゴリズムがあります。（詳細違ってるかも。よくご存知の方ありましたらご指摘ください。）

これは、どんな自然数を与えてもおそらく必ず停止するだろうと考えられているのですが、しかし停止することの証明はまだ与えられていません。

こんな簡単なアルゴリズム（あるいはプログラム）でさえ停止性が判断できないわけですから、ましてや通常の（これより）大規模なアプリケーションに関して、厳密な停止性の議論を行うのは、学術的な興味を除けば、ほとんど実用的でないと思います。

現実的には、モジュールごとに「思いつく限りの」境界条件の周辺を探索（テスト）するというところに落ち着くのかなと思います。この「思いつく限り」というところで主観が入ってしまうのが曲者なわけですが。

（「こういう方法論でやってます」という例示ではなくてすみません。）

お礼

ありがとうございました。

また、わからないことがありましたら
質問させていただきます。
そのときは、よろしくお願い致します。

補足

ご丁寧にお答えいただき、ありがとうございます。

xcrOSgS2wY様の適切なご回答、参考になりました。

素人ながらプログラムを多少なりとも書いている者として
不安を払拭する何かが有るのではと、
知識の背景としての基本情報処理を学び、
アルゴリズムの中にその答えがあるのではと考えておりました。

「プログラムの正しさ」に視点を広げるとしたら、
そこには一般論としてのテスト技法に回答を見いだす
ことが正しいのかもしれません。

もう少し、勉強してみたいと思います。
ありがとうございました。

回答No.1

mttk1238

どうも！
で、結局アルゴリズムを検証する方法ですよね？
何をどのように検証したいのですか？
変化する要素をつかむならトレース表が最適でしょうね。
（私の場合滅多に使用しませんが）
解があってるかどうかの検証なら、アルゴリズムによって様々あります。
もうちと詳しく質問したほうがよろしいのでは？

お礼

ご丁寧に、ありがとうございます。
もう少し補足してみたいと思います。

補足

早速のご回答ありがとうございます。
質問内容をまとめます。

1.きっかけ：
　作成したプログラム（アルゴリズム）の正しさをどの様に検証したらよいか疑問に思っていた。

2.今までの作成方法：
　１，機能とその順序を箇条書きにする。
　２，図に表してみる
　３，コーディング
　４，変数やデータの境界や真ん中、あり得ない値などで正しさを検証
　５，おかしい場合は、デバックをして値の変化を確認、修正
　６，４を再度行い、問題がなければOKにする。（なにか不安が残る）

3.質問のあとに自分で調べたこと
　・アルゴリズムが正しいことの証明
　http://www.comm.musashi-tech.ac.jp/~uehara/ALG/ALGCh1.pdf

4.３を元に正しさを考えると
　１，2.4などのテストをおこない結果の正しさを証明（不足か？）
　２，値の変化に着目してトレース表を作成し、ループ不変条件、ループ終了条件を証明

以上が質問と自己回答してみた内容です。

具体的な例でなく申し訳ございません、また、
プログラムの内容により固有の検証部分・方法があることも想像されますが、
一貫した検証方法が、皆さんがコーディングするにあたりあれば、
教えていただきたく思います。

以前、ベテランのプログラマーさんが、2.3まで進み、
「さてこれが正しいことを証明するには・・」と、テストデータを作成して
確認しておりました。きっとOKを出す基準をお持ちであったのだと想像したのです。

よろしくおねがいいたします。