/\A toku_?bass \z/x: 2009

2009年12月8日火曜日

リスニングは文字をみてはいけないと痛感しました。

よく言われることですが、最初は絶対に英文をみてリスニングをしてはいけない。これを身をもって知りました。

TOEICの公式問題集を復習がてらに何回も聞いたのですが、全然聞き取れない部分があって、でも英文をみたらすぐに聞き取れたんですね。なんでこれが聞き取れなかったんだって。

でも次の日聞いたら分からなかったw
英文をみると脳内で自分発音で再生されてるようです。

submitが聞き取れないのはショックでした。
原因はサブミットで「ブ」のところ。母音uなんて存在しないので。日本語英語で覚えてるとほんとヤバいですね・・・・。

あとweren'tが否定に聞こえなかったり、ourがまったく聞き取れないのが悩みです。
フルハウスとか絶望的に聞こえないですよ、ourが。

2009年11月25日水曜日

リスニングむじぃ

字幕なしフルハウスを観てたら、耳が英語になれてたせいか、リスニングで300点超えてた。
ただ悲しいかな、なんとなく聞き取れるようになっただけで、基礎力が上がってるわけではないので、確信をもって答えられる問題はそんなにない。

しばらくリスニング強化のためにシャドウイングしてます。

うちの会社、700点弱で海外勤務可らしい。
最近、海外勤務もええかな、と思ってきたのですよ。
インドは腹くだしそうだけど・・・・タイあたりならいいかな・・・

2009年11月2日月曜日

勉強会に参加

名古屋の勉強会に参加

とりあえず動け動け！ということで2つほど勉強会に参加することにした。
そのうち自分で発表したいところ。つか、そのうちとか言ってたらダメか。
何か発表するネタあるかなぁ・・・。

最近はC言語をやり直しています。自分が組込みをしているというのもありますが、
C言語をちゃんと習得しないで、LLを使うのって後ろめたさがあるので。

intのbit幅を求める

sizeof(int) * CHAR_BITはダメで、
以下のようにビットを一つずつ舐めていく。
http://www.bohyoh.com/CandCPP/FAQ/FAQ00018.html


/*--- unsigned型のビット数を返却 ---*/
int int_bits(void) {
int count = 0;
unsigned x = ~0U;
while (x) {
if (x & 1U) count++;
x >>= 1;
}

return (count);
}

2009年11月1日日曜日

やり直しC

stdio.hがないと怒られた。
そういえば、昨日OSを入れ直したから、libcが入ってないや。
sudo apt-get install libc6-dev

main関数と引数void

int main()とmain()は同じ。関数の型を省略するとint型にされる。
hoge(void)は引数をとらないことを明示してあり、
プロトタイプ宣言にてhoge()とした場合、引数なしではなく、”なんでもよい”ということ。

K&R 演習１

エラーメッセージを調べる

#include <stdio.h>

int main()
{
printf("Hello, World";
}

結果
test.c: In function ‘main’:
test.c:5: error: expected ‘)’ before ‘;’ token
test.c:7: error: expected ‘;’ before ‘}’ token

当然、怒られる。
7行目でのerrorは)がないせいで、;も引数扱いされ、終端としての役割がなくなっているためと考える。

#include <stdio.h>

int main()
{
printf("Hello, World";);
}

結果
test.c:5: error: expected ‘)’ before ‘;’ token

あるぇ？
どうやら；は認識されてる。

ちょっと調べるか

以下、後日編集
'（'　がきた時点で関数であると認識されてました。

メモ
バッカス・ナウア・フォーム　Backus Naur Form
yacc
lex

2009年9月27日日曜日

椅子買った

LM-18という椅子を買いました。
2万円代でハッピーになれる椅子です。

詳しい説明は省きますが、（PC、読書をしながら）リラックスできることが目的で買いました。

また掃除機は自動お掃除ロボ、ルンバ君を買いました。

今のところ、机2万、椅子2万、掃除ロボ3万って感じで、なにやらようやく人並みの生活ができそうな感じです。

彼女からは、贅沢しそうで心配とかいわれてますが、基本僕は贅沢しないです。家具とか、そういうものにはある程度金かけますけど、結局今回も椅子は2万で抑えたわけだし。
生活に必要なものが揃ったら、あとは精神世界で遊びますw
（あー、でも後輩にご飯おごるとかはするけど、食費なんか安いもんですよ。）

2009年7月17日金曜日

引っ越しました

なので、またまたネット環境はそろってません。
寮とちがって家賃が高いですが、満足しています。

仕事はまぁ順調な感じです。
ただ、整理整頓が苦手で、これは絶対に直したほうがよいな、と思うのでがんばります。
計画性は大分改善された気がします。とにかく手帳を書く＆みるようにしています。
はじめは、用事がないときはわざわざ手帳を開くなんてことはしなかったのですが、
「手帳を開く習慣がプライスレス」と考えるようになると、１日に7,8回は手帳をみるようになりました。

あとはアラーム機能さえあれば・・・職場で携帯は気が引けるしなぁ・・・

2009年6月17日水曜日

職場がwindowsなので・・・

エクセルやよくわからないツールの自動化のためにVBSをせっせと作ってます。
ただキー入力を送信したあと、しばらくwaitをかけて、またキー送信というのを繰り返すことしかできないので、waitをかけている間の処理が、思いの外長かったりするとアウトなのが、不便です。
これを解決する方法は、今のところ、少なくともvbsでは無さそうです。

困った。

あと、管理職がプロジェクトをエクセルで管理してるけど、エクセルに使われている気がして仕方がない。ほんとに表形式が一番管理しやすい方法なのだろうか？？

2009年6月7日日曜日

自分の考えを「5分でまとめ」「3分で伝える」

この本は、まとめることの重要さを説いています。
まとめることができれば、伝えることもできる。

まとめるには
1. 型をもつこと。つまりフレームワークってやつですね。

本は部分熟読しろ
1. 一つを熟読したほうが、そこから関連した本に飛んでいくことができるから

※僕はパラシュート型、スパイラル型のほうが、良いと思います。

コーネル式ノートが良い

まとめる力はリーダーの力
1. 様々な人の意見をまとめることで、落としどころを見つけられる
2. 落としどころをみつけたら、次はわかりやすいプランやビジョンで伝える

「お金を稼ぐ！」勉強法

この本が言いたいことは
勉強も大事だけどアウトプットがとても大切なのだという話。

給料のウチいくらかを投資に回す
1. 人脈構築のためなどの、自分の宣伝費を入れる。学習のための本代だけにしない
2. その投資は回収できるものか？
3. 一ヶ月の予算を組んで使い切る

学んでおいたほうがよい一般的なスキル
1. 英語
2. 会計
3. マーケティング

OUTPUTを考えてからINPUTをしろ。
1. OUTPUTには相手がいる

専門家を名乗れ
1. 今はスピードの時代。人より少しだけ優れているだけでいい
2. 知識は後からついてくる
3. 失敗しても、進化できるからいい

本の読み方
1. 本当に必要かどうかを知るために、特定分野の本を読みまくる
2. 本はあくまで叩き台。じっくり読まないで、その分の時間を実践にまわせ

意志に頼るのは止めて習慣づける
1. 習慣付けるならイレギュラーの少ない朝
2. 3日坊主というように、3のつくタイミングは注意。3週間目、3ヶ月目

2009年6月5日金曜日

ハードディスクを整理していたら、こんなものが

　　探し物はバグですか

　　見つけにくいバグですか

　　ソースの中も

　　メモリの中も

　　探したけれど見つからないのに

　　まだまだ探す気ですか

　　それより５時で帰りませんか

　　闇の中へ　闇の中へ

　　葬り去ろうと思いませんか

　　　　U Fu Fu ..（くり返し）

　　　　さーあぁ

　　休む事も許されず

　　正月さえも止められて

　　はいつくばって　はいつくばって

　　いつまでバグを探しているのか

　　出荷を終えたとき

　　見つかる事も良くある話で

　　あきらめましょう

　　闇の中へ

　　葬り去ろうと思いませんか

　　　　U Fu Fu ..（くり返し）

2009年5月30日土曜日

ネットつながったー

最低限の文化的な生活がこれでおくれます（涙

仕事のほうは、まぁ至って順調です。
寮と通勤時間は最低ですが、OJTの先輩は良く教えてくれるし、職場環境は良いです。

毎日Cソースを読んで、特許も読んで、たまに英語のマニュアル読んで、最近はこっそりVBScriptを組んだりしています。

はやく一人前になりたいなー

2009年4月30日木曜日

6月までネットワーク環境がないんです

というわけで、まだまだ更新できそうにありません。

2009年3月12日木曜日

就業規則

労働慣行

就業規則等に盛り込まれていなくてもずっと慣習的に行われてきて、社員みんなが当然行われると認識していることは”労働慣行”となり、制度化されているのと同じ効果が生じます。

これは恐ろしい。
しかし恐怖政治であったり、就業規則とまったく異なることであったりすると認められない。例外中の例外・・・・かな。

日給月給制

あと、日給月給制という言葉を知った。ウチの会社はこれ。
基本的には"決められた日数を働いたら規定の月給を払いますよ"ということ。
なので、"日給をまとめて月末に支払う"方法とは異なる。
しかし前者か後者かはキチンと確かめないと会社が混同している場合がある。

また月給日給制という言葉はない。

言葉の定義が曖昧なのは恐ろしい

いざ就職、転職したときに、言葉の定義が会社側が間違っていたがためにトラブルになるかもしれない。

2009年3月11日水曜日

PCのない生活

ノートPCをもってないので、引越ししたらしばらくPCがない生活を送るかも。

PCは誘惑も多いけど、英語の勉強には必須（発音をすぐ調べられる）なので悩みどころ。会社に自習室ないかな。

2009年3月4日水曜日

これは面白い討論方法だ

僕はディヴェートに関して素人なので、こういう解りやすい手法は面白くて良い。

条件の後付け

マルクスより先に「Capitalism」ないし「Capitalist」という言葉を使った人として英語版wikiで紹介された人の中には「ゾンバルト（Werner Sombart）」なんてどこにも出ないのですが。

と後から条件文を挿入するのだ。これは法廷で「証拠の文書には被告の名前はどこにも出てきません」と主張した弁護士が、検察側に「出ているじゃないか」と指摘されると「被告は犯人としてはどこにも出ないのですが」と言い逃れをするようなものだ。裁判官は「被告の名前は文書に出ている。代理人の最初の弁論は撤回してください」というだろう。

仮定の反転→同意語による証明（らしきもの）

「構造改革」が労働者への労働の成果の配分の現象を生じさせるものであれば，それは家計収入自体の減少をもたらしますから，国内需要が減少するのは当然のことです。（原文ﾏﾏ）

この文章は（誤字を訂正すれば）つねに正しい。トートロジーだからである。したがって、ここから何も意味のある命題を導くことはできない。私が「構造改革で需要は増える」と書いているのに、それとは逆の仮定を置いて何事かを証明したつもりになっている彼が、素人なら何もいう気はない。

構造改革で需要は増える→構造改革で需要は減少
仮定が反転している。その反転した仮定を証明して、反転前の仮定を証明した気になっている。

しかも反転させた仮定の証明もおかしい、と池田先生。
トートロジーとは同語反復。「トートロジーとは、つまりトートロジーのこと」
（収入と需要がトートロジーかどうかは僕には解りません）

2009年3月2日月曜日

英語メモ

掛け橋

"serve as a bridge"は架け橋になる、橋渡しをするという意味。

だけど、問題集にはこうあった。

a temporary position may serve as a bridge to full-time employment.
臨時雇用から正社員になれることもあります。

つまり、A <-> B ではなくて、A -> B という一方通行的なニュアンスでも可ってことですね。

ディフェンス

defenseは防御、弁護などを意味するけれど、正当性の主張の意味もある。
学会での発表で自分の理論を主張するときはdefense。

ex.
defending an argument
論拠の主張

2009年3月1日日曜日

超ひさしぶりにゲーム買った

買ったのはマリオ＆ルイージRPG3
感想としては、おもしろい。
スーファミの初代マリオRPGの面白さには敵わないものの、
うまくDSの機能を使って、工夫してあると思います。
グラフィックも小ネタも中々。
まぁ、超オススメ！ってわけではないですが、安全パイであることは確か。

マリオ系にハズレなし？

2009年2月26日木曜日

Beautiful Code

積み本になってたBeautiful Codeを何章か読んだ。
泣ける。地元本屋のくだらない本は焚書してほしい。
（毎週エクセルの特集をしてる雑誌とクオリティに差がない）
燃やしちまえ…！そんなもんは…！！（気分は泣きながら語るカイジ）

2009年2月23日月曜日

計算機プログラムの構造と解釈　問題1.15

問題1.15

(ラジアンで表す）角度の正弦は、xが十分に小さいとき、 $￥sin(x)￥approx x$ の近似と、正弦の引数の値を小さくするための三角関係式
$￥sin(x)=3￥sin￥frac{x}{3}-4￥sin^3￥frac{x}{3}$
を使って計算できる。

あー、つまり、入力した角度を計算式を用いて、極限まで小さくして、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の関数として)何か。

$a/3^N < 0.1$
$a < 3^N/10$
定数1/10を省略
$a < 3^N$
$N > log_{3} a$
${￥red}N > ￥frac{￥log_{2}a}{￥log_{2}3}$
${￥red}N > ￥frac{1}{￥log_{2}3}*￥log_{2}a$
定数を省略
${￥red}N > ￥log_{2}a$
$0.1 < a/3^N + 1$ のときも同様に考える。

スペースは $￥log (a)$
ステップ数は呼び出した数だけリターンするのでスペースの2倍になるが、
定数倍は無視するので同じく $￥log (a)$

2009年2月22日日曜日

計算機プログラムの構造と解釈　1.2.3

時間計算量と領域計算量

よく使うオーダー $O$ は時間計算量（の増加の程度）のこと。
なので一般的に計算量といえば時間計算量のことを指す。
領域計算量はメモリやステップ数、スペースの増加の程度のこと。
シータ $￥Theta$ と呼ぶ。

領域計算量

十分大きなnの値に対し、
$k_{1}f(n) ￥leq R(n) ￥leq k_{2}f(n)$ なるnと独立な正の定数 $k_{1},k_{2}$ があればR(n)は $￥Theta (f(n))$ の増加の程度だといい、
R(n)= $￥Theta (f(n))$ と書く。

fibonacciでは $￥Theta (n^2)$ のステップ数と、 $￥Theta (n)$ のスペースを必要とする。
オーダーと同じく、大体の計算量しか計算しない。
3n^2+10n+17ステップが必要なプロセスもすべて $￥Theta (n^2)$ の増加の程度という。

計算機プログラムの構造と解釈　問題1.12 問題1.13

問題1.12

次のパターンをPascal三角形という
$￥begin{matrix} &&&&&1￥￥ &&&&1&&1￥￥ &&&1&&2&&1￥￥ &&1&&3&&3&&1￥￥ &1&&4&&6&&4&&1 ￥end{matrix}$
三角形の辺上のすべて１で、内部の数は、その上の２つの数の話である。
再帰的プロセスでこれらの要素を計算する手続きを書け。


(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の展開の項の係数になっている。
$x+y$
$x^2+2xy+y^2$
$x^3+3x^2y+3xy^2+y^3$

問題１.13

$￥phi = (1+sqrt5)/2$ としてFib(n)が $￥phi^n/sqrt5$ に最も近い整数であることを証明せよ。
フィボナッチの説明の時に証明済み。

2009年2月15日日曜日

超「超」整理法

amazon:超「超」整理法
読みながらメモ。

小手先ではなく考え方が大事。
初めは秩序よくならんでいても、書類が増えるほど、その秩序を維持するコストが増大する。とくにコウモリ問題とか。自動的に秩序が成り立つ仕組みを考えるべき。

紙媒体なら、使ったら、手前にしまう押し出し方式で。

Gmailは便利。オンラインストレージとしても便利。
ただスレッド機能はいただけない。これのせいでメールの時系列が崩れる。

最初のinput（走りメモ書き）と最後のoutput（本にする）は紙で。中間はPCが効率的

自分の専門意外は適当にやろう。今または自分が死ぬまでに機械ができそうなことはしない

Gmail博士になるのでなければ、ある機能をすべて使おうとするのは時間の無駄。

複数のラベル（タグ）づけは紙にだってできる。固定観念をすてよ。
フォルダ(分類)分けは自由な発想を妨げる。工学部卒が経済の教授でもいいじゃないか。
白鳥を鳥だとしか認識しないひとに、白鳥の湖はぜったいに作れなかった。白鳥が人に恋をするのだから。

タグづけが重要だから、名前の付け方が超重要。

索引がついてる本はおすすめ。なぜなら、索引は本が書き上がってからしか作ることができないので、締切りであっぷあっぷしてる状態で、なくてもいい上に面倒な索引をつけているのは「相当気合の入った本」だから。

知識の代わりに必要になったのは、ウェブでは得られないもの。
問題設定、仮説の構築、モデルの活用。

仮説とは否定するための命題である。無帰仮説と呼ばれる。
理論とは棄却されなかった仮説の体系である。だから新たな理論体系がでてくれば棄却される。

モデルとは単純化。最たるものは、摩擦の存在しない古典物理学の世界。
このおかげで物理は進化した。
一貫性を示すためにはモデルが必要。モデルなしにデータだけを集めることを「理論なき計測」という。典型は、データを回帰式にあてはめて分析すること。

何か異常なものがあるのは誰でもわかるが、本来あるべきものがないこと、はモデルが必要。例えば、誕生日表に59人の誕生日が記されていて、誕生日が同じ日の人がいないのは、確率的に考えておかしい。よって偽造されたもの。

大企業にいるメリットがなくなってきている。
大企業のメリットには「知的奴隷」を使えることが一つ。整理法などなくても、「おい、例の書類」だけでよい。しかし、いまは検索ができる。
年功序列は年金と同じで、少子化の今、若い人はババを掴まされる可能性が高い。

2009年2月9日月曜日

計算機プログラムの構造と解釈　1.2.2

復習

この節にでてくるfibonacci数や黄金比の性質やそれらの証明はすでに説明した。
fibonacci数列
 黄金比

木構造再帰(tree recursion)

Fibonacci数を例にとってみる。
$F_n = ￥begin{cases} 0 & ￥mbox{if }n = 0￥￥1 & ￥mbox{if }n = 1￥￥F_{n-1}+F_{n-2} & ￥mbox{if }n > 1￥￥￥end{cases}$


(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)は $￥frac{￥phi^n}{sqrt5}$ に最も近い整数であるので、
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))

こんなん見つけたw

どう転んでもLisp

計算機プログラムの構造と解釈　1.2

1.2 手続きと,その手続きによって生成されるプロセス

再帰的手続き、再帰的プロセス、反復的プロセスについて学ぶ。
※再帰的手続きだから再帰的プロセスとなるのではない。

1.2.1 線形再帰と反復

$n!=n￥cdot(n-1)￥cdot(n-2) ￥dots 3 ￥cdot 2 ￥cdot 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))

フィボナッチ数列

フィボナッチ数列の定義

$F_n = ￥begin{cases} 0 & ￥mbox{if }n = 0￥￥1 & ￥mbox{if }n = 1￥￥F_{n-1}+F_{n-2} & ￥mbox{if }n > 1￥￥￥end{cases}$

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …

近似式

$F_n = ￥lfloor ￥frac{￥phi^n}{sqrt5} + ￥frac{1}{2} ￥rfloor$
$￥left ￥lfloor x ￥right ￥rfloor$ は床関数と呼ばれるもので、要は小数点以下切り捨て
なので、これは四捨五入

近似式の証明

まずはこれを証明する。
$￥color{red}{F_{n} = ￥frac{￥phi^{n}-￥psi^{n}}{sqrt5}}$

３項漸化式 $F_{n+1} = F_{n} + F_{n-1}$ の特性方程式 $x^2 = x + 1$ を解くと、
$x = ￥frac{(1 ￥pm sqrt5)}{2}$
これを、
$￥phi = ￥frac{(1+sqrt5)}{2}$ 、 $￥psi = ￥frac{(1-sqrt5)}{2}$
とおく。特性方程式の解から逆に漸化式を作成すると、
$F_{n+1} - ￥phi F_{n} = ￥psi(F_{n} - ￥phi F_{n-1})$ …(1)
$F_{n+1} - ￥psi F_{n} = ￥phi(F_{n} - ￥psi F_{n-1})$ …(2)

$￥phi ￥neq ￥psi$ なので、
(1)、(2)はそれぞれ
初項 $F_{2} - ￥phi F_{1}$ 、公比 $￥psi$ の等比数列
初項 $F_{2} - ￥psi F_{1}$ 、公比 $￥phi$ の等比数列
なので、
$F_{n+1} - ￥phi F_{n} = ￥psi^{n-1}(F_{2} - ￥phi F_{1}) = ￥psi^{n-1}(1-￥phi) = ￥psi^{n}$ …(3)
$F_{n+1} - ￥psi F_{n} = ￥phi^{n-1}(F_{2} - ￥psi F_{1}) = ￥phi^{n-1}(1-￥psi) = ￥phi^{n}$ …(4)
が得られる。

(3)(4)の差をとると、
$￥begin{align} (￥phi - ￥psi)F_{n} &= ￥phi^{n-1}(F_{2} - ￥psi F_{1}) - ￥psi^{n-1}(F_{2} - ￥phi F_{1})￥￥ &= ￥phi^{n-1}(1 - 1*￥psi) - ￥psi^{n-1}(1 - 1*￥phi) ￥￥￥end{align}$

ここで、 $￥phi - ￥psi = sqrt5$ 、 $1-￥psi = ￥phi$ 、 $1-￥phi = ￥psi$ なので

よって任意のnに対して次式が成り立つ
$F_{n} = ￥frac{￥phi^{n}-￥psi^{n}}{sqrt5}$

ここで $|￥psi| < 0.62$ であるから
n < 1 のとき $|￥psi^n| < |￥psi| < 0.62$ であり、
$|￥frac{￥psi^n}{sqrt5}| < 0.5$ である。

よって
$￥frac{￥phi^{n}-￥psi^{n}}{sqrt5} - 0.5 ￥quad < ￥quad ￥frac{￥phi^n}{sqrt5}￥quad < ￥quad ￥frac{￥phi^{n}-￥psi^{n}}{sqrt5} + 0.5$

数学的帰納法だと

$￥color{red}{F_{n} = ￥frac{￥phi^{n}-￥psi^{n}}{sqrt5}}$
の証明は数学的帰納法だと、

$F_0 = (￥phi^0 - ￥psi^0)/sqrt5 = 0$
$F_1 = (￥phi^1 - ￥psi^1)/sqrt5 = 1$
$F_k = (￥phi^k - ￥psi^k)/sqrt5$
$F_{k+1} = (￥phi^{k+1} - ￥psi^{k+1})/sqrt5$
$￥begin{align}F_{k+2} &= F_{k+1} + F_{k}￥￥ &= ￥frac{(￥phi^{k+1} - ￥psi^{k+1})}{sqrt5}+￥frac{(￥phi^k - ￥psi^k)}{sqrt5} ￥￥ &=￥frac{￥phi^k(￥phi+1) - ￥psi^k(￥psi+1)}{sqrt5}￥￥ &= ￥frac{￥phi^{k+2}-￥psi^{k+2}}{sqrt5} ￥￥￥end{align}$
よって任意のnに対して次式が成り立つ
$F_{n} = ￥frac{￥phi^{n}-￥psi^{n}}{sqrt5}$

フィボナッチ数列の隣り合う 2 項の比は黄金比に収束する

黄金比の説明のときに残しておいた宿題。

$￥lim_{n ￥rightarrow ￥infty}￥frac{F_{n}}{F_{n-1}} ￥rightarrow ￥phi$
$x = ￥lim_{n ￥rightarrow ￥infty}￥frac{F_{n}}{F_{n-1}} = ￥lim_{n ￥rightarrow ￥infty}￥frac{F_{n-1}+F_{n-2}}{F_{n-1}} = ￥lim_{n ￥rightarrow ￥infty}￥left(1+￥frac{F_{n-2}}{F_{n-1}}￥right) = 1 + ￥frac{1}{x}$
$x = 1+￥frac{1}{x}$
$x^2 = x + 1$

黄金比の値は、二次方程式 x2 = x + 1 の正の解なので、これで証明終了

登録: 投稿 (Atom)