東大大学院 創造情報学専攻 専門科目対策
こんにちは！
ma3tkです！
今日は創造情報学専攻のアルゴリズム分野、ハードウェア分野についてまとめてみました。
モチロン、個人的な対策・見解ですので、参考程度に、でお願いします。
語彙説明は長くなりそうなので次回にします。
アルゴリズム分野
ソートはアルゴリズム分野の基礎ですが、一度もソートらしいソート問題は出ていません。これも穴場となるか、スルーするべきなのか…。自分はひと通り軽くやってスルーしました。
- データ構造
スタックとかキューとかリストとかハッシュとか。どんな種類があってどんな方法で実装されてて、どんな欠点があってどう補うか。計算量も調べる。基礎知識として。
- 計算量
アルゴリズムの大切な部分である計算量。この問題はもちろんあります。概念と計算量を理解するだけではなく、どうすれば高速化できるのかというのが問題になりやすいです。簡単にならどの教科書にでも載ってますが、アルゴリズムイントロダクションが一番詳しいかなと思います。
基本的な再帰から再帰の方法(深さ優先だとか、幅優先だとか)を知ることと、実際に知っているだけではなくて、問題練習をしたり、コーディングしてみて実装してみるといいと思います。自分は粗方解いてみた後に、コード化して答え合わせをしていました。自分が学習する際、再帰は理解するまでが長くかかりました。
- 練習練習練習
アルゴリズム分野はとりあえず問題慣れするのと、スマートなコードを読み解く能力と書きなおす能力が必要だと思います。読んで解きなれる作業を繰り返しましょう。
- 参考書
ベターにまずアルゴリズムイントロダクションを読み解く作業から。でなそうって思う場所があるので、そういうところはとりあえず飛ばし、簡単なソートやグラフ関係などを。理解度を高めるために章末問題等を解きましょう。ネットに答えが上がってる章もあります。
ちなみに三巻目からもソーティングネットワークが出てるので、図書館等で借りて読むのがいいかと思います。
また、ウィキペディアでプログラミング言語についても学んでおくといいかと思います。どんな言語があってどんな設計があるのかなど。
おいおい…こんなん最初からわかるわけないだろ、って人は薄いアルゴリズムの本を読んでからこれに挑むといいと思います。
ハードウェア分野
- 出題科目
コンピュータアーキテクチャ、論理回路、OSあたりがメインかと思われます。
- コンピュータアーキテクチャ
基本的に考えるよりも暗記ばっかりです。命令セットアーキテクチャ、処理速度、パイプラインとハザードあたりがキモです。何も考えずに
をやるといいと思います。わかりやすいし、詳しい。ただその分分厚いですが。
別冊は読みましたが、歴史しか書いてないのでやる必要はないです。CDも上巻に付いてるのですが、論理回路は別のほうが詳しいと思います。なので、CDはチラ見して終わりました。これがわからないって人は論理回路を先にやるといいかも…。それでも易しい気はするんだけど…。
2進数化から2進数の四則演算、簡略化、組み合わせ回路各種、フリップフロップ、カウンタ、レジスタ、状態遷移図などなど。元は全く出来なかったんですが、最終的に一番得意な科目だったと思います。簡単なので。
とりあえず全部の回路の流れと設計はできます。書いてるうちに暗記してしまったレベルになりました。状態遷移図はそんなにやってなかったんですが、この科目は単純な解き方で解けるので、受験に出たときになんとかなるレベルでした。
これはコンピュータ科学専攻だっけかの坂井修一先生の論理回路入門が最強です。薄いですが、内容がまとめられ、いくつか間違いもあり、問題もちょっとあるので、本当に入門的な感じです。ただ、色々な回路がすべてまとまっているわけではないので、この本に足りない部分はネットで調べるなり、他の教科書を参考にするなりで対応します。真理値表、カルノー図、
設計、遅延を防ぐ方法等が試験の問題のテーマかと思います。
- OS
OSも暗記ゲー(笑)状態です。授業もとってなかったんですが、こんなに簡単ならばとればよかったかと。現在のOSと程遠いくらいに基礎的な内容ですが、キャッシュメモリやページングやスケジューリングと各記憶媒体の関係がわかって目からウロコでした。これは教科書まるまる覚えてください、としか言いようがないかな。読むならば半日、舐めるように見るとちょっと時間がかかるかな。唯一セマフォとかの排他処理あたりを理解するのに時間がかかったりするので、なめてかからないほうがいいかな。
個人的にはこの二冊を同時に読み込んでました。書いていない部分とかもあるので両方あったほうがいいかと思います。
ひとこと
実は創造情報学専攻は先生が他の専攻等も兼任されているので、
- 東京大学大学院情報学環学際情報学府 先端表現情報学コース
- 東京大学大学院情報学環学際情報学府 総合分析情報学コース
- 東京大学大学院情報理工学系研究科 コンピュータ科学専攻
- 東京大学大学院情報理工学系研究科 電子情報学専攻
あたりの過去問も非常に有用です。2011年の冬入試のフィボナッチとか、学環の総合分析情報学の得意技くらいの問題でしたし。
かぶらない場所もあるので、選んでやってみるといいかと思います。
また、学環の問題は簡単なので、腕試しでやってみるのもいいですね。
最後に
教科書は読み込みよりも何度読みなおしたかがいいかと思います。
長期記憶をするためには繰り返し読むことが重要！！
入試まですぐだと思うので、早めに取り組みましょう！
