情報学専攻入学者選抜試験
情報科学問題冊子

注意事項

１. 問題冊子は、本表紙を含めて全部で１４ページあります。レポート作成開始時に問題冊子のページ数を確認して、落丁がある場合は直ちに試験本部へご連絡ください。

２. 解答は解答用紙に記入してください。問題冊子に記入しても採点されません。

３. 解答用紙は印刷して全て提出してください。

４. ５分野から３分野を選んで解答してください。解答した分野のみが採点されます。

数学・数理系

2020-07 情報科学問題冊子

以下の全ての問題について、途中の計算や説明を明記し、答えよ。
（問１） 行列!, #を次のように定めるとき、行列!, #の固有値と固有ベクトルを求めよ。ただし、固有ベクトルは大きさを 1 に正規化しておくこと。

!=#

1 2
5 6
(,* = #
(3 46 7（問２） （１）,（２）の各問に答えよ。
#$(") #'(") # ! $(") # ! '(")

（１） $(&) = & ! , )(&) = * !" とするとき、 #" ,#", #" ! ,#((")（２） 設問（１）の結果をふまえて、微分方程式 #" = & ,#" !

#)(")#"をそれぞれ求めよ。

= 2-(&) の一般解をそれぞれ求めよ。
（問３） ガロア体において（１）〜（３）の各問に答えよ。

（１） ＧＦ（３）の要素を係数とする最高次の係数が１である２次の既約多項式を全て求めよ。
（２） ＧＦ（３）の要素を係数とする方程式 ｘ2 + １＝０ の解の一つをαとして、拡大体ＧＦ（３2）の元を全て求め、（１）で求めた既約多項式を全て因数分解しなさい。

（３） ＧＦ（２3）において、α4（α＋α6）-1 を求めよ。
（αは既約多項式の解）ソフトウェア系

2020-07 情報科学問題冊子（問１） 探索アルゴリズムと整列アルゴリズムについて以下の演習・調査を実施し，レポートにまとめよ．
（１） 8 つのデータが配列 int a[] = {2, 3, 5, 7, 11, 13, 17, 19}; として保存されている．
この 8 個のデータから二分探索で要素を探索することを考える．例えば，13 を探索したときと6 を探索したときの二分探索のトレース結果を以下に示す．なお変数 low は探索範囲の左端，
変数 high は探索範囲の右端，変数 middle は探索範囲の中央 (middle = (low+high) / 2 (整数演算は切り捨てを想定))を示す．
search(13):turn 1 start: low: 0, high: 7, middle: 3
end: low: 4, high: 7, middle: 3turn 2 start: low: 4, high: 7, middle: 5correct.
search(6):turn 1 start: low: 0, high: 7, middle: 3
end: low: 0, high: 2, middle: 3turn 2 start: low: 0, high: 2, middle: 1
end: low: 2, high: 2, middle: 1
turn 3 start: low: 2, high: 2, middle: 2
end: low: 3, high: 2, middle: 2fail.
（１−１） 上記のトレース結果を踏まえて，二分探索のアルゴリズムの実装方法を理解し，2 を探索した場合と，18 を探索した場合のトレース結果をまとめよ．
（１−２） 上記の表示が可能な二分探索を実施するプログラム (C 言語）を実際に作成せよ．レ
ポートには作成したプログラムと 2 と 18 の探索時の実行結果を記せ (解答用紙にプログラムの雛形を記すので利用して良い)．

ソフトウェア系

2020-07 情報科学問題冊子（２） 挿入ソートが下記のプログラムで実装済みであるとする．
int compare(int i, int j){return a[i] - a[j];}void swap(int i, int j){
int tmp;
tmp = a[i]; a[i] = a[j]; a[j] = tmp;
return;}void insertionSort() {for (int i = 1; i < dataNum; i++) {int j = i;while(j>=1 && compare(j-1, j) > 0) {swap(j-1, j);j--;}}return;}（２−１） この時，配列 int a[] = (A) {1, 2, 3, 4, 5, 6}; の場合，(B) {6, 5, 4, 3, 2, 1}; の場合 (C){2, 3, 4, 5, 6, 1}; の場合の 3 通りについて，compare() 関数(メソッド) の実行回数とswap()関数(メソッド) の実行回数を示せ．実際にプログラムを作成して測定して良い．
（２−２） 挿入ソートにおけるソートするデータが(A)整列済み,(B)逆順整列済み,(C)1 番目から最後の 1 個前までが整列済みで最後のデータが最小値，のそれぞれについて整列の計算量を導出せよ（計算量をいきなり書くのではなく，なぜその計算量になるのか順を追って説明せよ）．

ソフトウェア系

2020-07 情報科学問題冊子（３） 以下のデータ構造とアルゴリズムの組み合わせに関する問題に答えよ（データ構造・アルゴリズム の表記で組み合わせを示す）（３−１） 配列・線形探索における「登録」「探索」「削除」の計算量とその計算量になる理由を示せ．
（３−２） 配列・二分探索における「登録」「探索」「削除」の計算量とその計算量になる理由を示せ．
（３−３） 配列＋連結リスト・ハッシュ（チェイン法）における「登録」「探索」「削除」の計算量とその計算量になる理由を示せ (ハッシュテーブルサイズ B がデータ数 N よりも十分に大きいと仮定)．
（３−４） 配列・ハッシュ（オープンアドレス法）における「登録」「探索」「削除」の計算量とその計算量になる理由を示せ (ハッシュテーブルサイズ B がデータ数 N よりも十分に大きいと仮定)．
（４） 以下の整列アルゴリズムに関する問題に答えよ．なお，計算量で示されている.は登録されているデータの個数を示す．
（４−１） 「バブルソート」「挿入ソート」「選択ソート」の 3 つから 1 つを選んで利用しようとする場合を考える．計算量の観点からするといずれの手法もO(.! )だが，通常，バブルソートの処理が一番遅くなる．その理由を示せ．
（４−２） 「クイックソート」は整列範囲の右端を枢軸（ピボット）に選ぶ方法では，整列済みのデータの整列の計算量がO(.! )になってしまう．この理由を示せ．また，これを改善し，整列済みのデータでも整列の計算量がO(. log .)になるようにするための手法を説明せよ．

ソフトウェア系

2020-07 情報科学問題冊子（問２）2 台のロボット O (織姫) と H (彦星) が 5×5 マス上にいる．
図 1 の通り，O と H の初期位置はそれぞれ座標 (1, 1) と (5, 5)とする．図 2 の通り，各マスには移動時の報酬の値がラベル付けされている．マス 7 の報酬の値を 8(7) と表す．マス 7 の整数
座標を (&, 9) とするとき，|& − &′| ≤ 1 または|9 − 9′| ≤ 1 を満たす整数座標 (&′, 9′) のマス 7′ を 7 の近傍と呼ぶ．ただし
1 ≤ &, & * , 9, 9 * ≤ 5 とする．このとき，7 のすべての近傍からなる集合を Γ(7) と表す．図 3 の通り，7 の近傍は最大 9 つあり，それぞれを 7+ , 7, , … , 7- と表す．なお，端のマスでは近傍は 9つ存在しないことに注意する (例えば座標 (1,1) のマスの近傍
は 7+ , 7. , 7/ , 7- の 4 つ)．
さて，2 台のロボットは今いるマス 7 から 1 ステップで 7 の任意の近傍 7′ に移動できる．ここで 7 から 7* へ移動する確率 @801 (7′ | 7) は 2 台のロボット共に同じで次のように定義される:@801 (7′ | 7) =8(7′).
∑3"∈ 6(3) 8(72 )C ステップ後にロボット O がマス 7 に存在する確率を
99 (7,9@87"8(7, C) と表すとき，@87"8C + 1) と @87"8(72 , C) 間には次の漸化式が成り立つものとする:

9 (7,9@87"8C + 1) = ∑3"∈6(3)(@87"8(72 , C) ∙ @801 (7 | 72 )),ただし C ≥ 0, 72 ∈ Γ(7) ．
: (7,: (7,また C ステップ後にロボット H がマス 7 に存在する確率を @87"8C) と表すとき，@87"8C + 1) と: (7,@87"8C) 間にも上記と同様の漸化式が成り立つものとする．

ソフトウェア系

2020-07 情報科学問題冊子

このとき，以下の問いに答えよ．
（１）

座標 (5, 5) のマス 7 の各近傍 72 ∈ Γ(7) に対して，7 から 72 に移動する確率 @801 I72 J 7)を近傍毎にそれぞれ答えよ．
（２）

9C = 1 のとき，ロボット O が存在する確率 @87"8(7, 1) が最大となるマス 7 の座標を答えよ．

（３）

C = 2 のとき，ロボット O と H が同じマスで出会う確率，すなわち全てのマスの集合をK と書

9: (7,くとき ∑3∈; (@87"8(7, 2) ∙ @87"82)) を答えよ．

（４）

9 (7,: (7,C = 5 のとき，ロボット O と H が出会う確率，すなわち @87"85) ∙ @87"85) が最大となるマス 7 の座標とその確率を答えよ．なお単に答えを示すだけでなくどのようにその答えを導出したかがわかるよう解法の手順も説明せよ．プログラムを作成した場合はそれを添付しても構わない．

ハードウェア系

2020-07 情報科学問題冊子（問１）コンピュータ内部では数値はすべて０と１の組み合わせとして処理される。いま、命令長 16 ビットのコンピュータにおいて、整数を 16 ビットの 2 進数で表現することを考える。負の数は 2 の補数を用いて表すとする（最上位ビットが符号ビットとなる）。このとき、以下の問いに答えよ。
（１）16 ビットの 2 進数で表現された以下の数を符号付き 10 進数で表せ。ただし、計算の過程も示すこと。
a)0000101011001110

b)

1111000010011101

c)

1000000000000000（２）16 ビットの 2 進数の中から、任意に正の数と負の数を 1 つずつ選んで加算しても、決してオーバーフローが起こらないことを証明せよ。

（３）現代のコンピュータでは通常、2 の補数を負の数として扱っている。1 の補数を負の数として扱うと、数字を符号付き 10 進数で表示するときに変換がより容易になるという利点があるにもかかわらず、1 の補数が負の数として採用されない理由について考察せよ。

ハードウェア系

2020-07 情報科学問題冊子（問２）次の文章を読み、問いに答えよ。

コンピュータの主な機能として、情報の入力、演算、記憶、制御、出力、の５大機能が挙げられる。
このうち、中央処理装置（CPU）は主に演算と制御の機能を担う。① CPU は、主記憶装置（mainmemory）から命令を読み出し、デコーダによって解釈し、演算を行ったあと、結果をふたたび主記憶装置に格納することで命令を実行する。
CPU は、情報を処理するために一時的に蓄えるレジスタや、演算を行う ALU、これらの素子や主記憶装置をつなぐためのバスなどで構成される。主記憶装置には命令とデータを区別せず格納でき、プログラムされた命令に従ってデータを処理することができる。
以上のようなアーキテクチャは②と呼ばれる。

（１）下線部①で、主記憶装置にアクセスする方法として様々なアドレシング方式（Addressing mode）が用いられる。アドレシング方式のひとつであるポストインクリメントレジスタ間接アドレシング（Post-increment register indirect addressing）について、その特徴を説明せよ。

（２）文中の②にあてはまる語句を答えよ。

（３）②のようなアーキテクチャが広く採用された理由について考察せよ。

ハードウェア系

2020-07 情報科学問題冊子（問３）２人で遠隔じゃんけんを行う装置を設計する。表１のように、A と B が出し手を入力すると、勝者の名前が表示される仕組みである。A，B の出し手を入力とし、結果を出力とすると、入力は（未入力・グー・チョキ・パー）の４種類、出力は（未表示・A・B・あいこ）の４種類となり、入力４ビット、出力２ビットの演算となる。
表２ 入出力の対応表

表１ A, B の出し手と結果の組み合わせ
AB

未⼊⼒

グーチョキ

パー

未⼊⼒

未表⽰

未表⽰

未表⽰

未表⽰

グー未表⽰

あいこ

AB

チョキ

未表⽰

B

あいこ

Aパー

未表⽰

AB

あいこ

A1A2

未⼊⼒

００

グー０１

チョキ

１０

パー

１１S1S2

未表⽰

００A０１

B

１０

あいこ

１１

（１）A の入力を（A1, A2）、B の入力を（B1, B2）、出力を（S1, S2）として、真理値表を作れ。入出力の対応は表２に従うものとし、(B1, B2)の対応は（A1, A2）の対応表と同様とする。

（２）（１）の真理値表をカルノー図を用いて論理圧縮する。S1 について、図１に示すカルノー図を書き、図２の論理回路を作成した。不足している箇所を補って、カルノー図と論理回路を完成させよ。ただし、AND 素子は全部で４つまで使用できるものとする（AND 素子は２〜４入力のものを使用できる）。

図１ S1 に関するカルノー図
図２ S1 の論理回路

OS とネットワーク

2020-07 情報科学問題冊子（問１）各自が普段使用している PC がプライベートネットワーク上にあり，ゲートウェイを通じてインターネットに接続されているとする．その PC 上の Web ブラウザで https:// から始まるインターネ
ット上の Web ページへアクセスすることを考える（URL は受験者が任意に選定する）．以下の設問に回答せよ．
（１）どのようなやりとりが行われて所望の Web サーバへリクエストが正しくルーティングされるか，またレスポンスが正しく返ってくるのか，ネットワークの観点から詳しく説明せよ．特にリクエストの送信時においては自 PC 内のアプリケーション層からデータリンク層までの流れを実際に自分の PC で実行した ifconfig/ipconfig コマンド，arp コマンド，traceroute/tracert コマンドの結果を添付して，説明すること．また，次のキーワードを必ず使用すること．図を描いてもよい．
[キーワード]SSL/TLS，サーバ証明書，なりすまし，ポート番号，443 番，共通鍵，公開鍵，MAC アドレス，
IP アドレス，
グローバル IP アドレス，ルーティング，デフォルトゲートウェイ，ARP，DNS，nslookup，
TCP，HTTP，リクエスト，レスポンス，NAT，アプリケーション層，トランスポート層，ネットワーク層，同一セグメント，HTML，CSS（２）Web サーバでは，Web ブラウザからのリクエストに対して，どのようなソフトウェア的な処理が行われてホームページやインラインコンテンツを正しく返すのか，オペレーティングシステムの観点か
ら詳しく説明せよ．特に Web サーバが起動されてから，リクエストを受信し Web ブラウザへ返信する処理まで，Web サーバ内のアプリケーション層からディスクアクセスまでを考慮して説明すること．さらに，多数の Web ブラウザからの同時に膨大なアクセスが Web サーバに到達する時，Web サーバでどのような現象が発生する可能性が高まるか，その理由と共に，どのような改善を施せばその現象を抑制できるか説明せよ．その際，次のキーワードを必ず使用すること．図を描いてもよい．
[キーワード]プロセス，ソケット，ファイルディスクリプタ，ファイル，システムコール，ライブラリ関数，バッファ，fopen()，read()，send()，recv()，リクエスト，レスポンス，ヘッダ，仮想メモリ，物理メモリ，仮想アドレス，ページイン，ページアウト，スワップ領域，ディスクアクセスヒューマンサイエンス系

2020-07 情報科学問題冊子（問１）2019 年末に始まったとされる新型コロナウィルス感染症（COVID-19）の流行 1 は、その後、世界中へと拡がり、2020 年 3 月 11 日、世界保健機関（WHO） はパンデミックを宣言するに至った。感染者と犠牲者が増え続けるなか、その対策として世界の国々でロックダウンが行著作権の関係上未掲載としています。

われ、日本でも緊急事態宣言がなされた。これにより、全世界で何十億人もの人々の生活と行動が多大な制約を受け続けている（2020 年 5 月現在）。
引用元：PengZhou, et al. ``A pneumonia outbreak associated with a new
たとえば、その感染防止のためにテレワークの導入が進められ社会における働き方が変わりつ
coronavirus of probable bat origin,'' Nature 579, pp.270-273 (2020).

つあり、教育現場でも対面授業に代わってオンライン授業やオンデマンド授業が行われている。
このことを踏まえて、（１）～（３）の設問について、それぞれ、下記のキーワードのうち 3 つ以上を用いて 100 字以上 300 字以内を目安に記述せよ（必要な場合には 300 字を超過してもかまわない）。なお、解答にあたって用いるキーワードは（１）～（３）のあいだで重複しても構わない。

引用文献：1. Peng et al. (2020) Nature 579: 207-273.
キーワード：
感覚、知覚、知識、知能、思考、推論、問題解決、意思決定、運動、順応、学習、記憶、意識、感情、パーソナリティ、コミュニケーション、共感、意図推定、ヒューリスティックス、認知的合理性、認知バイアス、ルール、フレーミング効果、利己的帰属バイアス、知的インタラクション、身体性、行動主体感、順モデル、ラバーハンド錯覚、体外離脱の錯覚、ヒューマンインタフェース、バーチャルリアリティ、マルチモーダルインタフェース (多感覚統合)、脳情報デコーディング（１） 現在のオンライン授業、あるいはオンデマンド授業の課題を情報学の観点から分析・考察せよ。
（２） （１）で挙げた課題を解決するために有効だと考えられる対策や対処方法を論ぜよ。
（３） （２）を実現するために情報学がどのような貢献をすることができるかについて論ぜよ。

ヒューマンサイエンス系

2020-07 情報科学問題冊子（問２）現代医学ではまだ特効薬が開発されていない、ある感染症の感染が拡大しているとする。この感染症は罹患者全員が感染源となる可能性がある。この感染症に罹患すると発熱や咳などの症状が出ることが知られているが、罹患者の中には症状が出ない者もいる。そこで、この感染症への罹患を発見するための検査 P が注目を集めている。検査 P に関しては、次のことが知られている。


その感染症にかかっている人に検査 P を適用すると、60%の確率で正しく陽性と判定される。



その感染症にかかっていない人に検査 P を適用すると、5%の確率で誤って陽性と判定される。
あなたは、A 地域の症状がない人の中で、その感染症に実際に罹患していた人の割合は 10%だったという報道を聞いた。
（１） A 地域の無症状の人の中から無作為に抽出された 1 人に検査 P を実施し、検査結果が陽性だったとき、次ページにあるサンプル問題の考え方を参考にして、この人が実際にその感染症に罹患している確率を求めよ。
（２） A 地域に住んでいる症状がない 100 人の中で、実際に感染症に罹患している人の数と、検査 Pの陽性的中率（本当に感染症に罹患していることを検査 P が検出する精度）には図 1 の関係性があることが知られている。検査 P の陽性的中率を我々が受け止めるうえでの注意点について述べなさい。
（３） 上記のような確率を考える際に、人は一般的にどのような思考に陥りがちなのか、「事前確率（または基準率）」ということばを用いて説明したうえで、どのようにすれば人が陥りがちな思考パターンを回避できる可能性があるか、根拠を示したうえであなたの考えを説明しなさい。

ヒューマンサイエンス系

2020-07 情報科学問題冊子【サンプル問題（Tversky & Kahneman(1980)を和訳）】ある夜にタクシーがひき逃げ事故を起こした．その町には，緑タクシーと青タクシーの２つの会社がある．町内を走るタクシーのうち緑は８５％で，青は１５％である．この事故の目撃者は，タクシー著作権の関係上未掲載としています。
は青だったと証言している．裁判所は，事件の日の夜と同じ状況で目撃者の信頼性をテストした結果，青か緑かを正しく識別できる確率は８０％であった．青タクシーが事故を起こした確率を求めよ．
引用元：Tversky, A., & Kahneman, D. ``Causal schemas in judgments
考え方：under uncertainty.'' In M. Fishbein (Ed.), Progress in social psychology.
「青タクシーが事故を起こした」という証言がなされる場合は，青タクシーが事故を起こした×正Vol. 1. Hillsdale, NJ: Lawrence Erlbaum Associates. pp. 49-72 (1980).
しく証言できた場合(Pb)と，緑タクシーが事故を起こした×間違った証言をした場合(Pg)である．
実際に青タクシーが事故を起こした確率は，「青タクシーが事故を起こした」という証言がなされる全ての場合の中で，実際に青タクシーが事故を起こした場合を考えればよい．つまり以下の式で求められる．
実際に青タクシーが事故を起こした確率 = Pb/(Pb+Pg)

図 1 感染症の罹患者数と検査 P の陽性的中率の関係