2010年12月23日木曜日

クリスマスツリー講義

今月(2010年12月)始め, Knuth先生から, いつもの航空便ではなく, 珍しくメイルで返事が来た. その最後に

By the way, my lecture next Monday will probably be webcast live, so you might be able to watch it via Internet in Japan.

と書いてあった. その日(日本時間では7日朝)は所用あって, インターネットも見ずに過ぎたが, ホームページには,

Monday, 06 December, 5:30pm, in the new NVIDIA auditorium (Huang Engineering Center) A Computer Musing entitled ``Why pi?'' [the sixteenth annual Christmas Tree Lecture]

あ, これがあのクリスマスツリー講義(Christmas Tree Lecture)だったのか.

すぐに連想するのは, 元祖「クリスマス講演」である.

「これから皆さんにロウソクのお話をいたそうと思います.」で始まるMichael Faradayの「ロウソクの科学」は, 1860年のクリスマスであった. だから150年前の話だ. ところでこの原題はThe Chemical History of a Candleという.

Royal Institution Christmas LecturesをWikipediaでみると, 1825年に始まり, 第2次世界大戦中を除き, 今年も続けているというから, 英国のこだわりにはまったく脱帽する.

一方, クリスマスツリー講義は, Knuth先生が, 年末に一般向けに講義するものらしい.

TAOCP V4F4の表4に8次のクリスマスツリーパターンという図があり, その脚注に(TAOCPに脚注があるのは異例なことだが),

"This name was chosen for sentimental reasons, because the pattern has a general shape not unlike that of a festive tree, and because it was the subject of the author's ninth annual "Christman Tree Lecture" at Stanford University in December 2002."

と書いてある.

8次は大きすぎるから遠慮し, 6次のクリスマスツリーは以下のように, 6ビットの二進数64個を, 6C3=20行, 6+1列に配置する.

左からの各列は, 1の個数が0, 1, ..., 6である. 従って中央の高さは6C3である. 同じ行では, 右に行くに従い, 0が1に変っていく. 赤い0は, 次に1になるもの, 青い1は, 前に0だったものだ.

この配置法は, 1951年にde Bruijn, van Ebbenhorst Tengbergen, Kruyswijkが発見した.



101010
101000 101001 101011
101100
100100 100101 101101
100010 100110 101110
100000 100001 100011 100111 101111
110010
110000 110001 110011
110100
010100 010101 110101
010010 010110 110110
010000 010001 010011 010111 110111
111000
011000 011001 111001
001010 011010 111010
001000 001001 001011 011011 111011
001100 011100 111100
000100 000101 001101 011101 111101
000010 000110 001110 011110 111110
000000 000001 000011 000111 001111 011111 111111


これはどうできているかというと, 1次は

0 1

の1行. これではクリスマスツリーにならない. 2次は

10
00 10 11

の2行. いささかツリーらしくなる.

さて, n次のツリーの各行を,
σ1,...,σs
とすると, n+1次のツリーは, 各行を
σ20,...,σs0と
σ10,σ11,...,σs1の
2行にする.

すなわち, 後に0をつけたものと, 後に1をつけたものを作り, 0をつけたものの先頭の1個を1をつけたものの先頭に移動するのである. 先頭を外した後が0個になったら, その行は除く.

Schemeで書くと

(define (next ct)
(if (null? ct) '()
(let ((ss0 (map (lambda (s) (string-append s "0"))
        (car ct)))
(ss1 (map (lambda (s) (string-append s "1"))
        (car ct))))
(set! ss1 (cons (car ss0) ss1))
(set! ss0 (cdr ss0))
(if (null? ss0) (cons ss1 (next (cdr ct)))
(cons ss0 (cons ss1 (next (cdr ct))))))))

である. ctを

(define ct '(("0" "1")))

によって1次のクリスマスツリーとし, ctにnextを順に作用させると,

(("10") ("00" "01" "11"))

(("100" "101") ("010" "110") ("000" "001" "011" "111"))

(("1010") ("1000" "1001" "1011") ("1100")
 ("0100" "0101" "1101") ("0010" "0110" "1110")
("0000" "0001" "0011" "0111" "1111"))


が得られる. クリスマスツリーらしいのは, 次数nが偶数の時である.

6次のクリスマスツリーパターンは, 異なる64の要素があるから, それを八卦の64のパターンで置き換えたのか以下である.



これは, 昨年の, 私からKnuth先生へのクリスマスカードであった.

0 件のコメント: