エンジニアをリングする

プログラをミングしたり。

my web site twitter

数学・情報系を専攻してないWebエンジニアがSICPを読んだメモ (1.2.3)

SICP LISP 数学

minghaiさんによるSICP全訳を読んでいます。

数学・情報系を専攻してないWebエンジニアがSICPを読んだメモ (1.1) - エンジニアをリングする
数学・情報系を専攻してないWebエンジニアがSICPを読んだメモ (1.2.1) - エンジニアをリングする
数学・情報系を専攻してないWebエンジニアがSICPを読んだメモ (1.2.2) - エンジニアをリングする

課題1.12リベンジ！

前回パスカルの三角形の課題がでていて、どう解けばいいのかわからなかったんですが、翻訳されたminghaiさんからコメントを頂きました。

さて、課題1.12のパスカルの三角形ですが問題文(仕様)があやふやなのでどう解いても良いのですが、多くの人は入力に何行目の何番目の要素という2つの値を入れて、その場所の値のみを求めているようです。もちろんpascalの三角形を書くのも全く正解だと言えるでしょう。

なるほど、全部出力しようと思って四苦八苦してたんですが、要素をひとつ求めるならできそうです。
ということでやってみたら、できました！！
ex_1_12.scm

わーーい！！
あっさりできた・・・
日をおいたのもよかったのかもしれません。
minghaiさんありがとうございます！！

課題解けるとうれしいですね。

1.2.3 増加のオーダー

オーダーとは

かんたんに。

  • 計算の仕方（アルゴリズムの種類）によって、プロセスの量（消費する計算資源の割合）が大幅に異なる
  • その違いを説明する便利な記法が「増加のオーダー」

定義

定義がちょっと難しい。

n が問題サイズを測るパラメータ、R(n) をサイズ n の問題に対しプロセス が要求するリソースの量だとします。
もし任意の十分に大きな n の値に対して正の定数 k1 と k2 が n に独立して存在し k1f(n) <= R(n) <= k2f(n) を満たす時、R(n) は増加の次数 Θ(f(n)) を持ち R(n) = Θ(f(n)) (“シータ f(n)” と発音する) と記述されます。

問題サイズn

問題サイズ n の例として挙げられていたのは、

  • フィボナッチ数のn番目を求める（前節）
  • 平方根の近似値を求める場合、必要な精度の桁数
  • 行列の乗算では行列の行数

など。

図

定義難しかったですが、このオーダーのあたりは「数学ガール乱択アルゴリズム」で読んだのでなんとなく三本線のグラフのイメージが浮かんでます。
かきました。

f:id:yoshiko_pg:20140526191046j:plain

  • R(n) が常に k2f(n) 以下である = Ｏ(f(n))
  • R(n) が常に k1f(n) 以上である = Ω(f(n))
  • 上記２つが共に成り立つ = Θ(f(n))

なんかこんなイメージです。

SICPの定義の表記に従ってΘ(f(n))と書きましたが 、Θ(f(n))とΘ(n)の違いがわかってない・・・

プロセスの種類とそのオーダー

6/1: コメントを頂き修正しました。

今までにやったプロセスの種類についてオーダーが解説されていたので、種類をおさらいしたいと思います。

  • 線形再帰プロセス
    ステップ数：線形に増加　記憶域：線形に増加
  • 線形反復プロセス
    ステップ数：線形に増加　記憶域：一定
  • 木再帰
    ステップ数：指数関数的に増加　記憶域：線形に増加

一定、線形に増加、指数関数的に増加　の３種類があります。
それぞれのオーダーは以下。

  • 一定：Θ(1)
  • 線形に増加：Θ(n)
  • 指数関数的に増加：Θ(2n)

増加の次数

オーダーにおいては掛ける数や足される数は小さな差なので無視される。
一番大きな次数だけを残す。

増加の次数はプロセスの行いについて概観的な説明のみを与えます。例えば n2 ステップ、1000n2 ステップ、3n2 + 10n + 17 ステップを必要とするプロセスは全て増加の次数は (n2) になります。

参考：オーダーについて知っておくべき5つのこと - わさっき

課題

1.14 count-changeのプロセスの木

ex_1_14.scm
記憶域：Θ(n)
ステップ数：Θ(2n)
関数からというよりは木再帰の解説から。。。（記憶域が線形、ステップ数が指数関数的）
あと自身の中で自身を２回呼んでいるから2nかな。
ステップ数はどこを数えればいいんだろう。

1.15 三角法の恒等式

ex_1_15.scm
大きい数で計算しても６回分しか深くならない！！
ということは記憶域は一定でΘ(1)
記憶域が最深6でも「増加の次数」はΘ(6)じゃなくてΘ(1)でいいのかな？
あとプロセス数の次数は3で割ってるのでlog3かと思ったけどあってるのかな・・・
ちょっと正直ラジアンやったことなくてよくわからない・・・

感想

数学できなさが効いてきてます。
ラジアンとか普通わかるんでしょうね。

私の「数学・情報系専攻してなさ」についてですが、高校・大学（１年）と音楽を専攻していたため、他の科目のまともな授業がありませんでした・・・。
なのでセンター試験はおろか高校受験勉強すらしてない感じです。
最後にやった数学の記憶といえば中学でやった三角形の内角の和です。。。
たぶんふつうの文系とかの数学できないレベルと違うんでしょうね。
それで危機を感じてSICP始めてみたわけですが、基礎知識のなさを痛感してます。

なのであんまり気持ちよくスムーズにいかないと思いますが、とりあえず進めることを目標にしていこうと思います。
じっくりやったほうがいいのだと思いますが、止まりそうなので・・・
２周目は深くじっくりやってみてもいいかなと思ってます。

生暖かく見守ってもらえると嬉しいです。