- 著者 : 荻原光徳(著)
- 出版社名 : 共立出版
- シリーズ名等 : アルゴリズム・サイエンスシリーズ 6 数理技法編
- 発売日 : 2006年11月
- ISBN : 9784320121720
- 計算量理論とは、計算にかかる手間(計算の複雑さ)をモデル計算機を用いて系統立てて研究する、理論計算機科学の一分野であり、Juris HartmanisとRichard Stearnsが1965年にアメリカ数学会誌に発表した論文"On the computational complexity of algorithms"によって創設された。その主眼は、計算問題のむずかしさを、それを解くアルゴリズムを実行する手間がどれくらいであるかによってクラス分けし、それらのクラスの性質および相互関係を調べることである。
計算量理論の分野は、1970年代初頭にStephen CookとLeonid Levinによって独立に提唱され、Richard Karpによって整備されたNP完全性の概念によって飛躍的進歩を遂げた。この概念は、計算量のクラスの性質を、そのクラスの代表的問題を通じて研究することを可能にした。
本書の主眼は、チューリング機械を用いて定義される基本的計算量クラスとその階層構造と包含関係について解説すること、そして、それらのクラスの完全問題を示すことである。紙面の都合上、とりあげることのできなかった発展的内容については、巻末の参考文献などを参照されたい。
なお、本書に登場する用語には、それに対応する英語を示してある。また、外国人名に対しては、少し強引なところもあるが、そのカタカナ読みを付しておいた。読者の参考になればさいわいである。
(「まえがき」より)※本データはこの商品が発売された時点の情報です。
閉じる
閉じる
閉じる
再入荷リクエストが完了しました。
リクエストした商品が再入荷された場合、
メールでお知らせします。
閉じる
再入荷リクエスト
リクエストした商品が再入荷された場合、
メールでお知らせします。
上記期間を経過しても商品が再入荷されない場合、設定は自動的に解除されます。(上記期間を経過するか、商品が再入荷されるまで設定は解除できません)