アルゴリズム特論Ⅱ --- 乱択アルゴリズム ---
乱択アルゴリズムの基礎を学習する.
「通常の」アルゴリズムの実行過程は,
それぞれの実行段階で次に実行する手順が一意に定められている.
これに対して,
次の手順を乱数を使って決定して進んでいくアルゴリズムが,
「乱択アルゴリズム(randomized algorithm)」である.
本講義では,
そのようなアルゴリズム論の一分野である乱択アルゴリズムの基礎を学習する.
講義スケジュール
- 導入(乱択アルゴリズムとは)
- 確率の基礎1
- 確率の基礎2
- 整列問題
- 素数判定問題1
- 素数判定問題2
- 素数判定問題3
- 素数判定問題4
- 素数判定問題5
- チェルノフバウンド1
- チェルノフバウンド2
- 充足可能性問題1(決定性アルゴリズム)
- 充足可能性問題2(ローカルサーチ)
- 充足可能性問題3(バックトラック)
Last Update: 02/April/2020