情報
アルゴリズムシリーズ 第3巻
計算可能性・計算の複雑さ入門
ひとくちに“手に負えない問題”といっても、計算可能性の理論と計算の複雑さの理論では、困難さのレベルが異なる。
計算可能性の理論では、「計算できるか?」 を考えているので、手に負えない=計算不可能、つまり、それを解くプログラムがない場合を意味する。一方、計算の複雑さの理論では「どの程度の計算コストで計算できるか?」がテーマとなるので、手に負えない=まともなコストでは計算不可能と解釈される。
本書では、この2種類の困難さの意味を明らかにし、いろいろな問題の難しさの解明をする。
紙の書籍¥2,640定価(税込)
基本情報
発売日 | 1992年1月1日 |
---|---|
本体価格 | 2,400円 |
ページ数 | 230 ページ ※印刷物 |
サイズ | A5 |
ISBN | 9784764902008 |
ジャンル | 情報 |
タグ | アルゴリズム, 教科書 |
電子書籍形式 | 販売なし |
主要目次
1. 問題とアルゴリズム
2. 計算可能性入門
3. 計算可能性の分析
4. 計算の複雑さ入門
5. 代表的な計算量クラス
6. 多項式時間計算可能性の分析
参考文献
練習問題解答
2. 計算可能性入門
3. 計算可能性の分析
4. 計算の複雑さ入門
5. 代表的な計算量クラス
6. 多項式時間計算可能性の分析
参考文献
練習問題解答