オートマトン 言語理論 計算論 II [第2版]

書影

Information & Computing  4

オートマトン 言語理論 計算論 II [第2版]

定価:
2,860
(本体:2,600円+税)
難易度:中級

発行日:2003年8月5日

発行:サイエンス社

ISBN:978-4-7819-1027-7

サイズ:並製A5

ページ数:256ページ

在庫:在庫あり

内容詳細

オートマトン,言語および計算理論の入門書として評価を得ている書の改訂翻訳版.前著の抽象的な話題が現在どのように使われているか例示し,モデル検査アルゴリズム,ドキュメント記述言語など新しい応用も豊富に盛り込まれている.

目次

8 テューリング機械入門
8.1 コンピュータで解けない問題
8.2 テューリング機械
8.3 テューリング機械のプログラム技法
8.4 基本テューリング機械の拡張
8.5 制限されたテューリング機械
8.6 テューリング機械とコンピュータ
8.7 第8章の要約
8.8 第8章の参考文献

9 決定不能性
9.1 帰納的可算でない言語
9.2 帰納的可算な決定不能問題\r
9.3 テューリング機械の決定不能問題\r
9.4 ポストの対応問題
9.5 他の決定不能問題\r
9.6 第9章の要約
9.7 第9章の参考文献

10 実行不能な問題
10.1 クラスPとクラスNP
10.2 最初のNP完全問題
10.3 制限された形の充足可能性問題
10.4 その他のNP完全問題
10.5 第10章の要約
10.6 第10章の参考文献

11 その他の「問題のクラス」
11.1 NPに属す言語の補集合
11.2 多項式領域で解ける問題
11.3 PSに対して完全な問題
11.4 乱数を利用して定義される言語のクラス
11.5 素数性判定問題の計算量
11.5 第11章の要約
11.6 第11章の参考文献

索引


サポート情報

その他

正誤表


Information & Computing 4
「オートマトン 言語理論 計算論 II [第2版]」 サポートページ



■ 正誤表

J.E.ホップクロフト・R.モトワニ・J.D.ウルマン 著 野崎昭弘・高橋正子・町田 元・山崎秀記 訳『オートマトン 言語理論 計算論 II』第2版第2刷に誤りがございましたので,お詫びして訂正いたします.


場所
奥付   国際基督教大学名誉教授 東京工業大学名誉教授

関連書籍