1. |
授業の概要(ねらい)・ディプロマポリシーとの関連 |
|
近年コンピュータの性能が向上し、チェス、将棋あるいは囲碁などゲームにおいて人間の世界チャンピオンにコンピュータが勝利するようになってきています。また、人間には処理しきれないような大量なデータから社会に役立つデータを見つけるための技術や人工知能などが一般化しつつあります。 本講義では計算機で計算できるとはどういうことか、それには限界があるのかといったことを理論的な面から学びます。計算機による計算を理論的に扱う ためにまず計算機そのものを単純な形でモデル化します。このモデルを計算モデルあるいはオートマトンと呼びます。計算機は入力データ、プログラム与えら れて初めて計算することが可能となりますが、この入力データ、プログラムもやはり単純な形でモデル化します。これを言語と呼びます。言語は一般にある 規則に従う記号列ですが、この規則を文法と呼びます。オートマトンと文法は互いに対をなし、さらに階層構造を持つことが知られています。 各階層に属するそれぞれのオートマトンまたは文法について、ある言語を生成できるか否か、受理できるか否かを示すことで各オートマトン及び文法の等 価性あるいは非等価性を示します。さらに最上位の階層に位置するオートマトンであるTuringマシンについて、その万能性と限界を示すことで本質的に計算 機では解けない問題があることを示します。 また、Turingマシンと計算量という概念を用いて計算機科学の対象となる問題が現実的な時間で解ける問題とそうではない問題に分けられることを示し、 後者の構造や相互関係について学びます。 この科目では、学位授与の方針(ディプロマポリシー)DP4Cに関連する能力を修得します。
|
2. |
授業の到達目標 |
|
この科目では次のような能力を修得することを目標とします。 学生は、簡単なオートマトンついて、入力と状態遷移関数が与えられた場合にその動作をトレースできる。 学生は、決定性有限オートマトン、(一般化された)非決定性有限オートマトン、正規表現、正規文法の等価性を理解し、それぞれを相互に変換 するアルゴリズムを利用できる。 学生は、代数系としての正規言語の性質を説明できる。 学生は、Chomsky標準形の意味を理解し、任意の文脈自由文法をChomsky標準形に変換できる。 学生は、Chomskyの階層について説明できる。 学生は、決定性プッシュダウンオートマトンと非決定性プッシュダウンオートマトンの非等価性を説明できる。 学生は、プッシュダウンオートマトンと文脈自由文法の等価性を説明し、相互に変換するアルゴリズムを利用できる。 学生は、決定性Turingマシン、非決定性Turingマシン、その他のTuringマシンのバリエーション及び論理回路との等価性を説明でき、Turingマシンの万能性とその限界を説明できる。 学生は、計算量の概念を理解し、問題、アルゴリズムの計算量をオーダ記法で表すことができる。 学生は、計算量のクラスとしてのP、NP、NP完全、NP困難について、その複雑性(計算量)の関係を説明し、NPの定義を説明できる。
|
3. |
成績評価の方法および基準・フィードバック方法 |
|
中間レポート(50%)、期末試験の成績(50%)。 講義内容、レポート、試験への質問、フィードバック等は原則的にLMSまたはオフィスアワーで対応します。
|
4. |
教科書・参考書 |
|
テキスト:丸岡 章著、"計算理論とオートマトン言語理論、" サイエンス社、ISBN-13: 978-4781911045 使用教材:LMS
|
5. |
準備学修の内容・必要な時間 |
|
各講義前に、昨年度または今年度の講義ノート、講義スライド、及び関連する資料等をLMS上に掲載します。これらの資料を利用して1.5時間程度の予習をしてください。 資料は講義で利用するスライドと同じ内容を含んでいます。これらの資料は事前に印刷するかスマートフォン、タブレット等にダウンロードして授業中に 参照できる状態にしてください。講義中はスライドの内容をノートに写すことに専念するのではなく、先に述べた資料を参照しながら話を聞いて理解したり、講義中の演習問題を解くことに専念してください。 また、原則として各講義に対する演習問題をLMSのテストとして公開します。このテストは評価の対象ではありませんが、復習に利用してください。復習に は1.5時間程度が必要です。
|
6. |
その他履修上の注意事項 |
|
中間レポートが提出されない場合は単位の取得が著しく困難になります。中間レポートは締切を守って必ず提出するようにしてください。 自主学習支援に関しては,LMS上の講義資料、テストを積極的に活用してください。 事前に履修すべき科目は、論理数学、論理回路、データ構造とアルゴリズム、プログラミング言語論です。 同時に履修すべき科目は、グラフ理論です。 事後に履修すべき科目は、計算機アーキテクチャ、情報セキュリティです。 この科目はJabeeプログラムの必修科目で、学習・教育到達目標中項目4-1に対応しています。
|
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回】 | テスト、まとめ |
|