計算数学I

(1) 初等的な計算モデルとしてオートマトンやそれに付随する概念について述べる。決定性・非決定性の違い，正規言語との同等性を述べる。 (2) プッシュダウン・オートマトンについて述べる。記憶装置としてスタックを付加した計算モデルである。文脈自由言語との同等性を述べる。 (3) チューリング機械について説明する。制限のない記憶装置を付加した計算モデルである。計算可能性の概念はチューリング機械を用いて定式化される。停止性問題等の計算不可能な問題について説明する。 (4) 時間があれば，計算複雑性理論の初歩を解説する。時間複雑性クラスPおよびNP，空間複雑性クラスPSPACE等を考える。

講義による。

試験による。

多くの書籍が出版されており一つには固定しないが，Michael Sipser, "Introduction to the Theory of Computation"は読みやすいと思う。和訳あり。

同上

予備知識は仮定しない。初歩から解説する。

履修学生　各位 2025年Sセメスターの「授業評価アンケート」をWebアンケートにて実施いたします。 （数理科学研究科の合併科目の場合は担当教員を確認し、アンケートをお願いします） 授業の方法や内容、設備などの改善に役立てることを目的として、受講学生全員に、無記名で、授業に対する評価や要望を確認し、改善に繋げます。 複数の教員が担当した科目については、平均的な評価で構いません。 お手数ですが、ご協力のほどよろしくお願いいたします。 【回答締切】 2025年7月31日（木） ＜アンケート回答までの流れ＞ １．シラバスに記載のある、詳細情報／Detailed Information　その他／Others　にURLが記載されています。 　（履修科目１科目につき1回）履修科目の授業評価アンケート回答をお願いします。 【学生回答用URL】 　https://forms.office.com/*****　　 ２．履修科目数に応じて１．のURLにアクセスを繰り返しながら入力をお願いします。 ※「1.科目・担当教員」一覧に記載のない科目はアンケート対象外科目です。