解答つきアルゴリズムと計算量ワークシート

無料で印刷できるアルゴリズムと計算量のワークシート：やさしい問題から試験レベルまで 8 問、解答つき。印刷するか PDF で保存できます。

新しいワークシートヒントつきでオンライン練習

先生方へ： 授業で自由に印刷・コピーしてお使いいただけます。新しいワークシートごとに数値が変わり、専用の解答が付きます。授業ページに ExamProblems へのリンクを載せていただけると嬉しいです。

名前: ____________________   日付: ____________

1.やさしい

増加の下界（lower bound）を表す記法はどれですか？

  1. AΘ（Big Theta）
  2. BΩ（Big Omega）
  3. CO（Big O）
  4. Do（little o）
2.やさしい

ある問題が通常「扱いやすい（tractable）」と呼ばれるのはどのような場合ですか？

  1. A解がない場合
  2. Bあらゆる可能性を試すことでしか解けない場合
  3. C定数時間で解ける場合
  4. D多項式時間で解ける場合
3.やさしい

アルゴリズムとは何ですか？

  1. A数式を書くために設計されたプログラミング言語
  2. Bグラフィカルなインターフェースをもつあらゆるコンピュータプログラム
  3. C数値を格納するデータ構造
  4. D問題を解く、明確に定義された手順の有限の列
4.ふつう

素朴な再帰によるフィボナッチ（fib(n) = fib(n−1) + fib(n−2)）の時間計算量はどれですか？

  1. A定数時間
  2. B指数時間
  3. C線形時間
  4. D対数時間
5.ふつう

プリム法は最小全域木をどのように構築しますか？

  1. A開始頂点から 1 本の木を成長させ、木から出る最も安い辺を加える
  2. B幅優先探索を実行し、BFS 木を残す
  3. Cすべての辺を重みでソートし、森の中で閉路をつくる場合を除いて 1 本ずつ加える
  4. D閉路がなくなるまで最も高い辺を取り除く
6.ふつう

O(log n) のように、Big O で対数の底が通常省略されるのはなぜですか？

  1. A底の異なる対数は定数倍しか違わないから
  2. B底は n が小さいときにしか問題にならないから
  3. C対数は常に整数に丸められるから
  4. D計算機科学のすべての対数は底が 10 なので、省略されているから
7.むずかしい

クラス NP の定義として正しいものはどれですか？

  1. Aどのアルゴリズムでも解けない問題
  2. B証拠（certificate）が与えられれば、「はい」の答えを多項式時間で検証できる決定問題
  3. C多項式でない問題
  4. D多項式時間で解けない問題
8.むずかしい

最短単純路は多項式時間で見つけられます。一般のグラフで 2 頂点間の最長単純路を見つけることについて、何が知られていますか？

  1. A常に O(V + E) で解ける
  2. BNP 困難である
  3. C重みの符号を反転すればダイクストラ法で解ける
  4. D決定不能である

解答

  1. 1. B · Ω（Big Omega）
  2. 2. D · 多項式時間で解ける場合
  3. 3. D · 問題を解く、明確に定義された手順の有限の列
  4. 4. B · 指数時間
  5. 5. A · 開始頂点から 1 本の木を成長させ、木から出る最も安い辺を加える
  6. 6. A · 底の異なる対数は定数倍しか違わないから
  7. 7. B · 証拠（certificate）が与えられれば、「はい」の答えを多項式時間で検証できる決定問題
  8. 8. B · NP 困難である

ステップごとの詳しい解答：このトピックは examproblems.com で練習できます。