2021-07 情報科学 問題冊子

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

注意事項
以下の指示にしたがって解答してください
数学・数理系
5 分野から3 分野を選択

ソフトウェア系
ハードウェア系
OS とネットワーク
ヒューマンサイエンス系

１. 問題冊子は、本表紙を含めて全部で１５ページあります。

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

３. 解答冊子は A4 片面印刷で印刷して全て提出してください。

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

数学・数理系

2021-07 情報科学 問題冊子

以下の全ての問題について、途中の計算や説明を明記し、答えよ。
（問１） （１）、（２）の各問に答えよ。
（１） ふたつの平面 𝑥 − 𝑦 + 𝑧 = 1, 2𝑥 + 𝑦 + 3𝑧 = 5 のなす角度𝜃としたとき、cos 𝜃を求めよ。
（２） 次の連立方程式を掃き出し法（ガウスの消去法）で解け。

3𝑥 + 2𝑦 + 𝑧 = 47𝑥
0 + 8𝑦 + 9𝑧 = 10
5𝑥 + 5𝑦 + 6𝑧 = 6（問２） （１）、（２）の各問に答えよ。
（１） ３つの多変数関数 𝑓(𝑥! , 𝑥" ) = 𝑥! + 𝑥" , 𝑔(𝑥! , 𝑥" ) = 3𝑥!" − 4𝑥"" , ℎ(𝑥! , 𝑥" ) = 𝑥!# − 3𝑥! 𝑥"" について、その勾配 grad 𝑓(𝑥! , 𝑥" ), grad 𝑔(𝑥! , 𝑥" ), grad ℎ(𝑥! , 𝑥" )を求めよ。
$%('! ,'" ) $%('! ,'" )（ヒント：勾配は、grad𝑓(𝑥!, 𝑥") = A（２） ３つの関数

"!*"'

$'!

,$'"

Bと定義される。
）, log+ (1 + 𝑥 " ), tan 𝑥 のマクローリン展開を、それぞれ𝑥 ,の項まで求めよ。

（問３） 実数 𝑥 に対して、

𝑓(𝑥) = lim A lim cos"0 (𝑚! 𝜋𝑥)B-→/ 0→/と置くとき、この関数𝑓 ∶ R → Rは次の関数となることを示せ。
1 (𝑥 ∈ Q)
𝑓(𝑥) = N0 (𝑥 ∉ Q)
ただし、𝑚, 𝑛は整数とし、𝐐は有理数全体の集合とする。
（ヒント：𝑥 が有理数の場合、 𝑥 の分母を 𝑁 として 𝑁𝑥 が整数となるような自然数𝑁 をとると𝑚 ≥ 𝑁 となること、その時に 𝑚! は 𝑁 の倍数になることをヒントに数列の極限を考えてみよ。
）

頁番号

2/15

ソフトウェア系

2021-07 情報科学 問題冊子

（問１）（１） 混合ガウス分布モデルのパラメータ（各分布の平均ベクトルと分散共分散行列）を最尤推定により推定する際に，目的関数を偏微分して混合ガウス分布のパラメータ（各分布の平均ベクトルと分散共分散行列）を導出しなさい．その際，途中の導出式も記載すること．なお，入力される音声の観測データを x（データ量を L，次元数を D），混合分布数を M，混合ガウス分布の重みをw，平均ベクトルを μ，分散共分散行列を Σ とする．また，ガウス分布の式は下記とする．

N ( x | µ , å) =

1
(2p )

D/2|å|

1/ 2

ì 1
ü
expí- ( x - µ )T å -1 ( x - µ )ýî 2
þ（問２） Left-to-right 型の隠れマルコフモデルを用いた音声認識システムでは，その尤度計算にForward アルゴリズムもしくは Viterbi アルゴリズムを用いることが多い．それぞれのアルゴリズムについて説明しなさい．
（問３） 生成モデルに基づく大語彙音声認識システムの原理についてベイズの定理を用いて説明しな

さい．なお，想定するシステムは，認識結果を単語単位で出力する音声認識システムであり，音響モデル，言語モデルが利用される．説明にあたっては，ベイズの定理中の各確率値がいずれのモデルから推定された確率値であるかを明らかにすること．
（問４） 以下の離散分布の left-to-right 型隠れマルコフモデルにて，文字列 abcba を出力する際の確率が最大となる状態系列とそのときの確率値を Viterbi アルゴリズムを用いて求めなさい．その際，確率値だけを記載するのではなく，その確率値を求めた計算式も記載すること．

出力確率：状態 1（a:0.6, b:0.3, c:0.1）、状態 2（a:0.3, b:0.5, c:0.2）、
状態 3（a:0.1, b:0.2, c:0.7）

頁番号

3/15

ソフトウェア系

2021-07 情報科学 問題冊子

（問５） 成績管理プログラムについて、以下の問いに答えよ。

成績管理を行うプログラムを以下のように設計した。
1.

成績管理の対象は名前と評点（以下、単に「データ」と呼ぶ）のみとし、それぞれ名前（names）、評点（scores） という配列変数を定義して用いる。登録人数を記憶しておく変数 count と併せて、複数人のデータを扱えるようにする。

2.

データの操作に関して、未登録者の名前と評点を登録する機能、登録者全員の平均点を計算する機能を持つ。

（１） 未登録者の名前と評点を登録する機能は、以下の 5 つのステップを正しい順番に並び替えることで実現できる。登録機能を実現する処理の順番に A～E を並び替えよ。ただし、登録人数を表す変数（count）の値は、0 に初期化しておくものとする。また、配列変数には添え字 0 から順番に値を格納することとする。
A： 評点（scores）を入力する
B： 登録人数（count）を増やす
C： 名前（names）を入力する
D： データ（names, scores）を登録する
E： 正常に登録されたことを登録人数とともに知らせる（２） 登録者全員の平均点を計算する機能を実現するため、配列変数 names, scores と count に加えて、合計点を表す変数 total を定義した。
① これらの変数を用いて平均点を計算する処理を、（１）のように適切なステップに分けて文章で説明せよ。
② ①で設計したプログラムにおいて想定される動的エラーの内容とその対処法を述べよ。

頁番号4/15

ソフトウェア系

2021-07 情報科学 問題冊子

（問６） スタックを用いた逆ポーランド電卓プログラムについて、以下の問いに答えよ。
（１） 数式は木構造で表現できる。数式 f: 6 ÷ ( 7 － 5 ) ＋ 4 × ( 3 ＋ 2 ) を、解答欄の例に倣い、木構造で表現せよ。
（２） 木のなぞりを利用して、（１）の数式 F を、逆ポーランド記法に書き変えよ。
（３） 整数型データを扱うスタックを操作する関数 push と pop を C 言語で実装した。プログラム

６-①の空欄（あ）～（え）に入る適切な文を答えよ。
【プログラム６-①】/* スタックの定義 */int stack[100];/* スタックの初期化 */int n = 0;/* スタックにデータを積む */void push(int x) {;（あ）;（い）}/* スタックからデータを降ろす */int pop() {;（う）（え）;}

A: n = n - 1
B: n = n + 1
C: n = n - x
D: n = n + x
E: return x
F: return stack[n]G: x = stack[n]H: stack[n] = x

C 言語で実装した逆ポーランド電卓の主要部分をプログラム６-②に示す。このプログラムは、逆ポーランド記法で表現された数式（ただし、演算数は一桁の整数に限定）を入力とし、その計算結果を出力するものである。ここで、getchar()は標準入力に入力した一文字のコードを int 型で返す関数、isdigit(int c)は引数 c が 0 ～ 9 の数字一文字を表す場合に真、それ以外の文字の場合に偽を返す関数である。
（４） （２）で求めた数式 f の逆ポーランド記法表現をプログラム６-②によって計算する過程におけるスタックの変化を図示せよ。

頁番号

5/15

ソフトウェア系

2021-07 情報科学 問題冊子

【プログラム６-②】/* 逆ポーランド電卓プログラム */void calc(){
int a, b, c;
n = 0;/* 入力された文字列を先頭から末尾まで一文字ずつ読み込む */while((c=getchar())!=EOF){
if(isdigit(c)){/* 文字コードを数値に変換 */push(c-‘0’);} else {switch(c){case ‘+’:b=pop(); a=pop();push(a+b);
break;
case ‘-’:b=pop(); a=pop();push(a-b);

case ‘*’:b=pop(); a=pop();push(a*b);
break;
case ‘/’:b=pop(); a=pop();push(a/b);
break;
case ‘¥n’:/* 数式の末尾の改行文字（¥n）に到達したら計算結果を表示 */printf(“%d¥n”, pop());
break;}}}}

break;

頁番号

6/15ソフトウェア系

2021-07 情報科学 問題冊子

（問７） ソートアルゴリズムについて以下の各設問に答えよ。

バブルソート、選択ソート、挿入ソートのプログラムを C 言語で実装した。プログラムの主要部分を以下に示す。変数 compare_count と exchange_count はそれぞれ整列中のデータの比較と交換の回数を数えるためのものである。
【プログラム７-①】/* 整列の過程を表示する関数 */void show_data(int a[], int n, int p, int c, int e){
int i;
for(i=0; i<n; i++){printf("%d ", a[i]);if(i==p)printf("| ");}printf("compare=%d, exchange=%d¥n", c, e);}/* バブルソート */void bubble_sort(int a[], int n){
int i, j, t;
int compare_count=0, exchange_count=0;
for(i=0; i<n-1; i++){for(j=n-1; j>i; j--){if(a[j-1]>a[j]){t=a[j]; a[j]=a[j-1]; a[j-1]=t;}}
show_data(a, n, i, compare_count, exchange_count);}}/* 選択ソート */void selection_sort(int a[], int n){
int i, j, t, lowest, lowkey;
int compare_count=0, exchange_count=0;
for(i=0; i<n-1; i++){lowest=i;lowkey=a[i];for(j=i+1; j<n; j++){if(a[j]<lowkey){lowest=j; lowkey=a[j];}}t=a[i]; a[i]=a[lowest]; a[lowest]=t;
show_data(a, n, i, compare_count, exchange_count);

頁番号

7/15

ソフトウェア系

2021-07 情報科学 問題冊子}}/* 挿入ソート */void insertion_sort(int a[], int n){
int i, j, t;
int compare_count=0, exchange_count=0;
for(i=1; i<n; i++){j=i;while(j>=1 && compare_count++>=0 && a[j-1]>a[j]){t=a[j]; a[j]=a[j-1]; a[j-1]=t;j--;}show_data(a, n, i, compare_count, exchange_count);}}（１） プログラム７-①では、変数 compare_count と exchange_count をインクリメントする文が一部抜け落ちている。3 つのソートアルゴリズムそれぞれについて、適切な位置にcompare_count++; と exchange_count++; の両方ないしどちらか一方を追記してプログラ

ムを完成させたうえで、100 1 2 3 4 ... 99 という 100 個のデータをこのプログラムによって整列するとき、3 つのアルゴリズムそれぞれについて、並び替えが完了した時点でのcompare_count と exchange_count の値を示せ。

（２） 3 つのアルゴリズムの計算量の違いを、ランダムに並んでいるデータと、大部分がソート済みであるデータについて、それぞれ考察せよ。

頁番号

8/15

ハードウェア系

2021-07 情報科学 問題冊子

（問１） コンピュータ内部では数値はすべて０と１の組み合わせとして処理される。いま、命令長 16ビットのコンピュータにおいて、小数部をもつ数値を整数部 10 ビット、小数部 6 ビットの固定小数点形式として表現することを考える。すなわち、2 進数(nnnn nnnn nn.dd dddd2）の形の固定小数点数表現となり、表現できない数値は切り捨てとする。また、負の数は 2 の補数表現を用いて表す。このとき、以下の問いに答えよ。
（１） 以下の固定小数点数表現の値を 10 進数で表せ。計算の過程も示すこと。

(ア) 0010 1011 00.00 11002(イ) 1111 0101 00.11 00112（２） 10 進数で表現された以下の値を固定小数点表現で表せ。計算の過程も示すこと。

(ア) 511.87510（３）(イ) 3.1410(ウ) －32.110

現代のコンピュータでは、通常負の数を 2 の補数表現として扱っている。負の数の表現として「符号絶対値表現」という表現形式も存在する。符号絶対値表現とは、数の絶対値の 2 進数の表現に対して、正の数であれば最上位の符号ビットを０とし、負の数であれば、符号ビットを１とするものである。符号絶対値表現は数値を符号付き１０進数で表示するときに変換が容易であるという利点があるにもかかわらず、現代のコンピュータでは符号絶対値表現がほとんど採用されていない理由について、演算を実現する演算器のハードウェアの規模、演算速度の点から考察せよ。

頁番号

9/15

ハードウェア系

2021-07 情報科学 問題冊子

（問２） 0101100110101…… のようにクロック（CLK）と同期して 1 ビットずつ入力されるビット列の中からビット列 0011 を検出する順序回路を、D フリップフロップを用いて設計する。入力を𝑥、出力を𝑧、状態を(𝑄! 𝑄1 )と表す。ビット列 0011 を検出する状態遷移図は図１とする。
以下の問に答えよ。

態𝑄! , 𝑄1 を決めるフリップフロップの入力
𝐷! , 𝐷1 のそれぞれの次状態関数

0/01/0（１） 出力 z を決める出力関数𝑔(𝑥, 𝑄! , 𝑄1 )と次状⇒ (00) 0/0(01)

1/0

𝑓! (𝑥, 𝑄! , 𝑄1 )，𝑓1 (𝑥, 𝑄! , 𝑄1)の最簡形の論理

0/0

(11)

0/0

1/0

(10)

1/1

図：ビット列 0011 を検出する状態遷移図

式を求めなさい。導出の過程も示すこと。

（２） （１）で求めた論理式に基づき、図 2 に示す順序回路を完成させよ。ただし、使用できる論理ゲートは 2 入力の AND ゲートと NOT ゲートだけとし使用するゲート数はできるだけ少なくすること。テクノロジマッピング（論理式中の演算を AND ゲート、NOT ゲートの組合せに変換する）がある場合にはその過程を示すこと。
※上下の D フリップフロップをどちらの状態ビットに用いても良いが回路図中に𝑄! , 𝑄1 信号を明記すること

CKCCK

L
K
図２ ビット列 0011 を検出する順序回路

頁番号

10/15

ハードウェア系

2021-07 情報科学 問題冊子

（問３） 計算機アーキテクチャに関する以下の問いに答えなさい。
（１） コンピュータの入出力装置をメモリバスに接続しメモリとしてアクセスできる「メモリマップ

ド IO 方式」と入出力専用の命令と IO 専用のバスを持ち入出力装置にアクセスできる「IO マッ
プド IO 方式」とを比較し、それぞれの方式の利点について考察しなさい。また、近年の高性能プロセッサは「IO マップド IO 方式」が多く採用されている理由について考察しなさい。

（２） プロセッサの内部もしくは外部からの通知を受け取り動作する仕組みとして、(A)ハードウェア割込み（外部割り込み）、(B)ソフトウェア割込み（ソフトウェア割込み命令による割込み）、(C)例外の 3 種類がある。それぞれの割込み要因の違い、割込みマスクの可否、主な用途について説明しなさい。

頁番号

11/15

OS とネットワーク

2021-07 情報科学 問題冊子

（問１） ユーザプログラムがオペレーティングシステムに仕事を依頼する際には、OS コール（システムコールと呼ぶこともある）を行う。この機能を実装するにあたって、内部割込み（トラップ； trap）を発生させる命令を利用することが広く行われている。その理由について、次の３点がわかるように論じよ。
(A) OS コール完了後にはユーザプログラムに戻って再開できること、OS コールとして複数の機能（例えば、ファイルのオープン、現在時刻の取得、アクセス権制御、など様々な機能）を用意できること、の他に、OS コールを実現するためのもうひとつ重要なポイントは何か。
(B) 割込み信号が CPU に届いたときの CPU の動作。
(C) (A)の３つのポイントそれぞれが、(B)のどの動作によってなぜ満たされるのか。

（問２） オペレーティングシステムは、種々の計算資源（CPU、メモリ、外部記憶、入出力機器など）を仮想化したインタフェースをユーザに提供することによって、ユーザの利便性向上を図っている。仮想化を行うにあたっては、(A) 計算資源を同一の大きさのブロックの集まりとみなすことによって管理し、大きさの異なるものであっても統一的、効率的に扱えるようにすること(B) 限りある計算資源が無限にある（あるいは、ハードウェア上の制限がほとんどない）ように見せ、さらにそれをユーザ一人で独占して使えるように見せること(C) 計算資源それぞれを利用する際に必要な、特有かつ煩雑な手続きをユーザから隠し、統一した仮想的インタフェースを通してアクセスできるようにすることが本質的に重要となる。
この観点から、メモリ、外部記憶、入出力機器のそれぞれが、どのような形で仮想化され、ユーザに利便性を提供しているのか論じよ。(C)については、どのような情報がユーザから隠されているかについて必ず議論すること。ただし、必ずしも、特定のオペレーティングシステムを例にして詳細な議論をする必要はない。解答欄に示した解答例程度の議論をすれば十分である。なお、入出力機器に対する(A)の議論をする必要はない。
解答欄のスペースが足りなければ枠を広げてもよいが、問２の解答全体で A4 紙２枚以内に収めること。

頁番号

12/15

OS とネットワーク

2021-07 情報科学 問題冊子

（問３） コンピュータネットワーク通信における「フロー制御」と「輻輳制御」について、以下について答えなさい。
（１） フロー制御と輻輳制御の概要、違いについて述べよ。
（２） ウインドウ制御とは何か、その利点と問題点について述べよ。
（３） TCP におけるフロー制御と輻輳制御について、受信側からのフィードバックをベースにする方法と送信側でレートを変化させていく方法の概要をそれぞれ述べよ。
（４） ネットワークレイヤ以下における「輻輳制御」についていくつか例を簡単に述べよ。
（５） ウインドウ制御におけるスロースタートアルゴリズム（Karn のアルゴリズム）の概要について述べよ。
（６） 送信する 1 フレーム（パケット）長を L[bit/frame]、通信速度を b[bit/sec]、往復の伝播遅延時間を R[sec]、ウインドウ幅を w[frame]、1 フレームを受信した後で ACK を送出するまでの受信処理時間を r[sec]とする。ACK のサイズは無視してよいとする。このとき、ウインドウサイズが 1 フレーム分の時の回線利用率を示しなさい。また、受信バッファのサイズが有限であるときの最大回線利用率とそのときのウインドウサイズはいくつになるか示せ。
解答欄のスペースが足りなければ枠を広げてもよいが、問３の解答全体で A4 紙３枚以内に収めること。

頁番号13/15

ヒューマンサイエンス系

2021-07 情報科学 問題冊子

（問１） 日本、アメリカ、イギリス、フランス、ドイツ、ロシア、トルコ、中国、インド、タイ、インドネシア、オーストラリア、ブラジル、チリ、エジプト、ガーナの各国から、それぞれ 100 万件の人の表情を集めたデータベースがある。データベース中の各レコードは、撮影された国、撮影日、被写体の性別、被写体の年代、表情データ（写真）で構成されている。表情データは、パスポートの写真と同じ規格1で撮影されており、既存のライブラリ等を用いればコンピュータで顔検出が可能な精細さで記録されている。また、表情データは、そのデータの被写体が暮らしている国と同じ国で小さな頃から暮らしてきた人であれば、明確にその被写体が表している感情を読み取ることができるものとなっている。このデータベースは研究目的に限って無料で使用することができる。
あなたは、このデータベースを用いて、喜んでいる、怒っている、悲しんでいる、楽しんでいるという 4 つの感情別に、各レコードを自動的に分類した結果を確認することになった。分類システムは、機械学習（教師あり学習）を用いて実装されていた。
以下の（１）〜（３）について、それぞれ 100 字以上 300 字以内を目安に記述しなさい（必要な場合には 300 字を超過してもかまわない）。以下の解答に直接関係する文献や web サイト等がある場合は、それらの出典情報を示すこと（出典情報は文字数に含めない）。
（１） 各レコードを教師あり学習で感情別に分類した結果には、どのような問題が生じている可能性があるかを説明せよ。
（２） （１）の問題が生じる原因を説明せよ。
（３） （２）であなたが示した説明に従ってシステムを改善するならば、システムをどのように設計すればよいかを説明せよ。教師あり学習を使用しない方法でもかまわない。なお、ここで言う「設計」とは、システム設計の上流工程における要件定義と基本設計に相当する粒度の内容を指す。

1 外務省 「パスポート申請用写真の規格（令和 3 年 5 月 18 日更新）」

https://www.mofa.go.jp/mofaj/toko/passport/ic_photo.html
頁番号

14/15

ヒューマンサイエンス系

2021-07 情報科学 問題冊子

（問２）（１） 情報科学分野で頻繁に用いられる次の 3 つの概念に対して、それぞれの定義を人の認知的な関与の観点に基づいて説明せよ。
① データ (data)② 情報(information)③ 知識（knowledge）（２） ある「情報」を人物 A から人物 B に口頭で伝えたとき、その情報は事実とは異なるもの（誤り）だと B が判断したとする。（１）での解答に基づいて A-B 間で伝えられた情報が誤りだと判断されてしまったときの A と B の情報処理的過程を 3 通り以上推定し、それぞれについて説明せよ。

頁番号15/15