オートマトンと計算理論
担当者盛 拓生教員紹介
学年・開講期2年次 後期  [理工学部 情報電子工学科]
科目の種類専門
区分・単位選択 2単位
科目ナンバー3C223

授業の概要(ねらい)

 近年コンピュータの性能が向上し、チェス、将棋あるいは囲碁などゲームにおいて人間の世界チャンピオンにコンピュータが勝利するようになってきています。また、人間には処理しきれないような大量なデータから社会に役立つデータを見つけるための技術や人工知能などが一般化しつつあります。
 本講義では計算機で計算できるとはどういうことか、それには限界があるのかといったことを理論的な面から学びます。計算機による計算を理論的に扱うためにまず計算機そのものを単純な形でモデル化します。このモデルを計算モデルあるいはオートマトンと呼びます。計算機は入力データ、プログラム与えられて初めて計算することが可能となりますが、この入力データ、プログラムもやはり単純な形でモデル化します。これを言語と呼びます。言語は一般にある規則に従う記号列ですが、この規則を文法と呼びます。オートマトンと文法は互いに対をなし、さらに階層構造を持つことが知られています。
 各階層に属するそれぞれのオートマトンまたは文法について、ある言語を生成できるか否か、受理できるか否かを示すことで各オートマトン及び文法の等価性あるいは非等価性を示します。さらに最上位の階層に位置するオートマトンであるTuringマシンについて、その万能性と限界を示すことで本質的に計算機では解けない問題があることを示します。
 また、Turingマシンと計算量という概念を用いて計算機科学の対象となる問題が現実的な時間で解ける問題とそうではない問題に分けられることを示し、後者の構造や相互関係について学びます。
 この科目では、学位授与の方針(ディプロマポリシー)DP4Cに関連する能力を修得します。

授業の到達目標

 この科目では次のような能力を修得することを目標とします。
学生は、簡単なオートマトンついて、入力と状態遷移関数が与えられた場合にその動作をトレースできる。
学生は、決定性有限オートマトン、(一般化された)非決定性有限オートマトン、正規表現、正規文法の等価性を理解し、それぞれを相互に変換 するアルゴリズムを利用できる。
学生は、代数系としての正規言語の性質を説明できる。
学生は、Chomsky標準形の意味を理解し、任意の文脈自由文法をChomsky標準形に変換できる。
学生は、Chomskyの階層について説明できる。
学生は、決定性プッシュダウンオートマトンと非決定性プッシュダウンオートマトンの非等価性を説明できる。
学生は、プッシュダウンオートマトンと文脈自由文法の等価性を説明し、相互に変換するアルゴリズムを利用できる。
学生は、決定性Turingマシン、非決定性Turingマシン、その他のTuringマシンのバリエーション及び論理回路との等価性を説明でき、Turingマシンの万能性とその限界を説明できる。
学生は、計算量の概念を理解し、問題、アルゴリズムの計算量をオーダ記法で表すことができる。
学生は、計算量のクラスとしてのP、NP、NP完全、NP困難について、その複雑性(計算量)の関係を説明し、NPの定義を説明できる。

成績評価の方法および基準

中間レポート(50%)、期末試験の成績(50%)。
講義内容、レポート、試験への質問、フィードバック等は原則的にLMSまたはオフィスアワーで対応します。

教科書・参考文献

種別書名著者・編者発行所
教科書計算理論とオートマトン言語理論丸岡 章著サイエンス社、ISBN-13: 978-4781911045
参考文献チューリングの計算理論入門高岡詠子著講談社、ISBN-13: 978-4062578516

準備学修の内容

 予め、各回の講義資料をLMS上で公開します.
 講義資料はPC、タブレット、スマートフォン等にダウンロードするか紙に印刷するなどして、講義中いつでも参照、書き込みできるようにしてください。
 授業前にこれらの資料に1時間程度目を通した上で、理解できた点、理解できていない点をそれぞれ把握して授業に臨んでください。
 授業後には、30分程度かけてLMS上のテストで理解度を確認し、復習してください。

その他履修上の注意事項

 中間レポートが提出されない場合は単位の取得が著しく困難になります。中間レポートは締切を守って必ず提出するようにしてください。
 自主学習支援のためにLMSを利用します。講義資料等はLMS上で公開されているので事前に入手し、講義中はノートをとることよりも、講義を聞いて理解すること、演習問題を解くことに集中してください。
 事前に履修すべき科目は、論理数学、論理回路、データ構造とアルゴリズム、プログラミング言語論です。
 同時に履修すべき科目は、グラフ理論です。
 事後に履修すべき科目は、計算機アーキテクチャ、情報セキュリティです。
 この科目はJABEEプログラムの必修科目で、学習・教育到達目標中項目4-1に対応しています。 

授業内容

授業内容
第1回すべては計算から始まる
第2回計算の理論のための概念や用語
第3回有限オートマトン
決定性有限オートマトン
第4回非決定性有限オートマトン
決定性有限オートマトンと非決定性有限オートマトンの等価性
第5回正規表現
第6回正規言語/文脈自由言語
第7回文脈自由文法
第8回プッシュダウンオートマトン1 -プッシュダウンオートマトンの定義-
第9回プッシュダウンオートマトン2 -プッシュダウンオートマトンと文脈自由文法の等価性-
第10回Turingマシン1 -Turingマシンの定義とその拡張-
第11回Turingマシン2 -非決定性Turingマシン-
第12回Turingマシンの万能性とその限界
第13回Turingマシンに基づいた計算量限定の計算、計算量クラス
第14回論理回路に基づいた計算量限定の計算、計算量クラスの分類
第15回テスト、まとめ