授業科目名 特別講義・計算可能性理論 (Computability Theory) 担当

特別講義・計算可能性理論
(Computability Theory)
授業科目名
鈴木 登志雄
(SUZUKI Toshio)
担当教員名
分担教員名
クラス
所属等
非常勤講師
研究室
依岡 輝幸
理学専門科
目
対象学年
1年
学期
前期
単位数
2
必修選択区分
曜日・時限
選必
集中
キーワード
計算可能性、計算複雑さ（計算量）
授業の目標
ＮＰ完全性という概念とその背景の理解を目標にする。
学習内容
学部科目「計算機構論」で学んだ計算可能性から派生・発展した概念を学
ぶ。とくに計算可能性より緩やかな概念である半計算可能性（帰納的可算
性）と、計算可能性よりきつい概念である多項式時間計算可能性について
学習する。これらを踏まえ、ＮＰ完全性について学習する。
１． 序：計算可能性と計算複雑さを学ぶ意義
２． 計算機構論の復習とチューリング計算機
授業計画
受講要件
３． 計算困難性の度合いの比較
４． 計算複雑性の基本事項
５． 計算量クラス
６． 計算量クラスＰに属する集合の例
７． 非決定性多項式時間計算量クラスＮＰ
特になし。計算機構論をすでに履修した、あるいは今後履修予定であるこ
とが望ましい。
テキスト
プリントを配布する。
参考書
田中尚夫「情報の数理 計算論理入門」裳華房（１９９７）、渡辺治「計
算可能性・計算複雑さ入門」近代科学者（１９９２）。
予習・復習につ
いて
復習はよくしてください。
成績評価の方法･
基準
授業参加度とレポートを加味して行う。
オフィスアワー
担当教員からの
計算量クラスＰに属する集合の話の中でも、とくに２ＳＡＴ（二和積形論
理式の充足可能性判定問題）がＰに属することの証明は面白いところで
メッセージ
す。
教職科目区分