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

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

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

アルゴリズムの最悪実行時間は何を表しますか？

1. A最小の入力に対する所要時間
2. B遅いコンピュータでの所要時間
3. Cサイズ n のランダムな入力に対する期待所要時間
4. Dサイズ n のすべての入力にわたる最大の所要時間

選択ソート（selection sort）はどのように動作しますか？

1. Aシフトによって各要素を成長していくソート済み部分に挿入する
2. B順序が逆になっている隣り合う要素を繰り返し交換する
3. C未ソート部分の最小値を繰り返し見つけ、それを先頭に交換する
4. D配列を半分に分け、それらをマージする

辺の重みが非負のグラフで、一つの始点からの最短経路を求めるアルゴリズムはどれですか？

1. ADijkstra 法
2. BKruskal 法
3. C深さ優先探索（DFS）
4. Dどの場合でも Bellman–Ford が必要

O(n²) のアルゴリズムは O(n³) でもあると言うのは正しいですか？

1. Aいいえ。Big O は常に関数の正確な増加率を述べなければならないから
2. Bはい。ただし n が 100 より小さい場合に限る
3. Cいいえ。n が大きいとき n³ は n² より小さいから
4. Dはい。Big O は上界であり、n² は n³ より速く増加しないから

問題が最適部分構造をもつとはどういう意味ですか？

1. A最適解を部分問題の最適解から構成できる
2. Bすべての部分問題が同じサイズである
3. C問題の最適解がちょうど 1 つで、すべての部分問題がそれを共有しているから
4. D問題を定数時間で解ける

ある NP 完全問題に対する多項式時間アルゴリズムを誰かが見つけたら、何が導かれますか？

1. A停止問題が決定可能になる
2. Bすべての指数時間アルゴリズムがただちに線形時間で動くようになる
3. CNP のすべての問題が多項式時間で解けることになり、P = NP となる
4. Dその 1 つの問題だけが P に移る

巡回セールスマン問題はどのように分類されますか？

1. A決定版は P に属するが、最適化版は NP 完全である
2. Bダイクストラ法がすべての都市を 1 回ずつ訪れて解くので、P に属する
3. C決定不能である
4. D決定版は NP 完全で、最適化版は NP 困難である