Aizu SICP 第四回 - やろーじだい

2016/6/11 に Aizu SICP 第四回を行った。途中の練習問題は一旦飛ばした。

タイムテーブル

19:10 ~ 19:30: 読書 p38「1.2.2 木の再帰」~ p42 練習問題1.11前まで
19:30 ~ 20:00: 質疑
20:05 ~ 20:20: 読書 p43「1.2.3 増加オーダー」 ~ p47 「1.2.4 指数計算」練習問題前まで
20:20 ~ 20:50: 質疑

今回の内容

1.2.2 木の再帰

より正確には、Fib(n) は ${\Phi^{n} / \sqrt{5}}$ に最も近い整数になります (練習問題 1.13参照)。 ${\Phi}$ は次の値です。
$\Phi = \frac{1 + \sqrt{5}}{2} \approx 1.6180$
${\Phi}$ は黄金比 (golden ratio) で、次の等式を満します。
${\Phi^{2} = \Phi + 1}$
そのため、このプロセスのステップ数は、入力に対して指数的に増加します。
p38~39

最後の「そのため」は、

より正確には、Fib(n) は ${\Phi^{n} / \sqrt{5}}$ に最も近い整数になります。
P38

にかかる。
　両替の問題は読書会中に各自紙に書くことによって理解を試みた。数学的な話題になってくると紙とペンが欲しくなるので準備が必要だった。
　この章の中で

count-change は、fib の一つ目の実装同様、冗長な木の再帰のプロセスを生成します (292 の計算にはかなりの時間がかかるでしょう)。
P42

という話があったが、現在の性能では数ミリ秒であり、この本がかなり前にかかれた本であることを再確認した。

1.2.3 再帰オーダー

任意の十分に大きな ${n}$ に対して、 ${n}$ と独立な正の定数 ${k_1}$ と ${k_2}$ が存在し、 ${k_1f(n) \leq R(n) \leq k_2f(n)}$ を満たすとき、 ${R(n)}$ は増加オーダーが ${\Theta(f(n))}$ であると言い、 ${R(n) = \Theta(f(n))}$ (シータ f(n) と読む) と書きます。(別な言い方をすると、大きな ${n}$ に対して、 ${R(n)}$ の値は ${k_1f(n)}$ と ${k_2f(n)}$ で挟まれるということです。)
P44

という定義から、 ${\Theta(n)}$ は ${O(n)}$ と ${\Omega(n)}$ を満すものとしての ${\Theta(n)}$ であると考えてよさそう。

1.2.4 指数計算

　ここの主題とは無関係だが、

ここで、ある整数が偶数かどうかをテストする述語は、基本手続きの remainder (割り算の余り) を使って次のように定義します。
P46

ということから Scheme の言語仕様には、even? は含まれていないようだ (Racket 上では実装されている)。こういったことがこれから先頻繁に表れると考えられるので注意する。基本的に Racket 上で実装されているならば、実装の方法を確認した上で既に実装されているものを利用して問題無いと思う。

質疑応答など

「木の再帰プロセス」と「再帰プロセス」は別な概念か

　あえて「木の」と表記していたのが気になったとういことだったが、「木の再帰プロセス ${\in}$ 再帰プロセス」という考えで問題は無いか。

両替アルゴリズムの他のより良いものは何があるか

一方で、答えを計算するためのよりよいアルゴリズムをどう設計するかというのは自明ではありません。この問題は、読者への宿題とします。
P42

読書会中にはメモ化の他には、何かしら反復プロセスで実装するというアバウトな考えしか浮かばなかった。

　その後、木の下から集めていくことをイメージして1時間くらい考えてみたがわからなかった。

${\Theta}$ は空間や計算量共に使えるものか

　P43 で定義された ${R(n)}$ のように様々なものを表すことができると考えられる。

ビックオー ${O}$ について

注：ビッグオーをビッグシータの意味で使うことも多いので注意が必要です。
http://mathtrain.jp/landausymbol

ということが URL のページで書いてあったが、実際に ${O}$ を ${\Theta}$ の意味で使っているところを目撃した記憶がない。