内容説明
人間が計算（アルゴリズム）というものについて理論的にきちんと考え始めたのは、１９３０年代のことである。１９６０年代に入り、形式言語・オートマトン理論・プログラム理論などコンピュータにまつわる新しい理論が誕生し、計算量理論は多くの有能な研究者達によって発展を続けている。本書は、計算のモデルとして最もすぐれているチューリングマシンを中心に、コンピュータの進歩と歩調を合わせ進展している「アルゴリズム情報理論」を歴史的背景とともに解説した斬新なテキストである。
目次
第１章 準備
第２章 チューリングマシン
第３章 計算量のクラスと基本定理
第４章 計算量のクラスの階層
第５章 還元可能性と完全問題
第６章 並列計算
第７章 確率性アルゴリズムと近似計算
感想・レビュー
※以下の感想・レビューは、株式会社ブックウォーカーの提供する「読書メーター」によるものです。
l
0
タイトル通り、チューリングマシンから計算量に関する概念を考える。良書2008/01/24
