検索したい科目／教員名／キーワードを入力し「検索開始｣ボタンをクリックしてください。
※教員名では姓と名の間に１文字スペースを入れて、検索してください。
コンピュータ科学特論
| 科目名 | コンピュータ科学特論 | ||||
|---|---|---|---|---|---|
| 教員名 | 戸田 誠之助 | ||||
| 単位数 | 2 | 学年 | 4 | 開講区分 | 文理学部 |
| 科目群 | 情報科学科 | ||||
| 学期 | 前期 | 履修区分 | 選択 | ||
| 授業テーマ | オートマトンと形式言語の発展的な話題，ならびに，計算理論の基礎的な話題。 |
|---|---|
| 授業のねらい・到達目標 | 本学部2年次科目の「オートマトン」ならびに3年次科目の「応用形式言語」と「論理と計算」の内容を下地に，この授業の前半ではオートマトン・形式言語の発展的な事項を解説する。特に，非正則性の証明ならびにプッシュダウン・オートマトンと文脈自由文法の等価性を理解することを目標に授業を行う．さらに，後半では計算可能性の理論を解説する。特に，現在のアルゴリズム（計算可能性）の概念がチューリング機械によって定式化されることと，計算不可能な問題が存在することを理解することを目標に授業を進める．さらに，計算不可能性の応用的な話題として，連接理論や自然数論の認識不可能性，一階論理の判定不可能性，形式的体系の不完全性などを時間の許す限り解説する． |
| 授業の方法 | 講義形式で行う。 |
| 履修条件 | 有限オートマトン，文脈自由文法，一階論理（述語論理）に関する基礎事項を理解していること。 |
| 事前学修・事後学修，授業計画コメント | 例題を中心にそれまでの授業内容を十分に復習してくること。 |
| 授業計画 | |
|---|---|
| 1 | 正則言語の基礎事項（復習） |
| 2 | 正則言語の反復補題と非正則性の証明 |
| 3 | 文脈自由言語の基礎事項（復習） |
| 4 | プッシュダウン・オートマトン |
| 5 | 文脈自由文法からプッシュダウン・オートマントへ |
| 6 | プッシュダウン・オートマントから文脈自由文法へ |
| 7 | チューリング機械とChurch-Turingの提唱 |
| 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著／太田和夫他訳 『計算理論の基礎（原著第２版）』 共立出版 2009年 第2版 George S. Boolos, John P. Burgess, Richard C. Jeffrey, Computability and Logic (5th edition), Cambridge University Press, 2007, 5 edition |
| 成績評価の方法及び基準 | レポート(100%) |
| オフィスアワー | 毎週水曜日１２：１０〜１３：００ |