計算論

コンピュータサイエンス教科書シリーズ 16

計算論

計算可能性と計算の複雑さの理論の入門書。コンピュータはどのような問題を解くことができるのか,ということをきちんと論ずるための数学的な枠組みを与える。基本的な結果に限定し,それらが成り立つ理由をわかりやすく説明する。

ジャンル
発行年月日
2008/01/07
判型
A5
ページ数
214ページ
ISBN
978-4-339-02716-7
計算論
在庫あり

定価

2,860(本体2,600円+税)

カートに入れる

購入案内

  • 内容紹介
  • 目次
  • 著者紹介

計算可能性と計算の複雑さの理論の入門書。コンピュータはどのような問題を解くことができるのか,ということをきちんと論ずるための数学的な枠組みを与える。基本的な結果に限定し,それらが成り立つ理由をわかりやすく説明する。

1 アルゴリズムの限界と効率
1.1 アルゴリズムの概念
1.2 アルゴリズムの限界
1.3 アルゴリズムの効率
演習問題

2 ループプログラムと計算可能関数
2.1 ループプログラム
2.2 計算可能関数,決定可能述語,決定可能集合
2.3 数列の表現
演習問題

3 万能プログラムと計算不能関数
3.1 レジスタ機械プログラム
3.2 プログラムのゲーデル数
3.3 対角線論法と計算不能部分関数
3.4 RM プログラムの動作を記述する関数,述語と万能プログラム
3.5 停止性判定問題
演習問題

4 いろいろな決定不能問題
4.1 s-m-n 定理
4.2 プログラムに関する決定不能述語
4.3 還元可能性
4.4 枚挙可能集合
4.5 数学の定理と枚挙可能集合
演習問題

5 チューリング機械の基本概念
5.1 計算時間の分析に適したアルゴリズムのモデル
5.2 チューリング機械
5.3 ループプログラムとチューリング機械
5.4 ポストの対応問題
5.5 非決定性チューリング機械の概念
演習問題

6 時間限定チューリング機械
6.1 チューリング機械の計算時間
6.2 P, EXP, PSPACE
6.3 非決定性チューリング機械の計算時間とNP
6.4 NPの基本性質
演習問題

7 NP 完全集合
7.1 NP 完全集合の基本概念
7.2 充足可能性問題
7.3 いろいろなNP 完全集合
演習問題
引用・参考文献
演習問題解答
索引

小林 孝次郎(コバヤシ コウジロウ)