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

＜学位授与の方針＞

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

＜授業のねらい＞

アラン・チューリングは、まだ汎用電子計算機が発明される以前の1936年に、チューリング・マシンと後に呼ばれるようになる計算モデルを用い、その計算能力の限界（の一つ）を証明しました。それは計算理論の始まりでしたが、現代から考えてもとても深い内容を持っていました。本科目では、オートマトン・形式言語といった様々な計算モデルにふれることにより、計算とは何か・計算機でできることは何かを学び、チューリングの理論・思想の一端に触れます。同時に、現代社会において強く求められている数学的・論理的思考力を身につけることを目指します。

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

* 数学（集合論・論理等）に関する基礎知識
* 情報数学Iおよび離散数学の単位取得が望ましい

＜具体的な到達目標＞

* オートマトン等の計算モデルを理解すること
* 計算モデルの能力やその等価性を理解すること
* 具体的な例題について、オートマトンや文法を設計できること
* 背理法などの手法を用いて、数学的な命題を論理的に証明できること

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

## 準備学習
* 講義スライドを授業前に配布するので、それを参考書も参考にしつつ読んでおくこと
* 授業中に行われる演習について復習を行い、演習レポートとして提出すること

## 授業計画
1 . 導入・有限オートマトンの概要
本授業の目的、歴史的な経緯や位置付けを示し、最も単純な計算モデルである有限オートマトンについて、簡単な例題を用いて解説する。

2. 有限オートマトンの設計と定義
ある条件を満たす系列の集まりに対し、それを表す 有限オートマトンの状態遷移図を設計する方法について解説する。厳密な議論を可能とするため、有限オートマトンを数学的に定義する。準備となる集合論についても解説する。

3. 非決定性有限オートマトン
決定性と非決定性の違いについて解説し、非決定性有限オートマトンの特徴や定義について解説する。

4. 決定性有限オートマトンと非決定性有限オートマトンの等価性
非決定性有限オートマトンに対し、それと等価な決定性有限オートマトンを求める方法について解説し、それらの等価性の証明を行う。

5. 正規表現
プログラミング言語で使われる正規表現について振り返りを行う。その基礎となっている理論的な正規表現を定義し、正規表現が表す状態遷移図について解説する。

6. 正規表現と有限オートマトンの等価性
有限オートマトンが表す状態遷移図から、それに等価な正規表現を導くことを示し、正規表現と有限オートマトンはその見た目は異なるが表現能力が等価であることを証明する。

7. 正規言語とその閉包性・非正規言語
言語に対する演算とそれが閉じることの性質について解説する。正規ではない言語を示し、正規言語が満たす性質として反復補題について解説する。

8. 文脈自由文法
文法とは何かを説明し、その代表例である文脈自由文法について書き換え規則等の定義、文法の曖昧さについて解説する。

9. 正規文法、文脈依存文法
正規言語と同等の能力を持つ文法としての正規文法と、文脈自由文法に対する文法としての文脈依存文法について解説し、文法や言語の表現能力を表すチョムスキーの階層についてふれる。

10. 文脈自由文法の設計・言語生成能力の限界
言語が与えられるときに、その文法を設計する方法について解説する。 文脈自由言語でない言語の例と、ある言語が文脈自由言語でないことを証明する手法について解説する。

11. プッシュダウンオートマトン
スタックを使うことにより表現能力を高めた、プッシュダウンオートマトンの定義を示し、プッシュダウンオートマトンが受理する言語について解説する。

12. プッシュダウンオートマトンと文脈自由文法の等価性
プッシュダウンオートマトンと文脈自由言語の等価性について解説する。

13. 計算可能性
チューリング・マシンの停止問題について解説する。

14. 学習内容の振り返り
科目全体のまとめや、定期試験の総括を行う。計算の複雑さの理論として、P≠NP予想について解説する。

＜成績評価方法＞

定期試験と、演習レポートの結果で行う。

・定期試験(A)：100点満点で定期試験期間に行う。
・演習レポート(B)：授業内で実施する演習について、解答をレポートとして提出する。3段階で評価。

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

＜教科書＞

指定教科書なし

＜参考書＞

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

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

＜オフィスアワー＞

主に金曜日の午後に対応しますが、相談がある場合、事前にメールで予定調整してください。
連絡先：gengo.suzuki＠gmail.com, ju41431@ns.kogakuin.ac.jp
（原則、2つのアドレスを同報でお願いします）

＜学生へのメッセージ＞

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