SkillStack
テクノロジ系3 / 30問

高度情報処理技術者試験・情報処理安全確保支援士試験 令和3年度 春期 午前I 問3

アルゴリズム設計としての分割統治法に関する記述として、適切なものはどれか。

選択肢を押すと答え合わせができます。

正解と解説を見る

【正解】ウ

分割統治法は、大きな問題をそのまま解く代わりに、同じような構造をもつ小さな部分問題へ分割し、それぞれを解いた結果を統合して元の問題の解を得る方法です。「分割する」「小さな問題を解く」「結果を統合する」という三段階が基本です。ウは、全体を小さな問題に分け、個別の処理結果をつなぎ合わせて全体を解決すると述べているので、分割統治法の説明として適切です。代表例には、データ列を半分ずつに分けて整列し、最後に併合するマージソートがあります。

アは誤りです。粗い解を求め、その解を繰り返し修正して精度を高めるのは、反復改善法や逐次近似的な解法の考え方です。部分問題の解を統合する分割統治法とは異なります。

イは誤りです。全ての候補を基礎にしながら、解にならない候補や改善の見込みがない候補を除外するのは、バックトラッキング法や分枝限定法などの枝刈りを伴う探索の考え方です。

エは誤りです。各時点で、その場において最良と判断した選択を繰り返すのは貪欲法です。問題が貪欲法に適した性質をもたなければ、得られた解が全体の最適解になるとは限りません。

【ポイント】 分割統治法の代表例は、マージソート、クイックソート、二分探索などです。 部分問題を再帰的に解く形で実装されることが多く、問題を十分小さくしたときの終了条件も必要です。

出典:令和3年度 春期 高度情報処理技術者試験・情報処理安全確保支援士試験 午前I 問3
※ 解説は SkillStack 編集部が作成したものです。Web 表示のため、図表の配置や表記を一部改めています。

この回の30問を、アプリで通しで解く

  • 本番と同じ問題数・制限時間で通し演習(模試モード)
  • 間違えた問題は自動で「復習すべき問題」に回る
  • 解説で分からない点はAIに質問できる
SkillStackで無料で始める