計算の理論（2023年度 Sセメスター、小林担当分）

• 担当教員：今井（前半）、小林（後半）
• 時間および場所：S1/S2 火曜日5時限目、駒場12号館1225教室
• 講義内容（前半を含む。後ろの方は進み具合に応じて一部割愛）
  1. 計算とは（チューリング機械、アルゴリズム）
  2. チューリング・チャーチの計算仮説
  3. 決定不能な問題
  4. 計算困難さ（NP完全性入門）
  5. 難しい問題をなんとかして解く
  6. 色々な計算パラダイム（確率的計算など）
  7. 計算のモデル1（ラムダ計算）
  8. 計算のモデル2（ラムダ計算の表現力）
  9. ラムダ計算の性質、型つきλ計算
  10. 計算と論理1（カリー・ハワード同型）
  11. 計算と論理2（定理証明支援システム）
  12. 計算と論理3 （論理プログラミング）、その他（並行計算、プログラム検証など）
• 評価：レポート（期末試験は行わない）. ITC-LMSおよび講義中のアナウンスを参照
• 休講の予定：
• 参考文献（後半部分）

  小林直樹、住井英二郎、プログラム意味論の基礎、第７、８章、サイエンス社、ISBN 978-4-7819-1483-1.

  高橋正子、計算論：計算の可能性とラムダ計算、近代科学社

• 徳山 豪、小林直樹（編集）、理論計算機科学事典、朝倉書店（第6章および第7章）

  萩谷昌己、西崎真也、論理と計算のしくみ、第5章、岩波書店
  

• レポート課題および提出方法: 未定

  レポート提出に関する注意：こちらを参照