| 授業方針・テーマ |
計算の考え方について理解することを目的とする．コンピュータを抽象化することでコンピュータを理論的に扱う方法を説明する． |
習得できる知識・能力や授業の
目的・到達目標 |
コンピュータがある問題を解くことができるかどうかを判定する方法とそれにまつわる様々な問題を把握する． |
授業計画・内容
授業方法 |
第１回 講義の概要説明
第２回 チューリング機械
第３回 チューリング機械の変型
第４回 アルゴリズムの定義
第５回 判定可能な言語
第６回 停止問題
第７回 言語理論における判定不可能問題，単純な判定不可能問題
第８回 写像帰着可能性
第９回 再帰定理
第１０回 数理論理における判定可能性
第１１回 チューリング帰着可能性
第１２回 情報の定義
第１３回 計算理論に関するその他の話題
第１４回 計算理論に関するその他の話題（続き）
第１５回 まとめ
|
| 授業外学習 |
教科書を事前に予習しておく． |
| テキスト・参考書等 |
教科書
・Michael Sipster，計算理論の基礎 [原著第2版] 2.計算可能性の理論. 共立出版（2008）
参考書
・J．ホップクロフト他，「オートマトン 言語理論 計算論 II 第2版」，サイエンス社，2003年
・J. Kleinberg，E. Tardos，「アルゴリズム デザイン」，共立出版，2008年 |
| 成績評価方法 |
試験または課題（中間・期末，各35％），小レポート（30％）で評価を行う． |
質問受付方法
(オフィスアワー等) |
事前にメール等でのアポイントメントをお願いします．メールアドレスは授業中にお知らせします． |
特記事項
(他の授業科目との関連性) |
関連科目：
形式言語とオートマトン，言語処理系，離散数学
情報論理学，情報理論
アルゴリズム解析 |
| 備考 |
|
シラバス照会