11．動的計画法と擬多項式時間アルゴリズム

内容

1. スライド　1 11．動的計画法と擬多項式時間アルゴリズム
2. スライド　2 　これまでは、主に、「問題がいかに難しいか」を理論的に証明する方法について学んで...
3. スライド　3 １１−１．部分和問題（SUBSET SUM Problem)
4. スライド　4 インスタンス例
5. スライド　5 入力サイズ
6. スライド　6 部分和問題の指数時間アルゴリズム
7. スライド　7 したがって、次のようなアルゴリズムが得られる。
8. スライド　8 このアルゴリズムの計算量は、1-3を　　　　　回繰り返しており、 ２．において...
9. スライド　9 部分和問題の擬多項式時間アルゴリズム
10. スライド　10 方針
11. スライド　11 表の概形 （アルゴリズムの基礎にあたる。）
12. スライド　12 要素　　　　に注目した表の更新。
13. スライド　13 要素　　　　に注目した表の更新。
14. スライド　14 要素　　　　に注目した表の更新。
15. スライド　15 要素　　　　に注目した表の更新。
16. スライド　16 以上より、インスタンス
17. スライド　17 練習
18. スライド　18 　ここでは、DP法に基づく、部分問題を解くアルゴリズムの計算量を解析する。
19. スライド　19 　　このこから、各セルを計算するのに必要な計算時間は、 次のようになる。
20. スライド　20 もう一度入力サイズをおもいだすと、入力サイズは、
21. スライド　21 擬多項式時間アルゴリズムの定義
22. スライド　22 １１−２．ナップザック問題（KNAPSACK Problem)
23. スライド　23 KNAPSACKを解く擬多項式時間アルゴリズム
24. スライド　24 インスタンス例
25. スライド　25 方針
26. スライド　26 表の概形 （アルゴリズムの基礎にあたる。）
27. スライド　27 要素　　　に注目した更新
28. スライド　28 要素　　　に注目した更新
29. スライド　29 要素　　　に注目した更新
30. スライド　30 要素　　　に注目した更新
31. スライド　31 要素　　　に注目した更新
32. スライド　32 要素の決定。
33. スライド　33 練習
34. スライド　34 KNAPSACKを解くアルゴリズムの計算量を解析する。
35. スライド　35 RAMモデルでは、各セルの計算は明らかに定数時間で行える。
36. スライド　36 １１−３．Pの問題に対するDP法
37. スライド　37 行列積の演算最適化
38. スライド　38 演算順序による演算数の相違
39. スライド　39 練習
40. スライド　40 　　このように、行列の積の順序によっては、演算回数が 劇的に異なることがある。...
41. スライド　41 このアルゴリズムの計算量を解析しよう。
42. スライド　42 カタラン数は、
43. スライド　43 問題の考察（部分問題の同定）
44. スライド　44 漸化式
45. スライド　45 表
46. スライド　46 例えば、　　　　　　を計算するには、
47. スライド　47 インスタンス例
48. スライド　48 1
49. スライド　49 1
50. スライド　50 1
51. スライド　51 1
52. スライド　52 このアルゴリズムの計算量を解析する。
53. スライド　53 １１−４．再帰アルゴリズムと動的計画法
54. スライド　54 漸化式を基にすると、次のように、直接再帰アルゴリズムが 得られる。
55. スライド　55 再帰アルゴリズムの計算量
56. スライド　56 を帰納法によって示す。
57. スライド　57 部分問題の重複性
58. スライド　58 １１−５．動的計画法の一般的性質