文理学部シラバスTOP > 大学院博士前期課程 > 地球情報数理科学専攻 > コンピュータ科学特論Ⅱ
日本大学ロゴ

コンピュータ科学特論Ⅱ

このページを印刷する

科目名 コンピュータ科学特論Ⅱ
教員名 戸田 誠之助
単位数    2 課程 前期課程 開講区分 文理学部
学期 前期 履修区分 選択必修
授業テーマ オートマトンと形式言語の発展的な話題,ならびに,計算理論の基礎的な話題。
授業のねらい・到達目標 本学部2年次科目の「オートマトン」ならびに3年次科目の「応用形式言語」の内容を下地に,この授業の前半ではオートマトン・形式言語の発展的な事項を解説する。特に,非正則性の証明,プッシュダウン・オートマトンと文脈自由文法の等価性,非文脈自由性の証明を理解して欲しい。さらに,後半では計算理論の基礎的な事項を解説する。特に,現在のアルゴリズム(計算可能性)の概念がチューリング機械によって定式化されることと,計算不可能な問題が存在することを理解して欲しい。
授業の方法 講義形式で行う。
履修条件 オートマトンと文脈自由文法に関する基礎事項を理解していること。
事前学修・事後学修,授業計画コメント 例題を中心にそれまでの授業内容を十分に復習してくること。
授業計画
1正則言語の基礎事項(復習)
2正則言語の反復補題と非正則性の証明
3右不変同値関係と最小オートマトン
4文脈自由言語の基礎事項(復習)
5プッシュダウン・オートマトン
6文脈自由文法からプッシュダウン・オートマントへ
7プッシュダウン・オートマントから文脈自由文法へ
8文脈自由言語の反復補題と非文脈自由性の証明
9チューリング機械とChurch-Turingの提唱
10対角線論法
11停止性判定問題の計算不可能性
12帰着可能性とその基本的な性質
13帰着可能性の応用:空集合問題,正則性判定問題,等価性判定問題
14帰着可能性の応用:ポストの対応問題
15計算理論における発展的な話題
その他
教科書 講義ノートと配布資料だけで学習できるように授業を行う。
参考書 J.ホップクロフト,R.モトワニ,J.ウルマン  『オートマトン 言語理論 計算論 I』 サイエンス社 2003年 第2版
Michael Sipser著/太田和夫他訳 『計算理論の基礎(原著第2版)』 共立出版 2009年 第1版
岩田茂樹,笠井琢美  『有限オートマトン』 森北出版 1991年 第1版
成績評価の方法及び基準 レポート(100%)
オフィスアワー 毎週水曜日12:10〜13:00

このページのトップ