SC情報処理安全確保支援士試験 午前Ⅰ

平成28年度秋期 情報処理安全確保支援士 午前Ⅰ 問1

問題文と選択肢を読んで答えを考えてから、下の「正解と解説を見る」で確認しましょう。

問題

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

選択肢

  1. ア
    10
  2. イ
    20
  3. ウ
    100
  4. エ
    1,000
解き方のヒントを見る

反復回数を見積もる視点

区間を段階的に狭める計算では、初期の範囲と各反復での縮まり方を対応させ、求める精度に達するまでの流れを順序立てて確認することが重要です。途中の丸めや終了条件にも注意します。

この問題で問われていること

確認の中心は、初期状態から終了条件を満たすまでに、区間の大きさが各段階でどう変化するかを追い、反復を一回として数える境目を一貫させることです。特に開始時点を含めるかを確認します。

視点

初期条件、縮小の単位、目標とする精度、終了判定の関係を整理し、回数を数える基準が途中で変わっていないかを確認しましょう。

確認ポイント

  • 初期状態を反復回数に含めるか確認する
  • 各段階で比較している区間の基準をそろえる
  • 終了条件を満たした時点の数え方を確認する
正解と解説を見る

正解

ア

解説

このアルゴリズムは区間の中央値を繰り返し求める二分法です。(2)をk回実行した直後のx₁−xは1/2^kとなるため、停止条件1/2^k<0.001(2^k>1000)を初めて満たす最小のkを求めます。

理由

初期状態での区間の幅は x₁−x₀=1 です。(2)を実行すると中央値 x が求まり、(3)で判定される x₁−x はその時点の区間幅の半分になります。(2)をk回実行した直後の x₁−x は (1/2)^k と表せるため、停止条件は 1/2^k<0.001、すなわち 2^k>1000 です。2^9=512、2^10=1024 であることから、条件を初めて満たす最小の整数は k=10 となり、(2)は10回実行されます。

比較

判定条件は区間全体の幅ではなく、中央値xと右端x₁との差(x₁−x)です。1回の反復ごとにこの差は半分になり、9回目の実行直後は 1/512(約0.00195)で条件を満たしませんが、10回目の実行直後に 1/1024(約0.00098)となって0.001未満に達し、アルゴリズムが終了します。

選択肢ア(正解)

これは正解です。初期区間の幅は1で、(2)をk回実行した直後のx₁−xは1/2^kとなります。停止条件は1/2^k<0.001なので、両辺の逆数を取ると2^k>1000です。2^9=512では不足しますが、2^10=1024で初めて1000を超えるため、(2)の実行回数は10回になります。

選択肢イ

これは不正解です。20回という回数は、アルゴリズムが終了する最小回数ではありません。(2)の実行ごとにx₁−xは半減し、10回目で1/1024となってすでに0.001未満を満たします。条件を満たした時点で処理は終了するため、20回まで繰り返されることはありません。

選択肢ウ

これは不正解です。100回は、二分法による収束回数として過大です。判定対象であるx₁−xは指数関数的に減少し、2^k>1000を満たすk=10の時点で0.001未満となります。停止条件を満たした時点で終了するため、100回実行されることはありません。

選択肢エ

これは不正解です。1,000回は、許容誤差の0.001から連想した誤った数値と考えられます。このアルゴリズムは1回ごとに差が半減する二分法であり、1000回の線形探索のような計算は行いません。10回目で2^10=1024となって条件を満たし終了するため、1,000回は不要です。

学習のポイント

二分法における各反復でのx₁−xの半減と、停止条件を満たす最小実行回数の関係。

解説を確認したら、演習モードや同じ分野の類題で理解を定着させましょう。

出典:独立行政法人 情報処理推進機構(IPA)平成28年度秋期 情報処理安全確保支援士試験 午前Ⅰ 問1(公式資料:問題冊子(PDF) / 解答例)

関連する過去問一覧

IPA Advancedは非公式の学習サイトです。解説にはAIによる補助生成を含む場合があります。公式の問題冊子・解答例・採点講評を優先し、誤りは確認後に訂正します。運営・編集方針