2020年度 創造情報学専攻 冬入試 専門科目再現

2020年3月2日

2020年度 東京大学 情報理工学系研究科 創造情報学専攻 冬院試の専門科目(創造情報学)の再現です。冬入試の問題はすべて回収されてしまうため、試験終了直後に問題を可能な限り書き起こしておきました。問題文の表現は実際のものとは異なります。実際の問題文は、問題文の解釈のトラブルを防ぐために、下に再現したものよりも詳しく書かれていました。

第1問

以下のような迷路の探索を考える。ロボットは前後左右のいずれかの方向に1マスずつ進むことができる。ただし、太線部分は壁を表しており、壁を超えて進むことはできない。

図1 迷路

まず、ロボットを動かして迷路を探索するアルゴリズムを考える。

アルゴリズムⅠ

  1. ロボットは最初スタート地点におり、南を向いている。
  2. 右に壁がないとき、右に 90 度回転し、前に 1 マス進む。5. に飛ぶ。
  3. 前に壁があるとき、左に 90 度回転する。5. に飛ぶ。
  4. 前に 1 マス進む。
  5. ロボットがゴールにいれば探索を終了する。そうでなければ、2. に戻る。

(1) アルゴリズムⅠを使用したとき、迷路で訪れるセルの順番を図示せよ。

(2) アルゴリズムⅠを使用したとき、ゴールにたどり着けない迷路の例を1つ図示せよ。ただし、迷路のサイズは5×3とする。

次に、ロボットを動かさないアルゴリズムを考える。

アルゴリズムⅡ

  1. 空の待ち行列にスタート地点のセルを入れる。セルには訪問済みのフラグと経路 長の情報が付随しているものとする。スタート地点は訪問済みで、経路長は 0 で ある。
  2. 待ち行列からセルを一つ取り出す。これを u とする。
  3. u に隣接するセル v を東西南北の順に次のように処理する。
    (a) もし u と v の間に壁がある場合、もしくは v が訪問済みの場合、なにもしない。
    (b) そうでなければ、v を訪問済みにする。v の経路長を「u の経路長+ 1」とする。 v がゴールならばアルゴリズムを終了する。v がゴールでなければ、v を待ち 行列に入れる。
  4. 2. に戻る。

(3)  アルゴリズムⅡを使用したときの経路長・訪問セル数を書け。また、迷路で訪れるセルの順番を図示せよ。

(4)  アルゴリズムⅡの待ち行列をスタックに変更したものをアルゴリズムⅢとする。アルゴリ ズムⅢを使用したときの経路長・訪問セル数を書け。また、迷路で訪れるセルの順番を図 示せよ。

(5)  アルゴリズムⅡの待ち行列を優先度付き待ち行列に変更したものをアルゴリズムⅣとする。 ただし、優先度は現在位置からゴールまでのユークリッド距離とする。例えば、図1の迷路におけるスタートからゴールまでのユークリッド距離は√2である。アルゴリズムⅣを使用したときの経路長・訪問セル数を書け。また、迷路で訪れるセルの順番を図示せよ。

(6)  アルゴリズムⅣの優先度を「これまでの経路長+現在位置からゴールまでのユークリッド距離」としたものをアルゴリズムⅤとする。アルゴリズムⅤを使用したときの経路長・訪問セル数を書け。また、迷路で訪れるセルの順番を図示せよ。

(7)  アルゴリズムⅡ〜Ⅴはそれぞれ最短経路を保証するか。保証しない場合は反例となる迷路を図示せよ。ただし、迷路のサイズは5×3とする。

(8)  一般的な迷路における、アルゴリズムⅡ〜Ⅴのそれぞれの時間計算量をO-記法で表せ。 ただし、優先度付き待ち行列における挿入・削除はO(log n)かかる。

第2問

アドレス幅32ビットのメモリと、そのキャッシュを考える。メモリにおいて、1アドレス には1バイトのデータを格納する事ができる。キャッシュの単位をエントリといい、エントリにはタグ、valid bit、キャッシュデータの情報が管理されている。


DMC(Direct Mapped Cache)を考える。キャッシュのインデックスはアドレスの下位2ビットである。

(1)  キャッシュを構成するための最小ビットサイズを答えよ。

(2)  以下のアドレスの順番でメモリアクセスがあった場合、キャッシュヒット率はそれぞれ何%か。
(a) 0,4,0,8,0,4,0,8 (b) 0,1,2,3,0,1,2,3 (c) 0,1,2,3,4,0,1,2

(3)  DMC のインデックスとして上位ビットを採用するよりも下位ビットを採用するほうが、 一般に効率が良い。その理由を考え答えよ。


エントリ数4のFAC(Fully Associative Cache)を考える。

(4)  キャッシュを構成するための最小ビットサイズを答えよ。

(5)  (2) (a)〜(c) の順番でメモリアクセスがあった場合、キャッシュヒット率はそれぞれ何%か。

(6)  DMCのヒット率がFACのヒット率を上回るアクセスの順番の例を1つ答えよ。ただし、7回以下のアクセスで答えること。

第3問

以下に示す情報システムに関する 8 項目から 4 項目を選択し、各項目を 4〜8 行程度で説明せよ。必要に応じて例や図を用いてよい。

  1. 抽象構文木
  2. k近傍法
  3. マルコフ連鎖
  4. 畳み込みニューラルネットワーク
  5. NAT
  6. ARP
  7. RISC
  8. PID制御