第3章データ構造とアルゴリズム
3.6 Computer Science Theory3.6 コンピューターサイエンスの理論
• Problem modeling is constrained by the model of computation, or the rules of the underlying computer that is ultimately responsible for executing the algorithm. Combinatorial explosion poses a problem for computer algorithms because our model of computation assumes computers only have a single thread of execution and only execute one basic operation on each step.
・問題のモデル化は、計算モデル、すなわち最終的にアルゴリズムの実行を担うコンピューターの根本的な規則に制約される。組合せ爆発が問題になるのは、計算モデルが、コンピューターは1本の実行スレッドだけを持ち、各ステップで1つの基本操作しか実行しないと仮定するためである。
• A Turing machine is an abstract model of computation for executing any computer algorithm. A Turing machine describes computers in terms of three key ideas: a memory bank, an instruction table, and a program counter.
・チューリングマシンは、任意のコンピューターアルゴリズムを実行する抽象的な計算モデルである。メモリバンク、命令表、プログラムカウンターという3つの主要な考え方でコンピューターを記述する。
• Although today’s computers are much more efficient than the first computers that realized the Turing machine, most computers still rely on the same fundamental assumptions about how to execute algorithms. Even as computers become faster over time inefficient algorithms still cannot be used to solve any problems larger than a few thousand elements.
・今日のコンピューターは、チューリングマシンを実現した最初のコンピューターよりはるかに効率的だが、大半はアルゴリズムの実行について同じ基本的な仮定に依存している。コンピューターが時代とともに速くなっても、非効率なアルゴリズムでは、数千個の要素を超える規模の問題は解けないままである。
• The complexity of a problem is the complexity (i.e., the time or memory resources required) of the most efficient algorithms for solving the problem. In this chapter, we have focused on solving problems known to have polynomial time algorithms that can be described with a polynomial expression such as O(1), O(log N), O(N), O(N log N), O(N2), O(N3).
・問題の計算量とは、その問題を解く最も効率のよいアルゴリズムの計算量、すなわち必要な時間やメモリ資源である。本章では、O(1)、O(log N)、O(N)、O(N log N)、O(N2)、O(N3)などの多項式の式で表せる、多項式時間アルゴリズムがあると知られている問題を中心に扱った。
• Nondeterministic polynomial (NP) time complexity class refers to all problems that can be solved in polynomial time by a nondeterministic algorithm. A nondeterministic algorithm is a kind of algorithm that can rely on the special power of exploring infinitely many possible “alternate universes” in order to complete a computation.
・非決定性多項式（NP）時間計算量クラスは、非決定性アルゴリズムで多項式時間に解けるすべての問題を指す。非決定性アルゴリズムは、計算を終えるために、無限に多くの可能な「別の宇宙」を探索する特別な力に頼れる種類のアルゴリズムである。
• Technically, all P problems are also NP problems because we already have deterministic algorithms for solving them and therefore do not need to rely on the special power of nondeterminism. NP-complete refers to all the hardest NP problems—the combinatorial problems for which we do not have deterministic polynomial-time algorithms.
・厳密には、すべてのP問題はNP問題でもある。すでに決定性アルゴリズムで解けるため、非決定性の特別な力を使う必要がないからである。NP完全とは、NPで最も難しいすべての問題、すなわち決定性多項式時間アルゴリズムのない組合せ問題を指す。
• Longest paths and the traveling salesperson problem (TSP) are two well-known examples of NP-complete problems. What makes both these problems difficult is that we do not have a simple rule for selecting the next element to include in the solution.
・最長経路と巡回セールスマン問題（TSP）は、NP完全問題のよく知られた2つの例である。両方を難しくしているのは、次に解へ含める要素を選ぶ単純な規則がないことである。
• All NP-complete problems can be reduced to all the others, so an algorithm for solving any NP-complete problem solves every NP-complete problem. The question of P versus NP asks whether it is possible to design a deterministic polynomial-time algorithm for solving any—and therefore all—of these NP-complete problems.
・すべてのNP完全問題は互いに帰着できるため、どれか1つを解くアルゴリズムはすべてを解く。P対NP問題は、これらのどれか1つ、したがってすべてを解く、決定性多項式時間アルゴリズムを設計できるかを問う。
• Most theoretical computer scientists believe that it is impossible to design an efficient algorithm for longest paths, TSP, or any other NP-complete problems. An efficient algorithm for any one NP-complete problems would not only directly solve routing and logistics problems but would also enable massive advancements in drug discovery through scientific simulation, for instance. It would also break essentially all modern Internet security and password systems—among thousands of other problems.
・理論計算機科学者の多くは、最長経路、TSP、その他のNP完全問題に対して、効率的なアルゴリズムを設計するのは不可能だと考えている。NP完全問題のどれか1つに効率的なアルゴリズムがあれば、経路や物流を直接解決するだけでなく、たとえば科学的シミュレーションによる創薬も大幅に進められるだろう。また、現代のインターネットのセキュリティーやパスワードの仕組みを、事実上すべて破ることにもなる。これらを含め、数千もの問題に関わる。
Review Questions確認問題
Exercises 1–5練習問題 1–5
1. Why did we introduce tree data structures as an alternative to linear data structures? a. Some complex data can only be represented with a tree data structure. b. Some simple data can only be represented with a tree data structure. c. Linear data structures cannot implement sets and maps. d. Tree data structures are typically more effective at implementing sets and maps.
1. 線形データ構造の代わりとして、木のデータ構造を紹介したのはなぜか。a. 木のデータ構造でしか表せない複雑なデータがある。b. 木のデータ構造でしか表せない単純なデータがある。c. 線形データ構造では集合やマップを実装できない。d. 木のデータ構造は通常、集合やマップをより効率よく実装する。
2. How does the graph abstract data type differ from other abstract data types? a. It can model the relationships between elements. b. It is more efficient than other abstract data types. c. It can solve problems that other abstract data types cannot solve. d. It does not specify a particular data structure implementation.
2. グラフ抽象データ型は、ほかの抽象データ型とどう異なるか。a. 要素間の関係をモデル化できる。b. ほかの抽象データ型より効率がよい。c. ほかの抽象データ型が解けない問題を解ける。d. 特定のデータ構造による実装を指定しない。
3. What abstract data type do binary heaps most commonly implement? a. lists b. sets c. maps d. priority queues
3. 二分ヒープは、最も一般的にはどの抽象データ型を実装するか。a. リストb. 集合c. マップd. 優先度付きキュー
4. What is one way to describe the relationship between algorithms, problems, and modeling? a. Algorithms are the foundation for problem models. b. Algorithms solve a model of a problem. c. Each algorithm can only be used to solve a single problem. d. Each problem can only have a single model.
4. アルゴリズム、問題、モデル化の関係を述べるものはどれか。a. アルゴリズムは問題モデルの基礎である。b. アルゴリズムは問題のモデルを解く。c. 各アルゴリズムは1つの問題にしか使えない。d. 各問題に対してモデルは1つしか作れない。
5. At what point do computer scientists apply algorithm design patterns? a. when learning canonical algorithms b. when modeling a problem c. when solving new problems d. when analyzing an algorithm
5. コンピューター科学者がアルゴリズムの設計パターンを使うのは、どの段階か。a. 標準的なアルゴリズムを学ぶとき。b. 問題をモデル化するとき。c. 新しい問題を解くとき。d. アルゴリズムを解析するとき。
Exercises 6–10練習問題 6–10
6. How does the model of computation relate to the problem model? a. The model of computation is synonymous with problem model. b. Problem models constrain the model of computation. c. The model of computation constrains the problem modeling process. d. The model of computation describes a single algorithm for each problem model.
6. 計算モデルは問題モデルとどう関係するか。a. 計算モデルは問題モデルと同じ意味である。b. 問題モデルが計算モデルを制約する。c. 計算モデルが問題のモデル化の過程を制約する。d. 計算モデルは、各問題モデルについて1つのアルゴリズムを記述する。
7. Why is case analysis important? a. Case analysis provides an alternative to asymptotic analysis. b. Case analysis focuses on small inputs. c. Case analysis simplifies the step-counting by introducing a cost model. d. Case analysis considers factors other than the size of the problem.
7. 場合分けによる解析が重要なのはなぜか。a. 漸近解析に代わる方法を提供する。b. 小さい入力に注目する。c. コストモデルを導入して、ステップ数の計数を簡略化する。d. 問題のサイズ以外の要因を考慮する。
8. What is true about the order of growth of binary search with respect to the size of the sorted list? a. In the best case, the order of growth of binary search is constant. b. In the best case, the order of growth of binary search is logarithmic. c. In the worst case, the order of growth of binary search is constant. d. In the worst case, the order of growth of binary search is linear.
8. 整列したリストのサイズに対する、二分探索の増加のオーダーについて、正しいものはどれか。a. 最良の場合、増加のオーダーは定数である。b. 最良の場合、増加のオーダーは対数である。c. 最悪の場合、増加のオーダーは定数である。d. 最悪の場合、増加のオーダーは線形である。
9. How does time complexity relate to space complexity? a. Time complexity measures efficiency according to the size of the problem, while space complexity does not. b. Both time and space complexity measure the efficiency of algorithms as they relate to the nature of the problem. c. Time complexity focuses on asymptotic analysis while space complexity focuses on experimental analysis. d. Both time and space complexity can apply methods from asymptotic analysis and experimental analysis.
9. 時間計算量と空間計算量はどう関係するか。a. 時間計算量は問題のサイズに応じて効率を測るが、空間計算量はそうではない。b. どちらも問題の性質との関係で、アルゴリズムの効率を測る。c. 時間計算量は漸近解析に、空間計算量は実験による分析に注目する。d. どちらも漸近解析と実験による分析の方法を適用できる。
10. What are the three steps in divide and conquer algorithms?
10. 分割統治アルゴリズムの3つの段階は何か。
Exercises 11–15練習問題 11–15
11. Why do many greedy algorithms fail to compute the best solution to a combinatorial problem?
11. 多くの貪欲アルゴリズムが、組合せ問題の最良の解を計算できないのはなぜか。
12. What are the three steps in reduction algorithms?
12. 帰着アルゴリズムの3つの段階は何か。
13. What is quicksort’s algorithm design pattern and algorithmic paradigm? a. Quicksort is an application of the binary search tree algorithm design pattern and an example of the divide and conquer algorithmic paradigm.
13. クイックソートの設計パターンとパラダイムは何か。a. 二分探索木の設計パターンを適用したもので、分割統治のパラダイムの例である。
b. Quicksort is an application of the binary search tree algorithm design pattern and an example of the brute-force algorithmic paradigm. c. Quicksort is an application of the binary search tree algorithm design pattern and an example of the greedy algorithmic paradigm. d. Quicksort is an application of the binary search tree algorithm design pattern and an example of the randomized incremental construction algorithmic paradigm.
b. 二分探索木の設計パターンを適用したもので、総当たりのパラダイムの例である。c. 二分探索木の設計パターンを適用したもので、貪欲法のパラダイムの例である。d. 二分探索木の設計パターンを適用したもので、ランダム増分構築のパラダイムの例である。
14. What graph problems can breadth-first search solve? a. exponential node tree b. minimum spanning trees c. unweighted shortest paths d. weighted shortest paths
14. 幅優先探索で解けるグラフの問題はどれか。a. 指数的なノードの木。b. 最小全域木。c. 重みのない最短経路。d. 重み付き最短経路。
15. What is a primary drawback of hashing? a. There can be collisions as the same element can hash to multiple values. b. There can be collisions between multiple elements that hash to the same value. c. Hashing is slower than binary search for search problems. d. Hashing is faster than binary search for search problems.
15. ハッシュ法の主な欠点は何か。a. 同じ要素が複数の値へハッシュされて衝突することがある。b. 複数の要素が同じ値へハッシュされて衝突することがある。c. 探索問題では二分探索より遅い。d. 探索問題では二分探索より速い。