計算理論の基礎 ３「複雑さの理論」
Ｍｉｃｈａｅｌ Ｓｉｐｓｅｒ／著 太田和夫／監訳 田中圭介／監訳 阿部正幸／〔ほか〕訳
発売日：2008年5月
- 巻の書名
- 複雑さの理論
- ページ数
- ｐ２９４〜５０７ ４８ｐ
- ISBN
- 978-4-320-12209-3
- 著者情報
- 太田 和夫（オオタ カズオ）
１９７９年早稲田大学大学院理工学研究科修士課程修了。１９７９‐２００１年ＮＴＴ情報流通プラットフォーム研究所。現在、電気通信大学情報通信工学科教授理学博士。１９９１‐２年マサチューセッツ工科大学客員研究員。１９９５‐８年電気通信大学情報システム学研究科客員教授。１９９９‐２０００年マサチューセッツ工科大学客員教授。専門分野は情報セキュリティ
田中 圭介（タナカ ケイスケ）
１９９７年北陸先端科学技術大学院大学情報科学研究科博士後期課程修了。１９９７‐２００１年ＮＴＴ情報流通プラットフォーム研究所。２００１年東京工業大学大学院情報理工学研究科講師。現在、東京工業大学大学院情報理工学研究科准教授博士（情報科学）。２００６年‐現在、東京大学大学院情報学環・学際情報学府非常勤講師。専門分野は暗号理論、計算の複雑さの理論
阿部 正幸（アベ マサユキ）
１９９２年東京理科大学大学院電気工学専攻科修士課程修了。現在、ＮＴＴ情報流通プラットフォーム研究所特別研究員、主幹研究員、博士（工学）。１９９６年スイス連邦工科大学客員研究員。専門分野は情報セキュリティ（主に暗号プロトコルの研究開発）
植田 広樹（ウエダ ヒロキ）
１９９４年大阪市立大学大学院理学研究科前期博士課程（修士）修了。１９９４‐２００６年ＮＴＴ情報流通プラットフォーム研究所。現在、ＮＴＴ西日本法人営業本部セキュリティサービス推進室担当課長。専門分野は実験整数論（素因数分解）、コンサルティング（セキュリティ）
藤岡 淳（フジオカ アツシ）
１９９０年東京工業大学大学院理工学研究科博士課程修了。現在、ＮＴＴ情報流通プラットフォーム研究所主幹研究員。工学博士。１９９３‐４年スイス連邦工科大学客員研究員。１９９７年東海大学非常勤講師。２００１‐３年東京大学客員助教授。２００４‐８年国立情報学研究所客員准教授。専門分野は情報セキュリティ（特に暗号理論）
セブン-イレブン受取り(送料無料)
発送目安
発売日（発売日以降は当日）～2日で発送
宅配（送料¥550税込）
発送目安
発売日（発売日以降は当日）～2日で発送
交通状況・天候の影響や注文が集中した場合等、お届けにお時間をいただく場合がございます。
商品説明
M.Sipser教授の“Theory of Computation”の講義はMIT屈指の名講義で，教室には活気と笑いが絶えることはない。本書はその講義ノートをもとにまとめられた，この分野の標準的教科書である。
定理を述べたあと直ちに証明に取りかからず，証明のアイデアを与える工夫，証明の失敗例に言及して理解を深めさせるなど，随所に講義の雰囲気が感じられる，教育的配慮の行き届いた教科書になっている。
今回第2版では，初版の内容に「選ばれた問題」に対する解答を追加するとともに，いくつかの話題に関して，初版後の研究の進展について説明を加えた。
目次
７ 時間の複雑さ（複雑さの測定
クラスＰ
クラスＮＰ
ＮＰ完全性
他のＮＰ完全問題）
８ 領域の複雑さ（Ｓａｖｉｔｃｈの定理
クラスＰＳＰＡＣＥ
ＰＳＰＡＣＥ完全性
クラスＬとクラスＮＬ
ＮＬとｃｏＮＬの等価性）
９ 問題の扱いにくさ（階層定理
相対化
回路の複雑さ）
１０ 計算の複雑さの理論における先進的な話題（近似アルゴリズム
確率的アルゴリズム
交替性
対話証明系
並列計算
暗号）
商品詳細
- 出版社名
- 共立出版
- サイズ
- ２１ｃｍ
- フォーマット
- 単行本
- 原題
- 原タイトル：Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ ｔｈｅ ｔｈｅｏｒｙ ｏｆ ｃｏｍｐｕｔａｔｉｏｎ 原著第２版の翻訳
注意事項
- 本の帯に関して
- 帯つきでの出荷はお約束しておりません。
商品ページに、帯のみに付与される特典物等の表記がある場合でも、確実に帯つきでの出荷はお約束しておりません。
また、帯は商品の一部ではなく「広告扱い」のため、帯の有無・破損による交換や返品は承っておりません。 - 版・表紙について
- 版・表紙（カバー）のご指定は承っておりません。ご注文いただくタイミングによっては、お届けする商品の版や表紙が商品ページ上のものとは異なる場合がございます。
また、初版にのみにお付けしている特典（初回特典、初回仕様特典）がある商品は、商品ページに特典の表記がされている場合でも、無くなり次第終了となります。
