日記
2004/11/30
D論提出した。
2004/11/29
ようやくD論書けました。ふぅ。
暫定版をポストします。Researchのところから辿っていくと見ることが出来ます。
謝辞はまだないですけど、最終版には謝辞も付きます。
提出は明日を予定しています。
ちなみにA4用紙にこれを印刷すると文字が割と大きくなりますが、
実はA4用紙1枚に2ページ印刷すると正しい大きさになります。
印刷版もその大きさです。
2004/11/23
査読を1つ終わらせたら、また新しいのがやってきた。
2004/11/18
いきなり今日のゼミ当番になってしまって、急いで準備したら間違いだらけのものをやってしまった。
内容は劣モジュラ関数最小化で、組合せ的強多項式時間アルゴリズムまでできるわけないと思ったので、
双対定理が重要で、双対を解くために有向グラフを考えて増加道を探すんだ、っていうとこまではやりたかったのに、
全然できなかった。
やはり30分の壁は厚い。(結局40分ぐらい喋ってたけど。)
なので、今日出来たのは、まず定義と例、そして、Lovász extensionの凸性、
そして、劣モジュラ関数最小化の双対定理の説明までで、
結局、双対の線形計画問題を解けばいいのだけど、どうしてそれが難しいのか、っていうことに重点を置いてみた。
Lovász extensionを話したかったのは、実はおとといと昨日Lovászがチューリッヒに来ていて講演したからである。
(もちろん、劣モジュラ関数最小化の文脈でとても重要だから話したのだけど、それ以外のおまけの理由ということで。)
Lovászといえば離散数学のいろんな分野で先駆的な仕事をやりすぎていて、
枚挙しようとすると何か重要なものを忘れるのではないかと心配になるのでやめます。
とにかくすごい人、ということです。
2004/11/15
ECCCを見てみると無向グラフのst連結性判定をLOGSPACEで解くアルゴリズムの論文が出ていて、驚いた。
これは理論計算機科学の大きな未解決問題であったので、この論文が正しいとすると、大きなブレークスルーと言えると思う。
2004/11/11
最近、自分がアシスタントをやっている授業のおかげでデータ構造に興味を持ち始めている。
もちろんアルゴリズムとデータ構造は切っても切れない関係にあるのだけれども、
いままではどちらかというと、多項式性くらいしか気にしていなくて、
複雑なデータ構造を考えてアルゴリズムを効率化ようなことはあまり興味がなかった。
しかし、やはり複雑と思えるデータ構造もちゃんと勉強するとやはり基本から積み上げるとすーっと染み通るように理解できていく。
まだ勉強しはじめたばかりなのでよく分からないことも多いけど、
こういうものがアルゴリズムの理論の王道なのかな、とも思ったりした。
2004/11/9
チーズファンの皆様におかれましては、
山のチーズオリンピックで日本のチーズが金メダルとうニュースはもう御存じかと思います。
共働学舎新得農場さんが受賞されたということで、おめでとうございます。
お茶にもあるチーズということなので、どのようなものなのか大変興味があります。
実は、いま隠れチーズファンをしています。
こんなところに書いてしまったら隠れも何もないと思いますが、今はいろいろなものを試しています。
個人的に好きなチーズはアッペンツェラーです。
2004/11/8
Introductions to Algorithmsという本はイントロダクションという割りに高度なことを扱っていて、自分の知らないことがたくさん書いてある。
自分が知らないから高度だ、というのはもちろんおかしくて、それは自分の不勉強がもたらす結果なわけだけども、
それにしてもこの本はかなりよい。全部読んだわけではないけど、わたしのお薦め。
しかし、自分はまだ所有していない。
授業の関係でB-treeを勉強しなくてはいけなくて、その部分だけコピーしたのだけど、
データ構造についてはいろいろなものがちゃんと書いてあって、とてもよい。
ちなみに、union-findのpath compressionの解析といえば、
データ構造とアルゴリズムの理論の授業において、どうもとばしてしまいがちな難しい部分になっているけれども、
その新しい解析法をRaimund Seidelが行なったとどこかで見た。
何か月か前のことなので本当だったかどうか定かではないけども、新しい解析法はトップダウンにやるようである。
と書いた瞬間にどこだったか思い出した。
ベルリンCGCのコロキウムでしかも今日だったみたいだ。
はからずして、タイムリーな話題になってしまった。
しかも、もうすこしいろいろ調べたら、これはMicha Sharirとの共著で、
既にSIAM Journal on Computingから出版されることが决まってるようである。
プレプリントもWEBから入手できる。時間を見つけて読みたい。
やっぱり研究科名のはなしは発表者一覧を見たときの感想なんでしょうか。
2004/11/5
出版社の方で書き換えることもよくあるということで、校正はしっかりしないといけない、とコメントを頂きました。
ありがとうございます。
今年は龍谷大学に行かない予定です。
何か特に他の予定があるというわけではないのですが。
とりあえず、発表はしません。
アルゴリズムの世界でよく知られているMotwaniという研究者がいるけれども、
どうも日本人は「Motowani」と綴ってしまうことが多いようである。
挙げ足取りっぽくなるので具体的な言及は避けることにして、
とりあえず知っている本で1つ、あとGoogleで検索すると5つぐらい見つかる。
5つぐらいでは多いといえないけれども、日本人の感覚からすると間違いやすい綴りなので気を付けたい。
この間違いの理由はもちろんMotwaniを「モトワニ」と発音するからである。
英語っぽく「もおぅとわあぁにぃ」みたいに思ってると間違えない。(全く無理なことだとは思うけれども。)
これはShrekという映画を日本語吹替えで見たとき、
Shrekが「シュレック」とカタカナになったときに
「シュ」の部分にアクセントを置いて発音されていた違和感に似ている。
母音が本来ない場所に母音が来ているということで。
(細かいことをいうと、自分が英語でみたのはShrekで、日本語吹替えで見たのはShrek 2です。
どうでもいいんですが。)
2004/11/3
今日、ある学生さんと一緒に論文を読んでいて、ちょっとびっくりすることを見付けてしまった。
Journal of Algorithms, volume 30の194-214ページに
GoemansとSkutellaの書いた「Cooperative facility location games」という論文が出ていて、
これを読んでいたのだけれども
(ちなみにこれはSODA2000に出た論文で、上のジャーナル・バージョンはこの会議の特別号になっている。
これはSODAバージョンのときに既に読んでいたので内容は知っている)、
非常に重要な箇所で「maximize」でなくてはならないところが「minimize」になっている。
これは専門家が見れば明らかにおかしい、という部類の間違いで、
というのはminimizeが目的になっている線形計画問題の双対がminimizeになっているからである。
(もちろん、例外はあって、式変形とか符号の付け替えの後にもともとmaximizeであったものがminimizeになることはある。)
ということで、おかしいなと思って、GoemansのページやSkutellaのページから辿って入手できるプレプリント・バージョンを見てみると、
ちゃんと「maximize」と書いてある。
会議バージョンでも「maximize」と書いてある。
つまり、ジャーナルに投稿したものでは (あるいは最終稿では) ちゃんと「maximize」になっていたものが、
出版時に「minimize」になってしまったのである。
おかしい。
最近、学術論文の投稿、査読、編集、出版などは電子的に行われることが多く、
原稿もメールなどで送ることが多い。
(メールでなくても、ディスケットにファイルを入れて郵送することもある。
これは少し古いタイプであるけれども。)
ということなので、写植というものは送った原稿ファイルを
ジャーナルの形式に合わせるだけの作業であると思っていた。
しかし、上の例を考えると、
写植、あるいは写植でなくても編集者側のある段階で、
ある人が「内容」を読んで、手を加えているとしか考えられない。
しかも間違いを混入しているのである。
どうして電子的に送った最終稿にそのような形の変更をしないとならないのであろうか。
いくら英語がおかしかったり、誤植があったりしても、著者に無断で変えてはならないのではないだろうか。
もちろん、校正が著者に回ってくるのだけれども、
大抵、著者は自分が電子的に送った原稿が少なくともテクニカルな部分には使われていると想定しているものと思う。
(少なくとも自分は想定していた。)
それによって、写植や校正だけではなくて、編集全体や出版の質やスピードをよくすることが出来るものだと思っていた。
編集者が意図的に混入した間違いにまで
(間違いを意図的にしたということではなくて、何かを意図的に混入して結果的にそれが間違いだったということ)、
著者は責任を持たないといけないのだろうか。
おそらく極論に走ってると思うので、何か意見などあれば直接私までお願いします。
自分の日記とかblogに書くだけっていうのは、(アクセス・ログとか参考にして) 私がチェックしてる方だけでお願いします。
2004/11/2
今週、阪大から牧野さんがいらっしゃっています。
今日は昨日から考えていた問題のNP完全性 (そして近似不可能性まで) が証明できたので、ちょっと進んだ、という感じです。
明日はもう少し強いことまで示したいです。
10月の日記
過去の日記のリスト
[トップ]
okamotoy@uec.ac.jp
Last modified:Wed Dec 1 00:26:06 2004