計算できるもの、計算できないもの

実践的アプローチによる計算理論入門
ＷＨＡＴ　ＣＡＮ　ＢＥ　ＣＯＭＰＵＴＥＤ？

オライリー・ジャパン オーム社
ジョン・マコーミック　松崎公紀　長尾高弘　

• 価格: 5,060円（本体4,600円＋税）
• 発行年月: 2020年12月
• 判型: Ｂ５
• ISBN: 9784873119335

内容情報

[BOOKデータベースより]

プログラミングを通して手を動かしながら学ぶ計算理論の美しく深遠な概念。

全体像（はじめに：計算できるもの、できないものとは）
第１部　計算可能性理論（コンピュータプログラムとは何か；不可能なＰｙｔｈｏｎプログラム；計算問題とは何か　ほか）
第２部　計算量理論（計算量理論：効率が重視されるとき；クラスＰｏｌｙとクラスＥｘｐｏ：もっとも根本的な２つの計算量クラス；クラスＰｏｌｙＣｈｅｃｋとクラスＮＰｏｌｙ：簡単に検証できる難しい問題　ほか）
第３部　起源と応用（もともとのチューリングマシン；正しいことをすべて証明できるとは限らない；カープの２１個の問題　ほか）

[日販商品データベースより]

ゲーデル、チャーチ、チューリングの偉業を踏まえつつ、計算理論をわかりやすくかつ厳密に説明する教科書！
コンピュータサイエンスの「基本中の基本」である計算理論について、理論だけの難しい話に終始せずに、実際のプログラム（書籍ではPythonを使用。WebではJavaも用意）を示し、実践的なアプローチからも理解を促します。扱うトピックは、チューリングマシン、有限オートマトン、計算可能性問題、非決定性、NP完全問題など、計算理論の教科書としては定番とも言えるものですが、コンピュータサイエンスの根幹を支える理論だけでなく、その歴史的発展と意義についても理解することができます。