計算の理論II

担当教官： 大月 美佳

講義時間： 月曜5時限 （16:10〜17:40）

講義室：DC棟110講義室

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

後期選択2単位

はじめに

2004年の前期Iではオートマトンについて学習を行った。これを踏まえて、後期IIでは帰納的関数、Turing機械、計算量の考え方について学習を行う。

[上へ戻る]

本講義の評価方法

出席　(配点なし)

出席チェック兼用のミニテストを毎回実施する。 9回以上出席すること、9回に満たない場合には放棄とみなすので注意。 遅刻は20分まで。それを超えた場合には欠席として扱う。

レポート　（×2 各20点配点）

できない場合にも理由を記述の上期日までに必ず提出すること。 提出しない場合には放棄とみなすので注意。

定期試験　（60点配点） やむをえない事情で欠席した場合には必ず連絡すること。 連絡なく受けなかった場合には放棄とみなすので注意。

[上へ戻る]

2004年度 教科書・参考書

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

プリントを配布する。

参考書：

1. 有川 節夫・宮野 悟 「オートマトンと計算可能性」情報処理シリーズ9 (倍風館) ( amazon.co.jp)
2. J. ホップクロフト、J. ウルマン 「オートマトン言語理論計算論I [第2版]」(サイエンス社) \2600
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 [第2版]」(サイエンス社) \2600
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. モル 「計算機科学入門」(サイエンス社)

[上へ戻る]

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

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

[上へ戻る]

連絡先

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

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

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

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

[上へ戻る]