書名で キーワードで

詳細検索 >>

書籍詳細

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

  計算論

▼ 目次を読む

▼ 目次をたたむ

小林孝次郎 創価大教授 理博 著

発行年月日:2008/01/07 , 判 型: A5,  ページ数:214頁

ISBN:978-4-339-02716-7,  定 価:2,808円 (本体2,600円+税)

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

【目次】

1 アルゴリズムの限界と効率
1.1 アルゴリズムの概念
1.2 アルゴリズムの限界
1.3 アルゴリズムの効率
演習問題
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 完全集合
演習問題
引用・参考文献
演習問題解答
索引

【おすすめ本】

在庫は時期によりまして変動することがございますので、ご了承ください。