計算モデル論

  [ GB21504 ]
Models of Computation
対象:3・4学年 開設学期:秋AB 曜日・時限:月5・6 単位数:2単位
担当教員:井田哲雄

概要

抽象書換え系,帰納関数論,ラムダ計算を取り上げて,計算モデルとその性質を体系的に学びます.

学習・教育目標

プログラミング言語の操作的意味を与える計算の体系とその性質を学び,計算に対する深い理解を得ることを目指します.この授業で得られる知識は,ソフトウェアの性質を解析するのに役立ちます.

キーワード

計算モデル,ラムダ計算,帰納関数,書換え系

Keywords

models of computation, lambda calculus, recursive function, rewrite systems

時間割

講義内容/理解すべき項目
第1講計算モデルの概要
第2,3講帰納関数論
第4,5講抽象書換え系
第6,7講ラムダ計算 形式的体系の定義の方法,β簡約,β正規形
第8講以降ラムダ計算 合流性,停止性,ラムダ定義可能性,計算可能性,帰納関数論やラムダ計算の計算能力

教材

計算モデル論入門ーチューリング機械からラムダ計算へ,井田哲雄,浜名誠 共著,サイエンス社, 2006 を教科書として使います.

参考書籍

計算モデルの基礎理論(岩波講座ソフトウエア科学12巻),井田哲雄,岩波書店.

予備知識・前提条件

ソフトウェア技法,離散構造をすでに履修していることが望ましい.

成績評価

期末試験を行ないます.講義と演習の出席率,学期末試験の評価を総合して評価します.計算をモデル化できるか,計算モデルの性質を形式的に理解できるか,計算可能性について深い理解に達しているかを評価の基準にします.

教員メールアドレス

井田哲雄
email: ida(at)cs.tsukuba.ac.jp
skype: tetsuoscore

講義のWebページ

講義ホームページ:次のホームページから、"Models of Computation" へのリンクをたどってください.
www.i-eos.org/ida

備考

2時限連続の講義であるので、講義時間の一部を演習にあてます.