計算論
Calculation theory

授業科目区分

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

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

担当教員

安藤 友晴

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

NDC

410.9

科目分類コード

60010

オフィスアワー

この科目のキーワード

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

説明に使用する言語

日本語・英語を併用する

使用する教材の言語

日本語・英語で記述された資料を使用する

この科目に必要な日本の文化・事情の知識について

到達目標

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

授業の簡単な概要

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

学習内容

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

授業時間外での学修

特になし。

成績評価の基準と方法

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

達成度評価（評価方法：合計100点）

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

教科書・テキスト

プリントを配布する。

参考図書・参考文献等

・高岡詠子. チューリングの計算理論入門. 講談社, 2014, 224p., (講談社ブルーバックス). ・萩谷昌己, 西崎真也. 論理と計算のしくみ. 岩波書店, 2007, 256p. ・高橋正子. 計算論 : 計算可能性とラムダ計算. 近代科学社, 1991, 191p.

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

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

学習支援

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

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

特になし。