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

• 担当教員：河原林（前半）、小林（後半）
• 時間および場所：S1/S2 火曜日5時限目、駒場5号館524教室
• 講義内容（前半を含む。後ろの方は進み具合に応じて一部割愛）
  1. 計算、アルゴリズムとは（チューリング機械、決定不能問題など）
  2. アルゴリズム、計算の社会へのインパクト（PageRank、行列計算など）
  3. 計算困難さ（NP完全性入門）
  4. 難しい問題をなんとかして解く（近似など）
  5. 色々な計算パラダイム（乱拓アルゴリズム、オンラインアルゴリズムなど）
  6. アルゴリズムと入力の相性（入力を制限することにより解が得られることも）
  7. 計算のモデル1（ラムダ計算）
  8. 計算のモデル2（ラムダ計算の表現力）
  9. ラムダ計算の性質、型つきλ計算
  10. 計算と論理1（カリー・ハワード同型）
  11. 計算と論理2（定理証明支援システム）
  12. 計算と論理3 （論理プログラミング）、その他（並行計算、プログラム検証など）
• 評価：レポート（期末試験は行わない）. UTOLおよび講義中のアナウンスを参照
• 休講の予定：
• 参考文献（後半部分）
  • 小林直樹、住井英二郎、プログラム意味論の基礎、第７、８章、サイエンス社、ISBN 978-4-7819-1483-1.
  • 高橋正子、計算論：計算の可能性とラムダ計算、近代科学社
  • 徳山 豪、小林直樹（編集）、理論計算機科学事典、朝倉書店（第6章および第7章）
  • 萩谷昌己、西崎真也、論理と計算のしくみ、第5章、岩波書店
• レポート課題および提出方法: 随時、UTOLに掲示

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