この商品をご覧のお客様は、こんな商品もチェックしています。
- パソコン仕事が10倍速くなる80+αの方法
-
価格:1,496円(本体1,360円+税)
【2024年01月発売】
- 徹底討議 二〇世紀の思想・文学・芸術
-
価格:4,620円(本体4,200円+税)
【2024年03月発売】
- 日本とユダヤの古代史&世界史 縄文・神話から続く日本建国の真実
-
価格:1,870円(本体1,700円+税)
【2023年07月発売】
- 戦争と平和
-
価格:1,320円(本体1,200円+税)
【2024年01月発売】
- できるWord & Excel 2021
-
価格:2,156円(本体1,960円+税)
【2022年05月発売】
[BOOKデータベースより]
7 時間の複雑さ(複雑さの測定;クラスP;クラスNP;NP完全性;他のNP完全問題)
[日販商品データベースより]8 領域の複雑さ(Savitchの定理;クラスPSPACE;PSPACE完全性;クラスLとクラスNL;NLとcoNLの等価性)
9 問題の扱いにくさ(階層定理;相対化;回路の複雑さ)
10 計算の複雑さの理論における先進的な話題(近似アルゴリズム;確率的アルゴリズム;交替性;対話証明系;並列計算;暗号)
M.Sipser教授の“Theory of Computation”の講義はMIT屈指の名講義で、教室には活気と笑いが絶えることはない。本書はその講義ノートをもとにまとめられた、この分野の標準的教科書である。
定理を述べたあと直ちに証明に取りかからず、証明のアイデアを与える工夫、証明の失敗例に言及して理解を深めさせるなど、随所に講義の雰囲気が感じられる、教育的配慮の行き届いた教科書になっている。
今回第2版では、初版の内容に「選ばれた問題」に対する解答を追加するとともに、いくつかの話題に関して、初版後の研究の進展について説明を加えた。