授業科目名 （英文名） オートマトンと形式言語 (Automata a nd Formal Languages) 科目区分 対象学生 ※ 単位数 2.00 開講年次・ 学期 3年次・前期 担当教員 礒川 悌次郎 所属 工学部 電気電子情報工学科 ｵﾌｨｽｱﾜｰ・場所 ※ 連絡先 ※ 講義目的及び到達目標 講義目的：オートマトン理論と形式言語理論は計算機科学における必須の基礎理論の 一つである。現代の計算機の基礎的なモデルとなった、有限オートマトンからチュー リングマシンおよびそれと対応する形式言語を理解することによって、計算機に強い 体質を作ることが講義の目的である。 到達目標：計算機で解ける問題と解けない問題、原理的には解けるが現実的には手に 負えない問題があることを理解し、計算原理のモデルを正確に習得して、プログラム の本質を理解し、具体的なプログラム作成に計算アルゴリズム原理を反映させうる能 力を身につけること。 講義内容・授業計画 講義内容：オートマトンとは何か、形式言語とは何か、これらが計算機科学において なぜ重要なのか、それを理解するための基礎事項を詳細な数学証明にはこだわらず体 得しうる内容として講義する。 授業計画： １． オートマトン・形式言語理論とは何か・なぜ必要か ２． 数学的準備（集合・写像） ３． 有限オートマトン（定義・状態遷移図） ４． 非決定性有限オートマトン ５． 最簡形の決定性有限オートマトン ６． プッシュダウンオートマトン ７． チューリング機械Ⅰ ８． チューリング機械Ⅱ ９． オートマトンのまとめと演習 10. 形式文法と形式言語Ⅰ 11. 形式文法と形式言語Ⅱ 12. オートマトンと形式文法の関係 13. 言語の階層構造 14. 形式言語のまとめと演習 15. 全体のまとめと総合演習 テキスト 広瀬貞樹 著 「オートマトン・形式言語理論」 コロナ社 参考文献 M.Sipser著、太田・田中監訳「計算理論の基礎 1 オートマトンと言語」、共立出版(20 08) 成績評価の基準・方法 中間試験および期末試験の合計で評価する 履修上の注意・履修要件 ・本科目は，H30年度以前入学の学生を対象としている． ・論理数学など２年次までの計算機関連科目を可能な限り履修していることが望まし い． ≪新型コロナウィルス感染症に伴う特例措置に基づく遠隔授業≫ ・当授業は、原則全ての授業を対面で実施する予定ですが、履修者人数によっては、 新型コロナウィルス感染症対策として、履修者を複数の教室に分けて教室間をオンラ インで繋ぐ方法や、対面授業と自宅でのオンライン授業を隔週実施する方法とする場 合があり、自宅等でオンライン授業の受講を視聴できる通信環境(PC・タブレット等の 端末やWi-Fi環境)が必要となる場合があります。最終的な授業方法は履修登録後に決定 ・連絡します。 実践的教育 該当しない
備考 ・電気、電子、情報分野の広い知識と特化した分野の知識 ・多種多様な分野に対応できる能力
