読者です 読者をやめる 読者になる 読者になる

あざらしとペンギンの問題

主に漫画、数値計算、幾何計算、TCS、一鰭旅、水族館、鰭脚類のことを書きます。

フカシギの数え方

先日、北海道大学に行く機会があったのですが、そこの博物館で標題の「フカシギの数え方」という展示が行われていました。これは、北大の湊真一教授率いるプロジェクトの概要と成果を一般向けに紹介するもので、元々は今年始めまで東京でやっていたのを撤収後移設したものです。展示スペースには内容と関係したおもちゃが用意されていて、子供から大人まで幅広くターゲットにしていることが伺えます。主な内容は、組み合わせ爆発の恐ろしさと、それを解決するための圧縮情報処理技法ですが、ともかくは次の動画をご覧になってください。(丸投げ)


『フカシギの数え方』 おねえさんといっしょ! みんなで数えてみよう! - YouTube

題名にある「不可思議」とはすなわち10^64=10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 のことです。これだけ膨大な数の組み合わせを全部数えるなんてことは普通は不可能なわけです。ところが、全部の組み合わせを小さく圧縮した形で表現して、それを展開せずに処理することができれば、こんな数の組み合わせでもなんと普通のPCで処理できてしまうのです。その中心的技法である ZDD (Zero-suppressed decision diagram) による圧縮表現は90年代初頭に湊教授によって開発されたもので、D. Knuth教授曰く the most beautiful construct in computer science とのことです。

記憶によれば北大での展示は来年まで、少なくとも今年中はやっているので、機会があれば是非ご覧になってみてください。

北大のメインストリートです。…長いです。

f:id:azapen6:20131009045015j:plain

フカシギの数え方」の展示の一部で、先の数え上げが表になっています。桁数の増え方が辺の長さの二次関数になっているように見えるのは気のせいでしょうかね?

f:id:azapen6:20131009045358j:plain

最後に先の動画の続きを貼っておきます。


「フカシギの数え方」 同じところを2度通らない道順の数 - YouTube