【京都大学大学院】情報学研究科 通信情報システム専攻 計算機アーキテクチャ、アルゴリズム論の対策

はじめに

京大(通信情報)の情報系の科目の出題範囲は独特です。計算機は、一般的な講義の前半部分からの出題が多いです。アルゴリズムは、動的計画法以外の範囲からの出題が多いです。概要から説明していきます。

京大 情報学研究科 通信情報システム専攻 院試の全体

2022年度までの出題分野について

下記の試験科目9題から4題を選択し、解答する形式でした。試験時間は180分です。45分/1題のため、時間に余裕があります。

専門基礎Aは、学部1,2年の講義からの出題が多いです。専門基礎Bもありますが、これは学部3年レベルの内容が多いです。

京大 情報学研究科 通信情報システム専攻(専門基礎A)の大問構成 2022年まで
  1. 線形代数、解析学(A-1)
  2. 微分方程式、複素関数、ラプラス変換(A-2)
  3. 電磁気学(A-3) ←本記事で紹介
  4. 電気回路、電子回路(A-4)
  5. 情報理論(A-5)
  6. データ構造とアルゴリズムとプログラミング(A-6)
  7. 計算機アーキテクチャ(A-7)
  8. オートマトンと言語理論(A-8)
  9. 情報数学(A-9)

両方、試験時間に対して余裕がある設問内容になっています。アルゴリズム論は他大学と同等の出題範囲です。

アルゴリズム論は、ハッシュ、2分木(グラフ)ソートからの出題が多いです。取り扱っている参考書が多く、満点を狙える内容になっています。

後半は、疑似コードを読み解き、動作の計算、説明をする問題が毎年テンプレになっています。これも、プログラミングをしていれば特に対策は不要です。

日々の勉強がモノを言いそうな問題セットです。

計算機アーキテクチャは、本当に基礎範囲からの出題です。

前半は、2進数の計算を2の補数、または絶対値表記で行います。絶対値表記は、他大学の試験問題では出題されないものの、内容さえ理解してしまえば特に難しい内容ではありません。

後半は、計算機アーキテクチャの概要についての説明問題、また、パイプラインプロセッサの計算時間を求める問題が多いです。

説明問題は、教科書の内容を暗記することで点数が安定します。パイプラインについては、数値が変わるだけのことが多いので、一度解き方を理解さえしてしまえば、楽に解くことができます。

個人的には、専門科目Aで最もお買い得な大問だと思います。電気系出身者は敬遠してしまうかもしれませんが、もしもの時の保険科目にしても、そこまで勉強時間が取られない優良物件となっています。

<注意> 2023年度以降の出題について

2022年度までに対し、試験範囲が変更になりました。

今まで、専門基礎Aは選択式でしたが、下記4題が必修になりました。そして、必修に選ばれなくなった科目は専門基礎Bに移動になりました。

京大 情報学研究科 通信情報システム専攻(専門基礎A)の大問構成 2023年以降
  1. 線形代数、解析学
  2. 論理回路
  3. 情報理論
  4. 計算機アーキテクチャ
京大 情報学研究科 通信情報システム専攻(専門基礎B)の大問構成 2023年以降
  1. 数学(複素関数、フーリエ解析、微分方程式)
  2. 電磁気学
  3. 電気電子回路
  4. データ構造とアルゴリズム
  5. プログラミング言語
  6. 情報数学
  7. 情報通信工学(情報伝送、ネットワーク)
  8. 通信基礎論(通信工学)
  9. 電波工学(電磁波、アンテナ、伝搬)
  10. 計算機システム
  11. オートマトンとアルゴリズム論
  12. プログラミング言語処理系とOS
  13. 計算と論理

計算機アーキテクチャが必修になりました。本専攻を志望する際、対策が必須になりました。

そして、データ構造とアルゴリズムは専門基礎Bに移動になりました。

出題される科目群に変化はありましたが、出題範囲及び出題分野は2022年度に実施した入学試験と変化していないことを京大HPで説明されています。

ですので、次章の傾向と対策の説明内容自体は、2022年前後で特に変わらないです。

傾向と対策

全体

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

  • 2023年:
    アルゴリズム:出題無し
    計算機の基礎:浮動小数点の計算。パイプライン命令の説明。実行時間。
  • 2022年:
    アルゴリズム:ハッシュ法とデータの挿入方法。疑似コードの計算。
    計算機の基礎:2進数の計算(2の補数、絶対値表現)。浮動小数点の演算。
           命令セットアーキテクチャの説明。パイプライン命令の実行時間。
  • 2021年:
    アルゴリズム:無向グラフと隣接行列。疑似コードの計算。クイックソートの説明。
    計算機の基礎:2進数の計算(2の補数、絶対値表現)。メモリの整列化制約。
           パイプライン命令の実行時間。
  • 2020年:
    アルゴリズム:線形リストへのデータ挿入。疑似コードの計算。マージソートの説明。
    計算機の基礎:2進数の計算(2の補数、絶対値表現)。浮動小数点演算の説明。
           データアドレッシングモードの説明。
  • 2019年:
    アルゴリズム:2分木の構造。疑似コードの計算。基数ソートの説明。
    計算機の基礎:2進数の計算(2の補数、絶対値表現)。桁上げ選択加算器の説明。
           パイプライン命令の実行時間。
  • 2018年:
    アルゴリズム:最悪時間計算量の計算。疑似コードの計算。
    計算機の基礎:2進数の計算(2の補数、絶対値表現)。シフト演算。
           桁上げ先見加算器の説明。ロードストアアーキテクチャの説明。

アルゴリズム論の疑似コードの計算は、ユークリッドの互除法など、数学的な問題を背景にコード化したものが出題されることがあります。変数の動きを追うことの他に、計算内容が何をしたいのか、高校数学の知識を思い返しながら読んでいくと良いです。

計算機の基礎は、前半の問題はテンプレなので必ず取りたいです。こちらの記事でも説明していますので、是非読むことをオススメします。後半は、説明問題が多いですが、詳しい専門書に必ず記載されている内容です。次章にて対策書を紹介します。

対策に使える参考書(アルゴリズム論)

基本的に、下記の参考書一択だと思います。

Cによるアルゴリズムとデータ構造(改訂2版)  茨木 俊秀 (著)

京大の教授の方が執筆されている教科書です。時間計算量、ソート、動的計画法など、バランスよく説明されています。内容が分かりやすく、それでいてサンプルコードも充実しています。まさに、本院試を攻略するために生まれてきた本です。

それでいて、院試が終わってからも、プログラミングをする際に読み直すことがあります。それくらい素晴らしく、一生持っておきたい本です。

対策に使える参考書(計算機の基礎)

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

計算機の原理、構造について事細かに記載しています。400ページほどあり、本科目にはオーバーワークかもしれません。

しかし、専門基礎Bで計算機アーキテクチャを選択するならば、結局上記の本を購入することになります。大は小を兼ねる観点で、購入して良いかもしれません。

使い方としては、2進数の計算、命令セット、パイプラインの実行時間について記載されているページをつまみ食いする方法になると思います。それぞれ3章の3節、2章、4章の最初になります。多く見積もっても80ページほどで、実質5分の1の分量です。

他にも計算機アーキテクチャの本はありますが、上記3分野の内容をある程度の分量で記載しているものがなかなか見当たりません。演習問題も充実していることから、こちらを購入される方が良いでしょう。

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

2進数の計算は、一般的な内容ですので特に取り上げません。

命令セットとパイプラインに関する問題もあまり無いのが実情ですが、東工大(計算科学系)(問9)、阪大(電気電子情報通信専攻)(論理回路と計算機)をオススメしたいです。全部の年度が似ているわけでは無いですが、R5年、R1年など似た問題があります。ご自身で使えそうと思った問題を解いてみることをオススメします。

たまに、加算器に関する知識を問われることがあります。下記の記事で補強することもオススメします。

最後に

本問は、対策のしやすさから電気系の学生にもオススメできる科目です。参考書の値は張りますが、勉強時間と相談の上、保険科目に出来ればと思います。

タイトルとURLをコピーしました