積み本になってたBeautiful Codeを何章か読んだ。
泣ける。地元本屋のくだらない本は焚書してほしい。
（毎週エクセルの特集をしてる雑誌とクオリティに差がない）
燃やしちまえ…！そんなもんは…！！（気分は泣きながら語るカイジ）
2009年2月26日木曜日
Beautiful Code
2009年2月23日月曜日
計算機プログラムの構造と解釈 問題1.15
問題1.15
(ラジアンで表す）角度の正弦は、xが十分に小さいとき、
を使って計算できる。
あー、つまり、入力した角度を計算式を用いて、極限まで小さくして、xがsin(x)とほぼ同値になったら、xをsin(x)とみなして、復元してやるのね。
- a.(sine 12.15)の評価で、手続きpは何回作用されられたか。
gosh> (use slib)
#<undef>
gosh> (require 'trace)
#t
gosh> (define (cube x) (* x x x))
cube
gosh> (define (p x) (- (* 3 x) (* 4 (cube x))))
p
gosh> (define (sine angle)
(if (not (> (abs angle) 0.1))
angle
(p (sine (/ angle 3.0)))))
sine
gosh> (trace sine)
#<closure (debug:trace-procedure debug:trace-procedure)>
gosh> (sine 12.15)
CALL sine 12.15
CALL sine 4.05
CALL sine 1.3499999999999999
CALL sine 0.44999999999999996
CALL sine 0.15
RETN sine 0.1495
RETN sine 0.4351345505
RETN sine 0.9758465331678772
RETN sine -0.7895631144708228
RETN sine -0.39980345741334
-0.39980345741334
pは5回作用させられる。
ただtraceのCALLがよくわからない。
なんでCALLがsine 0.15で止まってるんだ？もう１回sineが呼ばれてないとおかしくない？
- b.(sine a)の評価で、手続きsineの生成するプロセスが使うスペースとステップ数の増加の程度は(aの関数として)何か。
定数1/10を省略
定数を省略
スペースは
ステップ数は呼び出した数だけリターンするのでスペースの2倍になるが、
定数倍は無視するので同じく
2009年2月22日日曜日
計算機プログラムの構造と解釈 1.2.3
時間計算量と領域計算量
よく使うオーダー
なので一般的に計算量といえば時間計算量のことを指す。
領域計算量はメモリやステップ数、スペースの増加の程度のこと。
シータ
領域計算量
十分大きなnの値に対し、
R(n)=
fibonacciでは
オーダーと同じく、大体の計算量しか計算しない。
3n^2+10n+17ステップが必要なプロセスもすべて
計算機プログラムの構造と解釈 問題1.12 問題1.13
問題1.12
次のパターンをPascal三角形という
三角形の辺上のすべて１で、内部の数は、その上の２つの数の話である。
再帰的プロセスでこれらの要素を計算する手続きを書け。
(define (pascal_tri r c)
(cond ((= c 0) 1)
((= r c) 1)
(else (+ (pascal_tri(- r 1)(- c 1))
(pascal_tri(- r 1) c )))))
おまけ
n行目が(x+y)^nの展開の項の係数になっている。
問題１.13
フィボナッチの説明の時に証明済み。
2009年2月15日日曜日
超「超」整理法
amazon:超「超」整理法
読みながらメモ。
小手先ではなく考え方が大事。
初めは秩序よくならんでいても、書類が増えるほど、その秩序を維持するコストが増大する。とくにコウモリ問題とか。自動的に秩序が成り立つ仕組みを考えるべき。
紙媒体なら、使ったら、手前にしまう押し出し方式で。
Gmailは便利。オンラインストレージとしても便利。
ただスレッド機能はいただけない。これのせいでメールの時系列が崩れる。
最初のinput（走りメモ書き）と最後のoutput（本にする）は紙で。中間はPCが効率的
自分の専門意外は適当にやろう。今または自分が死ぬまでに機械ができそうなことはしない
Gmail博士になるのでなければ、ある機能をすべて使おうとするのは時間の無駄。
複数のラベル（タグ）づけは紙にだってできる。固定観念をすてよ。
フォルダ(分類)分けは自由な発想を妨げる。工学部卒が経済の教授でもいいじゃないか。
白鳥を鳥だとしか認識しないひとに、白鳥の湖はぜったいに作れなかった。白鳥が人に恋をするのだから。
タグづけが重要だから、名前の付け方が超重要。
索引がついてる本はおすすめ。なぜなら、索引は本が書き上がってからしか作ることができないので、締切りであっぷあっぷしてる状態で、なくてもいい上に面倒な索引をつけているのは「相当気合の入った本」だから。
知識の代わりに必要になったのは、ウェブでは得られないもの。
問題設定、仮説の構築、モデルの活用。
仮説とは否定するための命題である。無帰仮説と呼ばれる。
理論とは棄却されなかった仮説の体系である。だから新たな理論体系がでてくれば棄却される。
モデルとは単純化。最たるものは、摩擦の存在しない古典物理学の世界。
このおかげで物理は進化した。
一貫性を示すためにはモデルが必要。モデルなしにデータだけを集めることを「理論なき計測」という。典型は、データを回帰式にあてはめて分析すること。
何か異常なものがあるのは誰でもわかるが、本来あるべきものがないこと、はモデルが必要。例えば、誕生日表に59人の誕生日が記されていて、誕生日が同じ日の人がいないのは、確率的に考えておかしい。よって偽造されたもの。
大企業にいるメリットがなくなってきている。
大企業のメリットには「知的奴隷」を使えることが一つ。整理法などなくても、「おい、例の書類」だけでよい。しかし、いまは検索ができる。
年功序列は年金と同じで、少子化の今、若い人はババを掴まされる可能性が高い。
2009年2月9日月曜日
計算機プログラムの構造と解釈 1.2.2
復習
この節にでてくるfibonacci数や黄金比の性質やそれらの証明はすでに説明した。
fibonacci数列
黄金比
木構造再帰(tree recursion)
Fibonacci数を例にとってみる。
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
このコードは再帰的プロセスである。
(fib 5)を計算するには(fib 4)(fib 3)を計算する必要があり、その(fib 4)と(fib 3)もまた同様である。
最終的には(fib 1)と(fib 0)の計算となるが、これらの計算回数（ステップ数ではない。ステップ数は節の数に比例する）は、F(n)のときF(n+1)回となる。
これは数学的帰納法を用いれば証明できる。
またF(n)は
F(n)の値は指数的に増加することがわかる。
そして木構造再帰のステップ数は指数的に増加する。ステップ数は節の数に比例する。
必要なスペースは、計算中のノードの深さを知っていればよいので、入力に対して線形にしか増えない。必要なスペースは木構造の最大の深さに比例する。
fibonacci数列の反復的プロセス
変数a,bをa=F(1)=1,b=F(0)=0で初期化して、
a = a+b
b = a
としてn回繰り返すと、a=F(n+1),b=F(n)となっている。
ステップ数はnに線形に増加している。線形反復プロセスである。
(define (fib n)
(fib-iter 1 0 n))
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
木構造再帰のメリット
その１
直感的にコードを記述できること。
反復的プロセスを生成する反復的アルゴリズムを作り出すのは難しい。
木構造を生成してから、メモ化などによって工夫を凝らしていくことで改善。
アルコリズムは直感的で解りやすいし、速いし、で良いとこ取りを狙う。
その２
階層構造のデータを扱うプロセスを考えるときに強力な手法。
解釈系自身は式を木構造再帰的プロセスを使って評価している。
両替問題
※ぶっちゃけ、この両替問題の意図がわからない。何を学習させようとしているの？？
本の例題は「１ドルを50,25,10,5,1セントで両替する場合の数は？」だが、
ここでは問題を簡単にするために、10セントを5,1セントで両替する問題にする。
両替対象の金額をa,両替する硬貨の種類をnとすると、a=10,n=2である。
このときの両替の場合の数は、
「5セントを使わないで両替した場合の数+5セントを使って両替した場合の数」
となることは明白である。
このとき、後者には工夫の余地がある。
10セントを「必ず５セントを使って」5セントと１セントで両替するときの場合の数は、
(10-5=)5セントを5セントと1セントで両替するときの場合の数と等しい。
つまり、
(a=10,n=2)は(a=5,n=2)と(a=10,n=1)に分けられる。
少ない金額の問題に再帰的に縮小させることができる。
具体的には次の規程が必要となる。
- aが0なら、両替の場合の数は1:割り切れたから両替可能
- aが0より少なければ両替の場合の数は0 : 割りきれてない
- nが0なら、両替の場合の数は0 : 0種類だから当然、終了条件になる
(define (count-change amount)
(cc amount 2))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))
define( (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)))
これはかなり冗長な木構造再帰的プロセスを生成する。
しかしより良い明白なアルゴリズムはない。
2009年2月8日日曜日
計算機プログラムの構造と解釈 問題1.11
n<3に対してf(n)=n,n>=3に対して、f(n)=f(n-1)+2f(n-2)+3f(n-3)なる規則で定義できる関数fがある。これを再帰的プロセス、反復的プロセスの方法で手続きを書け。
;再帰的プロセス
(define (xfib-rec n)
(cond ((< n 3) n)
(else (+ (xfib-rec (- n 1))
(* 2 (xfib-rec (- n 2)))
(* 3 (xfib-rec (- n 3)))))))
;反復的プロセス
(define (xfib-iter n)
(define (iter a b c count)
(cond ((< n 3) n)
((= count 2) a)
(else (iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))
(iter 2 1 0 n))
再帰的プロセスは驚くほど直感的にかけた。数式そのまま。
逆に反復的プロセスは木構造を一部書いてみてから、コードを書いた。
タイムインターメディアに答えが載ってるので参考にしてるんですが、反復的プロセスのコードがあんま良ろしくないような…
(define (f-iter n)
(define (iter a b c count)
(cond ((= count 0) c);負の数に対応していない
((= count 1) b);((= count 2) a)で良いのでは？？
(else (iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))
(iter 2 1 0 n))
計算機プログラムの構造と解釈 1.2
1.2 手続きと,その手続きによって生成されるプロセス
再帰的手続き、再帰的プロセス、反復的プロセスについて学ぶ。
※再帰的手続きだから再帰的プロセスとなるのではない。
1.2.1 線形再帰と反復
線形再帰プロセスを生成する手続き
(define (factorial n )
(if (= n 1)
1
(* n (factorial (- n 1)))))
これを置き換えモデルにすると
線形再帰プロセス
(factorial 4)
(* 4 (factorial 3))
(* 4 (* 3 (factorial 2)))
(* 4 (* 3 (* 2 (factorial 1))))
(* 4 (* 3 (* 2 1)))
(* 4 (* 3 2))
(* 4 6)
24
プロセスの形が横に伸びて(膨張)してから、縮小していっている。
これは遅延演算(deferred operations)の列を作るときに起こる。
下方向の流れがステップ数、横が覚えていなければならない演算の列の長さ。
ステップ数はnに線形。
この場合、列の長さもnに線形である。記憶しなればならない列の長さも線形に成長する場合、
線形再帰的プロセス(linear recursive process)という。
反復的プロセスを生成する手続き
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))
反復的プロセス
(factorial 4)
(iter 1 1)
(iter 1 2)
(iter 2 3)
(iter 6 4)
(iter 24 5)
24
このプロセスは横に膨張しない。
各ステップで覚えておく必要があるのは product,counterだけである。
一定数のレジスタだけ用意すればよいのでハードウェアと相性がいい。
必要なステップ数がnに線形に成長する場合、線形反復的プロセスと呼ぶ。
※注意
再帰プロセス + 遅延演算列が線形 = 線形再帰プロセス
反復プロセス + ステップ数が線形 = 線形反復プロセス
C言語の再帰手続きで反復的プロセスは不可能
設計上無理。原理的には反復的であっても、列が成長するように設計されている。
反復的プロセスは、do,while,until,for,whileのような特殊目的の
「ループ構造」を必要とする。
与太話
lisp:ループだせぇw
C：ループ使わないで何でもかんでも再帰とかマジキチ
らしい。
再帰的手続きで反復的プロセスができる性質をもつ実装を末尾再帰的という。
これは後の3章で学習する。
計算機プログラムの構造と解釈 1.1.8
手続き抽象
ある手続きの中で部品として使われている手続き。squareは2乗さえ返してくれれば、手続きの内容は関係ない。ブラックボックス。
局所名
スコープとか、そのあたりの話。説明不要。
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
guess,xは束縛変数(bound variable)といい手続き定義は仮パラメタを束縛する(bind)という。
- ,-,absは自由変数だが、good-enough?の仮パラメタにすると、束縛されてしまう。
(define (good-enough? abs x)
(< (abs (- (square guess) x)) 0.001))
フィボナッチ数列
フィボナッチ数列の定義
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …
近似式
なので、これは四捨五入
近似式の証明
まずはこれを証明する。
３項漸化式
これを、
とおく。特性方程式の解から逆に漸化式を作成すると、
(1)、(2)はそれぞれ
初項
初項
なので、
が得られる。
(3)(4)の差をとると、
ここで、
よって任意のnに対して次式が成り立つ
ここで 
n < 1 のとき 
よって
数学的帰納法だと
の証明は数学的帰納法だと、
よって任意のnに対して次式が成り立つ
フィボナッチ数列の隣り合う 2 項の比は黄金比に収束する
黄金比の説明のときに残しておいた宿題。
黄金比の値は、二次方程式 x2 = x + 1 の正の解なので、これで証明終了
登録:
投稿 (Atom)