研究日記 号外

私が書いたもので研究上のお知り合いの方々が一番よく読んでいる ものが論文ではない，というのはなかなか恥ずかしいことですが， では，もっとも読まれているものとは何なのか？と思われる方も いらっしゃるでしょう． おそらく，最も読まれているものは 私がウェブ上で書いている 「研究日記」 だと思います． これは，私が東大の修士課程に入った1999年4月に始まり，今も 続いています． 私がこれを始めた頃は，まだ「ブログ」という文化は無かったものの， 日本では日誌みたいなものをウェブ上に載せる方が (計算機科学に限らず) 何人かいらっしゃいました． これを始めた目的が何であったのかということは，ほとんど記憶に ないですが，私のことなので，大きな理由も無く始めたのだと思います．

理由も無く始めたものですが，なぜか読者が増えていったというのは どういうことなのでしょう？ 口コミか何かあったのでしょうか？ 京大のN先生に先日お会いしたとき， N先生は博士課程に進む学生に私の日記を読むように薦めて下さったそうです． それは，私の日記を見ると， 学生が研究者へと育っていく過程が見て取れるからなのだそうです． 当の本人としては嬉しいような開き直るしかないような，といった感じです． 他にも，私の日記に掲載された最新の論文情報などを見て， ビックリして私にメールを送って下さる方もいらっしゃいました． LA会誌編集のU先生からは， 日記の内容に関してそのようなメールを度々頂きます． とにかく，私の日記に読者の方々にとって有用な情報があるということは 日記を書いている意味がないわけでもないな，と思える証になっています．

実は，私自身，日本のアルゴリズム理論研究者の方で 公開ブログなどをつけている方をあまり存じ上げません． (ここで，「公開」とはアイデンティティを公開していること，とします．) 私のサーベイ力が無いためなのかもしれませんが， 今のところ把握しているのは，アルゴ研幹事の 東大医科研S先生のもの です．(実は，御本人と面識はないのですが．) 最適化の研究者では， 東京海洋大のK先生のブログ があり，様々な事項に自身の視点から鋭く突っ込む様が とても面白いです． また，数学の方では， 私の東大時代の先輩である 筑波大のH先生の「雑感」 は，昔の方を見ると私の研究日記と同期しているところなどが あり，合わせ読むと少し面白いかもしれません． 「自分も書いてるから見てほしい」という方がいらっしゃいましたら， お知らせ頂けると幸いです．

最近では，ブログ文化の隆盛によって， 海外の研究者のブログが頻繁に目に付きます． 私が始めに気づいたのは，計算幾何の Jeff Erickson です． そこから，計算量理論の Lance Fortnow も辿って見つけました． このブログは他の人もいろいろコメントを付けていて， かなり盛り上がっています． 他にも，アルゴリズムの David Eppstein や量子計算の Scott Aaronson があり，どれも興味深いものです．

Ericksonのブログに先日興味深い問題が投稿されていました． (問題自体はMohammad MahdianがFOCSで出したものだそうです．) まず，n個の風船が与えられます． 見た目はどれも完全に同じですが， 容量は1,1/2,1/3,...,1/nになっています． どの風船がどの容量を持っているか，見ただけでは分かりません． 風船に空気を入れると，容量に達するまでは膨らみ続けますが， 容量を越えた瞬間に割れてしまいます． 目標は，出来るだけたくさんの空気をn個の風船の中に蓄えることです． ただし，割れてしまった風船に入れた空気は蓄えられたとは見なしません．

これはアルゴリズムの問題ですが， おそらく1だけ蓄えるアルゴリズムはパッと思い付くでしょう． そして，この1という量を改善できないこと (すなわち，1が蓄えられる量の下界であること) を証明することも 敵対者論法から直ちに出来ます． 問題にされているのは，確率的なアルゴリズムで蓄えられる空気の量の 期待値を出来る限り大きくするものはどのようなものか，ということです． Mahdian自身はおよそ1.7183の空気を入れるアルゴリズムを考案した ようで，Ericksonと彼の学生Cranstonは少しだけ改善できると思って， 今計算をしているようです． このような面白い問題に出会えることも，ブログの面白いところです．

未解決問題といえば， 11月に名古屋で行なわれた特定研究の全体会議では 「未解決問題セッション」が組まれました． 私も含めて5名の方から未解決問題が出されて，それらについて グループに分かれてディスカッションしました． 私自身は巡回セールスマン問題 (TSP) に関する問題を出しました． 手持ちの未解決問題はいろいろあるのですが，いろいろな制約から 出すことの出来ない問題を捨てて，残った中から， 他の分野の人にも分かりやすい問題を出そうと思ったら， TSPが残りました． 京大のI先生や明大のT先生を中心にいろいろなアイディアを頂いて， 他にも多くの方がディスカッションに参加し， お茶を飲みながらとても楽しいひとときでした． TSPを解くための小さなプログラムを作っていったので， それを使って目で見て感触を得ることができたことは成功だったと思います． 本当に小さな即席プログラムだったので， 頂点数が10ぐらいのインスタンスまでしか解けなかったのですが， 懇親会でJAISTのA先生とその話をして， 「どんな稚拙なプログラムでも，やはり目で見えるのは大事だ」という A先生自身の体験談を聞かせて頂いて，そうなんだ，と自分でもその考えを 確かにしました． とてもよい経験でした．

未解決問題セッションを企画されたのはそのA先生でした． A先生自身の未解決問題やディスカッションにまつわる話は 前号のLA会誌でA先生自身が書かれてますが， 計算幾何の会議CCCG (Canadian Conference on Computational Geometryの略． ちなみに，CCCGは査読付きの会議ではないので， 注意しないといけません．スクリーニングがあるだけです．) では「未解決問題セッション」が毎年開かれて，それが 新たな研究を生む原動力になっていたり， そのような問題を集めたウェブページ もあります． 離散幾何では未解決問題だけを集めた本 (P. Brass, W. Moser, and J. Pach: Research Problems in Discrete Geometry. Springer, New York, 2005.) も最近出版されました． 幾何の分野にこのような伝統があるのは， おそらくErdős (「Erdős」であり「Erdös」ではないので注意が必要です．) のおかげなのではないかと思います．

最近，上のページにも挙げられている計算幾何学の大きな問題が 解かれました． それは，最小重み三角形分割を求める問題がNP困難である， ということの証明です． その結果はWolfgang MulzerとGünter Roteによるものですが， 証明はかなり込み入っていて，正しさを確認するために 数値計算を援用しています． (その点では四色定理の証明に似ています．) ちなみに，問題自体を簡単に述べると， 2次元平面上に与えられた有限点集合の三角形分割の中で 辺長和最小のものを求める最適化問題です． Garey & Johnsonの本にも未解決問題として載っていて， それ以後未だに未解決のものとして知られていました． 論文はいまのところ プレプリント として入手できます．

Back to Table of Contents Last modified: Thu Jul 21 08:14:25 JST 2005 modified/maintained by R.Uehara (uehara@jaist.ac.jp)