猫型エンジニアのブログ

プログラム/ネットワーク系の技術関連をまとめたページです 

SICP

2.1

データによる抽象の構造 2章では「手続き」を組み合わせて「合成手続き」を構築したように、「データ」を組み合わせて「合成データ」を構築する(例 「整数」というデータを組み合わせて、「有理数」を構築する)。注意: 抽象という単語が本文で繰り返されて…

問題1.27〜問題1.29

問題1.27 カールマイケル数はフェルマーテストはパスしますが合成数になりました。 (define (carmichael-test n) (fermat-chrmichael-test n (- n 1))) (define (fermat-chrmichael-test n m) (cond ((= m 0) true) ((= (expmod m n n) m)(fermat-chrmichael…

問題1.21~問題1.23

問題1.21 > (smallest-divisor 199) 199 > (smallest-divisor 1999) 1999 > (smallest-divisor 19999) 7 問題1.22 (define (search-for-primes n m) (cond ((< m n)(newline) 'done) ((timed-prime-test n)(search-for-primes (+ n 1) m)) (else (search-for…

1.2.4~1.2.6

1.2.4 べき乗 べき乗を計算する手続きにおいて、各手続きのステップ数およびスペースの増加に関して4通りが紹介されている。・線形再帰 ステップ・スペースともにO(n) ・線形反復的 ステップはO(n)、スペースはO(1) ・対数的再帰 ステップはO(log n)、スペー…

問題1.18~問題1.20

問題1.18 (define (double x) (+ x x)) (define (halve x) (cond ((even? x) (/ x 2)) (else 0))) (define (even? x) (= (remainder x 2) 0)) (define (new-times a b ) (times-iter a b b 0)) (define (times-iter a b counter product) (cond ((= counter …

問題1.9~問題1.15

問題1.9 以下のように前者の式は再帰的プロセスであり、後者の式は反復的プロセスとなる。 この場合も再帰的な手続きのプロセスが、再帰的とは限らない例である。 (+ 4 5) (inc (+ 3 5)) (inc (inc (+ 2 5))) (inc (inc (inc (+ 1 5)))) (inc (inc (inc (inc…

1.2.1~1.2.3

1.2.1 線形再帰と反復 階上計算を行う2つの手続きが紹介されている。 ・線形再帰的プロセス:計算に遅延演算の列を使用するプロセス ・線形反復的プロセス:計算にプロセスを完全に記述する状態変数を使用プロセス 手続きとプロセスは明確に異なる。ここで紹…

問題1.6~問題1.8

問題1.6 (if ⟨predicate⟩ ⟨consequent⟩ ⟨alternative⟩)において、predicateが真ならばconsequentを評価し、predicateが偽ならばalternativeを評価する。 つまり、consequentとalternativeは必ずどちらか片方しか評価されない。しかしnew-ifの場合、consequen…

1.1.7~1.1.8

1.1.7 例:Newton法による平方根 数学の平方根の関数:平方根の定義を与える。(ありようの記述) 計算機科学の平方根の手続き:平方根の計算方法を与える。(なし方の記述) 数学では通常平叙文的(対象が何か)であり、計算機科学では通常命令文的(対象を…

問題1.1〜問題1.5

問題1.1 略 問題1.2 略 問題1.3 > (define (problem1-3 a b c) (cond ((and (>= b a) (>= c a)) (+ (* b b) (* c c))) ((and (>= a b) (>= c b)) (+ (* a a) (* c c))) ((and (>= a c) (>= b c)) (+ (* a a) (* b b))))) > (problem1-3 1 3 5) 34 > (problem…

1.1.4~1.1.6

1.1.4 合成手続き defineにより合成手続きに名前を付けることができる(前回は数や演算結果に名前を付けていた)。 一度defineで定義された場合、ユーザ定義の合成手続きと、解釈系にあらかじめ備わっている基本演算子の区別はつかない。合成手続きのbodyに…

SICP 勉強メモの目次

コンピュータ関係の書籍の中では、著名な計算機プログラムの構造と解釈を読み進めていきます。昔は書籍版しかなかったのですが、今ではWebで公開されていてとても助かります。 昔院生の時に読みましたが、挫折したもののリベンジです。大学院から情報系に進…

1.1.1 ~ 1.1.3

1 手続きによる抽象の構築 抽象化は、一般的に計算機科学においては対象に関する詳細を捨象すること(Wikipedia) 1.1 プログラムの要素 抽象化:合成物に名前をつけ、単一のものとして扱う。 例: 一番単純な抽象化は、defineを用いて、名前と数の対応付け…

MacBook AirにSICPの環境構築

MacでもSICPの勉強をしたいので、環境構築の仕方についてまとめました。 DrRacketのダウンロード ここからDrRacketをダウンロードしてきます。以前はDrSchemeだったのに変わってしまったのですね。SICP用の環境設定がうまくいきません。どうしたらいいんだろ…