よく一緒に購入されている商品
商品の説明
内容紹介
計算の理論の世界へ,ようこそ!
Michael Sipser教授の“Theory of Computation”の講義も,本書と同様に,このフレンドリーな挨拶から始まった.彼の講義はMIT屈指の名講義で,教室には活気と笑いが絶えることはない。本書は,その講義ノートをもとにまとめられたもので,計算の理論の主テーマである,「オートマトンと言語の理論」,「計算可能性の理論」,そして「複雑さの理論」をカバーした,この分野の標準的教科書である。
定理を述べたあと直ちに証明に取りかからず,証明のアイデアを与える工夫,証明の失敗例に言及して理解を深めさせるなど,随所に講義の雰囲気が感じられる,教育的配慮の行き届いた教科書になっている。
今回の第2版では,「第1巻:オートマトンと言語の理論」,「第2巻:計算可能性の理論」,「第3巻:複雑さの理論」の全3巻に分冊化した.また,初版の内容に「選ばれた問題」に対する解答を追加するとともに,いくつかの話題に関して,初版後の研究の進展について説明を加えた。
Michael Sipser教授の“Theory of Computation”の講義も,本書と同様に,このフレンドリーな挨拶から始まった.彼の講義はMIT屈指の名講義で,教室には活気と笑いが絶えることはない。本書は,その講義ノートをもとにまとめられたもので,計算の理論の主テーマである,「オートマトンと言語の理論」,「計算可能性の理論」,そして「複雑さの理論」をカバーした,この分野の標準的教科書である。
定理を述べたあと直ちに証明に取りかからず,証明のアイデアを与える工夫,証明の失敗例に言及して理解を深めさせるなど,随所に講義の雰囲気が感じられる,教育的配慮の行き届いた教科書になっている。
今回の第2版では,「第1巻:オートマトンと言語の理論」,「第2巻:計算可能性の理論」,「第3巻:複雑さの理論」の全3巻に分冊化した.また,初版の内容に「選ばれた問題」に対する解答を追加するとともに,いくつかの話題に関して,初版後の研究の進展について説明を加えた。
著者について
0.序 論
0.1 オートマトン,計算可能性,複雑さ
複雑さの理論
計算可能性の理論
オートマトン理論
0.2 数学的概念や用語
集合
列と組
関数と関係
グラフ
文字列と言語
Boole理論
数学的な語句の要約
0.3 定義,定理,証明
証明の発見
0.4 証明のタイプ
構成的証明
背理論
帰納法
演習,問題,解答
1.正規言語
1.1 有限オートマトン
有限オートマトンの正式な定義
有限オートマトンの例
計算の正式な定義
有限オートマトンの設計
正規演算
1.2 非決定性
非決定性有限オートマトンの正式な定義
NFAとDFAの等価性
正規演算の閉包性
1.3 正規表現
正規表現の正式な定義
有限オートマトンとの等価性
1.4 非正規言語
正規言語に対するポンピング補題
演習,問題,解答
2.文脈自由言語
2.1 文脈自由文法
文脈自由文法の正式な定義
文脈自由文法の例
文脈自由文法の設計
曖昧さ
Chomsky標準形
2.2 プッシュダウン・オートマトン
プッシュダウン・オートマトンの正式な定義
プッシュダウン・オートマトンの例
文脈自由文法との等価性
2.3 非文脈自由言語
文脈自由言語に対するポンピング補題
演習,問題,解答
0.1 オートマトン,計算可能性,複雑さ
複雑さの理論
計算可能性の理論
オートマトン理論
0.2 数学的概念や用語
集合
列と組
関数と関係
グラフ
文字列と言語
Boole理論
数学的な語句の要約
0.3 定義,定理,証明
証明の発見
0.4 証明のタイプ
構成的証明
背理論
帰納法
演習,問題,解答
1.正規言語
1.1 有限オートマトン
有限オートマトンの正式な定義
有限オートマトンの例
計算の正式な定義
有限オートマトンの設計
正規演算
1.2 非決定性
非決定性有限オートマトンの正式な定義
NFAとDFAの等価性
正規演算の閉包性
1.3 正規表現
正規表現の正式な定義
有限オートマトンとの等価性
1.4 非正規言語
正規言語に対するポンピング補題
演習,問題,解答
2.文脈自由言語
2.1 文脈自由文法
文脈自由文法の正式な定義
文脈自由文法の例
文脈自由文法の設計
曖昧さ
Chomsky標準形
2.2 プッシュダウン・オートマトン
プッシュダウン・オートマトンの正式な定義
プッシュダウン・オートマトンの例
文脈自由文法との等価性
2.3 非文脈自由言語
文脈自由言語に対するポンピング補題
演習,問題,解答
登録情報
|
この商品を見た後に買っているのは？
カスタマーレビュー
最も参考になったカスタマーレビュー
1 人中、1人の方が、｢このレビューが参考になった｣と投票しています。
形式:単行本
自分の専攻は物理で情報ではなく、
他の類書を読み通したわけでもないが、
理系教科書の中でも、
書かれているアイデアの高度さと、
その記述の易しさの幅は、
この本がかつて読んだ中では最高のものである。
情報・計算の分野の人の方が、
こういったアイデアの記述には一日の長でもあるのだろうか？
とにかく、目的と論理が（口語的であるにもかかわらず）明確で、
定理の証明の前にある「証明のアイデア」は特に素晴らしい。
内容は、
一巻：DFA（有限決定オートマトン）,NFA（非決定〃）,PDA（プッシュダウン）,REX（正規表現）,CFL（文脈自由言語）の解説と等価性、
二巻：チューリング機械
で、どれもこれも、 不思議と曖昧さ無く話が進み、
大変な知的興奮を味わえる。
内容も面白いのだが、それ以上にこのスタイルが圧倒的に素晴らしい。
他の類書を読み通したわけでもないが、
理系教科書の中でも、
書かれているアイデアの高度さと、
その記述の易しさの幅は、
この本がかつて読んだ中では最高のものである。
情報・計算の分野の人の方が、
こういったアイデアの記述には一日の長でもあるのだろうか？
とにかく、目的と論理が（口語的であるにもかかわらず）明確で、
定理の証明の前にある「証明のアイデア」は特に素晴らしい。
内容は、
一巻：DFA（有限決定オートマトン）,NFA（非決定〃）,PDA（プッシュダウン）,REX（正規表現）,CFL（文脈自由言語）の解説と等価性、
二巻：チューリング機械
で、どれもこれも、 不思議と曖昧さ無く話が進み、
大変な知的興奮を味わえる。
内容も面白いのだが、それ以上にこのスタイルが圧倒的に素晴らしい。
リストマニア
|
|
同じキーワードの商品を探す
フィードバック
- カタログ情報、または画像について報告
- 著者からのコメント
- 出版社からのコメント
|
