読書会メモ 第2回 及び 第３回
先週末はネット環境にいなかったため、本日までの２回分まとめてメモを残します。
●消化内容
【第２回】第１章 第２節 手続きとその生成するプロセス（p20〜p24）
【第３回】第１章 第２節 手続きとその生成するプロセス（p24〜p31）
●メモ
第１章第１節でSchemeの基本的な文法や特殊形式が解説された後、この第２節では様々な数学的アルゴリズムとそれにより生成されるプロセスについて述べられている。効率のいいアルゴリズムとは何か、如何にしてそのようなアルゴリズムを生み出せるのかを学ぶための節。この節を読んで、初めてアルゴリズムの本質に触れた気がした。ただし、自分の場合、数学の基礎知識がおぼつかないこと、再帰アルゴリズムの構成をまだ体で覚えていないことが足を引っ張り、理解するのに大変な時間がかかる。補助的な書籍を読みながら、だんだんと数学の知識を戻しつつあるが、まだまだ全然足りない。
増加の程度
ある関数Ｆ(n)への入力が増加していったとき、「プロセスのステップ数」と「必要とされる計算空間(スペース)」が増加する程度は以下の４種類に分類できる（下へ行くほど効率的）。
1. 指数的増加(α^n に比例)
2. 多項式的増加(n に比例)
3. 対数的増加(log n に比例)
4. 定数的増加(α に比例)
数学的世界では１番と２番の間に大きな線引きがなされる。すなわち、１は遅い、２〜３は充分速いと見なす。判断の根拠はアルゴリズムが実用に堪え得るかどうか（指数的増加を示すアルゴリズムは、容易に現実性を超えた量のステップ数を要求するようになる）。
一方、私たちが身を置く業務システムの世界では当然、よりシビアな線引きがなされる。データ件数に比例して応答時間が遅くなるシステムでは使い物にならない。
具体的に取り上げられていた例題は以下。
［Fibonacci数列のn番目の数を求めるアルゴリズム］
木構造再帰の実装により生成されるステップ数は指数的増加を示し、反復的再帰の実装によるステップ数は多項式的増加を示す。指数的爆発の影響力がいかに大きいかが明らかになる。
［α^n（べき乗）を求めるアルゴリズム］
直感的にはαをn回掛けるアルゴリズムが採用され、当然これはステップ数、スペース共にnに線形(つまり多項式的)な増加を示す。
一方、逐次平方(下記参照)を利用したアルゴリズムの実装はステップ数、スペース共にnに対数的な増加を示す。これは、再帰的計算プロセス内部において、（nが偶数でわたってくる度に）べき乗アルゴリズムのステップ数の根拠たる指数nを半分に減らすことが可能だからである。
逐次平方
α^n = (α^n/2)^2 = (α^2)^n/2 （nが偶数の場合）α^n = α・α^n-1 （nが奇数の場合）
