授業の概要（ねらい）

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

授業の到達目標

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

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

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

教科書・参考文献

準備学修の内容

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

その他履修上の注意事項

事前に履修すべき科目は、論理数学、論理回路、グラフ理論です。
同時に履修すべき科目は、データ構造とアルゴリズムです。
事後に履修すべき科目は、情報セキュリティです。

授業内容