専門科目
専門科目 情報テクノロジーコース
まちラボとわくらぼの使用について:使用しない
選択科目 2単位 4年次 前期
安藤 友晴
410.9
1001-01
チューリング機械/数理論理学/計算可能性/簡約/λ計算
この授業では「計算」について学ぶ。我々がコンピュータを使って何かを実現しようとするとき、コンピュータはその内部で計算をおこなって必要な結果を返す。つまり、コンピュータは計算をおこなう機械であり、そのためにコンピュータは「計算機」と呼ばれることもある。ところが、すべての問題がコンピュータによって計算可能なわけではない。このことは、コンピュータの登場以前から数学的に考察されており、計算可能な関数は数学的にどのような構造を持っているか既にわかっている。本授業では、計算可能性を定義するための仮想的な計算機である「チューリング機械」と関数の計算の理論である「λ計算」(「らむだけいさん」と読む)を通して、計算について学ぶ。
本格的な計算論に入る前に、まず必要な数学(集合と関係)および数理論理学について概観する。その後、チューリング機械とλ計算を中心に計算論について学ぶ。最後に、式の種類を表わす型の概念を用いたλ計算を扱う。
特になし。
・「計算可能性」とは何か理解できていること ・チューリング機械の概要について理解できていること ・λ計算の概要について理解できていること
試験: 50 / 100
レポート: / 100
小テスト(中間テストなど含む): / 100
小レポート(中間レポートなどを含む): 50 / 100
作品: / 100
ポートフォリオ: / 100
その他:
プリントを配布する。
・萩谷昌己, 西崎真也. 論理と計算のしくみ. 岩波書店, 2007, 256p. ・高橋正子. 計算論 : 計算可能性とラムダ計算. 近代科学社, 1991, 191p.
「論理学I」「論理学II」の学修内容を獲得できている必要がある。
・LMS上の教材で復習することが望まれる。 ・LMS上のフォーラムを利用されたい。
特になし。