３．多項式計算アルゴリズム

内容

1. スライド　1 ３．多項式計算アルゴリズム
2. スライド　2 ３−１：べき乗問題
3. スライド　3 素朴なべき乗の求め方
4. スライド　4 アルゴリズムnaive_pow(x,n) 入力：x,n 出力：xのｎ乗
5. スライド　5 アルゴリズムnaive_powの正当性。 （ほとんど明らかだが、証明することも...
6. スライド　6 アルゴリズムnaive_powの時間計算量
7. スライド　7 数学の記号とプログラム
8. スライド　8 高速なべき乗の求め方。
9. スライド　9 アルゴリズムfast_pow(x,n) 入力：x,n（ただし、　　　　　　　）...
10. スライド　10 命題ＦＰ１（fast_powの正当性）
11. スライド　11 帰納：
12. スライド　12 fast_powの時間計算量
13. スライド　13 一般の自然数に対する高速なべき乗アルゴリズム
14. スライド　14 このとき、　　　　　は次のように表せる。
15. スライド　15 アルゴリズムgeneral_fast_pow(x,n) 入力：x,n(ｎは一般...
16. スライド　16 ３−２：多項式の計算
17. スライド　17 素朴な多項式の求め方
18. スライド　18 アルゴリズムnaive_poly() 入力：x,次数n,係数a[n] 出力：
19. スライド　19 素朴な多項式計算アルゴリズムの正当性
20. スライド　20 証明
21. スライド　21 命題ＮＰ２（naive_polyの正当性２）
22. スライド　22 とする。
23. スライド　23 素朴な多項式計算アルゴリズムの計算時間
24. スライド　24 以上から、naive_polyの最悪時間計算量は、 であることがわかる...
25. スライド　25 補足：べき乗に高速なアルゴリズムを用いた場合
26. スライド　26 ホーナーの方法
27. スライド　27 アルゴリズムを示すまえに、等式の正当性を証明する。
28. スライド　28 このとき、各関数は次のような系列になる。
29. スライド　29 基礎
30. スライド　30 このとき、
31. スライド　31 ホーナーの方法の計算手順
32. スライド　32 アルゴリズムhorner_poly() 入力：x,次数n,係数a[n] 出力...
33. スライド　33 ホーナーの方法の計算時間
34. スライド　34 これより、
35. スライド　35 ホーナーの方法の繰り返し版