【九州大学大学院】システム情報学府 院試対策(アルゴリズム論、計算機アーキ)

試験範囲

アルゴリズム論は、データ構造、プログラミングからなります。

試験範囲が広く、出てくる言語も複数個あります。対策に時間がかかります。

計算機アーキテクチャは、科目名の通り論理回路とアーキテクチャからなります。

こちらの方が取り組みやすいと思います。しかし、パイプラインが試験範囲に含まれていたりと、論理回路の問題をただ解けば良いわけではありません。

九大 システム情報学府 院試の全体

電気電子工学専攻、情報理工学専攻と分かれています。数学は両者ともに同じ分野、選択範囲になっており、専門科目に違いがあります。

アルゴリズム、計算機アーキテクチャについては、専門科目に属しています。情報理工学専攻のみ選択可能です。

全体的な難易度ですが、アルゴリズム論は難しいと思います。前章でお話ししたように、とにかく範囲が広いです。他大学では、それぞれの科目が選択科目として存在していてもおかしくないですが、九大では全部で1科目です。非常に範囲が広いです。

おまけに、プログラミングもPython形式で記載されています。出身大学の講義が未だにC言語ですと、苦戦するかもしれません。内部生ならば当たり前にできる内容かもしれませんが、外部生には厳しい内容かもしれません。SQLを利用したデータ整理問題も出てきます。触っていないと厳しいです。

救いとしては、2024年度入試からプログラミングが廃止になったことです。これにより、アルゴリズム論のみの範囲になりました。アルゴリズム論の問題の中で一部出てくるかもしれませんが、少しマシになりました。

また、類似の問題がよく出題されますので、一度解き方をマスターすれば、点数が安定するかもしれません。

一方、計算機アーキテクチャですが、少し難しいと思います。理由はアルゴリズム論と同じです。論理回路だけの試験範囲ではないためです。パイプライン、キャッシュなど、計算機内部の動作説明問題が出題され、ここが他大学と異なります。

情報系の講義をしっかり取っていれば問題無いですが、電気系からの受験の時は苦労するかもしれません。ただ、順序回路の出題があまり無いことは救いです。論理回路の勉強はほどほどに、アーキテクチャに集中する方が良いかもしれません。

全体

最近5年分は以下の分野の出題がありました。

アルゴリズム論については、例年同じ形式の問題が多いです。1問目がデータ構造、探索、ソートのうちどれか。2問目でSQLのプログラミングによるデータ整理です。冒頭で難しいとお話ししましたが、同じ形式の問題が続いていますので、知識があれば満点狙えるかもしれません。

また、2024年からはプログラミングが試験範囲外になりますので、2問目を中心に削除になる可能性があります。

論理回路についても、同じ分野の問題が続きます。論理関数の簡単化はカルノー図を利用すれば解けます。必ず得点しましょう。

パイプラインについても計算時間が多いです。類題が少ないですが、自大の資料などを利用して勉強を進めていくと点数が安定します。たまに説明問題が出ますので、網羅的な勉強が必要です。

キャッシュについては説明問題が多いです。これも、講義資料と教科書の該当ページを読み進めていくことで、点数安定すると思われます。

教科書(アルゴリズム論)

世界標準MIT教科書 アルゴリズムイントロダクション 第4版 第1巻: 基礎・ソートと順序統計量・データ構造・数学的基礎 T. コルメン (原著), C. ライザーソン (原著), R. リベスト (原著), C. シュタイン (原著), 浅野 哲夫 (翻訳), & 5 その他(シラバス対象本)

洋書です。巻が分かれており、1巻ごとに大変詳しく解説されています。1巻目が時間計算量、データ構造。2巻目がグラフ理論です。グラフ理論も試験範囲に含まれますので、この本で試験対策を行うならば、両方の購入が必要です。ただ、出費がかさみます。

アルゴリズム設計が大好きで、院試に限らず今後ともに生きていくつもりならば、購入して良いかもしれません。

Pythonでのサンプルコードも説明していないため、プログラミング初心者には厳しいかもしれません。

Pythonを利用してのプログラミング本については、別サイトを参考にすると良いです。(管理人はあまり詳しくないため、本サイトで紹介する自信がありません。)

アルゴリズムとデータ構造 (未来へつなぐ デジタルシリーズ 10)  原 隆浩 (著), 水田 智史 (著), 大川 剛直 (著), 西尾 章治郎 (監修)

先の教科書はどうしてもオーバーワークのため、こちらを利用して対策しても良いかもしれません。阪大のシラバス本です。サンプルコードがPythonに似ている疑似コードで書かれており、解答作成の参考になると思います。加えて、本が薄めですので、すぐに1周できます。

探索問題を深く問うよりは、サンプルプログラムを与え、動作の説明をする問題が多いです。このため、概要を理解して、すぐにサンプルコードを習得した方が良いと考えます。

教科書(論理回路)

論理回路 (電子情報通信レクチャーシリーズ B- 5) 安浦 寛人 (著), 電子情報通信学会 (編集), 電子通信学会= (編集)(シラバス対象本)

論理回路は、どのような本でも問題無いと思います。理由は、真理値表からの論理関数の作成、簡単化の問題ばかり出題されるからです。これくらいならば、どの本でも解説されています。強いてシラバス本を紹介しましたが、ネットで検索して軽く復習する程度でも問題ないと思います。

一方で、計算機アーキテクチャについては説明問題が多いため、しっかりした本を選ばなければなりません。

教科書(計算機アーキテクチャ)

コンピュータの構成と設計　MIPS Edition　第6版 　上・下電子合本版 David Patterson (著), John Hennessy (著), 成田 光彰 (翻訳)(シラバス対象本)

シラバス対象本ですが、こちらも洋書です。1396ページもあり、詳しい説明になっています。ただ、1つの科目の対策に、ここまで時間を費やすことは厳しいと思います。先の洋書とともに、趣味の範囲での購入になると思います。

かと言って、何の本も無しに対策していくことは厳しいです。管理人としては下記の本をオススメします。

コンピュータアーキテクチャ(改訂5版)　馬場敬信 (著)

京大の対策ページでも紹介しました。400p有りますが、九大対策に重要になるのは中盤です。ここにパイプラインとメモリ、キャッシュの説明があります。3章の序盤で命令セットの概要。4章で、パイプラインの詳しい動作、課題、キャッシュについて学びます。少々値が張りますが、先の洋書よりは安く、院試勉強としても何とかなるボリュームだと思います。(実際に熟読する範囲は100~150p程度です。)

対策に使える他大学の問題

なるべく頻出分野ごとに並べていくと、以下のようになります。

アルゴリズム論は、京大(通信情報)の問題が一番似ていると感じます。ソートの動作原理と言うよりは、サンプルコードを渡して、その動作説明及び空欄補充に重きを置いている部分が同じであると考えます。

逆に、SQLのプログラミング問題に関しては知見がありません。がちがちの情報系大学院入試ならば、どこかの大学に似たような問題があるかもしれません。ただ、電気系と合同で実施するタイプの院試、専攻の枠組みだと該当なしになってしまうのが実情です。

論理関数に関しては、簡単化する問題ばかりのため、どこの問題でも変わりません。一応、東北大がこの手の問題を良く出しますので紹介しました。

アーキテクチャに関しては、京大(通信情報)でよく出題されます。オススメ本を利用して、類題演習に役立てると良いかもしれません。

最後に

本問は、院試対策することが厳しいです。どちらかと言うと、日ごろのプログラミングがモノを言うかもしれません。ゴリゴリの情報系の学生ならば選択すると良し、あまり自信が無い場合は、情報理論など、他の大問を選択した方が良いと感じます。