- 在庫状況:在庫あり(1〜2日で出荷)
- 複雑さの階層
-
- 価格
- 3,740円(本体3,400円+税)
- 発行年月
- 2006年11月
- 判型
- A5
- ISBN
- 9784320121720
この商品をご覧のお客様は、こんな商品もチェックしています。
- マイナ保険証の罠
-
価格:935円(本体850円+税)
【2023年08月発売】
- ChatGPT API×Pythonで始める対話型AI実装入門
-
価格:2,750円(本体2,500円+税)
【2023年10月発売】
- 知らないと一生バカを見るマイナカードの大問題
-
価格:990円(本体900円+税)
【2023年12月発売】
- データ思考入門
-
価格:990円(本体900円+税)
【2023年02月発売】
- はじめてのUXデザイン図鑑
-
価格:2,640円(本体2,400円+税)
【2023年03月発売】
[BOOKデータベースより]
第1章 準備
[日販商品データベースより]第2章 チューリング機械の基礎
第3章 基本的包含関係と階層構造
第4章 NP完全問題
第5章 NL、PSPACE、EXPTIME、およびNEXPTIMEの完全問題
第6章 NPを基にした階層
"計算量理論とは、計算にかかる手間(計算の複雑さ)をモデル計算機を用いて系統立てて研究する、理論計算機科学の一分野であり、Juris HartmanisとRichard Stearnsが1965年にアメリカ数学会誌に発表した論文""On the computational complexity of algorithms""によって創設された。その主眼は、計算問題のむずかしさを、それを解くアルゴリズムを実行する手間がどれくらいであるかによってクラス分けし、それらのクラスの性質および相互関係を調べることである。
計算量理論の分野は、1970年代初頭にStephen CookとLeonid Levinによって独立に提唱され、Richard Karpによって整備されたNP完全性の概念によって飛躍的進歩を遂げた。この概念は、計算量のクラスの性質を、そのクラスの代表的問題を通じて研究することを可能にした。
本書の主眼は、チューリング機械を用いて定義される基本的計算量クラスとその階層構造と包含関係について解説すること、そして、それらのクラスの完全問題を示すことである。紙面の都合上、とりあげることのできなかった発展的内容については、巻末の参考文献などを参照されたい。
なお、本書に登場する用語には、それに対応する英語を示してある。また、外国人名に対しては、少し強引なところもあるが、そのカタカナ読みを付しておいた。読者の参考になればさいわいである。
(「まえがき」より)"