出版社内容情報
ゲーデル、チャーチ、チューリングの偉業を踏まえつつ、計算理論をわかりやすくかつ厳密に説明する教科書!
コンピュータサイエンスの「基本中の基本」である計算理論について、理論だけの難しい話に終始せずに、実際のプログラム(書籍ではPythonを使用。WebではJavaも用意)を示し、実践的なアプローチからも理解を促します。扱うトピックは、チューリングマシン、有限オートマトン、計算可能性問題、非決定性、NP完全問題など、計算理論の教科書としては定番とも言えるものですが、コンピュータサイエンスの根幹を支える理論だけでなく、その歴史的発展と意義についても理解することができます。
内容説明
プログラミングを通して手を動かしながら学ぶ計算理論の美しく深遠な概念。
目次
全体像(はじめに:計算できるもの、できないものとは)
第1部 計算可能性理論(コンピュータプログラムとは何か;不可能なPythonプログラム;計算問題とは何か ほか)
第2部 計算量理論(計算量理論:効率が重視されるとき;クラスPolyとクラスExpo:もっとも根本的な2つの計算量クラス;クラスPolyCheckとクラスNPoly:簡単に検証できる難しい問題 ほか)
第3部 起源と応用(もともとのチューリングマシン;正しいことをすべて証明できるとは限らない;カープの21個の問題 ほか)
著者等紹介
マコーミック,ジョン[マコーミック,ジョン] [MacCormick,John]
ペンシルバニア州にあるディッキンソン大学のコンピュータサイエンスの准教授。コンピュータサイエンス分野の先進的な教育者であり、研究者、作家。オックスフォード大学でコンピュータビジョンの博士号を取得。Hewlett‐PackardならびにMicrosoftの研究所勤務の経験がある
松崎公紀[マツザキキミノリ]
東京大学工学部卒、同大学院博士課程中退。東京大学助手、助教、高知工科大学准教授を経て、2018年より高知工科大学教授。博士(情報理工学)。数理的手法によるプログラミング技法(特に並列プログラミングに対する応用)、および、深層学習によるゲームプログラミングについて研究している
長尾高弘[ナガオタカヒロ]
1960年生まれ、東京大学教育学部卒、(株)ロングテール社長、技術翻訳者(本データはこの書籍が刊行された当時に掲載されていたものです)
※書籍に掲載されている著者及び編者、訳者、監修者、イラストレーターなどの紹介情報です。