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