計算理論

科目基礎情報

学校	奈良工業高等専門学校	開講年度	平成30年度 (2018年度)
授業科目	計算理論
科目番号	0021	科目区分	専門 / 選択
授業形態	講義	単位の種別と単位数	学修単位: 2
開設学科	システム創成工学専攻（情報システムコース）	対象学年	専1
開設期	前期	週時間数	2
教科書/教材	なし
担当教員	岡村 真吾

到達目標

・オートマトン理論や形式言語理論の基礎を理解する。
・計算可能性や計算複雑性についての理論を理解し、各種問題について、その計算可能性や計算複雑性を論ずることができるようになる。

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
オートマトン理論、 形式言語理論	与えられた言語が有限オートマトンやプッシュダウンオートマトンで認識可能か否かを判断できる。	有限オートマトンやプッシュダウンオートマトンに関する定義や定理を理解している。	有限オートマトンやプッシュダウンオートマトンに関する定義や定理を理解していない。
計算可能性	与えられた言語がチューリング機械で判定可能か否かを判断できる。	チューリング機械に関する定義や定理を理解している。	チューリング機械に関する定義や定理を理解していない。
計算複雑性	与えられた言語が属する計算量のクラスを判断できる。	時間計算量や領域計算量に関する定義や定理を理解している。	時間計算量や領域計算量に関する定義や定理を理解していない。

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

JABEE基準 (d-1)

JABEE基準 (d-2a)

システム創成工学教育プログラム学習・教育目標 B-2

システム創成工学教育プログラム学習・教育目標 D-1

教育方法等

概要:

計算理論の基礎を学習する。

授業の進め方・方法:

計算機を用いて各種問題を解くにあたり、その問題は計算機を用いて解くことができるか、あるいは、
解くためにはどのくらいの計算量やメモリ量を必要とするか、といったことを検討するために必要な
理論について学習する。

注意点:

【参考書】
　「計算理論の基礎　[原著第2版] 1. オートマトンと言語」、Michael Sipser著、太田和夫・田中圭介監訳、阿部正幸・植田広樹・藤岡淳・
　渡辺治訳、共立出版
　「計算理論の基礎　[原著第2版] 2. 計算可能性の理論」、Michael Sipser著、太田和夫・田中圭介監訳、阿部正幸・植田広樹・藤岡淳・
　渡辺治訳、共立出版
　「計算理論の基礎　[原著第2版] 3. 複雑さの理論」、Michael Sipser著、太田和夫・田中圭介監訳、阿部正幸・植田広樹・藤岡淳・
　渡辺治訳、共立出版
　「チューリングの計算理論入門」、高岡詠子著、講談社
【関連科目】
　情報数学、データ構造とアルゴリズム、計算機言語処理、情報理論、情報セキュリティ
【学習指針】
　できる限り講義時間中に理解することを心がけること。疑問点については、質問するなり文献等を調べるなりして、
　自ら進んで解決するように努めること。
【自己学習】
　各講義終了後速やかに、講義内容において理解できたことと理解できなかったことを整理すること。
　理解できなかったことについては、次回の講義までに解決しておくこと。
【評価割合】
　試験の成績（100%）で評価する。ただし、本科目への取り組み姿勢に問題がある場合（講義時間中に取り組むべき
　演習問題に取り組んでいない、レポート等の課題が未提出、提出物の内容が不十分、など）は減点することがある。

授業計画

		週	授業内容	週ごとの到達目標
前期
	1stQ
		1週	オートマトン(1)	有限オートマトンを理解する。
		2週	オートマトン(2)	正規表現と正規言語を理解する。
		3週	オートマトン(3)	文脈自由文法と文脈自由言語を理解する。
		4週	オートマトン(4)	文脈自由文法の標準形を理解する。
		5週	オートマトン(5)	プッシュダウンオートマトンを理解する。
		6週	計算可能性(1)	チューリング機械を理解する。
		7週	計算可能性(2)	非決定性チューリング機械を理解する。
		8週	計算可能性(3)	判定可能問題を理解する。
	2ndQ
		9週	計算可能性(4)	判定不能問題を理解する。
		10週	計算可能性(5)	帰着を理解する。
		11週	計算複雑性(1)	時間計算量の基礎を理解する。
		12週	計算複雑性(2)	クラスPを理解する。
		13週	計算複雑性(3)	クラスNPを理解する。
		14週	計算複雑性(4)	NP完全を理解する。
		15週	計算複雑性(5)	領域計算量を理解する。
		16週	期末試験	授業内容を理解し、正しく解答することができる。

評価割合

	試験	合計
総合評価割合	100	100
専門的能力	100	100