コンピュータサイエンスの旅
チューリングオムニバス(第2巻) 計算理論 THE TURING OMNIBUS
A. K. デュードニー:著, 足立 暁生:訳
A5判 168ページ 並製
価格:2,090円 (消費税:190円)
ISBN978-4-501-51960-5(4-501-51960-6) C3041
奥付の初版発行年月:1993年02月 / 発売日:1993年02月中旬
価格:2,090円 (消費税:190円)
ISBN978-4-501-51960-5(4-501-51960-6) C3041
奥付の初版発行年月:1993年02月 / 発売日:1993年02月中旬
内容紹介
チューリングオムニバスは,コンピュータサイエンスの世界への気軽な入門書です。その書名が語呂あわせになっているように,チューリング(コンピュータの祖)の街を訪ね歩く観光バス(ツーリングオムニバス)の形をとった選集(オムニバス)です。景勝地の中には,理論の記念碑や応用の街路があり,たくみな比喩により全部で61ポイント解説されています。
目次
1 ゲーデルの定理
2 乱数
3 時間計算量と記憶域計算量
4 ランダムアクセス機械
5 非決定性
6 チューリング機械
7 充足可能性
8 計算可能でない関数
9 NP完全性
10 クックの定理
11 万能チューリング機械
12 NP完全問題
13 停止問題
14 語の問題
15 チャーチの提唱