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

オートマトン（再履）

このページを印刷する

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

この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応しています。
授業の方法 パワーポイントと配布印刷物を使用し、講義形式で行う。
本授業の事前・事後学習は，各２時間の学習を目安とする。
履修条件 再履修者用に開講された講義である。
授業計画
1 ガイダンス（授業のテーマや到達目標及び授業の方法について説明する）
オートマトン概観
【事前学習】シラバスを事前に確認すること。
【事後学習】第２回目以降の授業に備え、情報科学の言葉遣いになれておくこと。
2 アルファベット、文字列、言語
【事前学習】教科書１．５節を読んでおくこと
【事後学習】アルファベット、文字列、言語の定義と例をノートにまとめる。
3 決定性有限オートマトン（DFA）の定義
【事前学習】教科書２．１節を読んでおくこと。
【事後学習】DFAの定義をノートにまとめる。
4 決定性有限オートマトンの受理言語
【事前学習】教科書２．２．５節を読んでおくこと。
【事後学習】DFAの遷移関数と受理言語の定義をノートにまとめる。
5 決定性有限オートマトンの例と応用
【事前学習】教科書２．１節を読み直しておくこと。
【事後学習】第４回までの授業内容をもとにDFAの例を考察する。
6 非決定性有限オートマトン（NFA）の定義
【事前学習】教科書２．３．２節を読んでおくこと。
【事後学習】NFAの定義をノートにまとめる。
7 非決定性有限オートマトンの受理言語
【事前学習】教科書２．３．４節を読んでおくこと。
【事後学習】NFAの遷移関数と受理言語の定義をノートにまとめる。
8 非決定性有限オートマトンの例と応用
【事前学習】教科書２．４節を読んでおくこと。
【事後学習】教科書２．４節を参考にNFAとテキスト検索の関係をノートにまとめる。
9 決定性有限オートマトンと非決定性有限オートマトンの等価性
【事前学習】教科書２．３．５節を読んでおくこと。
【事後学習】NFAとDFAの等価性の証明をノートにまとめる。
10 ε-動作を含む有限オートマトン（εーNFA)の定義と性質
【事前学習】教科書２．５節を読んでおくこと。
【事後学習】εーNFAとNFAの等価性の証明をノートにまとめる。
11 有限オートマトンと正則表現の等価性
【事前学習】教科書３章に目を通しておくこと。
【事後学習】正則言語の定義と、有限オートマトンと正則表現の等価性の証明をノートにまとめる。
12 有限オートマトンの反復補題と応用
【事前学習】教科書４．１節を読んでおくこと。
【事後学習】ある種の言語が正則言語でないことを反復補題を用いて証明する方法をノートにまとめる。
13 各種オートマトンとチューリングマシン
【事前学習】教科書５章と６章に目を通しておくこと。
【事後学習】各種オートマトンのコンピュータサイエンスにおける役割について考える。
14 試験と解説
【事前学習】第２回～第１３回の内容を復習すること。
【事後学習】学修した内容の整理をする。
15 まとめ（これまでの復習・解説を行い授業の理解を深める）、ノート提出。
【事前学習】第１回～第１４回の内容をまとめ、ノートを整理しておく。
【事後学習】提示された話題について考察する。
その他
教科書 J. ホップクロフト，R. モトワニ，J．ウルマン 『オートマトン言語理論計算論Ⅰ』 サイエンス社 ２００３年 第２版
参考書 使用しない
成績評価の方法及び基準 授業内テスト(50%)、授業参画度(50%)
授業参画度は、小レポート、ディカッション、発表等で評価します。
授業内テストは、期末試験、小テスト等により評価します。なお、小テストは授業進行に合わせて適宜実施する。
オフィスアワー 授業終了後、講師室にて２０分間
備考 ・教室前方出入口からの無断退席者は減点する場合がある。
・授業中は特別な場合以外はサングラス不可、男子脱帽。
・各回の内容についてプログラムを作ることが望ましい。

↑このページのトップ