読者です 読者をやめる 読者になる 読者になる

by shigemk2

当面は技術的なことしか書かない

SICP(計算機プログラムの構造と解釈 第二版)を読む会 #yomukai

勉強会

概要

yomukai.connpass.com

Slackで

前回

www.shigemk2.com

今回

http://sicp.iijlab.net/fulltext/x121.html

1.2.1 線形再帰と反復

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

往路と復路の線形再帰的プロセス。

f:id:shigemk2:20150602221313p:plain

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

展開の線形反復的プロセス。(末尾再帰)

f:id:shigemk2:20150602221437p:plain

1.2.2 木構造再帰

フィボナッチが代表例。

f:id:shigemk2:20150602221747p:plain

f:id:shigemk2:20150602221919p:plain

同じ結果を計算するより効率的な手続きに変換する「スマート翻訳系」

1.2.3 増加の程度

プロセスが入力が大きくなるにつれて必要とする資源を, 粗く見積る 増加の程度(order of growth)

計算量の例のアレ。

1.2.4 べき乗

普通の再帰。

(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))

末尾再帰。

(define (expt b n)
  (expt-iter b n 1))

(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                (- counter 1)
                (* b product)))) 

1.2.5 最大公約数

最大公約数(GCD)

  • GCDの計算法はEuclidのアルゴリズムが使える
  • Euclidのアルゴリズムの手続き
  • Euclidのアルゴリズムが必要とするステップ数が、対数的に増加するという事実は、Fibonacci数と面白い関係にある
(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

remainderは余りを求める関数。 https://www.shido.info/lisp/scheme2.html

1.2.6 例: 素数性のテスト

(define (smallest-divisor n)
  (find-divisor n 2))


(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))


(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n)
  (= n (smallest-divisor n)))
(prime? 1409)
  • 確率的アルゴリズム エラーの機会が任意に小さくなることの証明出来るテスト

http://sicp.iijlab.net/fulltext/x126.html

計算機プログラムの構造と解釈[第2版]

計算機プログラムの構造と解釈[第2版]

  • 作者: ハロルドエイブルソン,ジュリーサスマン,ジェラルド・ジェイサスマン,Harold Abelson,Julie Sussman,Gerald Jay Sussman,和田英一
  • 出版社/メーカー: 翔泳社
  • 発売日: 2014/05/17
  • メディア: 大型本
  • この商品を含むブログ (2件) を見る