計算理論の基礎 ３「複雑さの理論」
Ｍｉｃｈａｅｌ Ｓｉｐｓｅｒ／著 田中圭介／監訳 藤岡淳／監訳 阿部正幸／〔ほか〕訳
発売日：2023年5月
- 巻の書名
- 複雑さの理論
- ページ数
- ｐ３３０〜５４０ ４０ｐ
- ISBN
- 978-4-320-12563-6
- 著者情報
- 田中 圭介（タナカ ケイスケ）
１９９７年北陸先端科学技術大学院大学情報科学研究科博士後期課程修了。現在、東京工業大学情報理工学院教授、サイバーセキュリティ研究教育センター長、博士（情報科学）。専門分野：暗号理論、計算の複雑さの理論
藤岡 淳（フジオカ アツシ）
１９９０年東京工業大学大学院理工学研究科博士課程修了。現在、神奈川大学情報学部システム数理学科教授、工学博士。専門分野：暗号理論、暗号応用。主要著書：『暗号・ゼロ知識証明・数論』（共著、共立出版）『ＩＴ Ｔｅｘｔ情報セキュリティ（改訂２版）』（共著、オーム社）
阿部 正幸（アベ マサユキ）
１９９２年東京理科大学大学院電気工学専攻科修士課程修了。現在、ＮＴＴ社会情報研究所フェロー、工学博士。２０１８年‐現在、京都大学大学院情報学研究科客員教授。専門分野：暗号理論、暗号プロトコル
植田 広樹（ウエダ ヒロキ）
１９９４年大阪市立大学大学院理学研究科前期博士課程（修士）修了。２０１９年‐現在、ＮＴＴ技術企画部門セキュリティ・アンド・トラスト室次長・担当部長。専門分野：実験整数論（素因数分解）、コンサルティング（セキュリティ）
太田 和夫（オオタ カズオ）
１９７９年早稲田大学大学院理工学研究科修士課程修了。現在、電気通信大学名誉教授（２０２０）、理学博士。２０１９年‐現在、産業技術総合研究所客員研究員。専門分野：情報セキュリティ。主要著書：『暗号・ゼロ知識証明・数論』（共著、共立出版）『ほんとうに安全？現代の暗号』（共著、岩波書店）
渡辺 治（ワタナベ オサム）
東京工業大学大学院理工学研究科修士課程修了。現在、東京工業大学理事・副学長（研究担当）、工学博士。主要著書『計算可能性・計算の複雑さ入門』（近代科学社）、『コンピュータサイエンス』（丸善出版）
セブン-イレブン受取り(送料無料)
発送目安
発売日（発売日以降は当日）～2日で発送
宅配（送料¥550税込）
発送目安
発売日（発売日以降は当日）～2日で発送
交通状況・天候の影響や注文が集中した場合等、お届けにお時間をいただく場合がございます。
商品説明
Michael Sipser教授による “Theory of Computation” の講義はMIT屈指の名講義で、教室には活気と笑いが絶えることはない。本書はその講義ノートをもとにまとめられた、この分野の標準的教科書である。
定理を述べたあと直ちに証明に取りかからず、証明のアイデアを与える工夫、証明の失敗例に言及して理解を深めさせるなど、随所に講義の雰囲気が感じられる、教育的配慮の行き届いた教科書になっている。
第3版では、「決定性文脈自由言語」に関する節が新たに加えられたほか（第2巻）、問題や解答が追加されるとともに、いくつかの話題に関して、第2版刊行後の研究の進展について説明を加えた。
目次
第7章 時間の複雑さ
7.1 複雑さの測定
7.2 クラスP
7.3 クラスNP
7.4 NP完全性
7.5 他のNP完全問題
第8章 領域の複雑さ
8.1 Savitchの定理
8.2 クラスPSPACE
8.3 PSPACE完全性
8.4 クラスLとクラスNL
8.5 NL完全性
8.6 NLとcoNLの等価性
第9章 問題の扱いにくさ
9.1 階層定理
9.2 相対化
9.3 回路の複雑さ
第10章 計算の複雑さの理論における先進的な話題
10.1 近似アルゴリズム
10.2 確率的アルゴリズム
10.3 交替性
10.4 対話証明系
10.5 並列計算
10.6 暗号
商品詳細
- 出版社名
- 共立出版
- サイズ
- ２１ｃｍ
- フォーマット
- 単行本
- 原題
- 原タイトル：Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ ｔｈｅ Ｔｈｅｏｒｙ ｏｆ Ｃｏｍｐｕｔａｔｉｏｎ 原著第３版の翻訳
注意事項
- 本の帯に関して
- 帯つきでの出荷はお約束しておりません。
商品ページに、帯のみに付与される特典物等の表記がある場合でも、確実に帯つきでの出荷はお約束しておりません。
また、帯は商品の一部ではなく「広告扱い」のため、帯の有無・破損による交換や返品は承っておりません。 - 版・表紙について
- 版・表紙（カバー）のご指定は承っておりません。ご注文いただくタイミングによっては、お届けする商品の版や表紙が商品ページ上のものとは異なる場合がございます。
また、初版にのみにお付けしている特典（初回特典、初回仕様特典）がある商品は、商品ページに特典の表記がされている場合でも、無くなり次第終了となります。
