2004, Theory of Computation I (Japanese Version)

平成16年度計算の理論I

担当教官：大月美佳

対象学生：知能情報システム学科3年

前期必修2単位

お知らせは、特にありません。

コンピュータに何か仕事をさせるということは、コンピュータに「計算」をさせるということである。ここでいう「計算」とはなんであろうか。

コンピュータに「計算」を行わせるためにはそのために「言語」を用いる。ここでいう「言語」とはなんであろうか。

オートマトンは「言語」を受理する抽象的な機械のことであり、コンピュータの「計算」のモデルの一つである。そう言われてわかるだろうか。

本講義では、現在のコンピュータの数学的・論理的背景である形式言語・オートマトン・計算量といった基本的概念の理解を目的とする。これらは、プログラミング言語論や暗号論などの基礎にあたるので、よく理解しておく必要がある。

【JABEE評価基準】

C:計算の理論，情報理論 (3) チューリングマシン/オートマトン、言語クラス、文法の相互関係を理解している。

C:計算の理論，情報理論 (4) 与えられた言語または正規文法に基づいて最小の有限オートマトンを設計できる。

C:計算の理論，情報理論 (5) 字句解析および構文解析の基礎を理解している。

教科書：

J. ホップクロフト、J. ウルマン「オートマトン言語理論計算論I [第2版]」(サイエンス社) \2816 ( amazon.co.jp) ISBN4-7819-1026-2

参考書：

有川節夫・宮野悟「オートマトンと計算可能性」情報処理シリーズ9 (倍風館) (amazon.co.jp)
E. キンバー、C. スミス「計算論への入門」（ピアソン・エデュケーション）(amazon.co.jp) ISBN4-89471-437-X
M. Sipser 「計算理論の基礎」(共立出版) \7500 (amazon.co.jp)
J. ホップクロフト、J. ウルマン「言語理論とオートマトン」(サイエンス社) (amazon.co.jp) ISBN4-7819-0250-2
A. サローマ「計算論とオートマトン理論」 Information & Computing (28) (サイエンス社) ( amazon.co.jp) ISBN4-7819-0521-8
J. ホップクロフト、J. ウルマン「オートマトン言語理論計算論II」(サイエンス社) \2816 ( amazon.co.jp) ISBN4-7819-0432-7
富田他「オートマトン・言語理論」(森北出版) ISBN4-627-80550-0
Derick Wood: Theory of Computation, Harper & Row Pub., 1987
渡辺治「計算可能性・計算の複雑さ入門」(近代科学社) ISBN4-7649-0200-1
高橋正子「計算論計算可能性とラムダ計算」(近代科学社) ISBN4-7649-0184-6
笠井琢美「計算量の理論」(近代科学社) ISBN4-7649-0130-7
小林孝次郎「計算の複雑さ」(昭晃堂) ISBN4-7856-3533-9
斎藤伸自他「離散数学」電気・電子・情報工学基礎講座33(朝倉書店)
D. Mandrioli and C.Chezzi, Theoretical Foundations of Computer Science, (John Wiley & Sons)
M. アービブ、A. クフォーリ、R. モル「計算機科学入門」(サイエンス社)