サイエンス 社計算モデル論入門

(井田哲雄,浜名誠共著)

の読者のためのページ

 

教科書として利用する場合のガイド

本書は筑波大学情報学類(学部の学科相当)の3,4年次生に対して開講されている計算モデル論の講義が基になっています.

計算モデル論の講義のシラバス(2006年9月ー11月開講)の一部を以下に抜き出します.この講義計画は75分×2回の講義を10週間行うスケジュールになっています.対応する本書の章を付け加えました.このような構成で講義をすることをおすすめしているのでありませんが,講義を進める上で参考にして頂ければ幸いです.

学習・教育目標:

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

授業計画:

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

講義内容 対応する本書の章
第1週 計算モデルの概要 第1章 序ー計算の考え方
第2週 帰納関数論 1
原始帰納関数
第5章 帰納関数
第3週 帰納関数論 2
一般帰納関数
第5章 帰納関数
第4週 抽象書換え系 1
抽象書換え系 の考え方
第6章 抽象書換系
第5週 抽象書換え系 2
合流性,停止性
第6章 抽象書換系
第6週 ラムダ計算
形式的体系の定義の方法
第7章 ラムダ計算
第7週 β簡約,β正規形
項の書換えの戦略
第7章 ラムダ計算
第8週 計算系の持つ基本的性質
合流性,停止性,不動点定理
第7章 ラムダ計算
第9週 ラムダ計算の応用
自然数と四則演算のラムダ項による表現
第7章 ラムダ計算
第10週 ラムダ定義可能性,計算可能性
帰納関数論やラムダ計算の計算能力
第7章 ラムダ計算

これからわかるようにこの計算モデル論の講義では,ラムダ定義可能性を中心に据えて,この概念を十分に説明するのに必要な知識を学習するような形になっています.筑波大学情報学類では,2年次生に言語Schemeを教えています.このため第4章は学生の自習用教材と考えています.また,学生は2年次の後半には,離散構造の講義を受講するようになっています.第2章は離散構造で学習した内容のうち本書の理解に必要な知識のまとめになっています.有限状態機械とチューリング機械の記述は,本書で特に付け加えたものです.計算能力を議論するためには,チューリング機械の理解が必要です.筑波大学の講義では第一週の講義に含める予定でいます.15週の講義を前提とするセメスター制をとっている大学での講義には2週間を有限状態機械とチューリング機械の説明に当てると良いと思います.ただし,本書での扱いは計算モデルとしての扱いですので,言語理論への応用や非決定性機械を扱ってはいません.コンパイラや形式言語の講義でこれらの内容は補う必要があります.

本書は120ページの比較的薄い教科書ですが,内容は2単位の講義に十分以上のものを含んでいると考えられます.2単位の講義の教科書として使う場合は,受講者の予備知識にあわせて,内容の適切な取捨選択が必要になると思います.

本ページの今後の計画

著者の連絡先:

Tetsuo.Ida@acm.org, hamana@cs.gunma-u.ac.jp

本ページは 2006年10月22日 に開設されました.