近代科学社

書籍検索
ジャンル選択

情報

アルゴリズムシリーズ 第3巻

計算可能性・計算の複雑さ入門

著者 渡辺 治


ひとくちに“手に負えない問題”といっても、計算可能性の理論と計算の複雑さの理論では、困難さのレベルが異なる。
計算可能性の理論では、「計算できるか?」 を考えているので、手に負えない=計算不可能、つまり、それを解くプログラムがない場合を意味する。一方、計算の複雑さの理論では「どの程度の計算コストで計算できるか?」がテーマとなるので、手に負えない=まともなコストでは計算不可能と解釈される。
本書では、この2種類の困難さの意味を明らかにし、いろいろな問題の難しさの解明をする。

紙の書籍¥2,400定価(税別)

基本情報

発売日 1992年1月1日
ページ数 230 ページ ※印刷物
サイズ A5
ISBN 9784764902008
ジャンル 情報
タグ 計算科学, アルゴリズム

主要目次

1. 問題とアルゴリズム
2. 計算可能性入門
3. 計算可能性の分析
4. 計算の複雑さ入門
5. 代表的な計算量クラス
6. 多項式時間計算可能性の分析
参考文献
練習問題解答

目次をさらに表示する