Main | August 2004 »

2004.07.29

山の前

に一応課題を終わらすことができました。CGとDNAコンピュータについて。
下のはCGの課題で作成したwebページ
http://homepage3.nifty.com/DO/cgreport04/index.htm

あと、洗濯して、準備して。

というわけで明日(7月29日)夜から、8月1日、もしかしたら山の上で一日待機とかあるかもしれないので2日に下山予定です。涸沢、穂高の方へいってきます。

| | Comments (0) | TrackBack (0)

2004.07.28

7月までに課題は

を合言葉にがんばっていたのですが、山登りが急遽入れてしまったために、かなり予定がきつきつに。
萩谷さんのは一応終わって院前の課題はCGのみ。プロバードさんの授業を聞きながら?CGはフラクタルと、テクスチャマッピングができたらしい。透視変換はやったことあるからきっとできると信じてる。
明日中に果たしてできるかが勝負。できなかったら下山後ということに。
でも、経験上、下山後は1週間は身動きがとれないからそうなるといろいろ厳しいよなぁ。

| | Comments (1) | TrackBack (0)

ゲーム

テレビゲームとデジタル科学展に行ってきました。
テレビゲームをみにいったはずが、コンピュータ創世記のいろんなやつがあって、驚いた。ENIACをはじめ、初期のIBMPC、マッキントッシュ、初のPCであるアルテアなどなどがありました。
 個人的にはテレビゲームより、こちらのほうが見所満点でした。テレビゲームはアタリの成功までがあったのですが、それ以降がぽっかり空いてました。今の話とつながっているから難しいのかなぁと思ったりして(販売統制とか)
そのあと上野夏祭りで楽焼きというのをやって、コップを作りました。

 夜は山に備えて、久しぶりに走りました。肉体的にストイックになると、精神的にもいい感じでひきしまるかなぁといつも思うのですが、普段は両方だらだらで

| | Comments (0) | TrackBack (0)

2004.07.26

山の買い物

をこじたとしてきました。

リュック、靴、レインコート。この三つでかなりの諭吉を必要とします。さらに、ヒュッテ代、移動代などを含めるとさらにいくけど、それでもそこで得た経験は今後の生活にそれ以上の利益をもたらすと思います。(と思わないといけない。)少なくともお昼過ぎに起きることはなくなる。1ヶ月ぐらいは。

そして、山に向けてなまった体を鍛えようと思っているのだけれど、何しろ時間が無い。あと5日?今日も久しぶりに走ってもうかなりきているのだが、ちょっときつめにいかないと。

7、8月の予定がつまってきた。7月中に課題を終わらせようと思ってたけど、山あるからきついよなぁ。山の上で課題は嫌だしなぁ。

| | Comments (1) | TrackBack (0)

2004.07.24

演習3打ち上げコンパ

にいってきました。非常に貴重な話をいただけたのと、N山さんのすごい才能に圧倒されたのと、お腹満腹でした。
あまり公にはできないので話をききたい場合は直接きいてください

| | Comments (0) | TrackBack (0)

2004.07.23

直前

ですが、今日学校で発表する予定のプログラムがまだ動いていません。修羅場

| | Comments (0) | TrackBack (0)

登山二回目

が急遽1時間前にほぼ決定。出発日は一週間後の予定。
急いで準備しないと間に合わない。どうしていつも前もって準備できないのかと思ってしまう。

体力的にはもうどうしようもないが、気休めに少し鍛えよう

| | Comments (0) | TrackBack (0)

BIP2004

自分で言うのもなんですが、バイオインフォマティクスコンテストの問題2で最優秀賞をとってしまったらしいです。驚き

| | Comments (0) | TrackBack (0)

2004.07.21

Skip List

カテゴリが授業名みたい

データを保持する二分木は、バランスが崩れて探索時間が悪化する場合があるので、平衡化して深さを均等にする必要があります。

例えば、AVL木は、どの節点も、その節点が持つ、二つの子の高さの差が1以下になるようにするという制限を加えることにより平衡化をはかっています。
また、赤黒木は全ての節点が赤、黒のどちらかの色を持ち、(1)もし節点が赤なら、その子は二つとも黒 (2)NIL nodeは黒 (3)根から葉へのパス上にある黒の接点の個数はどれも同じ という制限を加えて平衡化をはかります。

どちらも、新しい要素を挿入したり、削除したりして、この制約が守られなくなったときは、平衡になるよう、回転操作などを行わなければなりません。

Skip Listの情報はここから得ました。
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dv_vstechart/html/datastructures_guide4.asp


その一方で、Skip Listは、ソート済みリストを保持しておきます。それぞれの要素は次の要素へのポインタだけを持っておきます。
ただ、このままだと、探索は順に調べていかなければならないので、平均(要素数/2)回比較を行う必要があり、全然役に立ちません。そこで、Skipの文字通り、次の要素だけではなく、更に先の要素へのポインタを持つようにします。例えば、2で割り切れるindexを持つ要素が2個先の要素へのポインタを、4で割り切れるindexを持つ要素が4個先の要素へのポインタを持つ、8で・・・としておきます。すると、ある要素xの探索を行う場合には、8個先にある要素とxが小さいかかどうかを比較し、もし大きいなら、8個先に移動して調べるということになります。
これは二分木で、もしその節点で調べて、大きいか、小さいか調べて、大きいなら右の子を調べる(つまり左の子、その子孫をskipしている)ことと同じです。この時の探索時間は要素数がN個のとき、O(lg(N))です。

ただ、挿入、削除を行うとなると、2で割りきれるindexが2で割り切れなくなったりしてしまい、バランスが崩れてしまいます。
そこで、理想的な状況では、2個先の要素へのポインタを持つ要素は全体の50%、4,2個先へのポインタを持つ要素は25%、8,4,2個先へのポインタを持つ要素は12.5%・・という観察から、新しい要素を加える場合には、0.5の確率で2個先へのポインタを持つ要素とする、0.25の確率で4,2個先へのポインタを持つようにする・・・とします。

こうすることにより、ほとんどのデータにおいて、うまく理想的な状況と同じ状況が作り出せます。削除のときは単純にとりのぞいてしまいます。(削除の時は、確率0.5で2個先の要素へのポインタを持つ要素を取り除いていることになり・・)

こうして作られる、SkipListは、AVL、二色木などの平衡二分木と同様の性能を持ちながら、実装が簡単という利点があるそうです。

| | Comments (52) | TrackBack (0)

恐怖体験

目薬をさしたら、最近の炎天下で目薬がものすごく熱くなっていて、「目がー、目がー」状態

| | Comments (0) | TrackBack (0)

2004.07.20

夏だ一番大友祭り

こじた、あおき(俺はあえてこうよばせてもらう)に誘われスチームボーイをみてきた。

http://www.steamboy.net/top.shtml

映像、特に煙の描写はタイトルだけあってすばらしかった。あえて煙の描写にCGはつかっていないというのをどこかで聞いた気がするが、生きているようですごかった。ボリュームレンダリング周辺の技術やハードウェアが発達してもこのへんの表現は難しかったのかなぁ。

話の内容は、いろいろつっこむ部分はあるが、これはこれと受け止めればおもしろい。ただ、学校で見せたら問題かもしれない。ある意味大人の映画か。

ネタばれしないように、あえて詳しくかかないが、続編は ハ○ルの動く城対スチーム城かもしれない。ムスカもいたような気がする。

| | Comments (0) | TrackBack (0)

再チャレンジ

再度挑戦

http://d.hatena.ne.jp/dasm/20040719#1090220544

これで大丈夫かなぁ。

はてなにトラックバックするときは、URLを入れて、その後に"trackback"と入れて、さらにURLのリンクをいれないとだめなのか。

URLはリンクだけでいいのか。文章だけでいいのかわからん。たぶんどちらかだけでいいんだろうけど。心配

| | Comments (0) | TrackBack (1)

2004.07.19

simEとstockE

伊庭先生の授業の課題はGAかGEなんかを使っておもしろい応用例を作れというものをやろうと思っているのだけれど、前から気になっているSimEとStockEを実装したくて、それなら巡回セールスマン問題(TSP)が一番わかりやすいかなぁと思い、課題の趣旨に沿わない感じで進めています。

SimE、StockEはどちらも非決定的繰り返し最適化を行うアルゴリズムで、GAやSAなどより高速かつメモリ消費量が少ないのだけれど、回路設計などで主に利用されているだけのものらしいです(情報が古いかも)

SimEは一つの解のみに次々作用させていくもので、複数の候補解を交叉、突然変異を起こすGAとは違います。またSAと比べて、それぞれの解の良さに応じて、山登りの程度を変えるので、単調に段々と山登りの範囲が小さくなっていくSAとは違い、さらに複数の解の要素を独立に変更させる面で違います。

StockEはSimEと同様に、一つの解のみに作用し、山登りの範囲を解の良さで変えるのだけれど、SimEは解の要素をまとめて考えて、さらに、収束したなと思ったら、山登りの範囲を大きくしたり、収束回数を変えたりといろいろおもしろい戦略をとっています。

実際にTSPでSimEを作って見たところ、なかなか収束が速いみたいです。StockEも作ろうと思います。

| | Comments (0) | TrackBack (0)

鎌倉

今日はなんとなしに突然旅に出たいと思い、鎌倉と江ノ島へ行ってきた。
具体的には北鎌倉からスタートし、円覚寺、建長寺、鶴岡八幡宮行って、その後江ノ島渡って、横浜の花火を見て
中華街で食べて帰ってきた。大仏が時間不足で見られないのは残念だったが、久しぶりの休日らしかった。

丸一日歩きまわって足が棒のようだ。

| | Comments (0) | TrackBack (0)

トラックバック

テストされたのでテスト返し。(本当はこういうやり方はいけないらしいが)

もし地下にいたら連れて行っただろうに。一応ホワイトボードにスペルは間違っていたがビールと書いてあったのだけれど。

| | Comments (1) | TrackBack (1)

2004.07.16

コンピュータビジョン

の課題をやりました。
二つの違った位置のカメラから同じ物体の画像をとったとき、そのカメラ位置、スクリーン位置を表す情報を8つの対応点から求めることができるというものの、改良版の論文を読めというものでした。epipoleとか曖昧な概念だったんですけど、いろいろwebを探したら見つかりました。
本来なら、そういうwebをここで紹介するのがblogの使い方なのかもしれないけど、どこだったかわすれてしまった・・

今週中にできるだけ課題を終わらしておこう。課題は残り10個か

| | Comments (0) | TrackBack (0)

2004.07.15

第一回目

Blogは使わないという変な意地があったけど、はじめてみた。
今までの日記の内容は
http://homepage3.nifty.com/DO/diary.htm
にあります。

専門的な内容とどうでもいい内容を織り交ぜていきます。

今日は、午前歯医者に行った。歯の治療は長期戦になっているけど、ようやく終盤戦。もう少し。でも、あと親不知が2本ある。

新宿のスタバでrice code周辺を実装。

謎のインド人らしき人が突然隣に座り、捕まり、俺の名前を入れた絵を書いてあげるといわれ、いや別にいいですよといったつもりなのだが、書いてしまい、これを買ってくれないと困りますといわれ、困る俺だったが、500円で買ってしまった。だめだ・・有名なデザイナーで1万円ぐらい値段がつくといいが、絵を見る限りその希望は薄い。

その後、6時から補講があるのだが、ちょっと早目に行ってプールで1kmほど泳ぐ。ずっと同じレーンで泳いでいる人が微妙に知っている人そうで、微妙に違うような気がする非常に微妙な状況だった。向こう側の反応は、「なんだ、知らない人がじろじろ見ている」という顔か「あれ、あの人知っているかも」というどちらにもとれる表情だった。

補講を受けて、飯食べて帰宅。

家に帰ってからアテネオリンピックに備えて買ったTVチューナーボードを、パソコンに入れたが、その後、テレビにつながっているアンテナ線をいろいろするのが大変だった。

とりあえず、テレビはビデオ入力で普通のテレビが見れて、パソコンからTVは普通に見られるようになって、録画はテレビ側がBSだけできて、パソコンはBS以外できるという超謎な状況になった。

最初だから長めで

| | Comments (1) | TrackBack (1)

Main | August 2004 »