科目ナンバー

SG-IG5-8C51

履修条件・関連科目等

授業で使用する言語

日本語

授業で使用する言語（その他の言語）

授業の概要

確率的な操作は機械学習や通信ネットワークを含む昨今の計算科学の諸分野で現れ, それらにおいて重要な役割を担っている. 本講義では様々な具体例や代表的な確率モデルを挙げながら, 確率的な操作によって生じる興味深い振る舞いとその理論的な記述・解析法について学ぶ.

科目目的

代表的な確率的現象を複数の具体例を通し学ぶ. また, どのような場面でそれらが現れ, 活用されているかを学ぶ. そして, 代表的な確率的解析法を通し, その振る舞いを確率の言葉で議論出来るようになることを目指す.

到達目標

集中不等式を始めとした代表的な確率的解析法を理解し, その証明が出来る. また, それらを用いて代表的な確率モデルの振る舞いを説明できる.

授業計画と内容

第1回 導入: 確率の公理
第2回 確率変数, 期待値, 離散確率分布
第3回 確率不等式の基礎
第4回 独立な確率変数列
第5回 様々な集中不等式
第6回 集中不等式の応用
第7回 ボールとビン
第8回 多項分布とポアソン近似
第9回 負の相関
第10回 ランダムグラフの基礎
第11回 ランダムグラフと閾値
第12回 マルチンゲールの基礎
第13回 マルチンゲールと集中不等式
第14回 負荷分散

授業時間外の学修の内容

授業終了後の課題提出

授業時間外の学修の内容（その他の内容等）

授業時間外の学修に必要な時間数／週

・毎週１回の授業が半期（前期または後期）または通年で完結するもの。１週間あたり４時間の学修を基本とします。
・毎週２回の授業が半期（前期または後期）で完結するもの。１週間あたり８時間の学修を基本とします。

成績評価の方法・基準

成績評価の方法・基準（備考）

課題や試験のフィードバック方法

授業時間内で講評・解説の時間を設ける／授業時間に限らず、manabaでフィードバックを行う

課題や試験のフィードバック方法（その他の内容等）

アクティブ・ラーニングの実施内容

実施しない

アクティブ・ラーニングの実施内容（その他の内容等）

授業におけるICTの活用方法

実施しない

授業におけるICTの活用方法（その他の内容等）

実務経験のある教員による授業

いいえ

【実務経験有の場合】実務経験の内容

【実務経験有の場合】実務経験に関連する授業内容

テキスト・参考文献等

講義内で配布する資料に沿って進める.

参考書:
Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis, 2nd edition. Michael Mitzenmacher, Eli Upfal, Cambridge University Press, 2017.
参考書については講義内で必要に応じて適宜紹介する.

その他特記事項

参考URL