2024年 大学院理工学研究科 シラバス - 情報科学専攻
設置情報
| 科目名 | オートマトン論 | ||
|---|---|---|---|
| 設置学科 | 情報科学専攻 | 学年 | 1年 |
| 担当者 | 吉開 範章 | 履修期 | 前期 |
| 単位 | 2 | 曜日時限 | 金曜3 |
| 校舎 | 船橋 | 時間割CD | K53A |
| クラス | |||
| その他 | 実務経験のある教員による授業科目 | ||
概要
| 学修到達目標 | 「計算とは何であるか？」という命題を、集合論、グラフ、数学的証明などを駆使して理解すると共に、計算の複雑さを測定する理論についても学習し、計算機工学の基礎概念を理解し、さらに発展させることができるようになる。 |
|---|---|
| 授業形態及び 授業方法 |
対面授業。 講義だけでなく、企業研究所での実務経験を活かして、受講生自身で、与えらた課題に対する調査発表＆討論も実施する。 |
|
準備学習（予習・ 復習等）の内容・ 受講のための 予備知識 |
教科書の該当箇所を予習すること |
授業計画
| 第1回 | オートマトンの定義と意味 | 【事前学修】ラバスの内容を確認の上、授業に臨む事。 【事後学修】講義中の内容を復習し、理解しておく事。 | 【事前学修】 ２時間 【事後学修】 ２時間 |
|---|---|---|---|
| 第2回 | オートマトンと記号システムの歴史：誕生／成長／限界 | 【事前学修】35ページから50ページを読んで理解出来ない箇所を質問できるようにまとめておく事。 【事後学修】講義中の内容を復習し、理解しておく事。 | 【事前学修】 ２時間 【事後学修】 ２時間 |
| 第3回 | 有限オートマトン１ | 【事後学修】講義中で解いた課題を復習し、理解しておく事。 【事前学修】51ページから73ページを読んで理解出来ない箇所を質問できるようにまとめておく事。 | 【事前学修】 ２時間 【事後学修】 ２時間 |
| 第4回 | 非決定性 | 【事後学修】講義中で解いた課題を復習し、理解しておく事。 【事前学修】74ページから88ページを読んで理解出来ない箇所を質問できるようにまとめておく事。 | 【事前学修】 ２時間 【事後学修】 ２時間 |
| 第5回 | 正規表現 | 【事後学修】講義中で解いた課題を復習し、理解しておく事。 【事前学修】89ページから96ページを読んで理解出来ない箇所を質問できるようにまとめておく事。 | 【事前学修】 ２時間 【事後学修】 ２時間 |
| 第6回 | 非正規表現 | 【事後学修】講義中で解いた課題を復習し、理解しておく事。 【事前学修】97ページから130ページを読んで理解出来ない箇所を質問できるようにまとめておく事。 | 【事前学修】 ２時間 【事後学修】 ２時間 |
| 第7回 | 文脈自由言語１ | 【事後学修】講義中で解いた課題を復習し、理解しておく事。 【事前学修】131ページから144ページを読んで理解出来ない箇所を質問できるようにまとめておく事。 | 【事前学修】 ２時間 【事後学修】 ２時間 |
| 第8回 | 文脈自由言語２ | 【事後学修】講義中で解いた課題を復習し、理解しておく事。 【事前学修】145ページから150ページを読んで理解出来ない箇所を質問できるようにまとめておく事。 | 【事前学修】 ２時間 【事後学修】 ２時間 |
| 第9回 | チューリングマシン | 【事後学修】講義中で解いた課題を復習し、理解しておく事。 【事前学修】151ページから170ページを読んで理解出来ない箇所を質問できるようにまとめておく事。 | 【事前学修】 ２時間 【事後学修】 ２時間 |
| 第10回 | アルゴリズム | 【事後学修】講義中で解いた課題を復習し、理解しておく事。 【事前学修】171ページから186ページを読んで理解出来ない箇所を質問できるようにまとめておく事。 | 【事前学修】 ２時間 【事後学修】 ２時間 |
| 第11回 | 判定可能性１ | 【事後学修】講義中で解いた課題を復習し、理解しておく事。 【事前学修】187ページから203ページを読んで理解出来ない箇所を質問できるようにまとめておく事。 | 【事前学修】 ２時間 【事後学修】 ２時間 |
| 第12回 | 判定可能性２ | 【事後学修】講義中で解いた課題を復習し、理解しておく事。 【事前学修】204ページから215ページを読んで理解出来ない箇所を質問できるようにまとめておく事。 | 【事前学修】 ２時間 【事後学修】 ２時間 |
| 第13回 | 帰着可能性１ | 【事後学修】講義中で解いた課題を復習し、理解しておく事。 【事前学修】216ページから236ページを読んで理解出来ない箇所を質問できるようにまとめておく事。 | 【事前学修】 ２時間 【事後学修】 ２時間 |
| 第14回 | 帰着可能性２ | 【事後学修】講義中で解いた課題を復習し、理解しておく事。 【事前学修】237ページから250ページを読んで理解出来ない箇所を質問できるようにまとめておく事。 | 【事前学修】 ２時間 【事後学修】 ２時間 |
| 第15回 | これまでのまとめ | 【事前学修】これまでの資料を読んで理解出来ない箇所を質問できるようにまとめておく事。 | 【事前学修】 ２時間 【事後学修】 ２時間 |
その他
| 教科書 |
Michael Sipser 『計算理論の基礎 和書 』 共立出版 2008年 第２版
毎回使用するので、必ず準備すること。
|
|---|---|
| 参考資料コメント 及び 資料（技術論文等） |
|
| 成績評価の方法 及び基準 |
レポート（１００％） |
| 質問への対応 | メールで随時。 |
| 研究室又は 連絡先 |
e-mail: yoshikai.noriaki@nihon-u.ac.jp |
| オフィスアワー | |
| 学生への メッセージ |