文理学部シラバスTOP > 文理学部 > 情報科学科（情報システム解析学科） > オートマトン
日本大学ロゴ

オートマトン

このページを印刷する

平成２８年度以前入学者 オートマトン
教員名 夜久竹夫
単位数    2 学年    2 開講区分 文理学部
科目群 情報科学科
学期 後期 履修区分 選択必修
授業の形態 同時双方向型授業
Blackboard ID : 20203290
授業概要 コンピュータサイエンスの基礎理論の一つであるオートマトンの基本概念を明らかにし、オートマトンに関する基本的な定義と性質を講義する。
授業のねらい・到達目標 有限オートマトンを題材にして、決定性オートマトンと非決定性オートマトンの動作の関係を理解できるようになる。さらに有限オートマトンを一般化することにより、計算のモデルであるチューリングマシンについても概要が理解できるようになる。

この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応している。
授業の方法 パワーポイントと配布資料データを使用する。
Blackboard, WEBEX TEAMS, Zoom, google 等を使用する。
あらかじめ、WEBEX TEAMS 及び Zoom を利用可能にしておくこと。
履修条件 再履修者用に開講された講義である。
授業計画
1 ガイダンス（授業のテーマや到達目標及び授業の方法について説明する）、オートマトン概観（オンライン授業）
・1回目授業ではBlackboard の当該「コース」（科目）内の「連絡事項」を見て、指示に従う事。
【事前学習】シラバスを事前に確認し、授業全体の流れを理解すること （2時間）
【事後学習】第２回目以降の授業に備え、情報科学の言葉遣いになれておくこと。 （2時間）
2 アルファベット、文字列、言語（オンライン授業）
【事前学習】教科書１．５節を読んでおくこと （2時間）
【事後学習】アルファベット、文字列、言語の定義と例をノートにまとめる。 （2時間）
3 決定性有限オートマトン（DFA）の定義（オンライン授業）
【事前学習】教科書２．１節を読んでおくこと。 （2時間）
【事後学習】DFAの定義をノートにまとめる。 （2時間）
4 決定性有限オートマトンの受理言語（オンライン授業）
【事前学習】教科書２．２．５節を読んでおくこと。 （2時間）
【事後学習】DFAの遷移関数と受理言語の定義をノートにまとめる。 （2時間）
5 決定性有限オートマトンの例と応用（オンライン授業）
【事前学習】教科書２．１節を読み直しておくこと。 （2時間）
【事後学習】第４回までの授業内容をもとにDFAの例を考察する。 （2時間）
6 非決定性有限オートマトン（NFA）の定義（オンライン授業）
【事前学習】教科書２．３．２節を読んでおくこと。 （2時間）
【事後学習】NFAの定義をノートにまとめる。 （2時間）
7 非決定性有限オートマトンの受理言語（オンライン授業）
【事前学習】教科書２．３．４節を読んでおくこと。 （2時間）
【事後学習】NFAの遷移関数と受理言語の定義をノートにまとめる。 （2時間）
8 非決定性有限オートマトンの例と応用（オンライン授業）
【事前学習】教科書２．４節を読んでおくこと。 （2時間）
【事後学習】教科書２．４節を参考にNFAとテキスト検索の関係をノートにまとめる。 （2時間）
9 決定性有限オートマトンと非決定性有限オートマトンの等価性（オンライン授業）
【事前学習】教科書２．３．５節を読んでおくこと。 （2時間）
【事後学習】NFAとDFAの等価性の証明をノートにまとめる。 （2時間）
10 ε-動作を含む有限オートマトン（εーNFA)の定義と性質（オンライン授業）
【事前学習】教科書２．５節を読んでおくこと。 （2時間）
【事後学習】εーNFAとNFAの等価性の証明をノートにまとめる。 （2時間）
11 有限オートマトンと正則表現の等価性（オンライン授業）
【事前学習】教科書３章に目を通しておくこと。 （2時間）
【事後学習】正則言語の定義と、有限オートマトンと正則表現の等価性の証明をノートにまとめる。 （2時間）
12 有限オートマトンの反復補題と応用（オンライン授業）
【事前学習】教科書４．１節を読んでおくこと。 （2時間）
【事後学習】ある種の言語が正則言語でないことを反復補題を用いて証明する方法をノートにまとめる。 （2時間）
13 各種オートマトンとチューリングマシン（オンライン授業）
【事前学習】教科書５章と６章に目を通しておくこと。 （2時間）
【事後学習】各種オートマトンのコンピュータサイエンスにおける役割について考える。 （2時間）
14 授業内テスト（オンライン方式）
【事前学習】第２回～第１３回の内容を復習すること。(A-8-2) （2時間）
【事後学習】学修した内容の整理をする。 （2時間）
15 まとめ（これまでの復習・解説を行い授業の理解を深める）（オンライン授業）
レポートとノートコピー提出（メール及び会議システムによる）
【事前学習】第１回～第１４回の内容をまとめ、ノートを整理しておく。 （2時間）
【事後学習】提示された話題について考察する。 （2時間）
その他
教科書 J. ホップクロフト，R. モトワニ，J．ウルマン 『オートマトン言語理論計算論Ⅰ』 サイエンス社 ２００３年 第２版
参考書 使用しない
成績評価の方法及び基準 レポート:課題を授業中に提示する(30%)、授業内テスト:小テストを含む(50%)、授業参画度(20%)
・レポートは課題及びノートを含む。第15回でノートを回収する。
・小テストは授業進行に合わせて適宜実施する。
・授業参画度は、遠隔授業中の質疑応答の回数及び出席回数等により評価する。
オフィスアワー 授業時間後に行うWEBEX TEAMS による質問・相談受付及び授業時間外のメール受付（1回目授業で方法を指示）により代用する。
備考 ・1回目授業ではBlackboard の当該「コース」（科目）内の「連絡事項」を見て、指示に従うこと。
・あらかじめ、WEBEX TEAMS 及び Zoom を利用可能にしておくこと。
・各回の内容についてプログラムを作ることが望ましい。

↑このページのトップ