やさしい 計算理論

書影

Information & Computing  117

やさしい 計算理論

有限オートマトンからチューリング機械まで
定価:
2,090
(本体:1,900円+税)
難易度:入門

発行日:2017年12月10日

発行:サイエンス社

ISBN:978-4-7819-1413-8

サイズ:並製A5

ページ数:288ページ

在庫:在庫あり

内容詳細

本書は計算理論を基礎から丁寧にまとめ,その主要な成果を盛り込み,証明も含めて初学者が読み進められることを目指した.数多くの問題により,計算理論を使いこなせるよう工夫された好個の教科・参考書.

目次

I 計算理論とは

1講 系列を操作するしくみ
  問題

2講 計算理論のあらまし
  2.1 計算理論の誕生
  2.2 問題,手順,計算モデル
  2.3 チューリング機械のロバスト性
  2.4 この本のあらまし
  2.5 この本の構成

3講 再帰
  3.1 再帰的定義と組み立てルール
  3.2 ハノイの塔問題を解く手順の再帰的定義
  問題

4講 数学的準備
  4.1 集合
  4.2 系列と言語
  4.3 関数と問題
  4.4 グラフ
  4.5 論理演算とド・モルガンの法則
  4.6 定理と証明
  4.7 アルゴリズムの記述
  問題

II 有限オートマトンと正規表現

5講 有限オートマトンの動き
  問題

6講 有限オートマトンの設計
  問題

7講 有限オートマトンの定義
  7.1 有限オートマトンの形式的定義
  7.2 受理の定義
  問題

8講 非決定性有限オートマトンの定義
  8.1 非決定性有限オートマトンの形式的定義
  8.2 受理の定義
  問題

9講 決定性有限オートマトンと非決定性有限オートマトンの等価性
  9.1 非決定性有限オートマトンを模倣する決定性有限オートマトンの例
  9.2 非決定性有限オートマトンから等価な決定性有限オートマトンへの変換
  問題

10講 正規表現
  10.1 正規表現rが表す言語L(r)とそれを受理する状態遷移図M(r)
  10.2 正規表現rと言語L(r)の関係
  問題

11講 正規表現と有限オートマトンの等価性
  11.1 階層的状態遷移図への等価変換のあらまし
  11.2 状態遷移図から等価な正規表現への変換アルゴリズム
  11.3 計算モデル間の模倣
  問題

12講 有限オートマトンの受理能力の限界
  問題

13講 正規言語のクラスの閉包性
  問題

III プッシュダウンオートマトンと文脈自由言語

14講 文脈自由文法の定義
  問題

15講 正規文法,文脈自由文法,文脈依存文法
  15.1 正規文法による系列の生成と有限オートマトンによる系列の受理
  15.2 文脈自由文法とあいまい性
  15.3 文脈依存文法の定義
  15.4 チョムスキーの階層
  問題

16講 文脈自由文法の設計
  問題

17講 チョムスキーの標準形
  問題

18講 文脈自由文法の言語生成能力の限界
  問題

19講 プッシュダウンオートマトンの定義
  問題

20講 プッシュダウンオートマトンによる文脈自由文法のシミュレーション
  問題

21講 文脈自由文法によるプッシュダウンオートマトンのシミュレーション
  問題

IV 計算可能性

22講 チューリング機械の定義
  22.1 チューリング機械の形式的定義
  22.2 チューリング機械の受理の定義
  22.3 チャーチ・チューリングの提唱
  問題

23講 多テープチューリング機械
  問題

24講 決定性チューリング機械と非決定性チューリング機械の等価性
  問題

25講 万能チューリング機械
  問題

26講 チューリング機械の停止問題
  26.1 停止問題の決定不能性
  26.2 言語の認識と言語の決定
  問題

27講 ポストの対応問題の決定不能性
  27.1 ポストの対応問題の決定不能性
  27.2 帰着
  問題

解答
文献
謝辞
索引

サポート情報

正誤表