オートマトン・形式言語及び演習（3.0 単位） | |||
| 講義番号 | ： | 766 | |
| 科目区分 | ： | 専門基礎科目 | |
| 授業形態 | ： | 講義及び演習 | |
| 対象履修コース | ： | 情報工学 | |
| 開講時期１ | ： | ２年後期 | |
| 必修／選択 | ： | 必修 | |
| 担当教員 | ： | 酒井 正彦 教授 | 橋本 健二 助教 |
| •本講座の目的およびねらい |
| オートマトン理論・形式言語理論とは抽象的な計算装置の理論であり，コンパイラへの応用やモデル検査アルゴリズムへの応用などの情報処理全般の理論的基礎である．本講義では，これらの理論の基本的事項を学ぶ． 達成目標 １．オートマトン理論・形式言語理論の基本概念を理解し，説明できる． ２．異なる言語の表現間の変換を理解し，計算できる． ３．基本的な定理の証明を理解し，簡単な問題の証明に応用できる． |
| •バックグラウンドとなる科目 |
| 離散数学及び演習 |
| •授業内容 |
| １．有限オートマトン ２．NFAとDFAの能力の等価性 ３．ε動作 ４．正規表現とその性質 ５. 有限オートマトンの最小化 ６．文脈自由文法と構文木 ７．プッシュダウンオートマトン ８．文脈自由文法の標準形 ９．文脈自由言語の反復補題，チューリング機械 |
| •教科書 |
| 授業で用いるスライドのハンドアウトをＷＥＢ上に用意する． テキスト： J．ホップクロフト／J．ウルマン「オートマトン 言語理論 計算論Ｉ」、野崎明弘ら訳、サイエンス社、ＩＳＢＮ ４－７８１９－０３７４－Ｘ |
| •参考書 |
| なし |
| •評価方法と基準 |
| 達成目標に対する評価の重みは同等である．演習３０％，中間試験３０％，試験４０％で評価し，１００点満点で ６０点以上を合格とする． |
| •履修条件・注意事項 |
| •質問への対応 |
| 講義ならびに演習終了後30分間に対応する．それ以外は事前に時間などを打ち合わせること． 連絡先： 内線3803 sakai at is.nagoya-u.ac.jp URL： http://www.trs.cm.is.nagoya-u.ac.jp/~sakai/lecture/automata/ |