| English | 意味 |
|---|---|
| algorithm/ˈælɡərɪθəm/ | アルゴリズム |
| flowchart/ˈfləʊtʃɑːt/ | フローチャート |
| pseudocode/ˈsuːdəʊkəʊd/ | 擬似コード |
| tracing/ˈtreɪsɪŋ/ | トレース |
| binary search/ˈbaɪnəri sɜːtʃ/ | 二項探索 |
| linear search/ˈlɪnɪə sɜːtʃ/ | 線形探索 |
| efficiency/ɪˈfɪʃənsi/ | 効率性 |
手順が処理すべき入力を明示する
- アルゴリズムとは、タスクに対する曖昧さのない手順の記述である。有限のタスクを解決する手順は、すべての有効な入力に対して终止し、正しい結果を返さなければならない。
- 1つの入力での正常なトレースは、そのケースが正しく動作することを示すだけであり、すべての入力に対する証明ではない。境界条件や空入力の場合など、一般的な例では見逃されるエラーが露出することがある。
Which are required for a sequence of steps to be an algorithm? Choose all that apply.
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
A procedure solving the stated finite task needs unambiguous steps, correct results and termination on allowed inputs. Pseudocode and flowcharts are representations, not requirements to use a particular programming language.
選択と更新を明確に表現する
- フローチャートは、意思決定菱形、プロセス長方形、入力/出力平行四辺形、開始/終了ターミナルを使用し、有向矢印で接続する。
- 擬似コードは、特定の実装言語を必要とせず手順を記述する。トレースする前に、代入の意味、インデックスの始点、ループの範囲、分岐条件を明記すること。
Match each flowchart shape to what it means.
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
Use process rectangles, decision diamonds and start/stop terminals as given; input/output is normally shown by a parallelogram. Label decision branches and flow directions.
実際の変数の値を記録する
- トレースは指定された更新順序に従って追跡する。一時的な変数は、otherwise 上書きされて失われてしまう値を保持するために使用されることがある。
- 二項探索では low、high、middle、比較対象の値を示す。算術ループでは、変更されたすべての変数を示す。手順が何をするかだけでなく、その意図した目的も判断すること。
指定された二分探索の慣例。0始りの_dims境界を使用し、中央の値は平均の床（floor）とします。7を[1,3,5,7,9,11]内で探索する場合、インデックス2/値5、インデックス4/値9、そしてインデックス3/値7を比較します。この慣例では比較回数は3回です。
Linear against binary search
Halving beats checking one at a time, and the gap widens with the list.
Using zero-based inclusive bounds and floor((low+high)/2), how many comparisons does binary search use to find 7 in [1,3,5,7,9,11]?
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
Middle indices are 2, 4, then 3, with values 5, 9 and 7. Three comparisons under the specified convention.
前提条件のもとで作業量を比較する
- 線形探索は早期に停止できるが、n個のアイテムすべてを検査する可能性がある。二項探索はソートされた検索範囲を繰り返し半分に分割し、一貫した境界の更新が必要である。
- 効率性とは、定義されたモデルの下で必要な作業量が入力サイズに対してどのようにスケールするかを説明する。ソート自体にもコストがかかるため、未ソート入力に対して二項探索の整列保証を relying することはできない。
For an already sorted million-item list, approximately how many middle-value comparisons can binary search need in the worst case?
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
Each comparison halves the remaining search range; about 20 comparisons suffice for a million ordered items. This excludes any cost of sorting beforehand.
A binary search works on an unsorted list, just more slowly.
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
Without the required ordering, discarding a half can miss a present item. Some cases may happen to succeed, but correctness is not guaranteed.
ゼロと最終的な有効インデックスをチェックする。 Sheet 4.4では i < n を用いる和のループを扱っており、最後の項を見落としている。そのユークリッドのトレースも终止を説明しており、各正の約数がより小さい非負の余りに置き換わり、ゼロに達するまで続く。