株式会社サイエンス社 株式会社新世社 株式会社数理工学社
ホーム 会社案内 社員募集 ご意見・ご感想 リンク 当サイトの利用  



Information & Computing 4

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

J.E.ホップクロフト
R.モトワニ
J.D.ウルマン 著
野崎昭弘(大妻女子大学名誉教授)
高橋正子(東京工業大学名誉教授)
町田 元(一橋大学教授)
山崎秀記(一橋大学名誉教授) 訳

定価:2,808円(本体2,600円+税)
発行:サイエンス社
発行日:2003-08-05
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章の参考文献

索引