「honto 本の通販ストア」サービス終了及び外部通販ストア連携開始のお知らせ
詳細はこちらをご確認ください。
- みんなの評価
- あなたの評価 評価して"My本棚"に追加 評価ありがとうございます。×
- カテゴリ:大学生・院生
- 発売日:2006/11/24
- 出版社: 共立出版
- サイズ:22cm/283p
- 利用対象:大学生・院生
- ISBN:4-320-12172-4
- 国内送料無料
このセットに含まれる商品
前へ戻る
- 対象はありません
次に進む
商品説明
チューリング機械を用いて定義される基本的計算量クラスとその階層構造と包含関係について解説し、それらのクラスの完全問題を示した書。登場する用語には対応する英語を付す。【「TRC MARC」の商品解説】
計算量理論とは、計算にかかる手間(計算の複雑さ)をモデル計算機を用いて系統立てて研究する、理論計算機科学の一分野であり、Juris HartmanisとRichard Stearnsが1965年にアメリカ数学会誌に発表した論文"On the computational complexity of algorithms"によって創設された。その主眼は、計算問題のむずかしさを、それを解くアルゴリズムを実行する手間がどれくらいであるかによってクラス分けし、それらのクラスの性質および相互関係を調べることである。
計算量理論の分野は、1970年代初頭にStephen CookとLeonid Levinによって独立に提唱され、Richard Karpによって整備されたNP完全性の概念によって飛躍的進歩を遂げた。この概念は、計算量のクラスの性質を、そのクラスの代表的問題を通じて研究することを可能にした。
本書の主眼は、チューリング機械を用いて定義される基本的計算量クラスとその階層構造と包含関係について解説すること、そして、それらのクラスの完全問題を示すことである。紙面の都合上、とりあげることのできなかった発展的内容については、巻末の参考文献などを参照されたい。
なお、本書に登場する用語には、それに対応する英語を示してある。また、外国人名に対しては、少し強引なところもあるが、そのカタカナ読みを付しておいた。読者の参考になればさいわいである。
(「まえがき」より)【商品解説】
目次
- 第1章 準備
- 1.1 論理
- 1.2 集合
- 1.3 グラフ・木
- 1.4 写像
- 1.5 言語
- 1.6 関数の漸近的性状
- 第2章 チューリング機械の基礎
- 2.1 チューリング機械による言語の受理
著者紹介
荻原 光徳
- 略歴
- 〈荻原光徳〉1963年川崎市生まれ。東京工業大学大学院理学部博士後期課程情報科学専攻修了。米国ロチェスター大学コンピュータサイエンス学科主任教授。
関連キーワード
あわせて読みたい本
前へ戻る
- 対象はありません
次に進む
この著者・アーティストの他の商品
前へ戻る
- 対象はありません
次に進む