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

書影

Information & Computing  28

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

定価:
3,524
(本体:3,204円+税)

発行日:1988年10月1日

発行:サイエンス社

ISBN:978-4-7819-0521-1

サイズ:並製A5

ページ数:352ページ

在庫:品切れ

内容詳細

計算機科学の基礎づけに中心的な役割を占める「古典的計算可能性理論」「形式言語とオートマトンの理論」「計算量の理論」「暗号学」について解説する.

目次

1 序論:計算のモデル
2 言語理論の基礎
2-1 言語と書き替えシステム
2-2 文法
2-3 Postシステム
2-4 Morkovアルゴリズム
2-5 Lシステム
2-6 演習問題
3 制限つきオートマトン
3-1 有限オートマトン
3-2 Kleeneの特徴づけ
3-3 汎順序機械
3-4 反復補題
3-5 プッシュダウン・オートマトン
3-6 演習問題
4 テューリング機械と帰納的関数
4-1 汎用性の高い計算モデル
4-2 機械語のプログラミング,Churchの仮説,万能機械
4-3 帰納定理と基本的な決定不能性の結果
4-4 帰納的集合と帰納的言語,帰納的可算集合と帰納的可算言語
4-5 還元可能性と創造的集合
4-6 合成に基づく万能性
4-7 演習問題
5 有名な決定問題
5-1 Postの対応問題とその応用
5-2 Hilbertの第10問題とその帰結:ほとんどの問題は多項式で表現できる
5-3 語の問題とベクトル加算系
5-4 演習問題
6 計算の複雑さ
6-1 基本概念と公理的理論
6-2 計算量のクラス,間隙定理,圧縮定理
6-3 加速定理,最良アルゴリズムを持たない関数
6-4 時間有界,クラスTNTNT完全問題
6-5 手に負えないという証明つきの問題
6-6 領域尺度とトレード・オフ
6-7 演習問題
7 暗号学
7-1 背景と古典的な暗号系
7-2 公開鍵暗号系
7-3 ナップザック・システム
7-4 RSAシステム
7-5 通信における不可能に思える問題を解くプロトコル
7-6 演習問題
8 オートマトン・言語理論における動向
8-1 ペトリ・ネット
8-2 類似な文法と言語
8-3 鼓動型オートマトン
8-4 演習問題

サポート情報

関連書籍