計算理論とオートマトン言語理論[第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完全問題
  問題

解答
文献
おわりに
索引

サポート情報

関連書籍

ソーシャルメディア論

土方嘉徳

2,090円(税込)

入門
情報処理[第3版]

草薙信照

2,200円(税込)

入門
Linux/FreeBSD/Solarisで学ぶUNIX

皆本晃弥

2,530円(税込)

入門