子供の落書き帳 Remix

15/4/13:ひと月に一度更新するブログになってしまっている

院試2日目(専門科目)
2010/09/20(月) 00:49:58

※この文章は自分の受けた大学院入試に関する文章です。
同じ試験を受けた人か、受験生で過去問として解いた/解こうとしている人でないと
文章の意味がさっぱり分からないんじゃないかと思います。

大学院試験2日目。
正確に述べると「東京大学大学院 情報理工学系研究科 数理情報学専攻」の入学試験です。
1日目はこっちね。

8月24日。専門科目の数理情報学。
5問の中から3問選択して180分。
どれを選ぶかで勝負が決まるので、7~10分くらい掛けて問題をじっくり読む。

第1問……行列論。これは行けそう。
第2問……fisher情報行列の極限とかできる気がしない。
第3問……数値解析。
第4問……2階微分方程式のやや変形版。[・]つまりfloor関数の処理が面倒臭そう。
第5問……アルゴリズムはまさかの最小費用カバー問題か。

2は問題を見てすぐに解かないことを決定。
確率・統計のテコ入れを最後までやったのにこの決断をするのは若干気が引けたが、
避けるべき事態は「皆が楽に解ける問題なのに俺は解けない」という状態だ。
今回はそれに当てはまらないので良いだろう。
この勉強のおかげで、共通数学の問題が解けたしね。恩恵は十分受けてる。

そうなると残り4問から3問。
5を解かなかったら134になるがその組み合わせはないだろう、つまり5はどこかで解くことになる。
どこかで解くなら今解いてしまおう。というわけで5から始める。
今考えれば妙ちきりんな判断である。

(1)は反例の構成。{0,1}を0以上の全ての実数に緩和してるんだから、
1以上の数か0と1の間の数が最適値になってしまうように組めばよい。まぁ常識的に考えて後者だろ。
三角形のグラフの普通のカバーを考えて終了。

(2)は……2倍以下だと?どうすればいいんだ。
落ち着け、元の問題と緩和問題の最適値は「緩和問題≦元の問題」になる。
それ以上のことは分からないはずだ。
よって、きっと緩和問題の最適値の2倍以下であることを示す方針だろう。
まず、最適値を与えるものでオール1以下になるのが存在すること
(最適値を与えるものは必ずオール1以下、ではない。このへんの言い回し面倒だね)を示す。
あとはそれから元の問題の近似解を出すんだから、任意の辺の少なくとも一方が……とか言って終了。

(3)は弱双対定理の提示と証明。
定理の内容は覚えているから書けるが、証明は……どうやったっけ?
弱双対は不等式評価でいいから。最大流最小カットの定理の場合もそれなりに楽に示せた気がする。
(強双対定理は値が厳密に一致することを示さなければならないので、その値をとる双方のベクトルを
構成する必要がある。)
と、いうことは主問題と双対問題にある不等式を組み合わせると……あ、できた。

(4)は主問題と双対問題を一遍に解いて実行可能解を得ようというアルゴリズム。
問題の意味は何とかわかったが、証明できる気がしないのでここで第5問は終了にしよう。
1時間くらい経ってたかな。

4はx+ax'' = b の解を考えたら焦ってド忘れしたので、解かないことに決定。
いやsinとcosが積分定数部分になるのは分かる。残りの特解を忘れたんだ。
試験全部終わってから図書館に行く道すがらで考えたら、こんなのどう考えても
x≡b(定数関数)じゃねーか。
まぁ、試験中の俺はそれが思いつかなかったわけだ。
この時点で解く問題は1・3・5に決定だ。

あとはなんか小問の数をやたらと気にしてて、小問が(2)までの第3問を取った気がする。
4は(5)まであったんじゃないかなー。解いてないからよく憶えてないけど。
なんか最初に全体を見たとき、どれも小問の数が多くてやたら焦った覚えがある。

3。偏微分方程式を離散化して近似して解こうの巻。
(1)は落ち着いてテイラー展開だよね。オーダ記号の処理をしっかり出来れば大丈夫だよね。
ちょっとここだけ自信ない。書き方があってるのか怪しい。

(2)は安定性解析。
安定性の定義はバッチリ書いてあるのでそれに代入していけばよい。
うん。定義はうろ覚えだったからね。書かれてなかったらできなかったと思う。
今調べたけど、A-安定性とかいうやつなんだろうか。
Stiff equation(硬い微分方程式)とかいう単語が出てきたけど何これ。
この辺もうちょっと勉強したほうがよさそう。
前半は定義通り計算、ΔtとΔxとaの値次第で安定性が分かれる結果になったはず。
この辺で咄嗟に三角不等式を書こうとして戸惑うのが俺である。なんか三角不等式が使いこなせない。
後半。ちょっと待て。xでの偏微分を求めるのにその位置での値を使わないってことか!?
例えば位置i+1での値が6、位置i-1での値が3と決まっていたら、
位置iでの値が6だろうと4だろうと10000だろうと、xで偏微分した値(の近似)として同じ値が出ることになる。
これは解が吹っ飛びそうな予感が凄いするぞ。具体的にどうなるかっていうとこまでは
見当がつかないけど。計算進めると物凄くギザギザになった解になりそう。
というわけで直感では不安定。で、定義通り計算。良し、直感にあった答えが出た。幸せ。
多分これも1時間くらいで終了。残りは約1時間。

では1に行こう。
(1)は対称行列が直交行列を用いて対角化できること、
異なる固有値に対応する固有ベクトルが直交することから瞬殺である。
院試勉強を始めた頃は知らなくて、色んな人に突っ込まれたけど。

(2)は式を展開して、移項して全ての係数が正になるようにしたら、なんかを微分した形に見えてきた。
Ax=kxとx'x=1('は転置)の微分ですね。おk。終了。

(3)係数行列が正則であることを言えばよいわけで。

係数行列にかけて0になるような縦ベクトルzを考えると、
式の上の部分はzがx_kと線形従属であることを要求して、式の最下段はzがx_kの直交補空間内にあること
(つまりx_k成分を含まないこと)を要求しているから……うん、それは0ベクトルしかないね。
まぁこんなにしっかりした形で試験中に考えたわけじゃないです、もちろん。
直交補空間って単語とか試験終わった後から出したものだしww
行けそうだなって思って実際に答案書いたらちょっと詰まって、
そこからもうちょっとしっかり考えなおした感じ。

(4)最後。(2)で出した式が使えそう。
左からある行列をかける。ここまで解ければ合格できるだろうと思うと
緊張して、2項目以降にかけるの忘れた。
a(b+c+d)=ab+c+dみたいな式を一度書いたってことだ。で、誤りに気づいて深呼吸。
余計な項は実は全て0だから消える。で、示すべき式が導出できた、めでたし。

ここまで解いてから何してたんだっけ……解答用紙を全部見なおしたんだよな、確か。
そのあと第4問の(4)を解こうとしたけど、なかなか難しくて
何も書けないうちに終了。

ちなみに問題選択ですが、第1問は殆どの人が選んだっぽい。
他はどれが人気だったということも内容に思う。第2問~第5問はほぼ均等だろうな。
新学期始まったら皆に訊いてみたら面白そうな気もするけど、難しいかもな~。

それでは。

テーマ:自然科学 - ジャンル:学問・文化・芸術

  1. 2010/09/20(月) 00:49:58|
  2. 学校
  3. | トラックバック:0
  4. | コメント:2

コメント

質問

私は今年数理情報学専攻を受けるのですが、数値解析とアルゴリズムに関して若干苦手意識を持っています。そこでどのような書籍等を用いて残りの期間勉強していくといいかお忙しいとは思いますがアドバイスいただけたら幸いです。
  1. 2011/07/14(木) 20:32:46 |
  2. URL |
  3. えみ #-
  4. [ 編集 ]

うーん、俺は内部生で授業や演習で出題範囲の勉強をしてきたから、特にそれらの分野で本を買って試験対策をしたということが無いんですよね。

1年前のあやふやな記憶をもとに言いますと、数値解析はもともと出題確率が低いですし、「知らないと解けない」系統の問題はそれほど出ないはずです。微分を差分近似するときの代表的な方法をいくつか覚えておけばそれでOKだと思いますが。

アルゴリズムは鉄板のアルゴリズムイントロダクションくらいしか思いつかないけど、試験範囲カバーしようと思ったら2巻まで読まなければならないでしょう。練習問題などを解くのはオーバーワークなので流れと骨子が分かれば良いでしょう。
でもそこまでしてイントロダクション使わなくても良いような気がします。代わりに何使ったら良いのって訊かれても答えられないので困りますが。
ついでに言うと、山を張るなら間違いなくDP。あれだけは一通りできるようにしておくと良いかと思います。

まともな答になってないと思いますが、こんなところで。
  1. 2011/08/03(水) 00:44:20 |
  2. URL |
  3. ライナス #-
  4. [ 編集 ]

管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://luvtome.blog5.fc2.com/tb.php/436-9ebe88bf
この記事にトラックバックする(FC2ブログユーザー)

FC2Ad