(1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1) (N 1 1 2 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1) (N N N 1 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2) (N N N 1 2 1 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 …

k=1 (1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1) K=2 (N 1 1 2 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1) k=3 (N N N 1 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1) k=4 (N N N 1 2 1 1 1 2 1 1 2 1 1 2 1 1 2 1 1) k=5 (N N N N 2 1 1 1 2 1 1 2 1 1 2 1 1 2 1 1) K=6 (N N …

ガウス雑音がある通信路の通信路容量 を証明します。以下は、甘利俊一著「情報理論」に書いてあることをまとめたものです。証明のポイントは2つです。 加法的雑音があるとき、通信路容量の式が となることと、 平均電力が与えられたときの最大エントロピーが…

読者の宿題、atom-countを書いてみた。 (defun atom-count (x) (cond ((atom x) 1) (t (atom-count2 x)))) (defun atom-count2 (x) (cond ((null x) 0) ((atom (car x)) (1+ (atom-count2 (cdr x)))) (t (+ (atom-count2 (car x)) (atom-count2 (cdr x))))))

定常情報源のエントロピーレートには2つの表し方があります。 1つは で、もう1つは です。 この2つの極限が等しいことを示します。 まず、以下が成り立ちます。これをチェインルールといいます。 すなわち です。 ここで、条件が多くなるとエントロピーが小…

『プログラミングGauche』17章総称関数とオブジェクトの練習問題をやってみました。総称関数subは、関数呼び出しの回数と、関数実行にかかった時間を保持するクラスと、引数と結果を出力するクラスを継承しています。このままだと、クラスが保持する時間には…

アドベンチャーゲーム ;; -*- coding: utf-8 -*- (use util.match) (define *player* (make-player 'hp 320 'mp 66 'position (car *dungeon*) 'inventory '(potion potion daggar cookie daggar))) (define (reset!) (set! *player* (make-player 'hp 320 '…

最近、「プログラミングGauche」を読み直しています。SICPを読んでいて行き詰まってしまったのと、実践で使えるSchemeを修得したいという考えからです。今日はSchemeにおける関数の記法の変換をやってみました。 (define (mit-form->primitive-form expr) (l…

interp関数の(extend-env (bind (fdC-arg fd) (interp a env fds)) mt-env)を(extend-env (bind (fdC-arg fd) (interp a env fds)) env)とするとダイナミックスコープになってしまうので注意。(schemeはダイナミックスコープではなく、レキシカルスコープ) #…

一次合同式とは以下である。 のとき、と書ける。 （は整数)にこれを代入すると、即ち、より、はを約数として持たなければならない。よって、と書くと、なる。で割ると以下のようになる。 この一次合同式の唯一つの解をとすると、より 両辺に掛けて、即ちとな…

「Programming Languages: Application and Interpretation by Shriram Krishnamurthi」というPDFを読んでいます。http://cs.brown.edu/~sk/Publications/Books/ProgLangs/ これは、言語処理系に関する本のようです。インターネットで調べたところCPS変換に…

初期値837799のコラッツ数列をmod 127を演算してMIDIの音階にしてみました。 こちらで聴けます。 https://soundcloud.com/user783056320/837799a package collatz; import java.math.BigInteger; import javax.sound.midi.Instrument; import javax.sound.mi…

秋から冬になろうとしています。少し肌寒いですね。 最近は、SICPとAwodeyの圏論を読んでいます。 SICPは面白いけれど、問題がとても難しいです。 最初は全問解こうと思っていたのですが、2章後半であきらめました。 今は3章の「標準部品化力、オブジェクト…

乱数生成のアルゴリズムとしてメルセンヌツイスターを使うときにはsrfi-27を使います。 テストをするときなど、乱数列を再現させたいときがあります。 以下のrand関数は((rand 'reset) )で乱数源を初期化します。 (rand 'generate)を複数回実行することによ…

以下の積分 のフーリエ変換を求めます。 (※以下に述べることは、斉藤洋一著『信号とシステム (コロナ社)』に書いてあります。)方針としては、この積分はとヘビサイド関数の畳み込みなので、ヘビサイド関数のフーリエ変換を求めることに帰着します。(畳み込み…

import Data.Char type Bit = Int bin2int :: [Bit] -> Int bin2int = foldr (\x y -> x + 2*y) 0 int2bin :: Int -> [Bit] int2bin 0 = [] int2bin n = n `mod` 2 : int2bin (n `div` 2) make8 :: [Bit] -> [Bit] make8 bits = take 8 (bits ++ repeat 0) e…

type Bit = Int unfold :: (a -> Bool) -> (a -> b) -> (a -> a) -> a -> [b] unfold p h t x | p x = [] | otherwise = h x : unfold p h t (t x) chop8 :: [Bit] -> [[Bit]] chop8 = unfold (\x -> null x) (take 8) (drop 8) map' :: (a -> b) -> [a] -> …

import Data.Char -- caeser encription (upper case version) let2int :: Char -> Int let2int c = ord c - ord 'a' int2let :: Int -> Char int2let n = chr (ord 'a' + n) shift :: Int -> Char -> Char shift n c | isLower c = int2let ((let2int c + n…

;; 2.87, 2.88 ;;;;;;;;;;;;; ;; 汎用演算 ;; ;;;;;;;;;;;;; (define (equ? x y) (apply-generic 'equ? x y)) (define (project x) (apply-generic 'project x)) (define (raise x) (apply-generic 'raise x)) (define (add x y) (apply-generic 'add x y)) …

;; 2.86 ;;;;;;;;;;;;; ;; 汎用演算 ;; ;;;;;;;;;;;;; (define (equ? x y) (apply-generic 'equ? x y)) (define (project x) (apply-generic 'project x)) (define (raise x) (apply-generic 'raise x)) (define (add x y) (apply-generic 'add x y)) (defin…

このブログを参考にさせていただきました。 https://highmt.wordpress.com/2009/12/19/ntemacs%E3%81%A7tramp%E3%82%92%E4%BD%BF%E3%81%86/fakecygptyはcygwinのgccでコンパイルします。

b問題がちょっと難しかったので、記録しておきます。 b問題 不要なかっこは省き, 乗算は加算より前に行うと仮定する(x + 3 * (x + y + 2))のような, 標準の代数記法を許すと問題は実質的に難しくなる. われわれの微分プログラムが相変わらず動作するように, …

(define (make-sum a b . rest) (letrec ((make-sum-sub (lambda (terms sum) (cond [(zero? sum) (cond [(null? terms) 0] [(null? (cdr terms)) (car terms)] [else (cons '+ terms)])] [(null? terms) sum] [else (cons '+ (cons sum terms))])))) (let (…

(use gl) (use gl.glut) (define (display) (gl-clear GL_COLOR_BUFFER_BIT) (gl-begin GL_LINES) (gl-color 1.0 0.0 0.0) ((square-limit painter-wave 5) (make-frame (make-vect -1.0 -1.0) (make-vect 2.0 0.0) (make-vect 0.0 2.0))) (gl-end) (gl-flus…

;; 2.42 (define (queens board-size) (letrec ((queen-cols (lambda (k) (if (= k 0) (list empty-board) (filter (lambda (positions) (safe? k positions)) (flatmap (lambda (rest-of-queens) (map (lambda (new-row) (adjoin-position new-row k rest-o…

;; 2.29 (define (make-mobile left right) (list left right)) (define (make-branch length structure) (list length structure)) ;; a (define left-branch car) (define right-branch cadr) (define branch-length car) (define branch-structure cadr) …

SICPの問題1.29です。 (define (sum term a next b) (if (> a b) 0 (+ (term a) (sum term (next a) next b)))) (define (integral f a b n) (let* ((h (/ (- b a) n)) (inc (lambda (x) (+ x 1))) (term (lambda (k) (cond [(or (= k 0) (= k n)) (f (+ a (…

; 1.28 (use srfi-27) (define (expmod base exp m) (cond [(= exp 0) 1] [(even? exp) (miller-rabin (expmod base (/ exp 2) m) m)] [else (remainder (* base (expmod base (- exp 1) m)) m)])) (define (miller-rabin a m) (if (and (not (= a 1)) (not …

以下は、ふつうのフィボナッチ数列のアルゴリズムです。 (define (fib n) (cond [(= n 0) 0] [(= n 1) 1] [else (+ (fib (- n 1)) (fib (- n 2)))])) これを反復的になるように書き換えると以下のようになります。ステップ数はです。 (define (fib n) (fib-i…

SICPの問題1.18。「ロシア農民の方法」として知られるアルゴリズムらしい。これは30分くらい考えてわかった。解けたときすっきりした。 ; 1.18 (define (fast-* a b) (*-iter a b 0)) (define (*-iter a b n) (cond [(= b 0) n] [(even? b) (*-iter (double …