アルゴリズム特論II（乱択アルゴリズム）
アルゴリズム特論II（乱択アルゴリズム）
乱択アルゴリズムの基礎を学習する．「通常の」アルゴリズムの実行過程は，それぞれの実行段階で次に実行する手順が一意に定められている．これに対して，次の手順を乱数を使って決定して進んでいくアルゴリズムが，「乱択アルゴリズム（randomized algorithm）」である．本講義では，そのようなアルゴリズム論の一分野である乱択アルゴリズムの基礎を学習する．
講義スケジュール
導入（乱択アルゴリズムとは）
確率の基礎１（確率空間と確率変数）
確率の基礎２（マルコフの不等式）
整列問題（乱択クイックソート１）
素数判定問題１（群論の基礎）
素数判定問題２（初等整数論の諸定理）
素数判定問題３（フェルマーテスト）
素数判定問題４（ミラー・ラビン法１）
素数判定問題５（ミラー・ラビン法２）
チェルノフバウンド１（チェルノフの不等式）
チェルノフバウンド２（乱択クイックソート２）
充足可能性問題１（決定性アルゴリズム）
充足可能性問題２（ローカルサーチ）
充足可能性問題３（バックトラック）
Last Update: 02/April/2020