計算論
計算可能性と計算の複雑さの理論の入門書。コンピュータはどのような問題を解くことができるのか，ということをきちんと論ずるための数学的な枠組みを与える。基本的な結果に限定し，それらが成り立つ理由をわかりやすく説明する。
- ジャンル
- 発行年月日
- 2008/01/07
- 判型
- A5
- ページ数
- 214ページ
- ISBN
- 978-4-339-02716-7
- 内容紹介
- 目次
計算可能性と計算の複雑さの理論の入門書。コンピュータはどのような問題を解くことができるのか，ということをきちんと論ずるための数学的な枠組みを与える。基本的な結果に限定し，それらが成り立つ理由をわかりやすく説明する。
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 完全集合
演習問題
引用・参考文献
演習問題解答
索引
おすすめ本
-
-
英語で学ぶ 計算理論 - CD-ROM付 -
簡潔かつ包括的な計算理論の入門書である。形式言語とオートマトン理論を学び，部分的帰納関数とチューリング機械を通して，アルゴリズムの直感的観念の定式化を行う。また日英各々のスライドがCD-ROMに収められ，専門用語を学べる。
-
-
オートマトン・言語と計算理論
計算機では，解ける問題，解けない問題，解けることは解けるが時間がかかって手に負えない問題の3種類が存在する。このことを把握するため，計算機のモデルを正確に理解し上手に使えるように指導するのが本書の目的である。
-
-
形式言語と有限オートマトン入門 - 例題を中心とした情報の離散数学 -
記号処理はコンピュータの基本的な機能である。本書は，記号処理の基本である形式言語とオートマトンの基礎的な概念について，例題を多数挙げ解説する形式で系統的に記述した。
