天気寺悪酢

軽い放置プレイはいかがでしたか？今日は楽です．3時限onlyです．

昨日とかは結構鬼で，１〜３時限まで授業で，14時半くらいから輪講2本，さらに21時から輪講というスケジュールでした．おかげで明日までのレポートが進んでない・・・．もっと早くやっとけよって話なんですけど．

でまあ頑張ってるんですが，修論テーマに向けてプロジェクトに配属されるのが5月の連休明けくらいらしく，オレはバイオ系のプロジェクトに行きたいなと，若干心を決めた感じで．バイオって言っても，生体工学バリバリのごついこととかはたぶんやらず（やるなら嫌だ），たんぱく質はこんな配列で，とかその程度のような感じです．

今やってる輪講で，バイオ関係の論文が2本あったんですが，それがかなり面白くて，片方ではLCSを求めるアルゴリズムが出てきました．スミス・ウォーターマンっていうらしいけど，オレは違う名前で覚えてたんだよなぁ．

スミス・ウォーターマンは，長さがmとnの二つの文字列のLCSを，O(m*n)で求めるってやつなんです．大体の動きのイメージとして，二次元の表を左上から埋めていく感じなんですよね．で，あるフィールドは，それの上と左と左上のフィールドにしか依存しないんで，それら3つが分かれば，次のフィールドを埋めれるんですよ．これで何が美味しいかっていうと，依存関係がない部分は並列処理ができちゃうんで，斜め方向のフィールドをいっぺんに埋めれるんですね．左上から，右下方向に，ひとつずつずらしながら．

そうすると，プロセッサがmax(m,n)個あると，実行時間がO(n+m-1)になると．すげーわけです．

もう一個の論文もすげー面白くて，「反応の依存関係を調べる」みたいなテーマなんですけど，そのためにグラフとpqを使うんですね．pqには，反応を，それが起こる確率をキーとしてぶっこんで，確率の低い方から取り出してくるんですが，この辺をソートして実現したり，もしくはグラフアルゴリズムの方面からアプローチできないかと，考えてたわけです．結局良い方法は思い浮かばなかったんですけど．

でも今までやってきたことともリンクするし，ハードウェアとバイオっていう2つのオレ的未開拓領域にも踏み込めるんで，これはいいかなぁとおもっちょるわけです．脳みそが爆発しそうですけど．