第3章データ構造とアルゴリズム

Thought Provokers考えてみよう

Exercises 1–5練習問題 1–5

1. Maps can be defined in terms of sets: every map is a set whose elements represent key-value pairs, where the key must be unique, but the value might not be unique. Consider other relationships between abstract data types. Can sets and maps be defined in terms of graphs? Can lists be defined in terms of maps? Can priority queues be defined in terms of maps? Why might it be useful to define abstract data types in terms of other data types?

1. マップは集合で定義できる。すべてのマップは、キーと値の組を要素として持つ集合であり、キーは重複してはならないが、値は重複してもよい。抽象データ型のほかの関係を考えよう。集合とマップをグラフで定義できるか。リストをマップで定義できるか。優先度付きキューをマップで定義できるか。抽象データ型をほかのデータ型で定義すると、なぜ役立つのだろうか。

2. Graph theory refers to the mathematical study of graphs. How might a graph theorist describe linked lists and tree data structures? How does this differ from our use of abstract data types?

2. グラフ理論は、グラフの数学的な研究である。グラフ理論の研究者は、連結リストや木のデータ構造をどう記述するだろうか。それは、ここでの抽象データ型の使い方とどう異なるか。

3. Sorting and searching are two examples of data structure problems related to the storage and retrieval of elements. Where do sorting and searching appear in linear data structures, tree data structures, and/or graph data structures?

3. 整列と探索は、要素の保存や取得に関わるデータ構造の問題の2つの例である。線形データ構造、木のデータ構造、グラフのデータ構造では、整列や探索はどこに現れるか。

4. What are some benefits and drawbacks of simpler problem models, as they compare to more complicated problem models?

4. より複雑な問題モデルと比べ、単純な問題モデルには、どのような利点と欠点があるか。

5. The formal definition of Big O notation does not exactly match our working definition for orders of growth. Do some additional research to explain why binary search is also in O(N).

5. ビッグO記法の形式的な定義は、ここで使ってきた増加のオーダーの実用的な定義と、完全には一致しない。さらに調べ、二分探索がO(N)にも属する理由を説明しなさい。

Exercises 6–10練習問題 6–10

6. Since binary search is in O(N), it is also true that binary search is in O(N²). Explain why computer scientists might find O(N²) to be a less useful description of the runtime of binary search compared to O(log N).

6. 二分探索はO(N)に属するので、O(N²)に属するのも正しい。O(log N)と比べ、O(N²)では実行時間の記述として有用性が低いと、コンピューター科学者が考える理由を説明しなさい。

7. We can show that the worst-case order of growth for any comparison sorting algorithm must be at least linearithmic using an argument from combinatorial explosion in the number of unique permutations of elements in a list. What are the number of unique permutations of a list with N elements? How many comparison questions need to be asked to identify a particular permutation from among all the permutations? How do these questions relate to comparison sorting?

英語のヒント

7. リスト内の要素の異なる順列の数が組合せ爆発を起こすことから、どの比較整列アルゴリズムでも、最悪時の増加のオーダーが少なくとも線形対数でなければならないと示せる。N要素のリストの異なる順列は何通りか。すべての順列の中から特定のものを見つけるには、比較の問いを何回行う必要があるか。これらの問いは比較による整列とどう関係するか。

8. Breadth-first search is a fundamental algorithm design pattern for graph problems. How is breadth-first search applied as a foundation for designing greedy algorithms such as Prim’s algorithm and Dijkstra’s algorithm? How does Kruskal’s algorithm fit into these algorithm design patterns and paradigms? If Prim’s algorithm is analogous to sorting in Kruskal’s algorithm, why is there no analogue to the Dijkstra’s algorithm in sorting as well?

英語のヒント

8. 幅優先探索は、グラフの問題の基本的な設計パターンである。プリム法やダイクストラ法などの貪欲アルゴリズムの設計の基礎として、どのように使われるか。クラスカル法は、これらの設計パターンやパラダイムにどう位置付けられるか。プリム法がクラスカル法における整列に対応するなら、なぜ整列には、ダイクストラ法に対応するものもないのだろうか。

9. Suppose we want to find the longest path from a starting vertex to an ending vertex in a graph. How might a nondeterministic algorithm solve this problem in polynomial time?

9. グラフの開始頂点から終了頂点までの最長経路を求めたいとする。非決定性アルゴリズムは、この問題を多項式時間でどう解くだろうか。

10. Suppose we want to find the longest path from a starting vertex to an ending vertex in a graph (solving the function problem) without using a nondeterministic algorithm. Let’s say that P = NP and we have a deterministic polynomial-time algorithm that returns whether there is a path with exactly cost k (solving the decision problem). We also know the cost of the actual longest path. How can we repeatedly apply this decision algorithm to design a polynomial-time longest paths function algorithm?

10. 非決定性アルゴリズムを使わずに、グラフの開始頂点から終了頂点までの最長経路を求めたい（関数問題を解きたい）とする。P = NPで、コストがちょうどkの経路があるかどうかを返す、決定性多項式時間アルゴリズムがあるとする（判定問題を解く）。また、実際の最長経路のコストもわかっている。この判定アルゴリズムを繰り返し適用し、多項式時間で最長経路を求める関数アルゴリズムをどう設計できるか。

Labs実習

1. Simulate patients entering and exiting a hospital emergency room with a priority queue using patients’ time of arrival, basic assessment of severity, and availability of doctors specializing in the appropriate type of care. Decide how to prioritize patients based on a property of each patient, such as their arrival time, numeric severity rating, numeric urgency rating, and availability of care providers. Then, consider how your decision might result in unfair allocation of medical care to patients.

英語のヒント

1. 病院の救急室に患者が入ってきたり、出ていったりする様子を、到着時刻、重症度の基本的な評価、適切な治療を専門とする医師の空き状況を使う優先度付きキューでシミュレーションしなさい。到着時刻、数値化した重症度や緊急度、対応できる医療従事者の有無など、各患者の性質から優先順位をどう決めるか判断しなさい。その後、その判断によって、患者への医療の配分が不公平になる可能性を考えなさい。

2. Choose a lab from the Ethical Reflections Modules (https://openstax.org/r/76Ethics) for CS1. Follow the instructions to complete the assignment. Once you have finished, answer this additional reflection question connecting back to algorithm design: How did you utilize algorithm design patterns? How did your choice of algorithm designs affect the end outcomes in your program?

英語のヒント

2. CS1向けの「倫理を考えるモジュール」（https://openstax.org/r/76Ethics）から実習を1つ選び、指示に従って課題を完成させなさい。終えたら、アルゴリズム設計と関連付ける次の追加の振り返りに答えなさい。設計パターンをどのように活用したか。アルゴリズムの設計の選択は、プログラムの最終的な結果にどう影響したか。

3. Experimental analysis: Use a software-based “stopwatch” to compare the time (in microseconds) it takes to run a sequential search versus a binary search for successively larger and larger inputs. Relate experimental analysis to asymptotic analysis. What happens to small arrays? What happens to large-size array inputs? What happens when the target is near the front of the array? What happens when the target is near the end of the array?

3. 実験による分析：ソフトウェアで作る「ストップウォッチ」を使い、入力を次々に大きくしながら、逐次探索と二分探索の実行時間をマイクロ秒で比較しなさい。実験による分析と漸近解析を関連付けなさい。小さな配列では何が起きるか。大きな配列ではどうか。目的の要素が配列の先頭近くにある場合はどうか。末尾近くにある場合はどうか。