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