計算理論

科目基礎情報

学校	大分工業高等専門学校	開講年度	令和04年度 (2022年度)
授業科目	計算理論
科目番号	R04S525	科目区分	専門 / 選択
授業形態	授業	単位の種別と単位数	履修単位: 1
開設学科	情報工学科	対象学年	5
開設期	後期	週時間数	2
教科書/教材	なし 参考資料を配布する．
担当教員	徳尾 健司

到達目標

(1) 決定可能性，帰着可能性，再帰定理，計算複雑性などの諸概念について理解できる．(定期試験と小テスト)
(2) λ計算，自然演繹および計算と論理の対応関係について理解できる．(定期試験と小テスト)

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
目的・到達目標(1)の評価指標	決定可能性，帰着可能性，再帰定理，計算複雑性などの諸概念について，他者に説明できるレベルで理解している．	決定可能性，帰着可能性，再帰定理，計算複雑性などの諸概念について，講義で取り上げた例題を解くことができる．	決定可能性，帰着可能性，再帰定理，計算複雑性などの諸概念について，基本的な概念の定義や用語の定義を述べることができない．
目的・到達目標(2)の評価指標	λ計算，自然演繹および計算と論理の対応関係について，他者に説明できるレベルで理解している．	λ計算，自然演繹および計算と論理の対応関係について，講義で取り上げた例題を解くことができる．	λ計算，自然演繹および計算と論理の対応関係について，基本的な概念の定義や用語の定義を述べることができない．

学科の到達目標項目との関係

学習・教育目標 (B1) （数学、自然科学の力を身につける）

JABEE 1.2(c) （数学，自然科学及び情報技術に関する知識とそれらを応用する能力）

JABEE 1.2(d)(1) （分野別要件－専門工学（工学（融合複合・新領域）における専門工学の内容は申請高等教育機関が規定するものとする）の知識と能力）

JABEE 1.2(g) （自主的，継続的に学習する能力）

教育方法等

概要:

「計算とは何か」を規定するChurch-Turingのテーゼを軸に，2つのテーマを取り上げる．前半は計算モデルとしてTuring機械を用いて，決定可能性，帰着可能性，再帰定理，計算複雑性などの重要な概念について学ぶ．後半は，もう一つの計算モデルであるλ計算を用いて，計算と論理の関係について考究する．

(科目情報)
教育プログラム 第2学年 ○科目

授業の進め方・方法:

原則として毎回，授業内容の理解を問う小テストを実施するので，授業を良く聞いて理解に努めること．

(参考図書)
[1] Sipser, M., Introduction to the Theory of Computation, PWS Pub. Co.
[2] シプサ，M., 計算理論の基礎，共立出版．
[3] ホップクロフト, J. 他，オートマトン 言語理論 計算論 II [第2版]，サイエンス社．
[4] 鹿島亮，C言語による計算の理論，サイエンス社．
[5] 萩谷昌己・西崎真也，論理と計算のしくみ，岩波書店．
[6] Stuart, T., アンダースタンディング コンピュテーション，オライリー・ジャパン．
[7] 高橋正子，計算論，近代科学社．

(事前学習)
参考図書 [1, 2] の該当箇所を読んでおくことが望ましい．

注意点:

(履修上の注意)
配布プリントを整理するためのクリアファイル(A4サイズ)を用意すること．

(自学上の注意)
参考図書の必要箇所を参照して予習・復習を行うこと．授業内容は [1][4][5] に基づく．[2] は [1] の邦訳．[3] はこの分野の標準的な教科書の一つ．[6] はプログラミング (Ruby) を通して実践的に形式言語理論と計算理論を学べる本．[7] はλ計算の標準的な教科書．　

評価

(総合評価)
総合評価 = 定期試験 × 0.7 + 小テスト × 0.3

(再試験について)
総合評価が60点未満の者に対して実施する場合がある．受験資格者については試験解説時にアナウンスする．

授業の属性・履修上の区分

ICT 利用

遠隔授業対応

授業計画

		週	授業内容	週ごとの到達目標
後期
	3rdQ
		1週	イントロダクション	予備知識を確認する．(計算 / アルゴリズムの定義 / Church-Turingのテーゼ / Turing機械 / Turing計算可能 / 再帰的定義とプログラム / λ抽象)
		2週	Turing機械の変種	Turing機械の変種について理解する．(多テープTuring機械 / 非決定性Turing機械 / 現実のコンピュータとTuring機械)
		3週	帰着可能性	帰着可能性について理解する．(帰着 / 帰着可能性と決定可能性 / Turing機械の停止問題 / Turing機械の空性問題 / Turing機械の正規性問題)
		4週	写像帰着可能性	写像帰着可能性について理解する．(写像帰着可能性 / 計算可能関数 / 写像帰着可能性と決定可能性 / 写像帰着可能性と認識可能性)
		5週	再帰定理	再帰定理について理解する．(自己の文字列表現を生成する機械 / 再帰定理)
		6週	P≠NP予想	計算の複雑性について理解する．(時間計算量 / 漸近分析 / 時間計算量クラス / 多テープTuring機械の時間計算量 / 非決定性Turing機械の時間計算量 / クラスP / クラスNP / P vs NP)
		7週	NP完全性	NP完全性について理解する．(ブール式 / 充足可能問題 / Cook-Levinの定理 / 多項式時間帰着 / NP完全)
		8週	λ計算	λ計算について理解する．(λ式 / Curry化 / λ項 / α同値，α変換)
	4thQ
		9週	後期中間試験	目的・到達目標(1)
		10週	後期中間試験の解答と解説
		11週	Church-Rosserの定理	Church-Rosserの定理について理解する．(β簡約 / Churchの数字 / Church-Rosserの定理)
		12週	型付きλ計算	型付きλ計算について理解する．(型 / 型付け / Subject Reduction定理 / 強正規化可能性定理 / 型検査)
		13週	自然演繹	自然演繹について理解する．(自然演繹の図式 / NK, NJ)
		14週	Curry-Howardの対応	計算と論理の対応関係について理解する．(λ計算とNJ / λ項による証明図の表現 / Curry-Howard対応 / β簡約と証明図の変形)
		15週	学年末試験	目的・到達目標(2)
		16週	学年末試験の解答と解説

評価割合

	試験	小テスト	合計
総合評価割合	70	30	100
専門的能力	70	30	100