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



Information & Computing 106

「計算理論とオートマトン言語理論」
〜 コンピュータの原理を明かす 〜

丸岡 章(東北大学名誉教授) 著

定価:2,160円(本体2,000円+税)
発行:サイエンス社
発行日:2005-11-25
ISBN 978-4-7819-1104-5 / A5判/288頁


<内容詳細>
本書はオートマトンと言語理論,計算可能性の理論,計算量の理論を解説.図や例題を多く用いて直観的に分かるよう工夫した.

<目次>
I 計算の理論
1 すべては計算から始まる
    1.1 計算における壁
    1.2 計算モデルの妥当性
    1.3 本書を効率よく使うために

2 計算の理論のための概念や用語
    2.1 集合
    2.2 系列と言語
    2.3 関数と問題
    2.4 関数とグラフ
    2.5 論理演算と論理式
    2.6 命題と証明
    2.7 アルゴリズムの記述
  問題

II オートマトンと言語
3 有限オートマトン
    3.1 有限オートマトンによるモデル化
    3.2 非決定性有限オートマトン
    3.3 正規表現
    3.4 正規言語の性質
  問題

4 文脈自由言語
    4.1 文脈自由文法
    4.2 生成と受理
    4.3 チョムスキーの標準形
    4.4 文脈自由文法の言語生成能力の限界
    4.5 文脈自由言語の所属問題
  問題

5 プッシュダウンオートマトン
    5.1 プッシュダウンオートマトン
    5.2 プッシュダウンオートマトンと文脈自由文法の等価性
  問題

III 計算可能性
6 チューリング機械
    6.1 チューリング機械
    6.2 チューリング機械の定義の拡張
    6.3 非決定性チューリング機械
    6.4 チャーチ・チューリングの提唱
  問題

7 チューリング機械の計算の万能性とその限界
    7.1 万能チューリング機械
    7.2 停止問題の決定不能性
    7.3 帰着
    7.4 ポストの対応問題の決定不能性
  問題

IV 計算の複雑さ
8 チューリング機械に基づいた計算量限定の計算
    8.1 時間計算量
    8.2 多項式時間で計算できる問題とできないと予想される問題
    8.3 ΡとΝΡ
  問題

9 論理回路に基づいた計算量限定の計算
    9.1 論理関数と論理回路
    9.2 離散関数と離散回路
    9.3 決定性チューリング機械を模倣する論理回路
    9.4 非決定性チューリング機械を模倣する論理回路
    9.5 充足可能性問題
    9.6 回路の充足可能性問題の式充足可能性問題への帰着
  問題

10 ΝΡ完全
    10.1 ΝΡ完全
    10.2 いろいろなΝΡ完全問題
  問題

解答
文献
おわりに
索引