計算理論とオートマトン言語理論

書影

Information & Computing  106

計算理論とオートマトン言語理論

コンピュータの原理を明かす
定価:
2,200
(本体: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 いろいろなΝΡ完全問題
  問題

解答
文献
おわりに
索引


サポート情報

関連書籍

Windowsリテラシ

皆本晃弥森 雅生

2,420円(税込)

入門
CによるフラクタルCG

渕上季代絵

1,760円(税込)

中級
みんなのCプログラミング

皆本晃弥

2,640円(税込)

入門