シラバスの詳細な内容を表示します。
→ 閉じる（シラバスの一覧にもどる）
| 開講年度 | 2019 年度 | |
|---|---|---|
| 開講区分 | 工学研究科(博士前期課程)情報工学専攻 | |
| 領域 |
情報工学専攻指定 |
|
| 受講対象学生 |
大学院(修士課程・博士前期課程・専門職学位課程) : 1年次, 2年次 |
|
| 選択・必修 | ||
| 授業科目名 | （専攻指定）ソフトウェア基礎論特論 | |
| そふとうえあきそろんとくろん | ||
| Fundamental Theory of Software | ||
| 単位数 | 2 単位 | |
| ナンバリングコード |
※最初の2文字は開講主体、続く4文字は分野、最後の数字は開講レベルを表します。 |
|
| 開放科目 | 非開放科目 | |
| 開講学期 |
後期 |
|
| 開講時間 |
|
|
| 開講場所 | ||
| 担当教員 | 未定（工学研究科情報工学専攻） | |
| 授業の概要 | コンピュータサイエンスの基盤理論である計算量理論を理解し、コンピュータサイエンスに対する数理科学的な洞察能力を養う。 さらに計算量理論から現代暗号理論への発展についても学ぶ。 またアルゴリズムの設計理論（特にランダムネスを活用するアルゴリズム）を学び、先端的なアルゴリズムを設計・解析する技法を修得する。 |
|---|---|
| 学修の目的 | |
| 学修の到達目標 | |
| ディプロマ・ポリシー |
|
| 成績評価方法と基準 | 出席とレポートの成績 |
| 授業の方法 | 講義 |
| 授業の特徴 |
問題提示型PBL（事例シナリオ活用含） 問題自己設定型PBL プロジェクト型PBL 実地体験型PBL |
| 授業改善の工夫 | |
| 教科書 | 特に指定しない |
| 参考書 | S. Arora and B. Barak: "Computational Complexity Theory: A Modern Approach", Cambridge University Press, 2009. M. Mitzenmacher and E. Upfal: "Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis", Second Edition, Cambridge University Press, 2017. (第１版邦訳: 小柴, 河内: "確率と計算: 乱択アルゴリズムと確率的解析", 共立出版, 2009年.) |
| オフィスアワー | |
| 受講要件 | |
| 予め履修が望ましい科目 | |
| 発展科目 | |
| その他 |
| MoodleのコースURL |
|---|
| キーワード | 計算量理論， 現代乱択アルゴリズム |
|---|---|
| Key Word(s) | computational complexity theory, modern cryptography, randomized algorithms |
| 学修内容 | 第 1回 コンピュータの数理モデル 第 2回 P対NP予想と計算量クラス 第 3回 乱択計算クラス 第 4回 いかに問題の困難さを比較するか 第 5回 平均な計算困難さと暗号構成要素 第 6回 暗号理論における疑似乱数 第 7回 対話型証明システム・ゼロ知識証明システム 第 8回 乱択アルゴリズム入門 第 9回 離散事象と期待値 第10回 モーメントと分散 第11回 Chernoff限界 第12回 ボールとビンのモデル(1) 第13回 ボールとビンのモデル(2) 第14回 Markov連鎖とランダムウォーク 第15回 まとめ |
| 事前・事後学修の内容 |