アルゴリズム特論III（確率的手法）
アルゴリズム特論III（確率的手法）
確率的手法の基礎を学習する．数学の典型的なテーマに，数学的対象物の存在性（○○○数は無限に存在するか，など）を示すことがある．確率的手法は，特に，組合せ的な特徴の存在性を示すための（非構成的）手法である．この手法は，組合せ論をはじめ，理論計算機科学や統計物理の分野で，重要かつ強力な手法の一つとして用いられてきた．本講義では，組合せ論での代表的な適用事例と，計算量理論への応用例を学習する．
講義スケジュール
導入（確率的手法とは --- ラムゼー数を例に ---）
確率の基礎１（確率・確率空間，ユニオンバウンド）
確率の基礎２（チェビシェフの不等式，チェルノフバウンド）
確率的手法１（ハイパーグラフの２彩色（上界））
確率的手法２（ハイパーグラフの２彩色（下界））
確率的手法３（独立頂点集合（Turan の定理））
確率的手法４（ランダムグラフ（クリーク数））
確率的手法５（ランダムグラフ（彩色数））
回路計算量への応用１（回路計算量とは）
回路計算量への応用２（switching lemma）
回路計算量への応用３（回路計算量下界）
劣線形アルゴリズムへの応用１（劣線形アルゴリズムとは）
劣線形アルゴリズムへの応用２（regularity lemma）
劣線形アルゴリズムへの応用３（質問計算量上界）
Last Update: 02/April/2025