近代科学社

書籍検索
ジャンル選択

情報

コンピュータサイエンス大学講座 第17巻

計算量の理論

著者 笠井 琢美


本書では,入門書としての性格上,将来その評価があまり変わらない基本的なものに的を絞ってある。
第5章までが導入部であり,計算量を理解する上で最も大切なチエーリング機械を詳説し,計算可能性,機械モデル,形式言語とオートマトン理論に言及する。
第6,7章が本論であり,計算量理論の基本定理とその応用についてさらに詳しく述べる。

紙の書籍¥3,100定価(税別)

基本情報

発売日 1987年4月1日
ページ数 244 ページ ※印刷物
サイズ A5
ISBN 9784764901308
ジャンル 情報
タグ アルゴリズム
電子書籍形式 販売なし

主要目次

1.機械と言語
1.1 語と言語
1.2 対応,関係,グラフ
1.3 問題と符号化
練習問題1
2.Turing機械
2.1 多テープTuring機械
2.2 Turing機械のプログラムによる表現
2.3 単テープTuring機械
練習問題2
3.計算可能性
3.1 可算,帰納的可算,計算可能性
3.2 万能Turing機械
3.3 計算不能な問題
練習問題3
4.計算機モデル論
4.1 非決定性機械
4.2 交互機械
4.3 多プッシュダウン機械
4.4 ランダム・アクセス機械
4.5 計数器機械と帰納的関数
練習問題4
5.形式言語
5.1 生成文法
5.2 正則集合
5.3 文脈自由言語
5.4 0型言語と1型言語
5.5 文脈自由文法に関する計算不能問題
練習問題5
6.基本定理
6.1 線形加速定理
6.2 構成可能関数
6.3 時間量と領域量の関係
6.4 2テープTuring機械
6.5 階層定理
6.6 対数領域と多項式時間
7.完全問題
7.1 実際的計算可能性
7.2 完全問題
7.3 NP完全問題
7.4 PSPASE完全問題
7.5 EXPTIME完全問題
7.6 P完全問題とNL完全問題
7.7 詰め込み論法と未解決問題
練習問題7
練習問題解答
索  引

目次をさらに表示する