アルゴリズムの表現と基本的な手法

要点と定義

アルゴリズムは、問題を解くための処理手順です。流れ図は、端子、処理、判断、ループ端、データなどの記号と線で処理手順を表し、順次、分岐、繰返しを示します。擬似言語や決定表もアルゴリズムの表現に用います。

整列は、データを一定の順序に並べる処理です。ヒープソートは、未整列部分をヒープとして管理し、そこから最小値または最大値を取り出して整列済み部分へ移す処理を繰り返します。探索では、線形探索、二分探索、ハッシュ表探索など、データの並び方や格納方法に応じた方法を選びます。

再帰は、処理の定義の中で同じ処理を呼び出す方法です。終了に至る基底条件と、呼出しごとにその条件へ近づく手順が必要です。グラフの幅優先探索は、始点から辺をたどり、距離の近い階層から節点を調べます。

適用条件と例

二分探索は、対象が比較可能な順序で整列されているときに使えます。中央の値と比べ、目的の値がある側だけを残して範囲を狭めます。線形探索は先頭から順に調べ、ハッシュ表探索はキーに対応する格納位置を利用します。

二分法では、解を含む区間の中点を調べ、符号の変化を保つ側に区間を狭めます。連続性と端点での符号条件が解を区間内に保つ根拠となり、初期幅をLとすれば、k回の半分割後の幅はL／2^kです。幅が許容値より小さくなる最小のkを求めます。

再帰的な定義は、基底条件から順に呼出しをたどって値を計算します。階乗では、0の階乗を1とし、正の整数nについてnとn−1の階乗の積を用います。ユークリッドの互除法のように、余りを用いて問題を小さくする処理も、終了条件と引数の変化を追って確認できます。

幅優先探索は、根に近い階層から順に節点を調べます。二分木を根から階層順に配列へ格納した場合、配列の添字順の走査は幅優先の順になります。幅優先探索が最小化するのは辺の数であり、乗換回数を最小化できるかは、頂点・辺のモデルと各辺の意味によります。

二分法では、各反復で区間を半分にします。初期幅が1なら、k回の半分割後の幅は1／2^kです。判定条件が幅0.001未満の場合、2^9＝512では幅がまだ条件を満たさず、2^10＝1024で初めて満たすため、必要な反復回数は10回です。

ヒープソートは、未整列の要素をヒープとして管理し、最小値または最大値を取り出して整列済み部分へ移す処理を繰り返します。取り出すたびに未整列部分が縮まります。

流れ図で並列処理の同期点を示す場合、各並列経路は同期点に到達してから次へ進みます。したがって、同期後に次の反復へ戻る経路では、各処理が並列に繰り返されます。

二分木を根から階層順に配列へ格納し、各節点の子をその後の添字に置く表現では、配列添字順の走査は階層ごとに節点を調べる幅優先探索になります。

階乗の再帰定義は、0!＝1を基底条件とし、nが正のときn!＝n×(n−1)!とします。引数を一つずつ減らすことで基底条件へ到達します。