オートマトン論 (K53A)

日本大学理工学部

2020年大学院理工学研究科シラバス - 情報科学専攻

設置情報

科目名	オートマトン論
設置学科	情報科学専攻	学年	1年
担当者	吉開　範章	履修期	前期
単位	2	曜日時限	金曜3
校舎	駿河台	時間割CD	K53A
クラス

概要

学修到達目標	「計算とは何であるか？」という命題を、集合論、グラフ、数学的証明などを駆使して理解すると共に、計算の複雑さを測定する理論についても学習し、計算機工学の基礎概念を理解し、さらに発展させることができるようになる。
授業形態及び授業方法	講義だけでなく、受講生自身で、与えらた課題に対する調査発表＆討論も実施する。
準備学習（予習・復習等）の内容・受講のための予備知識	教科書の該当箇所を予習すること

授業計画

第1回	オートマトンの定義と意味【事前学習】シラバスの内容を確認の上、授業に臨む事。
第2回	オートマトンと記号システムの歴史：誕生／成長／限界【事前学習】テキスト35ページから50ページを読んで理解出来ない箇所を質問できるようにまとめておく事。（120分）
第3回	有限オートマトン１【事後学習】前回の講義中で解いた課題を復習し、理解しておく事。（120分）【事前学習】50ページから73ページを読んで理解出来ない箇所を質問できるようにまとめておく事。（120分）
第4回	非決定性【事後学習】前回の講義中で解いた課題を復習し、理解しておく事。（120分）【事前学習】73ページから88ページを読んで理解出来ない箇所を質問できるようにまとめておく事。（120分）
第5回	正規表現【事後学習】前回の講義中で解いた課題を復習し、理解しておく事。（120分）【事前学習】88ページから96ページを読んで理解出来ない箇所を質問できるようにまとめておく事。（120分）
第6回	非正規表現【事後学習】前回の講義中で解いた課題を復習し、理解しておく事。（120分）【事前学習】115ページから130ページを読んで理解出来ない箇所を質問できるようにまとめておく事。（120分）
第7回	文脈自由言語１【事後学習】前回の講義中で解いた課題を復習し、理解しておく事。（120分）【事前学習】130ページから144ページを読んで理解出来ない箇所を質問できるようにまとめておく事。（120分）
第8回	文脈自由言語２【事後学習】前回の講義中で解いた課題を復習し、理解しておく事。（120分）【事前学習】144ページから150ページを読んで理解出来ない箇所を質問できるようにまとめておく事。（120分）
第9回	チューリングマシン【事後学習】前回の講義中で解いた課題を復習し、理解しておく事。（120分）【事前学習】159ページから170ページを読んで理解出来ない箇所を質問できるようにまとめておく事。（120分）
第10回	アルゴリズム【事後学習】前回の講義中で解いた課題を復習し、理解しておく事。（120分）【事前学習】170ページから186ページを読んで理解出来ない箇所を質問できるようにまとめておく事。（120分）
第11回	判定可能性１【事後学習】前回の講義中で解いた課題を復習し、理解しておく事。（120分）【事前学習】193ページから203ページを読んで理解出来ない箇所を質問できるようにまとめておく事。（120分）
第12回	判定可能性２【事後学習】前回の講義中で解いた課題を復習し、理解しておく事。（120分）【事前学習】203ページから215ページを読んで理解出来ない箇所を質問できるようにまとめておく事。（120分）
第13回	帰着可能性１【事後学習】前回の講義中で解いた課題を復習し、理解しておく事。（120分）【事前学習】221ページから236ページを読んで理解出来ない箇所を質問できるようにまとめておく事。（120分）
第14回	帰着可能性２【事後学習】前回の講義中で解いた課題を復習し、理解しておく事。（120分）【事前学習】236ページから250ページを読んで理解出来ない箇所を質問できるようにまとめておく事。（120分）
第15回	これまでのまとめ

その他

教科書	Michael Sipser 『計算理論の基礎』共立出版 2008年第２版毎回使用するので、必ず準備すること。
参考資料コメント及び資料（技術論文等）
成績評価の方法及び基準	レポート（１００％）
質問への対応	随時。　メールアドレスは講義にて知らせます。
研究室又は連絡先	講義にて周知します。
オフィスアワー	金曜駿河台 13:00 ～ 16:00 タワースコラ１４階S1402
学生へのメッセージ

Copyright 2020 Nihon University College of Science and Technology. All rights reserved.