![計算理論の基礎 [原著第3版] 3.複雑さの理論の表紙](/_next/image?url=https%3A%2F%2Fthumbnail.image.rakuten.co.jp%2F%400_mall%2Fbook%2Fcabinet%2F5636%2F9784320125636_1_2.jpg%3F_ex%3D400x400&w=3840&q=75 "計算理論の基礎 [原著第3版] 3.複雑さの理論")
計算理論の基礎 [原著第 3 版] 3.複雑さの理論(ケイサンリロンノキソゲンチョダイサンハンサンフクザツサノリロン)
- 著者:
- Michael Sipser/田中 圭介/藤岡 淳/阿部 正幸/植田 広樹/太田 和夫(マイケル シプサー/タナカ ケイスケ/フジオカ アツシ/アベ マサユキ/ウエダ ヒロキ/オオタ カズオ)
- 出版社:
- 共立出版
- 出版日:
- 2023年05月08日
- ISBN:
- 9784320125636
- 価格:
- ¥4,290
- 在庫:
- 1
- 判型:
- 単行本
書籍紹介
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 暗号
この本に興味がある方におすすめ
この本に関連
Michael Sipser の他の書籍
![計算理論の基礎 [原著第3版] 2.計算可能性の理論の表紙](/_next/image?url=https%3A%2F%2Fthumbnail.image.rakuten.co.jp%2F%400_mall%2Fbook%2Fcabinet%2F5629%2F9784320125629_1_2.jpg%3F_ex%3D400x400&w=3840&q=75 "計算理論の基礎 [原著第3版] 2.計算可能性の理論")
![計算理論の基礎 [原著第3版] 1.オートマトンと言語の表紙](/_next/image?url=https%3A%2F%2Fthumbnail.image.rakuten.co.jp%2F%400_mall%2Fbook%2Fcabinet%2F5612%2F9784320125612_1_3.jpg%3F_ex%3D400x400&w=3840&q=75 "計算理論の基礎 [原著第3版] 1.オートマトンと言語")
関連記事
アルゴリズム本ガイド - 競プロだけじゃない、実務に活きる選び方
アルゴリズム本の 3 タイプと、実務でアルゴリズムの知識が活きる場面、数学が苦手な人向けの学習ルートを紹介します。
機械学習・AI 本ガイド - エンジニアが読むべき技術書の選び方
機械学習の基礎から実践まで学べる技術書の選び方を紹介。数学が苦手な人向けの学習ルートと、ML 本の賞味期限の見極め方を解説します。
ソフトウェア開発の歴史を変えた 5 冊の技術書
アルゴリズムの学問化からコードの可読性革命まで、ソフトウェア開発の方向性を決定づけた 5 冊の技術書を、時代背景とエピソードとともに紹介します。