出版社内容情報
Michael Sipser教授による “Theory of Computation” の講義はMIT屈指の名講義で、教室には活気と笑いが絶えることはない。本書はその講義ノートをもとにまとめられた、この分野の標準的教科書である。
定理を述べたあと直ちに証明に取りかからず、証明のアイデアを与える工夫、証明の失敗例に言及して理解を深めさせるなど、随所に講義の雰囲気が感じられる、教育的配慮の行き届いた教科書になっている。
第3版では、「決定性文脈自由言語」に関する節が新たに加えられたほか(第2巻)、問題や解答が追加されるとともに、いくつかの話題に関して、第2版刊行後の研究の進展について説明を加えた。
目次
7 時間の複雑さ(複雑さの測定;クラスP ほか)
8 領域の複雑さ(Savitchの定理;クラスPSPACE ほか)
9 問題の扱いにくさ(階層定理;相対化 ほか)
10 計算の複雑さの理論における先進的な話題(近似アルゴリズム;確率的アルゴリズム ほか)
著者等紹介
田中圭介[タナカケイスケ]
1997年北陸先端科学技術大学院大学情報科学研究科博士後期課程修了。現在、東京工業大学情報理工学院教授、サイバーセキュリティ研究教育センター長、博士(情報科学)。専門分野:暗号理論、計算の複雑さの理論
藤岡淳[フジオカアツシ]
1990年東京工業大学大学院理工学研究科博士課程修了。現在、神奈川大学情報学部システム数理学科教授、工学博士。専門分野:暗号理論、暗号応用。主要著書:『暗号・ゼロ知識証明・数論』(共著、共立出版)『IT Text情報セキュリティ(改訂2版)』(共著、オーム社)
阿部正幸[アベマサユキ]
1992年東京理科大学大学院電気工学専攻科修士課程修了。現在、NTT社会情報研究所フェロー、工学博士。2018年‐現在、京都大学大学院情報学研究科客員教授。専門分野:暗号理論、暗号プロトコル
植田広樹[ウエダヒロキ]
1994年大阪市立大学大学院理学研究科前期博士課程(修士)修了。2019年‐現在、NTT技術企画部門セキュリティ・アンド・トラスト室次長・担当部長。専門分野:実験整数論(素因数分解)、コンサルティング(セキュリティ)
太田和夫[オオタカズオ]
1979年早稲田大学大学院理工学研究科修士課程修了。現在、電気通信大学名誉教授(2020)、理学博士。2019年‐現在、産業技術総合研究所客員研究員。専門分野:情報セキュリティ。主要著書:『暗号・ゼロ知識証明・数論』(共著、共立出版)『ほんとうに安全?現代の暗号』(共著、岩波書店)
渡辺治[ワタナベオサム]
東京工業大学大学院理工学研究科修士課程修了。現在、東京工業大学理事・副学長(研究担当)、工学博士。主要著書『計算可能性・計算の複雑さ入門』(近代科学社)、『コンピュータサイエンス』(丸善出版)(本データはこの書籍が刊行された当時に掲載されていたものです)
※書籍に掲載されている著者及び編者、訳者、監修者、イラストレーターなどの紹介情報です。