検索したい科目／教員名／キーワードを入力し「検索開始｣ボタンをクリックしてください。
※教員名では姓と名の間に１文字スペースを入れて、検索してください。
コンピュータ科学特論Ⅰ
| 科目名 | コンピュータ科学特論Ⅰ | ||||
|---|---|---|---|---|---|
| 教員名 | 戸田 誠之助 | ||||
| 単位数 | 2 | 課程 | 前期課程 | 開講区分 | 文理学部 |
| 学期 | 前期 | 履修区分 | 選択必修 | ||
| 授業テーマ | オートマトンと形式言語の発展的な話題，ならびに，計算可能性の理論の基礎的な話題。 |
|---|---|
| 授業のねらい・到達目標 | 有限オートマトン，文脈自由言語，一階論理（述語論理）への理解を下地に，この授業の前半ではオートマトン・形式言語の発展的な事項を解説する。特に，非正則性の証明ならびにプッシュダウン・オートマトンと文脈自由文法の等価性への理解を目標に授業を行う．授業の後半では計算可能性の理論を解説する。特に，現在のアルゴリズム（計算可能性）の概念がチューリング機械によって定式化されることと，計算不可能な問題が存在することへの理解を目標に授業を進める．さらに，計算不可能性の応用的な話題として，一階論理の判定不可能性，連接理論や自然数論の認識不可能性，形式的体系の不完全性などを時間の許す限り解説する． |
| 授業の方法 | 講義形式で行う。 |
| 履修条件 | 有限オートマトン，文脈自由文法，一階論理（述語論理）に関する基礎事項を理解していること。 |
| 事前学修・事後学修，授業計画コメント | 例題を中心にそれまでの授業内容を十分に復習してくること。 |
| 授業計画 | |
|---|---|
| 1 | 有限オートマトンの基礎事項（復習） |
| 2 | 正則言語の反復補題と非正則性の証明 |
| 3 | 文脈自由文法の基礎事項（復習） |
| 4 | プッシュダウンオートマトン |
| 5 | 文脈自由文法からプッシュダウンオートマトンへ |
| 6 | プッシュダウンオートマトンから文脈自由文法へ |
| 7 | チューリング機械とチャーチ・チューリングの提唱 |
| 8 | 簡易プログラミング言語 |
| 9 | 万能チューリング機械 |
| 10 | 認識可能性，判定可能性，還元可能性 |
| 11 | 対角集合と反対角集合，対角線論法，停止性判定問題 |
| 12 | 全停止判定問題や空集合問題などの認識不可能性 |
| 13 | 一階論理（述語論理）の認識不可能性と判定不可能性 |
| 14 | 連接理論の認識不可能性 |
| 15 | 自然数論（真の算術）の認識不可能性 |
| その他 | |
|---|---|
| 教科書 | 授業内容はおおよそ参考書に準じるが，講義ノートと配布資料だけで学習できるように授業を行う． |
| 参考書 | Michael Sipser, Introduction to the Theory of Computation (3rd edition), Cengage Learning, 2012, 3 edition Michael Sipser（著）／太田和夫他（翻訳） 『計算理論の基礎 [原著第2版]』 共立出版 2008年 第2版 George S. Boolos, John P. Burgess, Richard C. Jeffrey, Computability and Logic (5th edition), Cambridge University Press, 2007, 5 edition |
| 成績評価の方法及び基準 | レポート(100%) |
| オフィスアワー | 水曜日１２：１０〜１３：００ |