概念・定理図鑑 · 基礎から応用へ

ループ不変条件:反復の境界で保たれる説明

初期化・保存・終了時の結論を配列の合計で確かめ、停止性を別に証明する理由を学びます。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 常に変わらない変数ではない
  2. 配列合計の不変条件
  3. 初期化・保存・結論を分ける
  4. 停止性には減少する量を使う
  5. この記事をロゲイアに質問する理解を確かめる

常に変わらない変数ではない

ループ不変条件は、反復の決められた境界で成立し続ける命題です。変数の値が全く変わらないという意味ではありません。例えば処理済み要素の数iと部分和sが毎回変化しても、「sは先頭i要素の合計」という関係は保てます。どの時点で条件を述べるかを明示することが重要です。ループの途中では一時的に関係が崩れても、次の反復の入口までに回復させる設計が考えられます。

配列合計の不変条件

配列aの長さをnとし、i=0、s=0から始めます。不変条件を「0≦i≦n、かつsはa[0]からa[i−1]までの合計」とします。最初は処理済み要素がなく、その和を0と定めれば成立します。i<nの間、sへa[i]を足してからiを1増やせば、次の入口でsは先頭i要素の合計になっています。終了時にi=nと分かれば、sが配列全体の合計だと導けます。

python
def prefix_sum(a):
    i, s = 0, 0
    while i < len(a):
        # Invariant: s == sum(a[:i])
        s += a[i]
        i += 1
    return s

初期化・保存・結論を分ける

不変条件を使う際は、初期状態で成立すること、条件を満たして反復へ入れば次にも保存されること、終了条件と合わせて目的を導けることを別々に確認します。「iは整数」のように成立し続けても弱すぎる命題では、合計が正しいことを示せません。また、配列の範囲外を読まないことや、整数のオーバーフローをどう扱うかも実装上の条件です。数学上の和の説明と、有限幅整数で動くコードの仕様を揃える必要があります。

停止性には減少する量を使う

不変条件が保たれるだけでは、ループが終わることは示せません。合計の例ならn−iを、0以上で各反復ごとに減る整数として使えます。iを増やさない誤った本体でも部分和の条件の一部が保たれてしまう場合があるため、停止性の検討は省けません。テストは具体的な入力で不具合を見つけるのに有用ですが、すべての入力に対する説明とは別です。不変条件と停止する量を並べることで、正しい結果へ到達する道筋を明確にします。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 2

学習コースから次を選ぶ