Reblogged from otsune
動画のおねえさんは深さ優先探索によるプログラムを使っていると思われるが、それだとスパコンを使っても10×10マスの格子を解くのに25万年も掛かってしまう。そこで、高速化のためにゼロサプレス型二分決定グラフ(ZDD; Zero-Suppressed Binary Decision Diagram)と呼ばれるアルゴリズムを利用することにした。このアルゴリズムを開発したのは北大の湊先生で、ZDDによりすべての経路を見つけ出すアルゴリズムとしてクヌース先生のSIMPATHを使った。ZDDについてはクヌース先生も強い関心を持っていて、 The Art of Computer Programming Volume 4, Fascicle 1(TAOCP 4-1)ではBDD/ZDDの詳細な解説を読むことができる。演習問題の解説だけで書籍の半分を使っていることからしても気合の入れようがわかるだろう。
実際に自分のノートPCでZDDアルゴリズムを使ったコードを走らせたら、ほんの10秒程度で10×10マスの問題を解いてしまった。おねえさんがスパコンで25万年かかった問題をノートPCでたった10秒である。約8千億倍の高速化だ。これだけ劇的に変わるとやっぱり楽しい。そして、アルゴリズムの重要性を再認識させられた。
良いもの。悪いもの。: 「フカシギの数え方」の問題を解いてみた (via otsune)(via peckori)
(via higure)
世界初の業務用レーザープリンタ、IBMの3800。印刷スピードはそこそこ早かったとか。
レーザープリンタのための書体さて、それではArialがいかに生まれたかを見ていきましょう。1975年にIBMは最初の業務用レーザープリンタ「3800」をリリースしましたが、その初期モデルに搭載されていた書体はタイプライター由来の字幅固定のものばかりでした。ちなみに一般家庭用冷蔵庫を5個並べたほどの大きさで解像度は240dpiという代物です。これのバージョンアップ機「3800-3」をリリースするにあたりIBMは字幅がプロポーショナルであるTimes New RomanとHelveticaの二書体を搭載するためMonotypeに接触します。Helveticaを所有していなかったMonotypeは、IBMにHelveticaに替わるカスタム書体の製作を提案、これが許可されてArialプロジェクトがスタートしました。ちなみにHelveticaを持っていれば話は楽だったかというとそうではなく、どのみち3800-3用にビットマップデータを新規に書き起こすことになっていましたので、いずれにせよ書体の新規製作と同等の作業量は必要だったのです。これについては後編にて解説します（たぶん）。
こうして1982年に生まれた新しいサンセリフ体ArialはIBMのプリンタではSonoran Sans Serifという名前で搭載されました。アリゾナ州のIBM Tusconの目の前にあるソノラ砂漠にちなんで付けられた名前です*¹。Times New RomanはSonoran Serif、他にも搭載されたプロポーショナル書体はどれもSonoranで始まる名前です（このプロジェクトはMonotypeにとっては相当な儲け話であり、IBMに独自の名前を使わせるぐらいはあっさり認めたそうです）。その後にMonotypeは、同様のニーズを持つ顧客にHelveticaの安価な代替書体という魅力をより明確にアピールするためにArialを完全にHelveticaと同じ幅に設定しました（1989年完成にPostScript版が完成）。これに乗った顧客の中で最も有名なのがMicrosoftです*²。1990年にWindows3.0にTrueTypeフォントとして搭載されたArialはその後OSの普及とともに爆発的に使用頻度を増していき、1996年にはコアフォント（インターネット用の標準フォントパック）に指定され、今ではVerdanaやGeorgiaなどとともにWebページ上でMacでもWindowsでも確実に表示できる書体の一つとなっています。
*¹ 以前Lucidaの回でSonranと記載していましたが、正しくはSonoranです。失礼致しました。
*² このことを例に「Helveticaのライセンス料をケチったからMicrosoftはArialを搭載した。Microsoftはタイポグラフィへの関心が薄い」といわれることが多いのですが、これは違います。最終的にはWindows用のArialの開発、ライセンスにMicrosoftが投じた予算は小国を賄えるほどだったそうです（それでもHelveticaで同じことをやるよりは安かったのかもしれませんが）。何にせよArialが現在かくも人気なのは偏にMicrosoftの手厚いサポートのおかげです。
(via voqn)
