情報処理安全確保支援士試験 情報セキュリティスペシャリスト試験 平成28年度秋期 午前Ⅰ 問1: 0 ≦ x ≦ 1 の範囲で単調に増加する連続関数 f(x) が f(0) ＜ 0 ≦ f(1) を満たすときに，区間内で f(x) ＝ 0 である x の値を

問題本文

0 ≦ x ≦ 1 の範囲で単調に増加する連続関数 f(x) が f(0) ＜ 0 ≦ f(1) を満たすときに，区間内で f(x) ＝ 0 である x の値を近似的に求めるアルゴリズムにおいて，(2) は何回実行されるか。 〔アルゴリズム〕 (1) x0 ← 0，x1 ← 1 とする。 (2) x ← (x0＋x1)/2 とする。 (3) x1 － x ＜ 0.001 ならば x の値を近似値として終了する。 (4) f(x) ≧ 0 ならば x1 ← x として，そうでなければ x0 ← x とする。 (5) (2) に戻る。

選択肢

• ア.10
• イ.20
• ウ.100
• エ.1,000

正解

ア. 10

解説

区間を毎回半分に絞る二分法（はさみうち法）の反復回数を問う問題。(2)で中点を求めるたびに探索区間は1→1/2→1/4…と半減する。終了条件 x1−x＜0.001 は区間幅の半分が0.001未満になることに相当し，1/2^n＜0.001 すなわち 2^n＞1000 を満たす最小のnは10。よって(2)は10回。アルゴリズムの計算量がlog₂(範囲/精度)に比例する典型例で，収束の速さを見積もる感覚は実務でも有用。

選択肢ごとの解説

• ア.区間幅が毎回半分になり1/2^n＜0.001を満たす最小nは10。これが正しい実行回数。
• イ.20回では精度が過剰で，実際には10回で終了条件を満たすため誤り。
• ウ.100は線形探索的な数で，半減を繰り返す二分法の回数とは一致せず誤り。
• エ.1,000は精度0.001の逆数に過ぎず，対数オーダの反復回数を取り違えており誤り。