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

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



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


高橋(徹)です。

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

日時:8月5日10:00〜17:00
場所:東京都文京区立 不忍通りふれあい館 会議室 
出席者:伊部さん、寺本さん、横山さん、金山さん、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 木構造再帰
 注32: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は、素数を使った暗号アルゴリズム。2つの素数を組み合わせるのがミソ。
  
夜の部は、根津駅そばの居酒屋さん大八にて
大いに盛り上がり、5時前からはいったのに10時半まで滞在。帰りは
どしゃぶりの雨でした(^^;

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

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