2024年 理工学部 シラバス - 応用情報工学科
設置情報
| 科目名 | オートマトン | ||
|---|---|---|---|
| 設置学科 | 応用情報工学科 | 学年 | 4年 |
| 担当者 | 保谷 哲也 | 履修期 | 前期 |
| 単位 | 2 | 曜日時限 | 火曜4 |
| 校舎 | 船橋 | 時間割CD | K24B |
| クラス | |||
| 履修系統図 | 履修系統図の確認 | ||
概要
| 学修到達目標 | オートマトンは、例えば、エレベーターや自動販売機などの機械動作過程について数学的に表現したり、コンピュータにおけるプログラミング言語の根幹を成す字句解析部、さらには我々が普段会話に用いる言語の論理構造を形式化するまでに至るような数学的記法の一つである。このようなオートマトンの概念を習得することができる。 |
|---|---|
| 授業形態及び 授業方法 |
対面形式にて行う。 |
| 履修条件 | 特になし。 |
| ディプロマ・ポリシー（DP）及びカリキュラム・ポリシー（CP）との関連 | 本授業科目はDP1・3・5及びCP1・3・5に該当しています。 |
授業計画
| 第1回 | オートマトンとは？ この科目で学ぶこと/今後の予定 | 事前学修：シラバスの確認 事後学修：今後行われる授業の流れについて | 事前学修：2時間 事後学修：2時間 |
|---|---|---|---|
| 第2回 | 集合・グラフ - 集合の定義・演算・グラフの基礎概念 | 事前学修：これまで学んだ集合・グラフについての復習 事後学修：集合およびその演算、グラフの定義・木構造について | 事前学修：2時間 事後学修：2時間 |
| 第3回 | 記号列と言語 - アルファベット・形式言語・所属問題・例（自動販売機） | 事前学修：形式言語とは何かについて事前に調べる 事後学修：記号の定義・記号列の演算および形式言語についての数学的な定義について | 事前学修：2時間 事後学修：2時間 |
| 第4回 | 正規表現（１） - 正規表現の定義・例・演習・正規表現の限界について | 事前学修：正規表現とは何かについて 事後学修：今後本講義で使用する正規表現、講義で登場した正規表現の例について | 事前学修：2時間 事後学修：2時間 |
| 第5回 | 決定性有限オートマトン(DFA) - 状態遷移図・5項組による定義 | 事前学修：決定性有限オートマトンという意味について 事後学修：正規表現や缶ジュース自動販売機をDFAと見立てた場合の動作、状態遷移図および5項組による数学的表現について | 事前学修：2時間 事後学修：2時間 |
| 第6回 | 非決定性有限オートマトン(NFA) - 非決定性とは・5項組による定義 | 事前学修：非決定性有限オートマトンとは何かについて 事後学修：正規表現や缶ジュース自動販売機をNFAと見立てた場合の動作、状態遷移図および5項組による表現法について | 事前学修：2時間 事後学修：2時間 |
| 第7回 | NFAからDFAへの等価変換 | 事前学修：DFAとNFAとの違いについての復習 事後学修：NFAからDFAへの等価変換法について | 事前学修：2時間 事後学修：2時間 |
| 第8回 | 授業内小テストAおよび解説 | 事前学修：これまで学んできたことのまとめ・復習 事後学修：小テストBの内容 | 事前学修：2時間 事後学修：2時間 |
| 第9回 | e-遷移を含む非決定性有限オートマトン(e-NFA) - e-遷移とは・５項組による定義 | 事前学修：e-遷移とは何かについて調べる 事後学修：e-NFAによる缶ジュース自動販売機の表現例・正規表現との関係について | 事前学修：2時間 事後学修：2時間 |
| 第10回 | e-NFAからNFA/DFAへの等価変換 | 事前学修：DFA、NFA、e-NFAの違いについての復習 事後学修：e-NFAからNFAまたはe-NFAからDFAへの等価変換について | 事前学修：2時間 事後学修：2時間 |
| 第11回 | 最小のDFA - 最小化のアルゴリズム | 事前学修：冗長なオートマトンとは何かについて 事後学修：講義で登場した冗長なDFAを最小化するアルゴリズムとその適用例について | 事前学修：2時間 事後学修：2時間 |
| 第12回 | 正規表現（２） - 正規表現からe-NFAへの変換・DFA/NFA/e-NFAの相互変換について | 事前学修：正規表現および3種類の有限オートマトン(DFA/NFA/e-NFA)との関係について 事後学修：講義で登場した正規表現を等価なe-NFAに変換する手法について | 事前学修：2時間 事後学修：2時間 |
| 第13回 | チョムスキー階層・文脈自由文法 - Chomskyによる言語の階層への分割について・文脈自由文法について | 事前学修：チョムスキー階層とは何か、また言語の階層化について 事後学修：正規言語と文脈自由言語との違いについて | 事前学修：2時間 事後学修：2時間 |
| 第14回 | プッシュダウンオートマトン(PDA) - 文脈自由文法をPDAにより実現・例・7項組による定義 | 事前学修：プッシュダウンオートマトンの意味について調べる 事後学修：PDAの構造・動作、およびPDAによる文脈自由言語の実現例について | 事前学修：2時間 事後学修：2時間 |
| 第15回 | 授業内小テストBおよび解説 | 事前学修：これまで学んできたことの総まとめ・復習 事後学修：小テストBの内容 | 事前学修：2時間 事後学修：2時間 |
その他
| 教科書 |
特になし。ただし、内容的には佐賀大学理工学部知能情報システム学科・山下先生著の講義資料に沿う：
https://www.fu.is.saga-u.ac.jp/yaman/yamane.html（２０２０年時点ではPDFがダウンロード可。非常にまとまりが良くオートマトンの全体像が掴み易い。）
|
|---|---|
| 参考書 |
タイトルに「オートマトン」を含むものはたくさん見つかるが、米田政明監修『オートマトン・言語理論の基礎』近代科学社 第１８版 ２０２０年 は演習問題・解答も充実していると思うのでおすすめである。
|
| 成績評価の方法 及び基準 |
授業内において度々出題される演習課題および授業内にて2回行う小テストによって評価する。以上について評価し（演習課題等50%、小テスト50%）、その６０点以上を合格とする。 |
| 質問への対応 | メールにていつでも対応可。 |
| 研究室又は 連絡先 |
houya.tetsuya@nihon-u.ac.jp |
| オフィスアワー |
火曜 船橋 12:15 ～ 13:15
|
| 学生への メッセージ |