アルゴリズム特論Ⅱ　--- 乱択アルゴリズム ---

乱択アルゴリズムの基礎を学習する． 「通常の」アルゴリズムの実行過程は， それぞれの実行段階で次に実行する手順が一意に定められている． これに対して， 次の手順を乱数を使って決定して進んでいくアルゴリズムが， 「乱択アルゴリズム（randomized algorithm）」である． 本講義では， そのようなアルゴリズム論の一分野である乱択アルゴリズムの基礎を学習する．

• 講義資料

講義スケジュール

1. 導入（乱択アルゴリズムとは）
2. 確率の基礎１
3. 確率の基礎２
4. 整列問題
5. 素数判定問題１
6. 素数判定問題２
7. 素数判定問題３
8. 素数判定問題４
9. 素数判定問題５
10. チェルノフバウンド１
11. チェルノフバウンド２
12. 充足可能性問題１（決定性アルゴリズム）
13. 充足可能性問題２（ローカルサーチ）
14. 充足可能性問題３（バックトラック）
15. まとめ