院試
後輩が試験のことを書いていたので書いてみる。向こうにはゲームのことしか書くつもりはないのでこっちで。
試験前日
TCO Round5の500で1行ミスをしてon siteを逃してやる気が無くなる。実質的には一日開いてるけど前日。
試験前
てきとうに出る所を予測してみた
- 分野基礎：エージェント、制約充足、プランニング
- アルゴリズム1：クイックソートの平均計算量
- 情報理論：通信路容量、ハミング符号、生成・検査行列
- 人工知能：SVM、遺伝的アルゴリズム、ニューラルネットワーク
- 数学：フーリエ変換(取る予定は無い)
勉強したのは情報理論、人工知能、オートマトンあたり
取るつもりなのがアルゴリズム*2、人工知能、オートマトン、情報理論、グラフ理論
13問中4問選択（生物、心理は無視）でアルゴリズムと人工知能はほぼ安泰なので後ろの三つでもう一問解く感じで。ちなみにグラフ理論はパッと見て解けるかどうかが分かりづらいし、完答できるか怪しいので奥の手である
専門
前から見ていく
- アルゴリズム1：文字列処理の問題。最後の設問に最悪の場合、普通の場合と書いてあるのでBM法かな？BM法については詳しくないので後回し
- プログラム？：完全にデータベースと融合してるじゃん。パス
- 計算と論理：いつものやつっぽい。勉強してないのでパス(後から聞くと傾向が変わったらしい)
- 情報理論：6x6行列のマルコフ情報源だと！1問目から解けるかどうか怪しいので保留
- 画像処理：二値化処理。見た感じ楽そう。勉強していれば余裕で解けそうだが、勉強してないのでパス
- パターン認識：パス
- 人工知能：積木の世界。これってプランニングじゃあ…。授業のレジュメに無かったし、プランニングの論理式の書き方とか覚えてないし保留
- アーキテクチャ：パス(後から聞くと傾向が変わったらしい)
- オートマトン：鳩の巣原理？たぶん解ける。
- アルゴリズム2：DP。解ける。
- 信号処理：フーリエ変換とか書いてる。パス
- グラフ理論：ハミルトン閉路。保留
- 数学：パス
あれ…、これやばくない？安泰だと思ってた人工知能がむずいし、簡単な問題が殆ど無いんですけど…。
とりあえずオートマトンを解いて落ち着こう…。オートマトンを途中まで解いて気になったことが出てきたので後回しにしてDPを解く。
DPは割と楽に解けた。ここまでで45分位か。
次はアルゴリズム1を解いてみる。よく見るとこれsuffix arrayじゃないか…。suffix arrayとか知ってる人3人くらいしか居なさそうなんですけど…。一応問題自体は前から順に解けば知らない人でも解ける形式にはなっているけど、理解するのに時間がかかるだろうし、手を出しにくいだろうなあ。
最長共通部分文字列の問題をO(n^3),O(n^2)で実装してお茶を濁す。lcpを使うか何かすれば、O(n)かO(nlogn)で実装できるはずだけどそんな余裕は無い
残り1時間半くらい。情報理論、人工知能は一問目から怖いので奥の手グラフ理論に手をつける。設問1でハミルトン閉路が作れない。作れるだろうという前提が間違ってるんじゃないのかと疑ってみたら作れないことが証明できた…。設問1からつまずいてしまった。設問2,3は余裕として、設問4のNP完全の証明の仕方を忘れた。2つあって片方は問題をNP完全問題(ハミルトンパス問題)に帰着してやればいいはずなんだけど、もう一方を忘れてしまった。なんか考えているうちにNPであることを言えばいいのを思い出しててきとうに証明した。残りは誘導があるのでそれに沿ってやるだけ。
残り40分でオートマトンの残りをやってしまおう。証明が怪しいけどたぶんできた。
感想
こんだけ書いて落ちたらもうどうしようも無いです。
問題自体は傾向が変わったり、難化したっぽい。アルゴリズムが出来る人はDPを、出来ない人は画像処理を取っておかないとかなりきつそう。ちなみに数学は確率が出たらしい。確率から出るとは完全に盲点だった。
どうでもいいけど予測（ヤマでは無い）は全部外れた。あと、あんな授業でやっていることとかけ離れたグラフ理論とか誰が解くんだwとか思っていたら解くことになりました。
面接
無かった。
合格発表
院には受かった。しかし、掲示されたやつにはどの研究室に受かったが書いてない…。
これから東京→実家って移動するので下宿にしばらく居なくて、郵送される合格発表の通知の書留速達が手に入らないんですけど…。事務にそんなことを言ったら、一回郵送して戻って来たやつを後で事務まで取りに来てとか言われた。
追記：第一志望に受かってたらしい。
