社内SICP勉強会(第3回) - 元データ分析の会社で働いていた人の四方山話

第２回の話題

浮動小数点の話題は、最近セキュリティがらみでありましたね。
- PHPの浮動小数点処理に無限ループのバグ | スラッシュドット・ジャパンオープンソース
- 浮動小数点変換バグはJavaにもあった
ここでこの話につながるのかなるほどーと思った。

範囲

1.2(P17)から問題1.13(P23)まで

内容

1.2 手続きとその生成するプロセス
- 手続きは計算プロセスの局所的進化(local evoluation)である。
- 局所的進化を手続きが規定するプロセスの全体としての、大局的(global)振舞について記述出来たらよいと思う
1.2.1 線形再帰と反復
- 階乗の計算
- 手続き作用の置き換えモデル(1.1.5節)で表現
- 再帰的プロセス(recursive process)と反復的プロセス(iterative process)
  - 再帰的プロセスでは、解釈系は後に実行する演算を覚えている必要がある。
    - n!では、nに線形に比例してステップが大きくなる。そのようなプロセスを線形再帰的プロセスという
  - 反復的プロセスでは、状態変数と、状態が変化した時、どう更新するか、終了条件などを覚えているだけでよい。
    - n!では、nに線形に比例してステップが大きくなる。そのようなプロセスを線形反復的プロセスという
- 反復的プロセスは再帰的手続きとして記述してあっても、固定スペースで実行できる。この性質の実装を末尾再帰的(tail recursive)という。
1.2.2 木構造
- 一般に、木構造再帰的プロセスで必要なステップ数は木構造の節の数に比例し、必要なスペースは木構造の最大深さに比例する。
両替の計算
- 問題のメモ

5つの種類の硬貨がある場合、
与えられた金額を満たす両替のパターンが
いくつあるか、という問題
木構造の枝までいくと
・うまく両替できた時：1
・両替できなかった時(合計を越えるor硬貨の種類が足りなくなる)：0
(define (cc amount kinds-of-conins))
のcondのelse節の実装がポイント
左の枝、より大きな硬貨を使うパターンを構築
右の枝、合計金額から現在の硬貨分の額を減ら

- 挑戦問題として、これを反復化せよ、というのがあるが時間があれば挑戦する。（たぶんない）

問題

問題1.9

traceを使うと視覚的に再帰的プロセスと反復的プロセスの違いを確認する事ができる。

(use slib)
(require 'trace)

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

(trace +)
(+ 4 5)
;; (inc (+ (dec 4) 5))
;; (inc (inc (+ (dec 3) 5)))
;; (inc (inc (inc (+ (dec 2) 5))))
;; (inc (inc (inc (inc (+ (dec 1) 5)))))
;; (inc (inc (inc (inc (inc (+ 0) 5)))))
;; (inc (inc (inc (inc 5))))
;; (inc (inc (inc 6)))
;; (inc (inc 7))
;; (inc 8)
;; => 9
;; aが0になるまでdecを繰り返す
;; decを繰り返した回数分incする
;; 膨張と収縮の形となっているので再帰的プロセスである。


(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

(trace +)
(+ 4 5)
;; (+ (dec 4) (inc 5))
;; (+ (dec 3) (inc 6))
;; (+ (dec 2) (inc 7))
;; (+ (dec 1) (inc 8))
;; => 9
;; aをdecすると同時にbをincする。
;; decを繰り返した回数分incされ、
;; aが0になった段階でbが求められている。
;; プロセスが伸び縮みしないので反復的プロセスである。

;; dec, incの実装
(define (dec x)
  (- x 1))

(define (inc x)
  (+ x 1))

(dec 3)
(inc 3)

問題1.10

;; Ackermann関数
;; http://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%83%E3%82%AB%E3%83%BC%E3%83%9E%E3%83%B3%E9%96%A2%E6%95%B0
;; 与える数が大きくなると計算量も爆発的に大きくなるという特徴がある。

(define (A x y)
  (cond [(= y 0) 0]
     [(= x 0) (* 2 y)]
     [(= y 1) 2]
     [else (A (- x 1)
           (A x (- y 1)))]))

(A 1 10)
;; 1024

(A 2 4)
;; 65536

(A 3 3)
;; 65536

;; 以下の数学的定義は？
(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))

;; (f n)
;; => (A 0 n)
;; => (* 2 y)
;; => 2n
(f 2)
(f 6)

;; (g n)
;; => (A 1 n)
;; => (A 0 (A 1 n-1))
;; => (A 0 (A 0 (A 0 n-2)))
;; => (A 0 (A 0 ... (A 0 (A 1 1)))
;; => (A 0 (A 0 ... (* 2 2)
;; => 2^n
(g 2)
(g 3)
(g 4)

;; (h n)
;; => (A 2 n)
;; => (A 1 (A 2 n-1))
;; => (A 1 (A 1 (A 2 n-2)))
;; => (A 1 (A 1 ... (A 1 (A 2 1))))
;; => (A 1 (A 1 ... (A 1 2)))
;; => (A 1 (A 1 ... (A 0 (A 2 1))))
;; => (A 1 (A 1 ... (A 0 2)))
;; => (A 1 (A 1 ... (A 1 (* 2 2)
;; １つの(A 1 2)で(* 2 2)が1つできる
;;  => 2 ^ 2 ^ ... ^ 2

問題1.11

;; n < 3 に対してf(n) = n
;; n >= 3 に対してf(n) = f(n-1) + 2f(n-2) + 3f(n-3)
;; なる規則で定義するf

;; 再帰的プロセスの方法
(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1))
      (* 2 (f (- n 2)))
      (* 3 (f (- n 3))))))

(f 3)
(f 4)
(f 5)
(f 10)

;; 反復的プロセスの方法
(define (f n)
  (f-iter 2 1 0 n))

(define (f-iter a b c count)
  (cond [(= count 0) c]
     [(= count 1) b]
     [(= count 2) a]  ;; ここはなくても同様の答えが得られる
     [else (f-iter (+ a (* 2 b) (* 3 c)) a b (- count 1))]))

問題1.12

;; Pascal三角形
;; 上からn段目、左からk個目の要素を求める

(define (pascal n k)
  (cond [(= n 1) 1] ;; 一番上
     [(= k 1) 1] ;; 左端
     [(= n k) 1] ;; 右端(各段の個数は段数に等しい)
     [(< n k) (print "your input is not invalid")]
     [else (+ (pascal (- n 1) (- k 1))
           (pascal (- n 1) k))]))

問題1.13

この問題はあまりscheme関係ないよね。
こことかを見ればよいのでは。
解法の流れ

まずヒントの証明を行う。
$\|\phi\| < 0.62$ であることを用いると、 $\frac{\|\phi^n\|}{\sqrt{5}} < \frac{0.62}{\sqrt{5}} < 0.5$ と言える。
$fib(n) - \|\frac{\psi^n}{\sqrt{5}}\| < \frac{\phi^n}{\sqrt{5}} < fib(n) + \|\frac{\psi^n}{\sqrt{5}\|$

と証明する。

所感など

再帰的プロセスはそのまま書き下させるけど、反復的処理になると直感的に書く事ができない