計算論

授業科目区分

専門科目
専門科目 情報テクノロジーコース

まちラボとわくらぼの使用について:使用しない
選択科目 2単位 4年次 前期




担当教員

安藤 友晴

研究室のホームページ,SNSなど

NDC

410.9

科目分類コード

1001-01

オフィスアワー

この科目のキーワード

チューリング機械/数理論理学/計算可能性/簡約/λ計算

到達目標

この授業では「計算」について学ぶ。我々がコンピュータを使って何かを実現しようとするとき、コンピュータはその内部で計算をおこなって必要な結果を返す。つまり、コンピュータは計算をおこなう機械であり、そのためにコンピュータは「計算機」と呼ばれることもある。ところが、すべての問題がコンピュータによって計算可能なわけではない。このことは、コンピュータの登場以前から数学的に考察されており、計算可能な関数は数学的にどのような構造を持っているか既にわかっている。本授業では、計算可能性を定義するための仮想的な計算機である「チューリング機械」と関数の計算の理論である「λ計算」(「らむだけいさん」と読む)を通して、計算について学ぶ。

授業の簡単な概要

本格的な計算論に入る前に、まず必要な数学(集合と関係)および数理論理学について概観する。その後、チューリング機械とλ計算を中心に計算論について学ぶ。最後に、式の種類を表わす型の概念を用いたλ計算を扱う。

学習内容

  1. 計算とは何か
  2. 集合
  3. 関係
  4. 命題論理
  5. 述語論理
  6. 直観主義論理
  7. 計算可能性
  8. チューリング機械
  9. 帰納的関数
  10. 停止問題
  11. λ項
  12. β簡約
  13. チャーチ・ロッサーの定理
  14. 型付きλ計算
  15. 学期末試験

授業時間外での学修

特になし。

成績評価の基準と方法

・「計算可能性」とは何か理解できていること ・チューリング機械の概要について理解できていること ・λ計算の概要について理解できていること

達成度評価(評価方法:合計100点)

試験:      50 / 100
レポート:    / 100
小テスト(中間テストなど含む): / 100
小レポート(中間レポートなどを含む): 50 / 100
作品:      / 100
ポートフォリオ: / 100
その他:

教科書・テキスト

プリントを配布する。

参考図書・参考文献等

・萩谷昌己, 西崎真也. 論理と計算のしくみ. 岩波書店, 2007, 256p. ・高橋正子. 計算論 : 計算可能性とラムダ計算. 近代科学社, 1991, 191p.

履修もしくは取得していなければいけない科目

「論理学I」「論理学II」の学修内容を獲得できている必要がある。

学習支援

・LMS上の教材で復習することが望まれる。 ・LMS上のフォーラムを利用されたい。

その他この科目を履修するために必要な条件

特になし。