[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[jfriends:00154] 第２回計算機プログラムの構造と解釈を読む会議事録

 ┼─────────── 【kenko＆kirei】 ───────────┼
 
        キラキラ光る、『もっと健康に、もっとキレイになる。』
      オープニング記念 ◆アンケート回答者様へ素敵なプレゼント◆
 ┼────────  http://www.kenko-kirei.com/ ────────┼
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=


高橋(徹)です。

第２回「計算機プログラムの構造と解釈」を読む会の議事録です。

日時：８月５日１０：００〜１７：００
場所：東京都文京区立 不忍通りふれあい館 会議室 
出席者：伊部さん、寺本さん、横山さん、金山さん、yamashitaさん、
　　　　橋本さん、えんどうさん、高橋（書記）
読み手：yamashitaさん
補助資料：yamashitaさんによる問題の解答例

1.2 手続きとその生成するプロセス
1.2.1 線形再帰と反復
　末尾再帰的：
　　自然で分りやすいが、スタックオーバーフローを起したりする。
　　→末尾再帰的に置き換える。ループに落しやすい
　　Q. 全ての再帰が末尾再帰的になるか？
　　A. No.　例えば問題1.10のAckerman関数は末尾再帰的にならない。
　　問題1.9の解答例を見ながら、末尾再帰的になるかどうかの説明。
　　(define (+ a b)
  　  (if (= a 0)
    　    b
      　  (inc (+ (dec a) b))))   
　　最初のdefineは、最後に展開されるのはincなので末尾再帰的でない。
　　(define (+ a b)
    　(if (= a 0)
      　  b
        　(+ (dec a) (inc b))))   
　　次のdefineは、最後に展開されるのが自身なので末尾再帰的。

　問題1.10のついでに、たらい回し関数の紹介。考案者は竹内先生、元
　Javaカンファレンスの会長でした。Lispでは非常に有名な方とのこと。
  （知らなかった・・・）
　　(define (tarai x  y z)
      (cond ((> x y)
             (tarai
               (tarai (- x 1) y z)
               (tarai (- y 1) z x)
               (tarai (- z 1) x y)))
             (else y))

1.2.2 木構造再帰
　注３２：evalがどうevalか、木構造を使っている。
　問題1.11 再帰→反復（機械的にはできる）
　パズルを解くような場合は、再帰で考える方が楽。
　p.24計算量：データの件数がおおいと大きく変わってくる。
　暗号の強度で、計算量の話しがでてくる。（指数的であることが拠り所）

　再帰的：トップダウン
　反復的：下から積み上げていく。

昼食：根津の中華料理屋さんでお昼をたべました。

　問題1.19　フィボナッチは前から順番に求めるしかないと思えるので、この
　アルゴリズムは「すごい」
　ここで、フィボナッチの応用について話題が広がった。CG方面で良く使って
　いる、フラクタルとか樹木の造形、おうむ貝の巻き方とか・・・

　正規順序：　なぜnormなのか？　λ式の展開を先に全部してしまってから
　評価する。
　lambda：　ラムダと読む。（記録者注：ランブダと読んでいたので、ここで
　はじめてラムダと読むことを知った・・・）
　(define (f x)
          (+ x 1))
  これはシンタックスシュガーであり
  (define f
          (lambda (x) (+ x 1)))
  Emacs Lispだと、関数定義は、(defun f(x) .......

　p.28　Fermatの小定理
　(Fermatといえば、最終定理で有名。)
　a^n ≡ a(mod n)
  a^(n-1) ≡ 1(mod n)

例えば、n=5として
　2^2 = 4 ≡ 4
  2^3 = 8 ≡ 3
  2^4 = 16 ≡ 1  <--- a^(n-1) ≡ 1
  2^5 = 32 ≡ 2　<--- a^n ≡ a　　

RSAは、素数を使った暗号アルゴリズム。２つの素数を組み合わせるのがミソ。
　　
夜の部は、根津駅そばの居酒屋さん大八にて
大いに盛り上がり、５時前からはいったのに10時半まで滞在。帰りは
どしゃぶりの雨でした(^^;

次回は、p.31 1.3 高階手続きによる抽象　から

-- 
Toru TAKAHASHI :-O    torutk@xxxxxxxxxxx
http://www.alles.or.jp/~torutk/