東京大学大学院情報理工学系研究科コンピュータ科学専攻 専門科目対策(院試)
- はじめに
- コンピュータ科学専攻:専門科目
- 情報数学
- 数値計算
- 離散数学
- アルゴリズムと計算量
- 形式言語
- 論理学,デジタル回路
- コンピュータアーキテクチャ(プログラミング言語,計算機アーキテクチャ)
- オペレーティングシステム
- 機械学習
- その他
- まとめ
はじめに
専門科目の対策にはかなりの時間をかけました.コンピュータ科学専攻の専門科目は異常とも思えるほどの科目量です.正直私も半年間ですべては勉強できませんでした.その量の多さゆえに当ブログの紹介も長くなるのでご了承ください.
コンピュータ科学専攻:専門科目
専門科目は1と2に分かれており,科目は以下の通りです.
専門科目Ⅰ
情報数学,数値計算,離散数学,アルゴリズムと計算量,形式言語,論理学,プログラミング言語,計算機アーキテクチャ,オペレーティングシステム,デジタル回路
この中から3問程度出題され3題すべてに解答する.出題にはJavaまたはC言語を使用する場合がある.
専門科目Ⅱ
専門科目Ⅰの科目に加え,機械学習,グラフィクス,自然言語処理,バイオインフォマティクス,コンピュータビジョンを出題範囲とし,この中から6問程度出題される.2問選択して解答する.C言語を使用する場合がある.
専門科目ⅡはⅠの内容も含まれているので主にⅠの内容から勉強するとよいでしょう.
専門Ⅰから順に参考書と勉強法について紹介していきます.因みに学校推薦の参考書は基本難しいか,海外の本を英訳したものなので言い回しばかりでわかりづらいです.
情報数学
情報数学は正直出題されにくいのでそんなに対策はしませんでした.読んだ参考書は1つのみ
この本は小難しく書いていないので電車の中などでサクッと読めます.よく構成されているなぁという印象です.情報数学は様々なエントロピーの理論と導出からハフマン符号の内容さえ押さえておけば十分かと思います.
それに出題されたところでオリジナルルールの符号化をして,そのエントロピーを求めよとか,確率や確率遷移の問題でエントロピーを求めよとか,それくらいしか使いどころがなさそうです.しかし何が出るかわからないので知識として持っておくことは重要です.本を買わないにしてもサイトでエントロピーを勉強しておくとよいでしょう.
数値計算
数値計算は解析や線形代数の数学の知識がかなり必要で出題範囲もかなり広いです.私が最も苦労を要した科目です.
この本には解答がありません.問い合わせたところプログラムがようやく公開されましたが一部しかありません.なんとこの本は「学校推薦の参考書」です.後輩たちのためにも全解答が公開される日が来るといいですね.でもまとまってはいます.解答はないけど.
ただこれを読むだけでは公式が出てきた背景がわからず,暗記するだけになってしまいます.そのため東京大学が公開している数値解析の授業(https://ocwx.ocw.u-tokyo.ac.jp/course_11404/)を参考にすると良いと思います.松尾さんのしゃべり方がくせになります.
数値解析で主に問われるのはニュートン法(2変数以上もあり),コレスキー分解,誤差系で常微分方程式の計算法,偏微分方程式の計算法も出ますが正直難しいので私は解きませんでした.計算方法を知るだけでは大門中30%くらいしか取れないので計算の安定性や次数,収束性も押さえておきましょう.
離散数学
離散数学はほぼ毎年出題される常連さんです.ただ範囲も広く地頭が最も試される科目です.形式言語やアルゴリズムと密接に関係しており考え方を知っておくことで解ける問題がかなり増えるので勉強することに越したことはないです.専門科目の中で最初に勉強するのがいいかもしれない.使った参考書はやさしく学べる離散数学と離散数学への招待です.
やさしく学べる離散数学で基本を学び,離散数学への招待で楽しさを学ぶとよいでしょう.英訳本なので回りくどく長いですが基本は上巻のみで十分なので我慢して読みましょう.私は下巻をほとんど読んでません,時間なかったし.離散数学への招待も答えはないので誰かが共有している答えか答え有の別の参考書で演習しましょう.いろんな解法に触れることで問題のアプローチの仕方が思いつくようになるのでたくさん問題を解きましょう.
離散数学の主な問題はノードとパスの問題に帰着できるので,小道や閉路のノードとパスの関係を読み込んでおくことで証明系は大丈夫かと思います.写像や同値関係,順序性,閉包などはよく聞かれます.証明法をおさえておくことが重要です.
アルゴリズムと計算量
アルゴリズムについて,範囲はそんなに広くはないものの深くまで掘る必要があるので難しいです.参考書は学校指定のものが最も簡潔でわかりやすいです.私は主にアルゴリズムイントロダクションで勉強しました.
アルゴリズムイントロダクション 第3版 総合版:世界標準MIT教科書
- 作者: Thomas H. Cormen,Clifford Stein,Ronald L. Rivest,Charles E. Leiserson
- 出版社/メーカー: 近代科学社
- 発売日: 2018/01/09
- メディア: Kindle版
- この商品を含むブログ (4件) を見る
学校指定の参考書でアルゴリズムの概要を学びつつ,アルゴリズムイントロダクションで演習するのが効率的です.アルゴリズムイントロダクションは分厚いですが丁寧に書いてあり,わかりやすいです.漏れなくやればどんな問題にも対応できるかと思います.計算量とアルゴリズム構築,具体的な計算,例外の計算(ダイクストラ法の負の値の対応など),アルゴリズムの比較(ダイクストラ法とワーシャルフロイド法など)が主に問われるのでここら辺を意識しながら勉強するとよいでしょう.
因みに蟻本やプロコン対策のデータ構造とアルゴリズムはアルゴリズム構築や計算量の勉強に向いていますがやるくらいならアルゴリズムイントロダクションを時間かけてやる方が効率的だと思います.
形式言語
形式言語とオートマトンにはかなり苦労しました.オートマトンの構成や定義,証明など暗記することが多い科目だなと個人的に感じました.オートマトンの構成は完全に思いついたもん勝ちなので経験と発想を鍛えることが重要です.
使った参考書はオートマトン・言語理論の基礎,オートマトン言語理論-計算論〈1〉,計算理論の基礎1です.
- 作者: 米田政明,大里延康,広瀬貞樹,大川知
- 出版社/メーカー: 近代科学社
- 発売日: 2003/05/01
- メディア: 単行本
- 購入: 3人 クリック: 19回
- この商品を含むブログ (5件) を見る
オートマトン言語理論 計算論〈1〉 (Information & Computing)
- 作者: J.ホップクロフト,J.ウルマン,R.モトワニ,John E. Hopcroft,Jeffrey D. Ullman,Rajeev Motwani,野崎昭弘,町田元,高橋正子,山崎秀記
- 出版社/メーカー: サイエンス社
- 発売日: 2003/04/01
- メディア: 単行本
- 購入: 1人 クリック: 172回
- この商品を含むブログ (19件) を見る
- 作者: Michael Sipser,太田和夫,田中圭介,阿部正幸,植田広樹,藤岡淳,渡辺治
- 出版社/メーカー: 共立出版
- 発売日: 2008/05/21
- メディア: 単行本
- 購入: 6人 クリック: 68回
- この商品を含むブログ (30件) を見る
オートマトン言語理論-計算論〈1〉はこれまで読んだ本の中で一番わかりにくい本です.これで勉強するのはお勧めしません.私は最初にこれを読み,だいぶ時間を無駄にしました.
オートマトン・言語理論の基礎は証明がない代わりにオートマトン構築問題が多く取り扱われており具体的な解答があります.形式言語は新たなルールで生み出された言語に対して構築,証明することが大事なので計算理論の基礎で慣れておくことが大切です.
有限オートマトンと正則言語,自由文脈言語の対応と棲み分けは問題としてもよく突っ込まれます.正則言語と自由文脈言語のPumping-Lemmaは証明系の要なので補題の証明も含めて覚えておきましょう.
内部生は先生お手製の教科書を持っておりそこに試験の類似問題が載っているそうです.東京大学の友人がいるなら譲り受けるのがいいと思います.「蓮尾一郎 形式言語理論」で調べれば授業ページが出てきます. そこには実際の期末テストの内容などがあり過去に入試でも出題された内容が解答付きで載ってるので利用するほかないです.(ただ教科書は学内ネットのみアクセス可能です.)答えを見る感じ,この教科書は計算理論の基礎を基にしてる気がします.
論理学,デジタル回路
論理学はコスパがいいです.学習に時間がかからず,本も1冊だけで十分なのですぐに対策が終わります.論理回路はやり方を覚えれば,あとはロジカルに構築していくだけなので点も取りやすいです.参考書は論理回路入門だけ使いました.
入試の傾向としては既存のカウンタや加算器を工夫して使わせる問題が出がちです.(H31 専門Ⅰ 大門1がいい例です.)なので論理回路入門の章末問題はしっかりやった方がいいです.また信号機を作ろう!的な順序回路はあんまり出題されることがないので一度読むだけ読んで後は組み合わせ回路~カウンタを重点的にやるとよいでしょう.まだ出題されたことはありませんがstatic-1-hazardとか特殊な事例も押さえておくと完璧だと思います.
コンピュータアーキテクチャ(プログラミング言語,計算機アーキテクチャ)
ここが一番時間をかけたといっても過言ではないです.入試本番1問も出ませんでしたが(泣)アーキテクチャ系は暗記が命です.知らないと書けません,解けません.例年通りならば必ず出ます.やりましょう.絶対です.
参考書は有名なパタヘネ本(コンピュータの構成と設計:著者のパターソンとヘネシーよりパタヘネ本と呼ばれる)から手を付けましたが完全に間違いでした.丁寧に書いてある割に言い回しのせいでわかりづらく,きついです.また重く幅を取るため外に持ち運んで勉強したい方には向きません.鈍器に近いです.でも持っておいた方がいいのは事実です.細かいところを突かれたときパタヘネ本にしか書いてないことがあるので辞書的な役割で持っておくのが吉です.一番使った参考書は電子情報通信レクチャーシリーズのコンピュータアーキテクチャです.これは東京大学の実際の授業でも使われている参考書でパタヘネ本を簡潔にまとめた本という印象です.エッセンスのみを抽出しているのでわかりやすく,問題も解答付きで載っているので勉強しやすいです.
コンピュータアーキテクチャ (電子情報通信レクチャーシリーズ)
- 作者: 坂井修一,電子情報通信学会,電子通信学会=
- 出版社/メーカー: コロナ社
- 発売日: 2004/03/01
- メディア: 単行本
- 購入: 8人 クリック: 75回
- この商品を含むブログ (2件) を見る
アーキテクチャでよく問われるのが仮想記憶,並列構造です.仮想記憶はTLB,ページテーブル,キャッシュ,2次記憶とそれぞれに構成が異なります.それゆえに頭がこんがらがりよくわからなくなるのでしっかりとまとめて暗記することが大切です.さらに手法が様々なので名前と手法をリンクさせましょう.
仮想記憶はなぜかサイトによってやり方がまちまちで混乱した記憶があるのでいつか当ブログでまとめたいです.並列構造はコンピュータの機構をしっかり理解しているか問いやすいので出題される傾向にあります.ただそんなに深いことは聞いてこないので教科書に載っている内容をしっかりと覚えていれば対応できるレベルだと思います.
機械語やディスクのシーク系はたまに出ることがあります.覚えておいて損はないでしょう.しかし機械語は命令の形さえわかってしまえばプログラム問題と一緒ですし,ディスクのシーク系は他大学の過去問を見てみると問題にルールが書いてあることが多いのでそこまで構える必要はなさそうです.(断定はできません.)
電気情報の過去問と傾向は似ているのでコンピュータ科学の過去問が終わってしまった人は解いてみるのもよいでしょう.
オペレーティングシステム
オペレーティングシステムは結構範囲が広いので何を対策したらいいのかよくわからないです.過去に出たのはデッドロック,ダイニングフィロソフィア問題,ページング・セグメンテーション,スケジューリング…傾向らしいものがないです.ただスケジューリングは他のアーキテクチャ系と絡めやすいので出されがちなのかなと思います.ここは1冊の参考書をパラ見して過去に出された用語を中心に攻めていくのが効率的な学習方法です.使った参考書は以下の3つです.
オペレーティングシステム (未来へつなぐ デジタルシリーズ 25)
- 作者: 菱田隆彰,寺西裕一,峰野博史,水野忠則
- 出版社/メーカー: 共立出版
- 発売日: 2014/09/09
- メディア: 単行本
- この商品を含むブログ (1件) を見る
岩波講座 ソフトウェア科学〈〔環境〕6〉オペレーティングシステム
- 作者: 前川守
- 出版社/メーカー: 岩波書店
- 発売日: 1988/09/06
- メディア: 単行本
- 購入: 3人 クリック: 10回
- この商品を含むブログ (2件) を見る
未来へつなぐデジタルシリーズはデッドロックについて詳しく書いてあったのでそこだけ参考にして他は読んでません.情報工学レクチャーシリーズはすべて読みました.章末問題は解答が詳細に書いてあってわかりやすいです.排他制御問題とスケジューリング問題がかなりしっかり書いてあるのでお勧めです.
ソフトウェア科学シリーズの方は古い本かつ分厚いので,最初抵抗感がありましたが読んでみれば簡潔にわかりやすく書いてあるのでこれもおすすめです.ここにしか書いてないもので早稲田の院試に出たものもあるのでここで点を取りたい人は必読といってもいいくらいです.
機械学習
機械学習は私の専門でもあったのでそんなに勉強せずに行ったのですがこれが間違いでした.手法を知っているだけではなく統計的な面から論ずる力がないと解答として不十分なものとなってしまうのでちゃんと本を買ってやりましょう.
学校指定の本はパラ読みしてみましたが重要な公式がいくつか書いてありまとめてあるという印象を感じました.読み物として良くできてはいますが,入試で聞かれるような問題を解くという感じはないです.そのため別の本で対策すべきかと思います.
統計的機械学習―生成モデルに基づくパターン認識 (Tokyo Tech Be‐TEXT)
- 作者: 杉山将
- 出版社/メーカー: オーム社
- 発売日: 2009/09/01
- メディア: 単行本
- 購入: 3人 クリック: 76回
- この商品を含むブログ (5件) を見る
その他
グラフィクス,自然言語処理,バイオインフォマティクス,コンピュータビジョンはやってません.すいません.しかし,バイオインフォマティクスに限って言うと,ただの確率の問題なので本番中に解ける問題がなくて困ったときはチャレンジしてみるのも手です.書くいう私も当日は機械学習と数値解析の問題がわからずコンピュータビジョン?グラフィックス?的な問題を選択したので,ここら辺は勉強して知識を蓄えるというより問題を読み込む力をつけることが大事なのかもしれないです.
まとめ
私の場合,専門のために勉強した内容がほとんど本番で問われませんでしたが勉強の過程で身に着けた「限られた時間で考える力」を駆使することで合格できました.そのため知識の暗記も重要ですが5年分の過去問を自分の力で解くことを意識して勉強すると良いのではないかと思います.
数学と合わせて全体で6~7割を目安にとれるように頑張ってください.でも本番は難易度が上がることで5割で合格できることもあるので全然解けなくても気を落とさずちゃんと面接には行ってくださいね.