乱択・Monte Carloアルゴリズム
乱数で候補またはfingerprintを選び、成功条件と誤り確率を評価して反復や事後検証を設計する。
この典型を扱う単元: 乱択の成功条件と誤り確率を設計する
検索別名: Las Vegas algorithm、Monte Carlo algorithm、probabilistic method、乱択アルゴリズム
未知問からこの典型を見つける手掛かり
- 扱う対象
- sample
- 乱数
- 候補
- 確率変数
- 使う手掛かり
- sampling
- ランダムに選
- 乱択
- 試行を繰り返
- 保つ不変量
- 事後検証
- 独立試行
- 誤り確率
- 高確率
- 求めるもの
- 候補を得る
- 衝突回避
- 高確率で発見
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: モデル変換
関連する典型
学習成果と学習単位
乱数で選ぶ対象と成功条件を定め、誤り確率を上から評価して必要な反復回数または決定的な事後検証を設計できる。
乱択の成功条件と誤り確率を設計するで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC272 G「Yet Another mod M」 公式問題主題: 乱択の成功条件と誤り確率を設計する / 主タグ
- ABC422 E「Colinear」 公式問題主題: 乱択の成功条件と誤り確率を設計する / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC272 G「Yet Another mod M」 公式問題主題: 乱択の成功条件と誤り確率を設計する / 主タグ
- ABC339 F「Product Equality」 公式問題主題: 乱択代数fingerprint / 補助タグ
- ABC367 F「Rearrange Query」 公式問題主題: 乱択代数fingerprint / 補助タグ
- ABC399 G「Colorful Spanning Tree」 公式問題主題: 線形matroid交差の乱択rank判定 / 補助タグ
- ABC422 E「Colinear」 公式問題主題: 乱択の成功条件と誤り確率を設計する / 主タグ
- ABC455 G「Balanced Subarrays」 公式問題主題: 乱択代数fingerprint / 補助タグ