△計算数理（k）[5E17]

＜学位授与の方針＞

○	1. 基礎知識の習得
◎	2. 専門分野知識の習得
○	3. 汎用的問題解決技能
○	4. 道徳的態度と社会性

＜授業のねらい＞

計算＝計算機でできること、とは何か？という問題は、「人口知能」の可能性が再燃している現代において、改めてその重要性が見直されています。本授業では、オートマトンや形式言語を通じて、計算とその複雑さを深く理解することを目指します。

＜受講にあたっての前提条件＞

集合論・グラフ理論に関する基礎知識を必要とします。
情報数学Ｉおよび離散数学の単位を取得しておくこと。

＜具体的な到達目標＞

有限オートマトン・プッシュダウンオートマトンの概念・対応する言語・文法との等価性を理解すること。
具体的な例題について、オートマトンや文法を設計することができること。

＜授業計画及び準備学習＞

　１　計算とは何か
　　　本授業の目的、歴史的な経緯や位置付けを示し、集合論・論理・グラフ理論などの以降で必要となる準備的な内容を解説する。
　　　準備学習：参考書1. 1〜4講を読んでおく。
　２　有限オートマトンと言語
　　　有限オートマトンの定義を示し、有限オートマトンが受理する言語について解説する。
　　　事前学習：参考書1. 5〜7講を読んでおく。
　３　非決定性有限オートマトン
　　　非決定性有限オートマトンの定義と、決定性オートマトンとの等価性について解説する。
　　　事前学習：参考書1. 8〜9講を読んでおく。
　４　正規表現
　　　正規表現の定義を示し、正規表現が表す言語について解説する。
　　　事前学習：参考書1. 10講を読んでおく。
　５　プログラミング言語の正規表現
　　　プログラミング言語で使われる正規表現について解説する。
　　　事前学習：Python、JavaScript等の自分の馴染みのあるプログラミング言語における正規表現について調べておく。
　６　正規表現の持つ性質
　　　有限オートマトンと正規言語との等価性、受理能力の限界について解説する。
　　　事前学習：参考書1. 11〜12講を読んでおく。
　７　正規言語の持つ性質
　　　言語に対する演算と、正規言語が持つ性質について解説する。
　　　事前学習：参考書1. 13講を読んでおく。
　８　文脈自由文法と言語生成能力
　　　文脈自由文法の定義と、文法の生成能力の階層について解説する。
　　　事前学習：参考書1. 14〜15講を読んでおく。
　９　文脈自由文法の設計
　　　文脈自由言語が与えられたとき、それを生成する文脈自由文法を設計する手法について解説する。
　　　事前学習：参考書1. 16〜17講を読んでおく。
１０　文脈自由文法の言語生成能力の限界
　　　文脈自由言語でない言語の例と、ある言語が文脈自由言語でないことを証明する手法について解説する。
　　　事前学習：参考書1. 18講を読んでおく。
１１　プッシュダウンオートマトン
　　　プッシュダウンオートマトンの定義を示し、プッシュダウンオートマトンが受理する言語について解説する。
　　　事前学習：参考書1. 19講を読んでおく。
１２　プッシュダウンオートマトンの性質
　　　プッシュダウンオートマトンと文脈自由言語の等価性について解説する。
　　　事前学習：参考書1. 20-21講を読んでおく。
１３　計算の複雑さ
　　　計算量およびクラスNPについて解説する。
　　　事前学習：オーダーについて復習しておく。
１４　学習成果の振り返り
　　　事前学習：前回までの総復習を行っておく。

＜成績評価方法＞

定期試験と、講義中に行う演習の結果で行う。

・定期試験(A)：100点満点で定期試験期間に行う。
・演習(B)：1-13回目の講義毎に実施。答案用紙を回収し、A、B、C、Dで評価）。

AとBを点数換算したものを、7:3の割合で評価した結果により、A+,A,B,C,D,Fで評価し、D以上を合格とする。

＜教科書＞

指定教科書なし

＜参考書＞

1.は、最近出版されたもので、コンパクトにまとまっており、入手しやすい。理解を深めるには、2.を参考にすることが望ましい。この分野では、興味深い読み物も近年出版されており、関連書籍・情報を、https://ggszk.org/computation_theory にまとめておくので、参考にしてほしい。

1. 丸岡 章 著 「やさしい計算理論―有限オートマトンからチューリング機械まで」　サイエンス社
2. Michael Sipser著　「計算理論の基礎　原著第2版　1　オートマトンと言語」　共立出版

＜オフィスアワー＞

メールアドレス：gengo.suzuki＠gmai.comにて随時受け付ける。

＜学生へのメッセージ＞

本授業は、コンピュータ・サイエンスの標準的なカリキュラムとして確立している内容です。コンピュータに付き合う上での、基礎的な頭の体操という側面も持っており、パズルを解くようなおもしろさもありますが、数学や論理を使った深い内容の一端にも触れることもできますので、積極的に取り組んでほしいと思います。