2024年度 学院等開講科目 情報理工学院 情報工学系
計算基礎論
- 開講元
- 情報工学系
- 担当教員
- 村田 剛志
- 授業形態
- 講義 (対面型)
- メディア利用科目
- -
- 曜日・時限
(講義室) - 火3-4 (W2-402(W242)) / 金3-4 (W2-402(W242))
- クラス
- -
- 科目コード
- CSC.T241
- 単位数
- 200
- 開講時期
- 2024年度
- 開講クォーター
- 1Q
- シラバス更新日
- 2025年3月17日
- 使用言語
- 日本語
シラバス
授業の目的（ねらい）、概要
情報基礎学で学んだ基礎概念を基に，情報工学に関するより高度の概念や理論の基礎について講ずる。
計算の原理，計算モデルを様々な角度から述べ，“計算”の本質を講義していく。
到達目標
チューリング機械，帰納的関数，λ計算，計算可能性の理論に関する初等的取り扱いができるようになる。
キーワード
チューリング機械，帰納的関数，λ計算，計算可能性
学生が身につける力
- 専門力
- 教養力
- コミュニケーション力
- 展開力 (探究力又は設定力)
- 展開力 (実践力又は解決力)
授業の進め方
対面での講義と演習の後に、中間試験と期末試験を行う。
授業計画・課題
| 授業計画 | 課題 | |
|---|---|---|
| 第1回 | オリエンテーション | 各講義の後には，講義内容を復習すること．教科書の演習問題を活用するとよい． |
| 第2回 | チューリング機械１：チューリング機械とは | 講義中で指定する． |
| 第3回 | チューリング機械２：データの二進コード化 | 講義中で指定する． |
| 第4回 | チューリング機械３：万能チューリング機械 | 講義中で指定する． |
| 第5回 | チューリング機械４：計算可能性 | 講義中で指定する． |
| 第6回 | 帰納的関数１：帰納的関数とは | 講義中で指定する． |
| 第7回 | 帰納的関数２：ゲーデル数によるデータの表現 | 講義中で指定する． |
| 第8回 | 帰納的関数３：帰納的関数の計算可能性 | 講義中で指定する． |
| 第9回 | 帰納的関数４：帰納的関数と計算可能性の等価性 | 講義中で指定する． |
| 第10回 | ラムダ計算１：ラムダ計算とは | 講義中で指定する． |
| 第11回 | ラムダ計算２：ラムダ式によるデータの表現 | 講義中で指定する． |
| 第12回 | ラムダ計算３：ラムダ計算の計算可能性 | 講義中で指定する． |
| 第13回 | チューリング機械・帰納的関数・ラムダ計算の関係 | 講義中で指定する． |
| 第14回 | まとめ / 期末試験 | 講義中で指定する． |
準備学修(事前学修・復習)等についての指示
学修効果を上げるため，教科書や配布資料等の該当箇所を参照し，「毎授業」授業内容に関する予習と復習（課題含む）をそれぞれ概ね100分を目安に行うこと。
教科書
渡辺 治，米崎 直樹，『計算論入門』 日本評論社
参考書、講義資料等
特になし
成績評価の方法及び基準
演習（４０％）、中間試験（３０％）、期末試験（３０％）により評価する。
関連する科目
- GRE.C101 ： 情報基礎学第一
- GRE.C102 ： 情報基礎学第二
履修の条件・注意事項
情報基礎学第一および第二の単位を修得していること、または同等の知識があること。
その他
詳細は以下サイトを参照のこと。
http://www.net.c.titech.ac.jp/lecture/comp/