計算の理論II

担当教官： 大月 美佳

講義時間： 月曜4時限 （14:20〜15:50）

講義室：AV講義室

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

後期選択2単位

はじめに

2001年の前期Iではオートマトンについて学習を行った。これを踏まえて、後期IIでは文脈自由文法からTuring機械、計算量の考え方について学習を行う。余裕があれば、帰納的計算可能の理論にも触れたい。

[上へ戻る]

本講義の評価方法

出席(2/3以上出席すること、遅刻は20分まで)

出席チェック兼用のミニテストを毎回実施する。

出席点＋レポート（中×1）＋定期試験

[上へ戻る]

2001年度 教科書・参考書

教科書（後期）：指定しない

プリントを配布する。

参考書：

1. 有川 節夫・宮野 悟 「オートマトンと計算可能性」情報処理シリーズ9 (倍風館) ( amazon.co.jp)
2. J. ホップクロフト、J. ウルマン 「 オートマトン言語理論計算論I」(サイエンス社) \2816 ( amazon.co.jp)
3. M. Sipser 「 計算理論の基礎」(共立出版) \7500 ( amazon.co.jp)
4. J. ホップクロフト、J. ウルマン 「 言語理論とオートマトン」(サイエンス社) (amazon.co.jp)
5. A. サローマ 「 計算論とオートマトン理論」 Information & Computing (28) (サイエンス社) ( amazon.co.jp)
6. J. ホップクロフト、J. ウルマン 「 オートマトン言語理論計算論II」(サイエンス社) \2816 ( amazon.co.jp)
7. 富田他 「 オートマトン・言語理論」(森北出版)
8. Derick Wood: Theory of Computation, Harper & Row Pub., 1987
9. 渡辺 治「 計算可能性・計算の複雑さ入門」(近代科学社)
10. 高橋 正子 「 計算論 計算可能性とラムダ計算」(近代科学社)
11. 笠井 琢美 「 計算量の理論」(近代科学社)
12. 小林 孝次郎 「 計算の複雑さ」(昭晃堂)
13. 斎藤 伸自他「離散数学」電気・電子・情報工学基礎講座33(朝倉書店)
14. D. Mandrioli and C.Chezzi, Theoretical Foundations of Computer Science, (John Wiley & Sons)
15. M. アービブ、A. クフォーリ、R. モル 「計算機科学入門」(サイエンス社)

[上へ戻る]

2001年度 後期スケジュール（予定）

題目にリンクがある場合は講義資料にリンクしてある。IEを使えばオンラインで見ることができる。PDFファイルも可能ならば追加する。

[上へ戻る]

連絡先

部屋：7号館(情報棟) 207号室 (0952-28-8858 内線：8858)

電子メール： mika@is.saga-u.ac.jp

WWW掲示板： 「計算の理論I及びII 質問掲示板」

レポート提出アドレス： mika@is.saga-u.ac.jp

[上へ戻る]