2010年06月

とか，オレンジ本（Pierce の Types and Programming Languages）を読み直して演習問題解いてて感動した（ex. 13.5.8）．だがしかし，学生らにはその辺の作者の意図を読み解くのは無理だったらしい．教科書読むってのも大変だよねぇ．

関係データベースの分野で： Select-Project-Join

軍事(戦闘機)の分野で： Self Protection Jammer

Haskell 分野で： Simon Peyton-Jones

SPJ normal form （データベース的な意味で）と叫ばれるたびに笑いをこらえるのが大変だった．Haskell にデータベース操作のプリミティブが入ったりしないかなぁ，LINQみたいに．そしたら Haskell 内に SPJ normal form が…　とかなりそうなのに．

関連して思い出したので．何故か研究室で定期的に上がっていたネタ，ATM．いつも５個ぐらい挙がってた気がするのだけど今思い出せるのは４つだけ：Adobe Type Manager, Anti Tank Missile, Automatic Teller Machine, Asynchronous Transfer Mode. もうひとつくらい定番で挙がっていた気がするのだけど思い出せない．なんだったっけ？

これまでのはクレジットカードと一体になって黄金に輝いていたのだけど，今回のはじみ〜な感じのICカードになってくれた．前のは身分証として提示するには少々問題があった（クレジットカード番号取られちゃうかもとか，一見して身分証に見えないとか（とある店の店員は身分証と認識してくれなかったりしたし））ので，単純な職員証になってくれてよかったと思う．

そういや免許証の更新も一ヶ月切ったなぁ．さっさと更新せねば．

爆発するかどうかはよくわからない．

OB/OG会主催の模擬練習会があったので問題だけ眺めてみた．最後のG問題を抜かせば全ての問題に対して想定解法と同じ解き方を思いついたけれど，実装しろとか言われるとめんどいのでやりたくない．

とりあえず問題A～Cは自明．問題Dはただのダイクストラでなく巡回順が決まっていることを活用してやらないと間に合わないのかなぁと思ってたら出題者の意図もその通りのようだった．まあ，同じ探索がかなり繰り返されるから再利用しなきゃねと考えた後に，巡回順が決まっているから情報の流れがDAGなのでただのDPでオッケーと気づく，というルートかね．問題Eは実装したくないだけ．端点の解だけで最適解を含むかどうかをちょっと悩んであげれば解き方は一意に定まるような．問題Fはやるだけなのでやるきにならず．問題Gは見積もりが思いついた解法では甘かった．もう少しひねりましょうと．なんにせよ実装なんかしたくない．

閑話休題．運営が微妙な感じなので小言を投げた．組織立って動くならば手順の最適化はしてしかるべき．

片面を６枚分，思いのほかjpegも大きいということを認識．

まあ，失敗写真というか残しておいてもしょうのない写真ばかりなので整理してやればメディア節約できるだろうけど面倒なので気にしない．

たまにはプリントしてみるか．

研究室のサーバの定期バックアップということで，初めてBD焼いた．大容量なのに意外と焼く時間が短く感じた．初めてのCD-RドライブはCD一枚焼くのに１５分かかったというに…

でも一枚の片面BDRには25GBしか入らないのでRAWで撮った写真の全データを保存しておくには枚数がかさみすぎるんだよなぁ…　二回出かけたらBDR一枚なわけで．明らかな失敗写真を捨てれば問題ないのだろうか？　とりあえずそのうち整理してみよう．

そういやVMのディスクイメージもデカすぎて片面だと入らないっけなぁ…　あと１０倍入るようになってくれるとありがたい．

今年の実験を見た限りでは制御用のドライバ回路をゼロから組ませるのは大変だなぁと．それでも空飛んだので今年の連中はよくやった．そして発表に編集した動画を持ち出したのも良かったかもしれん．実験の発表なら面白くなければいけない．もう少しテンポよく行けるとよかったけど．

さて，来年の実験のネタは何にするかね．SunSOPTひとつお亡くなりになったけど来年もSunSPOTネタで動くものにするが，はたまたFPGAでリダクションマシン作って遊んでみるか．FPGAの方が工作量が少なくて楽かもしれないが…　派手さに欠けるよなぁ．

とりあえず余ってる部品でそのうち空中に停止するように作り変えるか．あとは適宜重心をとれるような制御と．駆動系のパワー自体も一度測定しておいた方が良いなぁ．

わーお，思ったよりだいぶ多いぜぇ．まあ，普通には交通費か．

充電できないリチウムイオン電池を保護回路バイパスして充電してみた．充電器にも保護回路入っているので問題ないと思うけど，一方でやっぱりちょっと怖かったりする．まあ，本番は明後日なのでそれまでもてば問題ないから良しとしよう．

Suffix tree を線形時間で作るアルゴリズム．しかも文字列を先頭から処理できるオンラインアルゴリズムになっている．なぜかその元論文を読んだのでここにメモっておく．

とりあえず，二乗コストで suffix trie をオンラインに作るアルゴリズムがベース．この suffix trie は，各リーフが suffix に対応し，中間ノードは部分文字列に対応する．このアルゴリズムは，空文字列に対応する suffix trie から始め，それを逐次的に更新していくことで文字列全体に対する suffix trie を構成する．１文字追加することに対応する suffix trie の更新は，各ノードに持たせた suffix link を辿って行われる．suffix link は，そのノードの表現する部分文字列から先頭の一文字を取り去った文字列に対応するノードへのリンク（つまりは，suffix を取る操作に対応した状態遷移のこと）．

このベースとなるアルゴリズムは１文字分の更新にtrieの大きさに比例したコストがかかるため，二乗のコストがかかる．

Ukkonen のアルゴリズムのアイデアは，分岐せずに一列につながった suffix trie のノード達をその根元のノード一つで代表させること．実際のところ，ベースアルゴリズムで構成する suffix trie にはこういった一列に並んだだけのノード列が多く現れ，それらの suffix link の更新が非常に無駄だと感じる．

一文字追加する際の更新で少々面倒なのは，一纏めにされたノード達を適宜分割する操作が必要なこと．これ以外はベースと同じで，一纏めになっているノードに対して suffix link を保持していく．この作業は順次大きくなっていく木を下から上に辿るように行うだけなので（横に飛んだりするけれど概ね全部の分岐で上に向かうイメージ），結局のところならし計算量で線形コストになっている．あとは頭のいいインデックスを使っていて，その更新作業中にループが出てくるが，こちらもならしでループ本体が線形回しか呼ばれないので問題ない．そのならし計算量の見積りは，インデックシングに使われている文字列上のポインタ二つが常に大きくなる方向にしか動かないことによる．

まあ，並列化できそうにないね．

入力サイズnに対してO(n^2)な回路生成器ではやはり無理があった．燃料できてるのに送信すると not connected とか文句を言われるものが大量に…　2x2の行列で数字が大きめとかタンクが多いとかいう問題が結構全滅．3x3以上とか答えが分かっても送れない罠．

んで，終了数時間前にもう少し考えたらO(n)で作れる回路があることに気がついたので実装＆再提出．でも時間ギリギリかつ過去の答えを半分くらい消してしまっていたので答えの再計算に時間がかかるわで結局点数に影響なかった気がする．あとは提出自体にも時間がかかるので送られていない答えがそれなりに溜まっていた．残念．

最終的には，4000台弱の車に対してそのちちょうど半分くらいに燃料供給できたらしい．中途半端以外のなにものでもない成績だ…

そういや一人チームってどれくらいあったんだろう？　チーム人数の統計とかアンケートで出ないかなぁ．

あとは並列計算をどれくらい使ったのかとかの情報も興味があるところ．今回のは小型の回路を構成するための探索とか燃料の計算とか簡単に並列計算できそうな気配だったのだけど，参加者で並列処理したのはどれくらいだっただろうか？　つか，準備が間に合えばEC2+Hadoopとかで力技とかやってみたかったなぁ．来年までには準備しておこう．

順位確定： 32位みたい．

score:                  681.366
others' cars solved:    1956
cars submitted:         0

三進数エンコードの意味がやっと理解出来た．ここら辺のエンコード＆デコードはHaskellが楽だなぁ．それにしても下準備に２日もかかるとは情けない．

そして二日間で理解したこと：　ちゃんと寝ないと頭が回らない．考える前にプログラムを書いて動かすと吉．色々と頭を回すと（数学的な構造を探しだすとか）時間の無駄．

さて，次は「問題取得→簡単なら解く→提出する」を自動化するスクリプトでも組むか．

任意の系列を生成する回路を組めるようになったけれど短くできないなぁ．長さnの系列に対して最悪 O(n^2) かかる．

うーん，もう少し使いやすい回路片をランダムないし全探索で探すべきかねぇ．

とりあえず次はternary encodingをどうにかせねば．

回路組みあがったぁ　→　入れ物に詰め込んだぁ　→　配線があふれるので配線し直しぃ　→　詰め込んだらちゃんと納まったぜぇ　→　電源投入ぅ　→　火ぃ吹いたっ！

いや，配線し直した後の回路テストで無事動くことを確認した後に，絶縁処理の徹底をし無かったために詰め込んだらショートしたってオチなのだけど．久々に煙モクモクな場面を見た気がする．配線焼けまくりだったし．

うーん，自分が全部作業するときには意識せずとも気を付けているのだけど，他の人間の作業を眺めている時には注意が働かないみたい．残念，もういちど．

色々なところで同じサイズの子猫がみゃぁみゃぁ鳴いていた気がする．そういう時期だっけ？

水元公園に早朝の花菖蒲を見に＆撮影しに行くかと思って出かけたのだけど子猫二匹に捕まってそいつらを撮り続けていた気がする．とりあえず明るいレンズが無いと薄暗いなかのビデオ撮影は厳しいかもしれないなぁ，NEX-5．そして子猫達には70300Gのレンズが一番興味深いらしかった．STFもSEL1855も反応薄かったのだけどなぜか70300Gの時だけ無茶苦茶寄ってくるという．そして素早いので薄暗い中では被写体ブレして上手く写せなかった…　いくらISO感度を結構高く出来るとはいえやっぱり明るいレンズ必要だわ．

細かく話していたら１ページ２分以上のペースになって時間が足りなくなったというオチ．

閑話休題．Google の MapReduce でアプリケーションを実装する際にも，その計算を Map と Reduce に分解するのが難しいって問題が存在していたのねと．言われてみればたしかにそのとおりな気がする．基本的にMapReduceは関数型言語の世界での map しかやらないという認識になっているので，自分のイメージとしては並列化出来る部分は Map に押し付けて残りの逐次処理はキーをひとつにしてReduceに押し付ければいいやくらいに考えていた．ぶっちゃけこれでいいんじゃないかと未だに思ったりするのだが…　結局バケットソートする意外にreduceの段階でキーを変える必要性がわからない．分からないということは難しいに違いない．

そういや講演者用にペットボトル入りミネラルウォーターを頂いのだけど，これが普通のミネラルウォーターであったのが微妙に残念な気分．NII オリジナルの水とかでペットボトルにマークが入っていたりするとやる気がわくかもしれない．関係ないけど富士すその天然水でもやる気でるなぁ．

明日のスライドは大方出来上がった．あとは練習してしゃべりにくいところを細かく直せば良かろう．

ということで寝る．

多分持ち時間６０分なので３０枚強のスライドで丁度良いはず．スライドの初版をあげるのに経験上１枚毎に２０分を要するのでおおよそ１２時間あれば初版ができるはず．

うーん，出だしのアグレッシブさが足りないなぁ…

花菖蒲が思ってたより微妙な感じであった．まあ，狭いからしょうがない気もするのだけれども．そして黄色い花菖蒲は背が低くて周りの背の高いヤツらの影になってて残念．もう少しなにか考えて植えて欲しいような…

GNOMEのアプリケーションでrdesktopとかのフロントエンドになるGUIらしい．いままでrdesktopをダイレクトに使ってたけどtsclient使ったほうが起動が楽．

知らない便利GUIツールが多い気がする今日この頃．

イリウムイオン電池でモータを回そうとしたら過電流保護回路のせいでモータを回し続けることが出来ないという罠にはまった．うーむ，過電流保護だけ外す方法はないのだろうか？　悩ましい．

ふとおもったのだけど2013年に起きるかもしれないと言われている巨大な太陽フレアを無事に乗り越えるためには，やはりHDDとかの磁気による記録媒体ではなくBD－Rとかにデータを移しておいた方が良いのだろうか？　そう思ってHDDのデータ量を調べてみたけれどデジカメのデータだけで６００GBを超えるという状況に絶望した．単純に片面BD-Rで２４枚が必要とか焼く気にならない．

とりあえず光学記録媒体の容量がカメラの画素数より速く大きくなることを願う．

ううむ．設定とキャラが多すぎてワケ分からん．来月の中巻が出たときにまた読むか．

ホライゾンの第3巻上巻を手に持ってなんか薄くなったなぁと思ったけど，来月の新刊情報を見たら来月は第3巻中巻なのね．上下巻ではついに印刷所の限界を超えたのだろうか？

とりあえずAW５巻は読み終えたのでデカブツに取り掛かる．

http://code.google.com/p/mozc/wiki/LinuxBuildInstructions のインストラクションに従うだけ．最後に書いてる deb パッケージの作成でインストールするのが一番楽．それに気づかず上から順に作業した挙句にそれらが無駄だったことに最後に気づくという罠．

そして変換はストレスなく出来ている．予測入力も頭良いし．Windows版に比べて辞書が貧弱なのはどうでもいいし．満足．

面倒な用事も済んでまだ日が出てたので，NEX-5にズームくっつけて紫陽花の咲き始めた六義園に行ってきた．

んで，何種類かの紫陽花が色つきで咲いていた．玉紫陽花はまだまだ蕾すら無い．西洋紫陽花は色がついてなかった．

このレンズもちょいと絞るとよさげな気がする．解放だとポケポケ．とはいえ元が暗いのでちょっと絞るとF8だったりするのだけど

「受信」ってどういう定義なんだろう？　

あと，「協会の放送を受信することのできる」ってのは，原理的にできればいいのだろうか？　例えば，NHKの電波の来ないところにテレビを設置した場合にはどうなのだろうか？　また，仮にNHKがスクランブルをかけた場合にはどうなるのだろうか？　スクランブル解除できる状態でないと受信するできることにならないのだろうか？　それともスクランブル状態でも受信できることになるのだろうか？

B-CASカードの無いデジタルチューナは「協会の放送を受信することのできる」ってのに入るのだろうか？

PCにデジタルチューナを載せ，古いOSでそのPCを運用する場合にはどうなのだろうか？

PCにデジタルチューナを載せ，NHKをチャンネル選択出来ない再生ソフトを使う場合にはどうなるのだろうか？

また，ワンセグ対応の携帯からワンセグ用のアンテナを引っこ抜いたらどうなのだろうか？　アンテナ引っこ抜いた時点で「放送の受信を目的としない受信設備」になるのかどうか？　ビデオ再生専用のテレビとかが当てはまるのだから，アンテナを引っこ抜いたものは受信目的でないと解釈されるべきだと思うのだが．

結局のところ「受信」ってのがよく分からん．

曇りだったけど予定通りNEX-5Dを持って旅に出た．重たいので追加のレンズはSTFのみで．

まず，新宿御苑．この土日は無料．多少時期が遅かったけどまだ見られるバラが咲いていた．

で，パンケーキ．換算で24mmの画角なのでちょいと広い．まあ，旅行先とかで風景やらランドマークを撮ったり記念撮影するには良い気がする．そして等倍だと眠たい気がする今日この頃．ぶれたのだろうか？　縮小すりゃ問題ないから気にしない．

そして手ブレ補正付きのキットズーム．パンケーキに比べると大きいけど本体を含めて持ちやすいので大分小さく感じる．とりあえずワイ端とテレ端で．手ぶれ補正は動画を撮るときに非常にありがたい．ぶっちゃけ多少出っ張るのを気にしなければパンケーキ要らないんじゃないかと思う今日この頃．

そして本命のマウントアダプタ＋STFで．本体が軽いのでレンズ振り回しているだけの感覚．とりあえずよく写るので文句ない．本体優秀．ただ，やっぱり手ブレがきついかも．特に動画だと再生時に気持ち悪くなるような気がする．小さな三脚で体に固定するか，ネックストラップでテンション掛けるかしないと安定しない．要修行．

そのままの勢いで旧古河庭園．年間パス買ってるのでたまには行かないと損．もう面倒なので STFつけっぱなし．アングル液晶は結構便利．ウェストポジションに置いてネックストラップでテンションかけてとると安定するかも．ハイアングルだとどうやって安定化させるか悩む．

最後に王子駅手前の飛鳥山公園の線路側に咲くアジサイの様子．色付き始めたところでまだ大分白いけど，中途半端な色の付き具合が面白い頃．

結局，付いてきたパンケーキとズームはあまり使わなかったけど…　別のレンズで十分遊べることはわかった．ただ，焦点距離が長めのレンズで動画撮るには何らかのブレ対策をしないと見にくい動画になりがちかも．できれば今のサイズのままボディ内手ぶれ補正が欲しいところ．

DCモータをPWM制御するためのモータドライバ回路をFETで実装するってのも一般の学生らには簡単ではないらしい．PWMの信号自体はマイコンから生成するし回転方向一定でよいので，モータドライバにはスイッチのためのFET1つとそれを完全に駆動するための信号増幅器としてトランジスタが１つあればよいはず．あとは適当に抵抗少々．でもまあ，これくらいでも大変なわけだわな．

そういやPWM制御もFETも知らねー時に，リレーとRC発振回路と可変抵抗でスイッチングの周波数変えて回転数調整したことがあったなぁ．今考えてみると結構謎なことやったもんだ．

センターキューブというかエッジキューブというかの９０度その場回転ができるので，コーナーキューブを合わせてセンターキューブ回すだけで終わりかな？

フラットにした状態でのコーナーキューブの配置はフロッピーキューブと変わらん気がするのだけど…　同系統のスワップすることしか出来ないっぽいし．これが正しければパズルとしては簡単．

１．問題検出結果が上流から下流に流れ着くまでに時間がかかる．この伝達時間が問題検出間隔より大きければ上流は下流が問題対処していないと観測する．

２．何が問題であるかが上流からは明確にされておらず，下流の自発的な判断・対処が不能である．

この状況で「下流が対処しないからぶった切る」とか言われても…　完全に詰みなのだが．

ハァ

本体の出荷メールがついさっき来た．マウントアダプタだけフラゲで本体は発売日当日か…

残念なことにペリカンさんが運んでくるので受け取りタイミングが難しい．

ネットワークの上流を管理しているところから「お前んとことのネットワークでQQLiveのP2P通信が検出されたから対象PCをクリーンインストールしろ」とのお達しがあった（QQliveはトロイの木馬を入れるらしく，クリーンインストールしないとダメらしい）．とりあえずIPは分かっていたので，dhcpdのログからPC名を割り出し本人に確認．が，本人曰く「QQLive使ってない，詳細な情報をよこせ」．

よく分からんのだけど，可能性としては TrojanDownloader.hogehoge 系に感染して知らぬ間に QQlive をインストールされていたとかだけど…　 それにしても対策ソフト入れてあればトロイの木馬の感染を防げただろうにそれができてないってのも問題なわけで．この時点で何に感染しているか分からない危険マシンなので即クリーンインストール行き．ちゃんとやったかどうかは知らんけど．

まあ，無駄かつ法に触れそうなP2P通信は元を絶つに限る．

閑話休題．「P2P通信禁止」と上から言われるのだけど，そのP2P通信ってのの定義がよく分からないのは問題だと思う．P2P通信であることの明確な判断基準がなければ，「研究に使うための例外の申請」という行為すら出来ないし．

ファイル共有系のP2Pソフトウェアとか，匿名でメディアをブロードキャスト可能なP2Pソフトウェアとか，ここらへんははっきりアウトであって使うべきでないソフトだと容易に認識出来る．

けれど，それらの危険なのをおいとくとして，海外の研究者との議論などに使用するSkypeはどうなのか？　こいつに関してはググればP2Pだと分かり，部局によっては申請が必要ですよと明記してある．でも，頑丈なファイアウォールなどのせいでP2P通信出来ない時には中継サーバが入るのでP2P通信では無くなるのではないかとかの疑問は残るし，そもそもこれがP2Pだと指摘されない限り気づかない人間のほうが多いと思われる．

さらに分からないものとして，テレビ会議システムのPolycomがある．これはh.323のプロトコルを使っているのだけど，それはP2P通信と識別さるんじゃないのか？　とか．二つの端末が同等であってサーバクライアント式でないのだから，きっとこれはP2P通信だろうと思う．

さらにいえば，そもそもIPってP2P通信なんじゃないの？　とかの疑問も．広域ネットワークに集中管理的なサーバがあるとそれを潰されたときのダメージが大きいから，それが起きないようにと設計された皆対等なプロトコルであるはず．まあ，極論だけど．

結局，P2Pってよくわかんない．上流の誰か明確に定義してくださいませ．