情報処理安全確保支援士試験 情報処理安全確保支援士試験 令和3年度春期 午前Ⅰ 問3: アルゴリズム設計としての分割統治法に関する記述として，適切なものはどれか。

正解

ウ. 全体を幾つかの小さな問題に分割して，それぞれの小さな問題を独立に処理した結果をつなぎ合わせて，最終的に元の問題を解決する方法である。

問題の解説

分割統治法は、大きな問題を同種の小さな部分問題に分割し、各部分を独立に(多くは再帰的に)解いてから結果を統合して全体解を得る設計技法。マージソートやクイックソート、高速フーリエ変換が代表例。よってウが正解。アは近似法、イは分枝限定法、エは貪欲法の説明で、それぞれ別のアルゴリズム設計戦略であり区別が問われている。

選択肢ごとの解説

• ア粗い解を逐次改良して精度を上げる近似・反復法の説明であり分割統治法ではない。
• イ無駄な組合せを枝刈りして探索数を減らす分枝限定法の説明で誤り。
• ウ小問題に分割し独立に解いて結果を統合する分割統治法の本質を正しく述べている。
• エ各時点で局所最適を選び続ける貪欲法(欲張り法)の説明であり誤り。