60 アルゴリズム発見とプログラミング
60.1 学習目標
- 問題解決のプロセスを理解する．
- アルゴリズムの発見のためのヒューリスティックを理解する．
- トップダウン設計とボトムアップ設計の概念を理解する．
- ブラックボックステストとホワイトボックステストの概念を理解する．
60.2 問題解決とアルゴリズム発見
アルゴリズムは，問題を解決するための手順を指す．問題を解決するためには，アルゴリズムを発見し，そのアルゴリズムをプログラムとして実装する必要がある．十分なプログラミング能力があれば，アルゴリズムを実装することは比較的容易である．しかし，アルゴリズムを発見することは，しばしば難しい課題となる．
数学者George Pólyaが著した「いかにして問題をとくか」（How to Solve It）において，問題を解決するためのプロセスが紹介されている．
- 問題を理解する
- 問題を解くための計画を立てる
- 計画を実行する
- 結果を検証する
この問題解決のプロセスをプログラムに適用すると，次のようになる．
- 問題を理解する
- アルゴリズムを発見する
- アルゴリズムをプログラムとして実装する
- プログラムを実行し，結果を検証する
60.3 問題の理解
問題を理解するためには，問題の定義を明確にし，問題の条件や制約を把握する必要がある．問題の定義は，問題を解決するための出発点となる．
問題の定義を明確にするためには，次のような質問を考えるとよい．
- 問題について，どのような情報が与えられているか？
- 問題の制約と目的は何か？
- 問題の解はどのような形式で表現されるか？
- 問題をどのように数学的に表現できるか？
60.4 アルゴリズムの発見
「いかにして問題をとくか」において，Pólyaは問題解決のためのヒューリスティック（heuristic）を紹介している．ヒューリスティックとは，試行錯誤しながら経験と発明を積み重ねることによって問題を解いてゆく方法である．
下の表は，Pólyaが提案するヒューリスティックの一部を示している．
| ヒューリスティック | 説明 |
|---|---|
| 類推（Analogy） | Can you find a problem analogous to your problem and solve that? |
| 一般化（Generalization） | Can you find a problem more general than your problem? |
| 特殊化（Specialization） | Can you find a problem more specialized? |
| 帰納（Induction） | Can you solve your problem by deriving a generalization from some examples? |
| 分解（Decomposition） | Can you decompose the problem and “recombine its elements in some new manner”? |
60.5 プログラミング
よく知られているプログラミング方法として，トップダウン設計とボトムアップ設計がある．
トップダウン設計（Top-Down Design）は，初めに全体の構造を設計し，次に階層構造に従って上位から下位へとソフトウェアを開発していくものである．
ボトムアップ設計（Bottom-Up Design）は，最初に下位の部品を開発し，次にそれらを組み合わせて上位の部品を作成していくものである．
例 60.1 C言語でトップダウン設計を行う場合，まずはmain()関数を定義し，その中で必要な関数を呼び出す形でプログラムを構築していく．次に，各関数の実装を行う．一方，ボトムアップ設計では，まずは関数を作成し，それらを組み合わせてmain()関数を定義する．
60.6 テスト
プログラムを開発した後は，テストを行うことが重要である．簡単なテストケースを用意し，プログラムが期待通りに動作するかを確認できる．
よりシステム的なテスト方法として，ブラックボックステストとホワイトボックステストがある．
ブラックボックステスト（Black-Box Testing）は，プログラムの内部構造を考慮せず，入力と出力の関係に基づいてテストを行う方法である．どれだけのデータをテストしたかを示す指標はデータカバレッジ（Data Coverage）である．
ホワイトボックステスト（White-Box Testing）は，プログラムの内部構造を考慮し，その構造に基づいてテストを行う方法である．具体的には，コードの各部分が正しく動作するかを確認するために，条件分岐やループなどの制御フローを考慮してテストケースを設計する．テスト対象のソースコードがどれだけ実行されたかを数値で示すコードカバレッジ（Code Coverage）を測定することもある．