【レビュー】計算理論の基礎
【PR】この記事には広告を含む場合があります
- 出版情報
- ・著者：Sipser,Michael／著 太田和夫／翻訳 渡辺治／翻訳 阿部正幸／著 シプサマイケル／著
- ・出版日：2000-04
- ・ページ数：483P
- レビュー数
- ・週間：0記事
- ・月間：0記事
- ・年間：0記事
- ・全期間：2記事
ジャンルTop10選
目次
第1部 オートマトンと言語(正規言語
文脈自由文法)
第2部 計算可能性の理論(Church‐Turingの提唱
判定可能性
帰着可能性 ほか)
第3部 複雑さの理論(時間の複雑さ
領域の複雑さ
問題の扱いにくさ ほか)
概要
計算の理論の世界へ、ようこそ!Michael Sipser教授の「Theory of Computation」の講義も、本書と同様に、このフレンドリーな挨拶から始まりました。彼の講義はMIT屈指の名講義で、教室には活気と笑いがあふれていました。2,3回の聴講を考えていた私はその魅力に魅せられて、91年秋学期の全講義に出席することになりました。本書はSipser教授のMITでの講義ノートをもとにまとめられたものです。計算の理論の主テーマである、オートマトンと言語の理論、計算可能性の理論、そして計算の複雑さの理論をカバーしています。
レビューの一覧
・PythonでNFAを実装し、例の曲を判定する[2022-12-10に投稿]
・計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜[2018-05-10に投稿]
