英語で学ぶ 計算理論 - CD-ROM付 -

英語で学ぶ 計算理論 - CD-ROM付 -

簡潔かつ包括的な計算理論の入門書である。形式言語とオートマトン理論を学び,部分的帰納関数とチューリング機械を通して,アルゴリズムの直感的観念の定式化を行う。また日英各々のスライドがCD-ROMに収められ,専門用語を学べる。

  • CD付
ジャンル
発行年月日
2009/04/30
判型
A5
ページ数
238ページ
ISBN
978-4-339-02438-8
英語で学ぶ 計算理論 - CD-ROM付 -
在庫あり
2営業日以内に出荷致します。

定価

3,080(本体2,800円+税)

カートに入れる

購入案内

  • 内容紹介
  • 目次
  • 著者紹介

一部を除き全編英語表記で日本語訳は付属していません。
簡潔かつ包括的な計算理論の入門書である。形式言語とオートマトン理論を学び,部分的帰納関数とチューリング機械を通して,アルゴリズムの直感的観念の定式化を行う。また日英各々のスライドがCD-ROMに収められ,専門用語を学べる。

1. 形式言語の導入
1.1 はじめに
1.2 定義と記法
1.3 文字列と言語
1.4 回文
1.5 課題 1


2. 形式文法の導入
2.1 形式言語の定義
2.2 正規言語
2.3 課題 2


3. 有限状態オートマトン
3.1 有限オートマトンによる計算
3.2 有限オートマトンと正規言語
3.3 課題 3


4. REG の性質
4.1 ネローデの定理
4.2 正規表現
4.3 正規言語の反復補題
4.4 課題 4


5. UNIX における正規表現
5.1 字句解析
5.2 テキスト中のパターン検出
5.3 課題 5


6. 文脈自由言語
6.1 文脈自由言語の定義
6.2 文脈自由言語の閉包性
6.3 課題 6


7. 続:文脈自由文法
7.1 バッカス-ナウア形
7.2 構文木と曖昧さ
7.3 チョムスキー標準形
7.4 課題 7


8. CF と準同型写像
8.1 代入と準同型写像
8.2 CF の準同型的な性質
8.3 課題 8


9. プッシュダウンオートマトン
9.1 プッシュダウンオートマトンの導入
9.2 PDA と文脈自由文法
9.3 課題 9


10. CF, PDA, その先
10.1 グライバッハ標準形
10.2 主要定理
10.3 文脈依存言語
10.4 課題 10


11. 計算モデル
11.1 部分帰納的関数
11.2 対関数
11.3 一般帰納的関数
11.4 課題 11


12. チューリング機械
12.1 1 テープチューリング機械
12.2 チューリング計算
12.3 万能チューリング機械
12.4 言語の受理
12.5 課題 12


13. 計算論的解決不能性
13.1 停止問題
13.2 ポストの対応問題
13.3 課題 13


14. PCP の応用
14.1 文脈自由言語に関する結果
14.2 正規言語に関する再考
14.3 L0 に関する結果
14.4 まとめ
14.5 課題 14


15. 番号付けと計算量
15.1 ゲーデル数化
15.2 不動点,再帰,ライスの定理
15.3 計算量
15.4 計算量クラス
15.4.1 計算量クラスの帰納可算性
15.4.2 決定不能な結果
15.4.3 ギャップ定理
15.5 課題 15


付録
A.1 ギリシャ文字
参考文献
英和索引
和英索引
記号一覧

大久保 好章(オオクボ ヨシアキ)