計算の理論

Computation Theory

 

情報工学科  選択 2単位 1年春学期

 

【授業の目的】

 計算機科学における文法やアルゴリズム、およびプログラミング言語における関数やデータ型を理解する基礎となる集合、写像、関係の概念を学ぶ。さらに、プログラミングの基礎となる言語とオートマトン、および言語の表現形式について学ぶ。

 

【テキスト】  米田政明 他 著:「オートマトン・言語理論の基礎」、近代科学社

 

【評価の方法】

 課題の評価、中間試験、期末試験などで総合的に評価する。

 

【授業計画】

1.     はじめに

2.     集合と写像の復習

3.     決定性有限オートマトン                      

4.     非決定性有限オートマトン                      

5.     有限オートマトンが認識する言語

6.     有限オートマトンの最簡形

7.     プッシュダウンオートマトン                    

8.     プッシュダウンオートマトンが認識する言語    

9.     Turingマシン

10.  形式文法と形式言語

11.  正規表現と有限オートマトン

12.  文脈自由文法とプッシュダウンオートマトン

13.  句構造文法とTuringマシン

14.  言語の階層構造

15.  期末試験

 

決定性有限オートマトンのスライド(内容:決定性有限オートマトンの説明;【例2.1M21)はこちら

非決定性有限オートマトンのスライド(内容:非決定性有限オートマトンの説明;【例2.4M22)はこちら

空動作のある非決定性有限オートマトンのスライド(内容:空動作のある非決定性有限オートマトンの説明;【例2.5M23)はこちら

決定性プッシュダウンオートマトンのスライド(内容:決定性プッシュダウンオートマトンの説明;【例3.1M31)はこちら

非決定性プッシュダウンオートマトンのスライド(内容:非決定性プッシュダウンオートマトンの説明;【例3.2M32)はこちら

決定性PDAと非決定性PDAのスライド(内容:決定性プッシュダウンオートマトンと非決定性プッシュダウンオートマトンの言語受理能力の差;【例3.3M33と【例3.4M34)はこちら

チューリング機械のスライド(内容:チューリング機械の説明;【例4.1】(【例4.2】に同じ)M41と【例4.3M42)はこちら

非決定性チューリング機械のスライド(内容:非決定性チューリング機械;【例4.4M43)はこちら

計算機械としてのチューリング機械のスライド(内容:2進数の和を計算するチューリング機械;【例4.5M44)はこちら

 

【備考】

 選択科目ではあるが,情報処理の理論的基礎となる科目なので、できるだけ履修することを薦める.