2010-09-19
[ツッコミを入れる]
| 個人サイト |
| Preferred Infrastructure |
超久々のブログ更新です。昨日は京都大学プログラミングコンテスト(KUPC)を開催しました。沢山の方に参加していただき有難う御座いました。
KUPCを開催することに決まった際に「やはり京大であるからには、少し変わった問題を出さなければならない」という義務感を感じ、そのように問題を作りました。前からプログラミングコンテストで出る問題はジャンルが偏りすぎていると思っていたので、自分が身を置いているアルゴリズムの理論の世界を宣伝する目的もあり、以下の二つを入れることにしました。
問題の難易度は上手くいけばちょうど全完する人が一人二人出るかもしれないぐらいにしました。全完を防ぐ為の防衛問題がよく有りますが、結局そんな問題は無いのと一緒になってしまうので、防衛問題は設定しなかった(つもり)です。問題をずっと眺めていると全ての問題が自明に思えてくるので大変です。
問題文の作成には論文の執筆経験がかなり活きていたと思います。まず問題文をかなり推敲しました。論文だと書きあがってから5,6回は読み直すのですが、その度に抜けが見つかることを経験的に知っていたので、今回もそれぐらい読み直しました。問題H, I, Jで謝辞を入れたのも論文を書くようになって謝辞の文化が自分の中に身についていたからです。まぁ論文ではレストランや山に感謝することはないですが、飛んだ感じを演出するのには役に立ったかなぁと思います。
あとは出来るだけノリの良い文章を書くようにしました。問題B(蝉)や問題H(あばれうなぎ)でそのノリを感じてもらえれば幸いです。うなぎの問題文は名文だと思います。どうでも良いですが「うるさい」を「五月蝿い」と書くのはもはや時代遅れで、現代においては「八月蝉い」と書くべきだと思います。
以下は個人的な問題に関する感想＆裏側解説です。
ジャッジが院試を受ける為、全ての解説スライドを出すのは暫く時間がかかりそうですが、こういうのは旬が有ると思うので、先に問題D, G, Iのスライドをここに添付しておきます。
反省点としては、A, B, Cを解き終わった後はどの問題も手がつけられないという人の為に、作業問題を一つぐらい入れるのが良かったかなぁというのが挙げられます。ただ作業問題は誰でも手をつけられる代わりに面白くはないので難しいところです。来年も是非KUPCを開催したいです。まだまだ出したい問題は一杯あります。来年に備えて皆様、乱択とクエリ計算量とsomething elseの勉強をしましょう！
今日はSupercon 2010の結果発表を観に行ってきました。前年まではTAをしていたのですが、今年は直前にアメリカにいて、直後にスペインに行くので、一日だけの参加に留めました。上記のページには殆どまだ何も情報が無いのですが、関東の高校が一位〜三位を占めるという結果でした。
今回は問題がなかなか面白かったです。今までだと最適化問題が主流で焼きなまし＋適切なスコア関数以外やることあるんかいなという状況だったのですが、今年は正確な解を求めないといけない言わばICPCタイプの問題でした。具体的には50*50の盤面にいくつか障害物が置いてあり、障害物を避けながら2*1のタイルを敷き詰める置き方は何通り有るかという問題です。20*100とかならDPで、8*10^8とかでも行列乗算で解けるんでしょうか。コンテスト的にはそれに適当にヒューリスティックスを入れて、大部分の入力に対して解が求まれば勝てるようです。
ただジャッジが全データに対して正解データを用意しているということは50*50でも解く方法があるということなのですが、僕は最初全く分かりませんでした。二部グラフの完全マッチングの数え上げってPRASみたいなのは有ったような気がするけど#P-completeじゃなかったっけと悩んでいました。後で教えてもらったところによると、グリッドは二部グラフじゃなくて平面グラフとみなすのが良いようです。そして何と、平面グラフの完全マッチングの数え上げは多項式時間で解けるらしいです。リンク先の資料がとても詳しいです。Pfaffian Orientationというのが肝だそうで。
このアルゴリズムを僕は今まで全く知らなかったので、試しに実装してみました。例えば以下のような入力に対しては(各インスタンスの最初の行は、問題番号、高さ、幅、Mod)、
1 3 2 100000次のように出力します。最初にPfaffian Orientationを出力したのち、タイルの敷き詰め方の総数を出力しています。解が大きい時は桁落ちします。
..
..
..
1 3 2 100000
..
..
.*
1 3 6 100000
......
......
......
1 3 7 100000
....***
.......
.......
1 10 10 100000
****..****
***....***
**......**
*........*
..........
..........
*........*
**......**
***....***
****..****
.>.
v v
.<.
v v
.>.
3
.>.
v v
.<.
v
. *
0
.>.>.>.>.>.
v v v v v v
.<.<.<.<.<.
v v v v v v
.>.>.>.>.>.
41
.>.>.>. * * *
v v v v
.<.<.<.>.>.>.
v v v v v v v
.>.>.>.<.<.<.
41
* * * * .>. * * * *
v v
* * * .<.<.>. * * *
^ v v v
* * .<.<.>.<.>. * *
v ^ v v v v
* .<.<.<.<.>.<.>. *
^ v ^ v v v v v
.<.<.<.<.>.<.>.<.>.
v ^ v ^ v v v v v v
.<.<.<.<.<.>.<.>.<.
^ v ^ v v v v v
* .<.<.<.>.<.>.<. *
v ^ v v v v
* * .<.<.<.>.<. * *
^ v v v
* * * .<.>.<. * * *
v v
* * * *
32768
先に結論を書いておきますと、8/23からの週(末)が暇なので、関西で何かイベントが有ったり、会ってくれる人が居れば連絡ください！
去年の10月からお世話になっていたRutgers Universityですが、この8/19に日本に帰国します。おかげ様でゆっくり研究することが出来ました。その間サポートして下さった方々に感謝です。大学の人も家の人もみんな親切で本当に助かりました。出来れば日本とアメリカとその日の気分で住むところを選びたいところですが、そうもいかないですね…。
アメリカに来てから考え始めて論文にするところまで持って行けたのが多分五本(うち一つは参考にしていた論文に致命的なミスが有ってポシャりましたが)で、今やっているプロジェクトが三つほど有るので、抜群に仕事をしたかというと微妙かもしれませんがまぁ及第点かなと思っています。こちらの大学の人とやっているプロジェクトはうち一つだけで、本当はもっと一緒にやりたかったのですが、思っていたより量子コンピュータを研究している人ばかりだったので仕方がないと言ったところでしょうか。勿論研究とは関係なしに友人は沢山出来ました。
留学したものの義務としてそのメリットを語る必要があるのかなと思ったので少し考えていました。理論計算機科学というのは基本的には「計算機に纏わる数学的に綺麗な事柄を証明していく」というのが目的で、現段階で一番大きな目標が「P != NPを示す」ということなのだと思います。当然これは一人でやるわけではなくて、世界中の人たちで協力しあってやっていく。その時に彼らがどんな人達か知ることはとても重要だと思うのです。一緒に仕事をするのも彼らだし、何が重要か(言い換えれば綺麗か)を判断するのも彼らです。基本的に理論計算機科学はアメリカを中心に動いているので、その本場で彼らがどのような流儀で仕事をしているのかを直に見れるのは良い経験であったなぁと思います。勿論そんな堅苦しいことを考えずに、単に外国の文化に触れるのはそれ自体楽しいことです。
逆にデメリットは余り思いつきません。日本の友人とは日本に帰ればまた会えますし、食べ物は確かに油っこくて辛い時がありますが、言ってもその程度です。
なので留学をするチャンスがある人には積極的に勧めたいです。ずっと一箇所に長い間いると空気が淀んで思考も固まってくるので、たまにはそこを離れて換気をするのが良いと思います。そういう意味では僕もコンピュータから離れて別のことしろって話ですね…。
P != NPを示すのに代数幾何が使えるという話があるのですが（Lance Fortnowによる動画解説）、本格的に学ぶべきかどうか悩む…。Ketan Mulmuleyによる講義の資料とビデオが有るので、勉強する材料は揃っているのですが、代数幾何はちょっと余りにハードルが高い。けれども近く発展して行くのは目に見えている。今出川通りの北に転がっている人たちをこっちに引き込んだ方がいい気がするなぁ。代数幾何自体を発展させようとして苦労している人たち沢山いそうだし。
まだ先の話ですが6/14からPseudorandomness in Mathematical Structures Programというワークショップに参加する予定です。お題はpseudorandomness(擬似乱数)です。擬似乱数の直接的な応用は暗号だったり、確率を用いたアルゴリズムを使わないように変形する(BPP = Pが目標)ことだったりだと思うのですが、実のところ僕はその辺りの話は興味がありません。それより僕が面白いと思っているのは、pseudorandomnessを他の分野の証明の道具に使うことです。例えば関数f : {-1,1}^n → {-1,1}のフーリエ展開が良い例です。フーリエ展開はある関数を別の特性関数の線形和で表すことと言って良いと思います。この時、どんな関数も「(nに寄らない)定数個の特性関数の線形和」と「ノイズ」に分けれるというのがフーリエ展開から示唆されます。このノイズの部分を良くpseudorandomと読んでいるのですが、ノイズの部分を捨ててしまえば、元の関数fは、要するに定数個の特性関数でよく近似出来るというわけです。個人的にはこの部分がとても哲学的な示唆に飛んでいて好きです。詳しくはFOCS 2007のTerrence Taoによるチュートリアルを参照してください。
この性質を使うことで、実に様々な定理が証明されています。まず、上のフーリエ関数はCSPの近似困難性の解析をする上でよく使われています。また、上の考えをグラフに適用すればSzemeredi's regularity lemmaも証明できます。そこから性質検査の話にもつながります。他にもTao & Greenの「素数列中には任意の長さの等差数列が存在する」という定理の証明の道具にもなっています。
話を元に戻すと、このワークショップでその辺りの道具の今の状況が知れれば良いな思っています。また最近、軽く群論の検査にも手を出しているのですが、群論とpsudorandomの関係もこのワークショップで語られるそうなので、それも楽しみです。
今年もPFIでは夏季インターンを開催します。
内容は前年度のインターンの方々の感想を見てもらうのが一番早いかと思います。面接対策にはなるんではないでしょうか(笑)(追記) ところでオフィスが新しくなりました。写真
Before...
_ oxy [参加していただきありがとうございました。自分が自由に出来るコンテストではやりたいことをやろうと思いランダムとクエリ計..]
_ Apohypeweme [Programs, reviews of new products, reviews of software htt..]
_ NewsWheebab [ハ�繹� �頡�鉋籵鱚譛 關鉐赭鴃萵璢矼甅髓鞐辷�� 闔跪��Opera Mini, 艢關鉐 銜關珥纈 �辮�General ..]