ソート、パッキング、およびネットワークアルゴリズム
導入済み| English | 意味 |
|---|---|
| algorithm/ˈælɡərɪθəm/ | アルゴリズム |
急速パッキング法は常に最適か？
- パッキング法は素早く箱を満たすが、有効な急速配置が必ずしも最少個数の箱を使用するわけではない。
- この授業ではアルゴリズムを学ぶ：特定の種類の問題を解決するための有限かつ順序付けられた指示の集合である。
数学的構造を選択せよ
- 指定されたアルゴリズムを正確にトレースし、同点時のルールを含めよ。ファーストフィットパッキングでは、各アイテムを収容可能な最初の空きボックスに入れる。ファーストフィットディクレーシングは、ファーストフィット適用前にソートを行う。ヒューリスティックは最適でない場合でも有効であることがある。
- 計算する前に許容される入力と単位を明記すること。数式は単なる電卓の入力記録ではなく、関係性を表すべきである。
First-fitアルゴリズムは 2 個のバケットに 6,5,4,3,2 のアイテムを容量 10 で配置した結果、下限値と一致した。このことから何が言えるか？
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
下限値に達することは、このケースのみで最適性を証明するに過ぎない。ある例でのヒューリスティックの成功は、最悪場合の性能について何も示さない。他のアイテムリストではFirst-fitが下限値を超える可能性がある。
検証済みケースを解く
- 結果を初期の数量と比較して確認する。適切な場合、元の関係式に代入するか、グラフと数値解答を比較する。
ボックス容量が10で、アイテムが6,5,4,3,2の順にある場合、ファーストフィットにより6と4はボックス1に入れられ、次に5,3,2はボックス2に入れる。これにより2個のボックスを使用する。全サイズは20であるため、下限はceil(20/10)=2となる。この配置はこの实例に対して最適である。
ソート、パッキング、およびネットワークアルゴリズム
指定されたアルゴリズムの tie-breaker 規則を含めて、正確にトレースすること
モデルと解答例を比較し、1つの違いを説明せよ。
最初の例題におけるファーストフィット配置では、いくつのビンを使用していますか？
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
ファーストフィット配置では2つのビンが使用され、それぞれの総サイズは10です。
魅力的な近道を検証せよ
- ヒューリスティックが常に最適であることを示すために、ある例での成功だけでは不十分である。ソートトレースにおける中間リストを保持し、入力から直接ソート済み最終リストへ飛躍してはならない。ルート要求がある場合、最短パスの更新では predecessor（直前ノード）情報を保持する必要がある。
- 近道が機能しない場合は、それが破られる仮定を特定すること。要求された最終的な四捨五入まで正確な値を維持すること。
ある例で機能するパッキングヒューリスティックは、常に最適でなければならない。この主張は誤りである。どの定義や前提条件に違反しているかを説明せよ。
総サイズ20、容量10に対するビンの下限を求めなさい。
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
各ビンは最大で10しか収められないため、少なくとも ceil(20/10) = 2個のビンが必要です。
ある例題で機能するパッキングヒューリスティックが、常に最適解をもたらすわけではありません。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
成功した一例だけでは、ヒューリスティックが常に最適であることを証明できません。ソートトレースでは中間リストを保持し、入力から最終的にソートされたリストへ飛ばないでください。最短経路更新では、ルートが要求される場合、直前ノード情報を維持する必要があります。
新しい状況を読み解く
- ディ(resolve)ストラ法では、未確定の暫定ラベルの中で最小のものを選び、その近傍を更新する。ルートインスペクション問題では、閉路と開路を区別し、ペアリング之前に奇次数頂点を特定せよ。
- 完全な解答は数学的な結果を示し、その意味を説明する。指定された文脈内で可能であることを確認すること。
品目5,3,2を含むビン（容量10）に残りのスペースを求めなさい。
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
未使用容量＝10－(5＋3＋2)＝0。
各パッキングルールとその動作を対応させよ。
難易度 2/5 · 140 コイン + 今日初回完了時に小ボーナス付与
定義された通りアルゴリズムをトレースせよ。下限値は、パッキングが可能な最高品質の基準となる。
コースでこれを使用する
- Edexcel IAL 追加数学公式; 公式単位 D1。他単位の enrichment は範囲レビューで特定され、追加のカッシュイン要件ではない。
- 最終的な答えの前に手法を示し、試験用紙の電卓および数式ルールを使用すること。誤答については、最初に無効となったステップを特定して見直すこと。
特定の種類の問題を解決するための有限かつ順序付けられた指示の集合。関係性を選び、手順を示し、前提条件を確認し、結果を解釈せよ。