平成17年度後期　計算論入門

授業要目

授業方針：
コンピュータによる計算のための基礎理論・「計算」の数理に関する基本事項について、数学・情報を学ぶ学生を念頭にして講義する。

習得できる知識・能力や授業の目的・ねらい：　
情報学を学ぶ上で必須の基礎知識を身につけることで、コンピュータによる計算について理解し、情報についてさらに学ぶ準備ができる。

授業計画・内容：
有限オートマトンと文脈自由言語
計算可能性（Turing機械・帰納的関数）
アルゴリズムと計算量
について講義する予定である。時間が許せば、P≠NP問題・量子計算についても触れる。

テキスト・参考書等：
（テキスト）キンバー・スミス「計算論への入門」（杉原訳）ピアソンエデュケーション
（参考書）講義時間中に指示する。

成績評価方法：試験(60%)・出席とレポート(40%)によって評価する。

授業科目の関連性など： 

特記事項：
この科目は数学の教職免許の専門科目として必修である。
数学科の必修・選択必修科目ではない。
数学科4年次学生向けの特別研究の受講許可条件である学部科目50単位には含まれない。

10/ 3 はじめに、決定性有限オートマトン、レポート：練習問題2.2
10/17 非決定性有限オートマトン、正則言語、レポート：練習問題2.11
10/24 正則言語の続き、レポート：練習問題2.25
10/31 文脈自由言語、レポート：練習問題3.1
11/14 プッシュダウンオートマトン
11/21 休講（レポート）
11/28 （続き）、チューリング機械
12/ 5 （続き）
12/12 チューリング機械の拡張
12/19 計算可能性
12/26 アルゴリズム
 1/16 帰納的関数
 1/23 計算量, P≠NP問題
 1/30 試験

研究室へ戻る