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

書影

Information & Computing  122

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

コンピュータの原理を明かす
定価:
2,255
(本体:2,050円+税)
難易度:入門

発行日:2021年11月25日

発行:サイエンス社

ISBN:978-4-7819-1521-0

サイズ:並製A5

ページ数:280ページ

在庫:在庫あり

内容詳細

初学者でも読み進められるように証明を含め丁寧に記述し,全面的に見直しを行った著者渾身の改訂版.“なるほど,そういうことか”を繰り返し体験して楽しみながら学ぶことができる.章末問題にはすべて解答をつけた.

目次

I 計算理論とは
1 すべては計算から始まる
  1.1 計算理論の誕生と展開
  1.2 この本の学び方

2 計算理論のための概念や用語
  2.1 集合
  2.2 系列と言語
  2.3 関数と問題
  2.4 グラフ
  2.5 論理演算とド・モルガンの法則
  2.6 定理と証明
  2.7 再帰
  2.8 アルゴリズムの記述
  問題

II 有限オートマトン,プッシュダウンオートマトン,そして文脈自由文法
3 有限オートマトン
  3.1 有限オートマトンの導入
  3.2 非決定性有限オートマトン
  3.3 決定性有限オートマトンと非決定性有限オートマトンの等価性
  3.4 正規表現
  3.5 有限オートマトンの受理能力の限界
  問題

4 文脈自由文法
  4.1 文脈自由文法の導入
  4.2 文脈自由文法と導出のあいまいさ
  4.3 チョムスキーの標準形
  4.4 文脈自由文法の言語生成能力の限界
  4.5 さまざまな形式文法
  問題

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

III 計算可能性
6 チューリング機械
  6.1 チューリング機械の基本
  6.2 チューリング機械のロバスト性
  6.3 チャーチ・チューリングの提唱
  問題

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

IV 計算の複雑さ
8 クラスPとクラスNP
  8.1 現実的に計算できる問題とできない問題の例
  8.2 時間を限定した計算
  8.3 クラスPとクラスNP
  8.4 クラスEXP
  8.5 アルゴリズムの計算時間の評価
  問題

9 論理回路に基づいた計算時間限定の計算
  9.1 非決定性チューリング機械の論理式による模倣のあらまし
  9.2 論理回路と離散回路
  9.3 決定性チューリング機械を模倣する論理回路
  9.4 非決定性チューリング機械を模倣する論理回路
  9.5 論理回路を模倣する論理式
  問題

10 NP完全性
  10.1 NP完全の定義
  10.2 さまざまなNP完全問題
  問題

解答
文献
おわりに
索引

サポート情報

関連書籍

Fortran77プログラミング

原田賢一

1,815円(税込)

入門
花のCG

戸川隼人

1,880円(税込)

入門
ソーシャルメディア論

土方嘉徳

2,090円(税込)

入門