アルゴリズム、トレース、および正しさの証拠
導入済み| English | 意味 |
|---|---|
| algorithm/ˈælɡərɪθəm/ | アルゴリズム |
| boundary test/ˈbaʊndəri test/ | 境界テスト |
この観察を説明する要因は何か？
- アルゴリズムは特定の例では機能しても境界で失敗することがあります。テストはハッピーパスだけでなく、仕様に基づいて設計すべきです。
- まず予測を立てる。比較したい量や特徴を明記し、2つの説明を区別できる証拠は何かを決定せよ。
モデルを構築する
- アルゴリズムとは、タスクに対する有限かつ明確な手順のことです。トレースは状態の変化を記録します。ループ不変性は各反復によって維持される性質を示し、妥当性の正当化に役立ちます。
- アルゴリズム: 指定されたタスクを解決する有限の手順；境界テスト: 許容入力範囲の限界で行うテスト。
一般的な二項探索をリストに適用する前に満たすべき条件は何か。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
二項探索は中央値と比較してリストの半分を除外しますが、比較ルールに従ってリストが整列されている場合にのみ機能します。重複値は問題なく、任意の長さに対応できます。
各専門用語を正確な意味と対応させよ。
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
関連する物理量やプロセスを区別するために定義を使用せよ。
これを検証できる証拠を選ぶ
- 入力条件と期待される出力を記述します。境界ケース、空のコレクション（許可される場合）、重複項目、無効な値を使用します。誤ったアルゴリズムと、誤った実装または不完全な要件を区別してください。
- 小さな架空のソート済みリストに対する探索をトレースします。インデックスの慣例を明記してください。二分探索の場合、残りの区間が縮小するように境界を更新し、ソートがタスクの一部でない限り未ソート入力を却下してください。
この場合、調査やモデルをより妥当にする2つの習慣は何か。
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
条件や仮定を明記することで他者が正確に再現でき、根拠となる証拠を記録することで結論を検証できます。相反する結果を隠すと、誤った結論を疑う証拠を失いますし、単一の測定でより広い主張を成立させることはできません。
既知の量から始める
- 既知の値と単位を明記する。このケースに適応する仮定を持つ関係式を選び、代入前に変形する。
- 既知: 8要素のリストに対する線形探索は、探しているアイテムが最後にあるか存在しない場合に8回の比較を必要とする可能性があります。このモデルでは、リストの長さを倍にすると最悪ケースの比較回数も倍になります。二分探索は各ステップで区間をおおよそ半分ずつ減らしますが、適切な順序構造が必要です。
線形探索は一致しない14アイテムをスキャンします。いくつのアイテム比較が行われますか？同じ手順を用いる: 既知の数値 → モデル → 関係式 → 代入 → 単位と解釈。
線形探索で一致しない14個の要素をすべてスキャンする場合、何回の要素比較が行われるか。
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
結果は 14 回の比較です。既知：14 要素に対して一致なしで線形探索を行います。存在しないことが確定する前に全要素を比較するため、比較回数 = 14。不完全な探索は常に全长分を要します。
結論とその限界を確認する
- 成功したサンプルテストが、すべての有効入力に対する妥当性を証明するわけではありません。IBコースに、コースソースなしでCambridge固有の擬似コード構文を取り入れるべきではありません。
- 元の観察に戻り、結果が何を裏付けているか、どのような条件を前提としているかを説明し、対立する説明を検証する方法を一つ示す。
一度の成功したサンプルテストは、アルゴリズムがすべての有効入力に対して正しいことを証明する。この主張は誤りである：一度の合格テストは、その入力的にのみ動作することを示すに過ぎない。正しさはすべての有効入力に対する推論または証明が必要であり、空リストや境界値などのエッジケースは未テストのコードが失敗する場所そのものである。
アルゴリズム、トレース、妥当性の証拠: 入力条件と期待される出力を記述します。境界ケース、空のコレクション（許可される場合）、重複項目、無効な値を使用します。誤ったアルゴリズムと、誤った実装または不完全な要件を区別してください。
ある有効な入力の1つの成功したサンプルテストが、すべての有効な入力に対してアルゴリズムが正しいことを証明する。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
1つのテストパスが成功しても、その入力のみでアルゴリズムが正しく動作することを示すだけです。正しさは有効な入力の全てに対する推論や証明が必要です。空リストや境界値などのエッジケースで未テストのコードは failures を起こします。
指定されたタスクを解決する有限の手続きの技術用語を記せ。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
アルゴリズムとは、指定されたタスクを解決する有限の手順を意味する。