書名で キーワードで

詳細検索 >>

HOME  > 情報工学  / 情報数学  / オートマトン・計算理論  > オートマトン・言語と計算理論

書籍詳細

電子情報通信レクチャーシリーズ B-6)

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

▼ 目次を読む

▼ 目次をたたむ

岩間一雄 京大大学院教授 工博 著

… 著者ホームページです

発行年月日:2003/11/06 , 判 型: B5,  ページ数:186頁

ISBN:978-4-339-01821-9,  定 価:3,240円 (本体3,000円+税)

計算機では,解ける問題,解けない問題,解けることは解けるが時間がかかって手に負えない問題の3種類が存在する。このことを把握するため,計算機のモデルを正確に理解し上手に使えるように指導するのが本書の目的である。

【目次】

1.言語とは何か・なぜ必要か
 1.1 文章の意味を理解する
 1.2 文章の正しさを解析する
 1.3 形式言語を導入する
 本章のまとめと文献
1.言語とは何か・なぜ必要か
 1.1 文章の意味を理解する
 1.2 文章の正しさを解析する
 1.3 形式言語を導入する
 本章のまとめと文献
 理解度の確認

2.正規表現と有限オートマトン
 2.1 正規表現
 2.2 有限オートマトン
 2.3 非決定性有限オートマトン
 2.4 有限オートマトンと正規表現の等価性
 2.5 有限オートマトンの能力の限界
 本章のまとめと文献
 理解度の確認

3.文脈自由文法
 3.1 文脈自由文法の重要性
 3.2 文脈自由文法
 3.3 文脈自由文法と正規言語
 3.4 文脈自由文法の標準形
 3.5 文脈自由文法で生成できない言語
 本章のまとめと文献
 理解度の確認

4.プッシュダウンオートマトン
 4.1 プッシュダウンオートマトン
 4.2 プッシュダウンオートマトンの設計
 本章のまとめと文献
 理解度の確認

5.チューリング機械と0型文法
 5.1 チューリング機械
 5.2 0型文法
 5.3 チューリング機械によっても認識できない言語
 本章のまとめと文献
 理解度の確認

6.チューリング機械の停止性と決定問題
 6.1 チューリング機械の停止性
 6.2 非可解な問題
 6.3 ポストの対応問題
 本章のまとめと文献
 理解度の確認

7.NP完全問題
 7.1 クラスPとクラスNP
 7.2 NP完全性
 本章のまとめと文献
 理解度の確認

8.最近の話題―あとがきにかえて―
 8.1 固定パラメータ容易性
 8.2 対数領域限定計算
 本章のまとめと文献

索引

【おすすめ本】

在庫は時期によりまして変動することがございますので、ご了承ください。