アルゴリズムの追跡と設計

要点と定義

アルゴリズムは、問題を解くための処理手順です。処理の順序、判断条件、繰返しを追うと、入力から結果までの状態変化を確認できます。流れ図や擬似言語は、こうした手順を表す方法です。

バブルソートは、隣り合う要素を比較し、順序が逆なら交換する操作を繰り返す整列法です。昇順で左から右へ走査すると、走査範囲の最大値が右端へ移動します。走査を重ねるにつれて未整列範囲を狭めます。

幅優先探索は根に近い階層から順に調べる探索法で、深さ優先探索は一つの枝をたどってから戻る探索法です。分割統治法は、問題を小さな部分問題に分け、各部分を解いた結果を組み合わせる設計方法です。

適用条件と例

整列手順を追うときは、比較する要素の位置、交換条件、走査後に要素がどう移動するかを確認します。昇順のバブルソートでは、左から右へ隣接要素を比べる走査によって、その範囲の最大値が右端へ移動します。たとえば「四、二、三」は、一回の走査で「二、三、四」になります。

木の探索では、節点を調べる順序に注目します。根から各階層を順に調べるのが幅優先探索で、一つの枝をたどってから戻るのが深さ優先探索です。親の添字を i とし、子を 2i と 2i＋1 に置く配列表現では、添字順の走査が階層順になります。

分割統治法では、問題を小さな部分問題に分け、それぞれを解いてから結果を組み合わせます。部分問題を別々に処理できることが適用の手掛かりです。

隣り合う要素を比較し、昇順で逆の並びなら交換する操作を繰り返すのがバブルソートです。この特徴で整列手順を識別できます。

状態遷移表に基づく処理では、現在の状態と発生したイベントに対応する規則を順に適用し、次の状態を追います。表の該当欄が状態維持を示す場合は、その状態を次のイベントへ引き継ぎます。

根の添字を1とし、添字 i の左子と右子をそれぞれ 2i と 2i＋1 に置く表現では、配列を添字順に走査すると階層順に節点を調べます。これは幅優先探索の順序です。

分割統治法は、問題を複数の小さな問題に分け、それぞれを処理した結果を組み合わせて元の問題の解を得る設計方法です。

順に到着する処理を複数の装置へ割り当てる場合は、各時点の空き状況と割当規則を順次適用します。この例では完了時刻を更新しながら担当装置を追跡します。

流れ図の反復処理で隣接要素を比べ、逆順の場合だけ交換するなら、バブルソートの手順に当たります。交換条件とループ範囲を追うことで、整列の動きを確認できます。