情報科学 › ソフトウェア設計とテスト › 継続的インテグレーション

まとめ検査の期待回数と最適な大きさ

定理 6.2（「継続的インテグレーション」§6） ・ ✓公理まで証明済み

各変更が独立に確率 p∈(0,1)p \in (0, 1) で不良であり、いくつかの変更をまとめた版の検査は「不良な変更を 1 つでも含めば不合格、含まなければ合格」を決定的に返すとする。

(a) （2 段階の方式）b≥2b \ge 2 個をまとめて 1 回検査し、不合格なら bb 個を 1 つずつ検査する。このとき 1 変更あたりの期待検査回数は

E(b)=1b+1−(1−p)bE(b) = \frac{1}{b} + 1 - (1-p)^{b}

である。まとめない場合は E(1)=1E(1) = 1 とする。

(b) b=⌈1/p⌉b = \lceil 1/\sqrt{p} \rceil とすると E(b)≤2p+pE(b) \le 2\sqrt{p} + p である。また、すべての b≥2b \ge 2 について E(b)≥min⁡(2p, (1−p)/2)E(b) \ge \min\bigl(\sqrt{2p},\ (1-p)/2\bigr) である。特に p≤1/10p \le 1/10 ならば

2p ≤ min⁡b≥1E(b) ≤ 2p+p.\sqrt{2p} \ \le\ \min_{b \ge 1} E(b) \ \le\ 2\sqrt{p} + p .

(c) E(b)<1E(b) < 1 となる b≥2b \ge 2 が存在するための必要十分条件は p<1−3−1/3=0.3066…p < 1 - 3^{-1/3} = 0.3066\ldots である。

(d) （二分する方式）b=2kb = 2^{k} 個をまとめて検査し、不合格なら半分ずつに分けてそれぞれを同じ方式で検査する（1 個になったらそれ以上分けない）。この方式は不良な変更をすべて特定し、1 変更あたりの期待検査回数は 1b+2plog⁡2b\dfrac{1}{b} + 2p \log_2 b 以下である。

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

証明が使う定理を 前提 としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています（前提の定理類 29 件、定義なども含めて 35 件）。

印の意味: ✓公理まで証明済み ・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は 閉包の状況。

前提をたどる 証明が使う定理・定義（直接 4 件）

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

これを使っている定理

証明で明示的に参照している定理は、まだありません。

関連するノック 1 問