Web Syllabus(講義概要)

2019年度

ひとつ前のページへ戻る 教授名で検索

 
オートマトンと計算理論(Introduction to the theory of automata and computation) 盛 拓生
2年 テキスト授業Ⅱ・Ⅳ 専門科目選択 2単位
【通信・Ⅱ・Ⅳ】 19-1-1666-2349

1.
授業の概要(ねらい)・ディプロマポリシーとの関連

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

2.
授業の到達目標

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

3.
成績評価の方法および基準・フィードバック方法

 レポート課題の合格を前提として、試験(100%)。
 講義内容、レポート、試験への質問,フィードバック等は原則的にLMS、電子メールで対応します。

4.
教科書・参考書

テキスト:丸岡 章著、"計算理論とオートマトン言語理論、" サイエンス社、ISBN-13: 978-4781911045
使用教材:LMS

5.
準備学修の内容・必要な時間

 事前に昨年度または今年度の講義ノート及び関連する資料等をLMS上に掲載します。これらの資料を利用して学習をしてください。また、原則として各講義に対する演習問題をLMSのテストとして公開します。このテストは評価の対象ではありませんが、復習に利用してください。
 予習と復習を合わせて、当該期間中に30時間以上の学習が必要です。

6.
その他履修上の注意事項

 レポート合格が、科目修得試験受験の前提条件となります。
 事前に履修すべき科目は、論理数学、論理回路、グラフ理論です。
 同時に履修すべき科目は、データ構造とアルゴリズムです。
 事後に履修すべき科目は、情報セキュリティです。

7.
授業内容

【第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回】
まとめ