おにぎりおにぎりおにぎりおにぎりおにぎりおにぎりおにぎりおにぎりおにぎりおにぎり日記

 | 

2013-01-19

ADVENT CALENDAR DAY 6 - GRAPH THEORY

01:11

Competitive Programming Advent Calendar Div2012

http://partake.in/events/3fcea6d7-0bab-4597-82db-86439aadb1b9

の6(完全数)日目の記事です。


こんにちは、onigiriです。


今年の夏に、東大の情報理工の数理情報学専攻を受けました。

(ただし、合否は問わない)

そこの入試問題アルゴリズムに関する問題が出ているので、

その問題をいくつか紹介しようと思いましたが、

自分がやっていて面白くなさそうなので止めておきます。


というわけで、最近読んでいる、

Graph Theory の本

http://www.amazon.co.jp/Graph-Theory-Graduate-Texts-Mathematics/dp/1846289696/ref=sr_1_cc_1?s=aps&ie=UTF8&qid=1352562100&sr=1-1-catcorr

のまとめをTeXの練習を兼ねてまとめて見ようと思います。

見れば分かりますが、証明や定義の意味はあまり書いてません。

もっと知りたいと思った方は上の本を読んでみてください。

とても読みやすい本で、演習も豊富にあり、力がつく本だと思います。





おまけ


数理情報学の院試について少し。

(なんやかんやで結局やるタイプ)


問題について。

数学は、専門と一般がありますが、専門について書きます。

問題はここで見れます。

http://www.i.u-tokyo.ac.jp/edu/course/mi/admission.shtml


問5がいつもアルゴリズムです。

最近は、グラフばっかです。

僕の受けた(2013年、問題はまだない)もグラフ(Kruskalのやつ)でした。

やばい年もありますが、競技プログラミングを1年もやってれば割と楽に解ける問題ばかりです。



俺的難しさランキング!!!!!!!!

○簡単、△すこし難しい、×難しい。

×2012

△2011

○2010

○2009

△2008

○2007

△2006

○2005

○2004

○2003

○2002


ランキングじゃなくて、レイティングやん。

問1は、大体、大学1年生の時に習い終える線形代数が出てます。

アルゴリズム線形代数を解けばほぼ間違いなく合格です。


∴大学入ると同時に競技プログラミングを始めて、

平行して線形代数を普通に勉強すれば、2年生の時には大学院に通るレベルに達します。

わーい。



面接について。


1対15ぐらいで行われました。

僕の部屋には志望した3人の先生が全員いらっしゃいました。

最初に、志望教員3人の確認をされ、その後、志望理由と、もし入学できたら何を勉強したいかを聞かれました。

後は人それぞれだと思います。

僕はTopCoderのMarathonMatchについて話しました。

そういえば、話してる時に先生の間で何か回してました。

学部時代の成績か、筆記試験の点数か?

後で聞いた話によると、第1志望の先生は必ずいらっしゃって、必ず何か聞いてくださるようです。

以上です。

 |