大学院
過去（2017年度）の授業の情報です
学内のオンライン授業の情報漏洩防止のため，URLやアカウント、教室の記載は削除しております。
最終更新日：2025年4月21日
授業計画や教室は変更となる可能性があるため、必ずUTASで最新の情報を確認して下さい。
UTASにアクセスできない方は、担当教員または部局教務へお問い合わせ下さい。
最終更新日：2025年4月21日
授業計画や教室は変更となる可能性があるため、必ずUTASで最新の情報を確認して下さい。
UTASにアクセスできない方は、担当教員または部局教務へお問い合わせ下さい。
アルゴリズム論
乱択アルゴリズム
Randomized Algorithms
大学院のアルゴリズム入門講義として、縦軸に乱択アルゴリズムをすえ、横軸に基本的な問題から応用分野のものまでを対象に、アルゴリズムの設計と解析そして計算量理論について講究する。
時間割／共通科目コード
コース名
教員
学期
時限
4810-1111
アルゴリズム論
今井 浩
木曜3限
マイリストに追加
マイリストから削除
講義使用言語
単位
2
実務経験のある教員による授業科目
NO
他学部履修
可
開講所属
情報理工学系研究科
授業計画
1. 乱択アルゴリズム入門
2. 乱択アルゴリズムと計算量
3. ゲーム理論と乱択アルゴリズム
4. 確率不等式と乱択アルゴリズムへの適用1
5. 確率不等式と乱択アルゴリズムへの適用2
6. 確率的方法
7. マルコフ連鎖とランダムウォーク1
8. マルコフ連鎖とランダムウォーク2
9. 代数的手法1
10. 代数的手法2
11. 近似数え上げ
12. 応用問題
授業の方法
主に板書により講義する。一部、配布資料なりプロジェクタを用いることもある。
成績評価方法
講義中に出される問題の内、いくつかについてレポートを提出する。詳細は講義中に示す。
参考書
Rajeev Motwani and Prabhakar Raghavan: Randomized Algorithms. Cambridge University Press, 1995.
