すごくわかりやすい
コンピュータは1か0で動いていて、1か0を変数とするand, or, not で組み合わせた式を命題論理式とかブール式とか言うんですが、これがすべての基本。コンピュータのLSIの設計はブール式だし、NPと呼ばれる様々な分野の問題(もちろん暗号系も含まれる)もブール式の充足性問題に帰着されます。
a∧b, a∨¬b
とかね。こんな簡単なものが、ほとんどあらゆるものの基本だと言うのが凄い。問題は変数が多い時に難しくなります。千とかは既に当り前らしい。
BDDは命題論理式を最大共有された二分木で表すもので、ZDD は0に向かうノードを省略するもの。BDDは同じノードに向かうものを省略するので、BDDは対称で、ZDDは非対称な問題に向いてます。モデル検証とかにさんざん使われました。その辺りが90年代の認識だったんですが…
ブール式は集合演算でもある。aとかは「aがある」とか読むわけ。そして数百万の要素の集合を圧縮して表示できるということになると、商品管理とかの方の応用が盛り上がったらしい。
で、Knuth 先生のあれに載って、それから大きな予算が付いてという、
基礎研究での超サクセスストーリー
http://www-erato.ist.hokudai.ac.jp/
ということになったらしいです。Zero supress BDD で ZBDD と呼んでいたんですが、Knuth 先生がいけてないから ZDD にしろと言ったらしいです。
重複を許す集合を表す Seq BDDは20年ぶりに発見されたんだけど、Suffix Tree の最大共有と同じものだと。でも、そこに演算を定義できるのが画期的だと言うのを BDD 側から発見できたらしい。これも、
非常に簡単な構造が Break Through になる
という例だと思う。きっと、まだまだ、そういう見落としがある。単にライブラリを使うだけでなく、その基本に立ち戻るのが常に必要だね。
BDD は、もう普通の技術で自分でもライブラリ持っていたりするけど、手抜きなのをスライド見ながら発見したり。久しぶりにいじってみるか。
＊ ＊ ＊ ＊
ソフトウェア科学会全国大会は無事終了しました。当日の運営の方が、その前までのメールのやりとりよりも楽に感じました。運営と言うのはそうあるべきだな。最終日、亀山さんにぶち切れていたのを目撃した人も多いかも :-p まぁ、反省を活かして来年の人には楽をしてもらいたいと思います。
受け付けにいるよりも、発表聞いて質問している方が多かった。まぁ、それが正しい学会の参加の仕方だな。
いろんな人に迷惑かけました。いろいろありがとうございました。
一つの理由は、雨戸締められちゃうと、ずーっと寝ちゃうから。13時間ぐらい平気。18時間ぐらい寝てたこともある。起きると夕方というあれですね。
東京は夜明るいから雨戸開けても真っ暗にはならない。田舎の夜の真っ暗さの、どうしようもなさ、も嫌いではないんだけど、東京で体験するのは難しい。いや、雨戸締めろよ。
テレビとかレコーダとかにLEDがたくさんついていて結構明るいんだよね。そう言えば蛍光管な時計をいまだに使っているし。輝度は暗く設定するんだけどさ。
まぁ、朝日があたったからすぐに起きると言うわけでもなく。
＊ ＊ ＊ ＊
ソフトウェア科学会は、学生の発表はOB一名以外全部終りました。自分の発表も終った。今夜はガレリアで懇親会です。一般営業もしているようです。
直前までスライドだめだめだったのが、ぐっと良くなっていた。まぁ、気分はわかるけど、あんまり良くはないね。でも、発表良かったよとは言うけど。
一応できてるんだけど、途中、狭くなってるのね。そこで渋滞。まぁ、そのうち、いろいろできるんでしょう。でも道よりモノレール大学までのばして欲しいな〜
うみそらトンネルは、産業支援センタの丁度裏側に出ちゃうので、ぐるっとまわるはめになるみたいです。でも、少し早いかな。
車運転しない人なので、長距離自動車に乗るのは、ちょっとつらい。
日本ソフトウェア科学会全国大会は、なんとか進んでいるようです。受け付け意外にスムースだった。奥様偉い。
朝、10時の発表で結構準備不足もあって、質問、突っ込まれまくった。まぁ、これからだな〜
9/20 までに参加費振込でしたが、僕を含めて忘れた人がたくさん。なので、会場で徴収もありになったようです。
初日の受け付けが心配ですが、行列はできるでしょうけど、なんとかなるでしょう。事務局が金額入り番号入りの領収書とか送って来なければ、もっと楽だったんですけど。あるいは、けちらずにもっとたくさん送ってくれれば。そこがネックになる予感。
いろいろあるだろうな〜 今から楽しみです。
今日は高専の授業もあるしな〜
