2011年2月24日木曜日

対称関数

対称関数の続きである. そのブログの中程にある図に示すように, 2変数対称関数は8個, 3変数対称関数は16個ある.

n変数のBoole関数は, 定数関数も含めて22n(2の2のn乗乗)あるが, n変数の対称関数は2n+1しかない.



3変数対称関数の図を眺めると, 各立方体で, 同じ色の対称同士の点は, 000の(赤の)点から, 等距離にあることが分かる. 距離の計測法は, 000から立方体の稜にそって目的地まで進む最短距離, いわゆるマンハッタン距離である.



改めて眺めると, 赤までの距離は0, 緑までは1, 橙までは2, 青までは3である.

つまり対称の要素は4個あり, その要素を採用するか, しないかの問題であった. n変数は000...0の点から111...1まで行く辺の種類はn個なので, 要素の数は両端を含めてn+1, 従って2n+1になるのであった.

2011年2月21日月曜日

乗算表

「昔のウクライナの人たちはこうやって計算した」と話し出したのはMike Williamsさんだ.



指を出し, 小指の外から指の間を順に0,1,2,...と数える. 親指を飛び越えると5になる. そこで折り返し, 6,7,...と続ける. 小指を過ぎると10になる.

さて, 7×8をウクライナの人はどう計算するか. 片手(左とする)の指をさっき7と数えたところで, 上下に開く. 反対の手(右とする)でも, 8と数えたところで, 上下に開く. 左の上の指が2本. 右の上の指が3本. 左の下の指が3本. 右の下の指が2本となる.

10×(上+上)+(下×下)と計算する. つまり 10×(2+3)+(3×2)=56 が答だ.

下の指は最大で5だから, 5×5までを知っていれば良いのだ.

これで5<M,N≤10について, M×Nが計算出来る理由を, 下の色付きの図で説明する.




まず上左の図. 縦軸がMで, 中央に5があるから, Mは中央より上にある. 横軸がNで, Nも中央より右にある. この場合, Mの上(upper) MuとMの下(lower) Ml, Nの上(upper) NuとNの下(lower) Nlはそれぞれ図に示す範囲だ. 従ってMu×10は, 途中で色が変っているが, 横ハッチの部分である. 一方, Nu×10は, 縦ハッチの部分だ. そしてMl×Nlは, 斜めハッチの赤い部分である.

ところで, この図の右上の4半分は, 図の中心で180度回転すると, 左下に移すことが出来て, 右の図のようになる. Dと書いてある縦ハッチと横ハッチが重なっている部分は, 面積の計算で2回足しているが, 右上のD'のところへ移動することが出来, 全体がちょうどM×Nになるのである.

下の, 白黒の淋しい図は, 乗算の一方が≤5の時の方法である. 今, Mの方が5より小さいとする. M×Nは, 図では, ハッチに囲まれた左下の小さい白い部分である. この場合は 50−(10×Mu+Ml×Nl)と計算することになるが, これは面倒な気もする.


昔のウクライナ人に聞いてみたい.

2011年2月14日月曜日

水計算器

計算機にディジタルとアナログがあるのは周知のことだ.

アナログは計算尺のように物理量を使うといわれるが, 殆んどの機械は長さが基本である. しかし, もっと違う物理量を使うものはないか.

小学校のとき, 曲線で囲まれた面積を計測しようという課題があった. 私は, その形を厚紙から切抜き, 重さを測ればよいと考えたが, 先生の用意した解は方眼紙にコピーして, 桝目を数えるのだった.

面積計の話題は, このブログに何回も登場したが, 毛色が違うのは, ボストンの科学博物館にあった, 液体を使うPithagorasの定理の証明である.

ガラスで被われた一様な厚さの正方形の箱が3個, 3:4:5のPithagoras三角形の形においてあり, 色のついた水がはいっている. 箱の繋ぎ目は水が通れる. 全体の装置は垂直面になっていて, 中央あたりの水平の軸で回転できる.




まず3と4の箱が下に来るようにすると, その2つの箱に丁度いっぱいに水が入る. 次にそれを180度回転すると, 水はすべて5の箱に収まる.

「水は器に従いて」の歌の通り, 面積を保ちながら, 形が変えられるのを利用したものだ.

それなら体積は使えないかと考えたのが, 次の立方根計算器である.





右の円筒の途中まで水が入っている. 上まで満杯の時, 水面の高さを1とする. 図では0.5になっている. この水をそのまま, 左の円錐へ移す. そうすると円錐の母線に沿った目盛で, 先ほどの量の立方根0.79が読める仕掛けである.

しかしびしょびしょして, 実用にはなりそうもない. 粉体も無理だが, 微小な球の粒を, Pitagorasの機械のように, 閉じ込めて使うことなら出来そうである.

体積2倍の立方体をつくるのに, 使えたかもしれない.

2011年2月13日日曜日

対称関数

TAOCP V4F1にきれいな絵があった. 元の絵はもちろん白黒である.



これは3変数対称関数のBDD(二分決定図)ベースの図である.

そもそも対称関数とは, 変数をとりかえても値が変らないものである.

以下に2変数(xとy), 3変数(xとyとz)の対称関数を示す. 頂点にある色つきの丸は関数値が1の点で, 同じ色は対称の相手を表わす.



上の方の2変数対称関数は, それぞれの図で, 左下がx=0, y=0. 右上がx=1, y=1の点で, 破線は対称軸. 従って対称関数は, 同じ色の丸が対称軸について対称であるものである.

2変数関数が16あるうち, 対称なのはここにある0番から7番の8個である.

3変数のx, y, zは, 左上の0番の図に示す通りで, 3変数の場合も, 同じ色の丸は対称軸について3回対称である.

3変数関数は全部で256あり, 対称なのは0番から15番の16個である.

Boole関数は, こういう図の他, その真理値表で表わすことも出来る. x, y, zの各値に対し, 関数値を並べて書く. 例えば3番は多数決関数で


x 00001111
y 00110011
z 01010101
f 00010111


である. 図からは右下の経路で頂点をたどり1と0を書き取ればよい.


ところで, TAOCP 7.1.4項は, BDDが話題であった. BDDは下に示すような図で, 変数を調べる節点を実線と破線で繋げたものである.

一番上の入口(根)から出発し, 丸で示す変数の値を調べ, 値が1なら実線方向へ, 0なら破線方向へ進み, 次の変数をチェックする. 四角に⊥は, 関数の値が0で確定する, 四角にTは, 1で確定し, BDDの出口である.

下の図は, 3変数の16個の対称関数のうち16個のBDDで, 0番のオール0, 15番のオール1は定数関数なので, 省いてある.




最上段の右端の3番が, 話題の多数決関数で, 根の1番変数(xのこと)の脇に先ほどの真理値表が書いてある. xが0なら左下の2番変数へ進み, yを調べる. ここでyも0ならzと無関係に0なので, 0の出口になる. yが1なら, 決定はzによる. そこで3番へ進む. 上へもどり, xが1なら右下の2番変数へ進み, 2も1なら1の出口. 2が0なら3番の変数をしらべる. BDDはこのような図である.


ところでそれぞれの図の節点の数は, 0と1の出口は1個と数えるので, 1番から順に, 5, 7, 6, 7, 7, 7, 5, 5, 7, 7, 7, 6, 7, 5 で合計88個ある. 1の節点は14個あるが, 1段下の2の節点は6種類, 3の節点は2種類しかない. 同じものをまとめてメモリーにいれれば節約になるといってまとめたのが最初に掲げたBDDベースである. ここには節点は24しかない.

1の節点の左下の青の番号は, 対称関数の3変数の番号と一致している. 一番上の3番は, 実線で左の2へ, 破線で右の2に進むが, それぞれの2の左に青で1と3とあるのは, BDDの2の添字に合っている.

もう一度対称関数の絵で3番をみると, xが1の手前の四角の丸は, 直ぐ上の2変数の3番と同じ. xが0の向こうの四角は, 2変数の1番と同じであり, さきほどの添字はそれを表わしている.

変数の図はyの値で1変数の図に分解できる. 下の図が1変数の(対称)関数の図と, その右が0変数の図である.