九州大学大学院システム情報科学府

情 報 学 専 攻
情報知能工学専攻

令和２年度入学試験問題【令和元年８月２６日（月）、２７日（火）】情報学専攻九州大学大学院システム情報科学府 情報知能工学専攻
電気電子工学専攻修士課程 入学試験問題 （令和元年８月２６日）

令和２年度

数 学 (Mathematics)（7 枚中の 1）

解答上の注意 (Instructions):

1. 問題用紙は，『始め』の合図があるまで開いてはならない．
Do not open this cover sheet until the start of examination is announced.
2. 問題用紙は表紙を含め 7 枚，解答用紙は 3 枚つづり (1 分野につき 1 枚) である．
You are given 7 problem sheets including this cover sheet, and 3 answer sheets (1 sheet foreach ﬁeld).
3. 以下の 6 分野から 3 分野を選び解答すること．選んだ分野毎に解答用紙を別にすること．
Select 3 ﬁelds out of the following 6 ﬁelds and answer the questions. You must use a separate
answer sheet for each of the ﬁelds you selected.

1
2
3
4
5
6

分野
線形代数
微分方程式
ベクトル解析
複素関数論
確率・統計
記号論理学

ﬁeld
Linear algebra
Diﬀerential equation
Vector analysis
Complex function theory
Probability and statistics
Symbolic logic

page
2
3
4
5
6
7

4. 解答用紙の全部に，専攻名，コース名（情報学専攻を除く），選択分野番号（○で囲む），受験番号および氏名を記入すること．

Fill in the designated blanks at the top of each answer sheet with the department name,course name (except the department of informatics), the selected ﬁeld number (mark with acircle), your examinee number and your name.
5. 解答は解答用紙に記入すること．スペースが足りない場合は裏面を用いても良いが，その場合は，裏面に解答があることを明記すること．

Write your answers on the answer sheets. You may use the backs of the answer sheets when
you run out of space. If you do so, indicate it clearly on the sheet.
6. 解答は，日本語，英語のいずれかで記入すること．
Your answers must be written in Japanese or English.

情報学専攻九州大学大学院システム情報科学府 情報知能工学専攻
電気電子工学専攻修士課程 入学試験問題 （令和元年８月２６日）

令和２年度

数 学 (Mathematics)（7 枚中の 2）
6 分野のうちから 3 分野を選び解答すること．選んだ分野毎に解答用紙を別にすること．
Select 3 ﬁelds out of the 6 ﬁelds and answer the questions. Use a separate answer sheet
for each ﬁeld.

1. 【線形代数 (Linear algebra) 分野】
数列 a0 ，a1 ，a2 ，…は，a0 = 3，a1 = 1，a2 = 3 およびan = an−1 + an−2 + 2an−3（n = 3，4，5，…）で定義される．

(1) a3 ，a4 ，a5 を求めよ．
(2) 各 n = 0，1，2，…について次が成立つような行列 T を答えよ．




an+1
an




an+2  = T an+1 
an+3
an+2
(3) T のすべての固有値とそれぞれに対応する固有ベクトルを求めよ．
 
3
 
(4) ベクトル 1 を，前問で求めた固有ベクトルの線形結合として表せ．
3(5) an を求めよ．
Consider the sequence a0 , a1 , a2 , . . . deﬁned by a0 = 3, a1 = 1, a2 = 3 andan = an−1 + an−2 + 2an−3 ,n = 3, 4, 5, . . . .

(1) Find a3 , a4 and a5 .
(2) Give the matrix T such that





an
an+1




an+2  = T an+1 
an+2
an+3

for all n = 0, 1, 2, . . . .
(3) Find all eigenvalues of T and their corresponding eigenvectors.
 
3
 
(4) Express the vector 1 as a linear combination of the eigenvectors obtained in the3previous question.
(5) Find an .

情報学専攻九州大学大学院システム情報科学府 情報知能工学専攻
電気電子工学専攻修士課程 入学試験問題 （令和元年８月２６日）

令和２年度

数 学 (Mathematics)（7 枚中の 3）
6 分野のうちから 3 分野を選び解答すること．選んだ分野毎に解答用紙を別にすること．
Select 3 ﬁelds out of the 6 ﬁelds and answer the questions. Use a separate answer sheet
for each ﬁeld.

2. 【微分方程式 (Diﬀerential equation) 分野】

関数 y(x) の微分方程式(x4 − 1)dy
= y 2 + 2x3 y − 3x2dxについて以下の問いに答えよ．

(1) 与えられた微分方程式は，yp (x) = ax3 の形の特殊解を持つ．yp (x) を求めよ．ただし aは定数とする．

(2) 特殊解 yp (x) と関数 u(x) を用いて y = yp +1とおき，一般解を求めよ．
uConsider the diﬀerential equation(x4 − 1)dy
= y 2 + 2x3 y − 3x2dx

for a function y(x). Answer the following questions.
(1) Find one of the particular solutions yp (x) of the form yp = ax3 , where a is a constant.
1(2) Obtain the general solution with the replacement y = yp + , where u is a function of x.
u情報学専攻九州大学大学院システム情報科学府 情報知能工学専攻
電気電子工学専攻修士課程 入学試験問題 （令和元年８月２６日）

令和２年度

数 学 (Mathematics)（7 枚中の 4）
6 分野のうちから 3 分野を選び解答すること．選んだ分野毎に解答用紙を別にすること．
Select 3 ﬁelds out of the 6 ﬁelds and answer the questions. Use a separate answer sheet
for each ﬁeld.

3. 【ベクトル解析 (Vector analysis) 分野】

直交座標系において，x，y ，z 軸方向の単位ベクトルをそれぞれ i，j ，k とする．次の各問
に答えよ．

(
)2 (
)2
1
1
(1) 面 z = x + y と面 z = x − √+ y−√について，次の問いに答えよ．
2
2
(√ √
)
2 2 1
(a) 点 P,,が，いずれの面にも含まれることを示せ．
4 4 4
2

2

(b) 点 P において，それぞれの面の法線のなす角を求めよ．
(2) ベクトル場 A を A = x2 i − y 2 j + z 2 k とする．S を x2 + y 2 = 9，z = 0，z = 4 で囲まれた円筒の表面とするとき，面積分∫∫
A · n dS
S

を求めよ (ただし，n は S の外向き単位法線ベクトル).

The unit vectors on x, y and z axes of Cartesian coordinates are denoted by i, j and k,
respectively. Answer the following questions.
(
)2 (
)2
1
1
(1) Consider the surfaces z = x + y and z = x − √+ y−√. Answer the22
following questions.
(√ √
)
2 2 1
(a) Show the point P,,
is included in both surfaces.
4 4 4
2

2

(b) Evaluate the angle between the normals to the surfaces at the point P.
(2) Let the vector ﬁeld A = x2 i − y 2 j + z 2 k and S be the surface of the cylinder boundedby x2 + y 2 = 9, z = 0 and z = 4 . Evaluate the following surface integral∫∫
A · n dS ,S

where n is the outward-pointing unit normal vector of S.

情報学専攻九州大学大学院システム情報科学府 情報知能工学専攻
電気電子工学専攻修士課程 入学試験問題 （令和元年８月２６日）

令和２年度

数 学 (Mathematics)（7 枚中の 5）
6 分野のうちから 3 分野を選び解答すること．選んだ分野毎に解答用紙を別にすること．
Select 3 ﬁelds out of the 6 ﬁelds and answer the questions. Use a separate answer sheet
for each ﬁeld.

4. 【複素関数論 (Complex function theory) 分野】
図に示す z 平面における x = 1, y = 1, y = 1 − x で囲まれた三角領域 S を考える．以下の変換で S が写像される w 平面の領域 S ′ を図示すると共に、S ′ を囲む境界の方程式を示せ．た√だし，z = x + iy ，w = u + iv は複素数，x, y, u, v は実数，i = −1 である．

√
3i)
√
πi
(2) w = 2e 6 z + (1 − 3i)(1) w = z + (1 −(3) w = z 2

y
1

S

0

1

x

Consider the triangle region S bounded by x = 1, y = 1 and y = 1 − x in the z plane asshown in the ﬁgure. Illustrate the region S ′ in the w plane into which S is mapped under
the following transformations and ﬁnd the equations of the curves which enclose the region,
where z = x + iy and w = u + iv are complex numbers, x, y, u, and v are real numbers and√i = −1.
√3i)√
πi(2) w = 2e 6 z + (1 − 3i)(1) w = z + (1 −(3) w = z 2

情報学専攻九州大学大学院システム情報科学府 情報知能工学専攻
電気電子工学専攻修士課程 入学試験問題 （令和元年８月２６日）

令和２年度

数 学 (Mathematics)（7 枚中の 6）
6 分野のうちから 3 分野を選び解答すること．選んだ分野毎に解答用紙を別にすること．
Select 3 ﬁelds out of the 6 ﬁelds and answer the questions. Use a separate answer sheet
for each ﬁeld.

5. 【確率・統計 (Probability and statistics) 分野】
2

連続確率変数 X は区間 [0, 1) 上の一様分布に従うものとする．Y = − log (1−X)とする．ただ4
し log は自然対数とする．以下の各問に答えよ．

(1) 実数 t に対し，Y ≤ t の確率を求めよ．
(2) Y の期待値と分散をそれぞれ求めよ．

Let X be a continuous random variable uniformly distributed over the interval [0, 1). Let
2

Y = − log (1−X)
where log denotes the natural logarithm. Answer the following questions.
4(1) Find the probability of Y ≤ t for a real t.
(2) Find the expectation and the variance of Y , respectively.

情報学専攻九州大学大学院システム情報科学府 情報知能工学専攻
電気電子工学専攻修士課程 入学試験問題 （令和元年８月２６日）

令和２年度

数 学 (Mathematics)（7 枚中の 7）
6 分野のうちから 3 分野を選び解答すること．選んだ分野毎に解答用紙を別にすること．
Select 3 ﬁelds out of the 6 ﬁelds and answer the questions. Use a separate answer sheet
for each ﬁeld.

6. 【記号論理学 (Symbolic logic) 分野】(1) 以下の命題論理式をそれぞれ ϕ1 , ϕ2 , ϕ3 で表す．
(p → q) ∧ (p ∧ q → r),¬(¬(r → s) ∨ (¬p ∧ r ∧ s)),p↔r

ϕ3 は ϕ1 ∧ ϕ2 の論理的帰結であることを resolution 法により示せ．
(2) 以下の述語論理式をそれぞれ ψ1 , ψ2 , ψ3 で表す．
∀x∀y ((¬P (x, y) → P (y, x)) ∧ (Q(x, y) → ¬Q(y, x))),∀x∀y (P (x, y) → Q(x, y)),∀x (∃y Q(x, y) ∧ ∀y (Q(x, y) → ¬P (y, x)))以下の式は充足可能か否か，理由とともに答えよ．

(a) ψ1 ∧ ψ2(b) ψ1 ∧ ψ3(1) Let ϕ1 , ϕ2 , and ϕ3 denote the following propositional formulas, respectively:(p → q) ∧ (p ∧ q → r),¬(¬(r → s) ∨ (¬p ∧ r ∧ s)),p ↔ r.

Show by the resolution method that ϕ3 is a logical consequence of ϕ1 ∧ ϕ2 .
(2) Let ψ1 , ψ2 , and ψ3 denote the following predicate logic formulas, respectively:∀x∀y ((¬P (x, y) → P (y, x)) ∧ (Q(x, y) → ¬Q(y, x))),∀x∀y (P (x, y) → Q(x, y)),∀x (∃y Q(x, y) ∧ ∀y (Q(x, y) → ¬P (y, x))).

Determine whether each of the following formulas is satisﬁable. Justify your answer.
(a) ψ1 ∧ ψ2(b) ψ1 ∧ ψ3

令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(1/29)

解答上の注意 (Instructions):

1. 問題用紙は，『始め』の合図があるまで開いてはならない．
Do not open this cover sheet until the start of examination is announced.
2. 問題用紙は表紙を含め 29 枚，解答用紙は 3 枚つづり 2 部 (1 分野につき 1 部) である．
You are given 29 problem sheets including this cover sheet, and 2 sets of 3 answer sheets(1 set for each ﬁeld).
3. 以下の 6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙を別にすること．また，大問一つあたり一枚の解答用紙を用いよ．

Select 2 ﬁelds out of the following 6 ﬁelds and answer the questions. You must use a separate
set of answer sheets for each of the ﬁelds you selected, and use a separate answer sheet foreach question.

A
B
C
D
E
F

分野
電気回路
情報理論
オートマトンと言語
電磁気学
アルゴリズム／プログラミング
計算機アーキテクチャ

ﬁeld
Circuit theory
Information theory
Automata and formal languages
Electromagnetism
Algorithms and programming
Computer architecture

page
2
6
10
14
20
26

4. 解答用紙の全部に，専攻名，コース名 (情報知能工学専攻のみ)，選択分野名，受験番号，氏名および問題番号を記入すること．

Fill in the designated blanks at the top of each answer sheet with the department name, thecourse name (only for the department of advanced information technology), the selected ﬁeld,
your examinee number, your name, and the question number.
5. 解答は解答用紙に記入すること．スペースが足りない場合は裏面を用いても良いが，その場合は，裏面に解答があることを明記すること．

Write your answers on the answer sheets. You may use the backs of the answer sheets when
you run out of space. If you do so, indicate so clearly on the sheet.
6. 解答は，日本語，英語のいずれかで記入すること．
Your answers must be written in Japanese or English.

令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(7/29)
6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙 1 部を用いよ．また，
大問一つあたり一枚の解答用紙を用いよ．
Select 2 ﬁelds out of the 6 ﬁelds and answer the questions. Use a set of answer sheetsfor each of the ﬁelds you selected and use a separate answer sheet for each question.

【問 2】 X, Y を {0, 1} に値をとる確率変数とする．パラメータ α, β, γ ∈ [0, 1] に対し，

P (X = 0) = α,P (X = 1) = 1 − α,

P (Y = 0|X = 0) = β,P (Y = 1|X = 0) = 1 − β,

P (Y = 0|X = 1) = γ,

P (Y = 1|X = 1) = 1 − γ,とする．2 値エントロピー関数を−p log p − (1 − p) log(1 − p),h(p) =
0,

for 0 < p < 1,for p = 0, 1とする．以下の問いに答えよ.

(1) 条件付きエントロピー H(Y |X) を 2 値エントロピー関数を用いて表現せよ．
(2) β = 1 − γ とする．このとき，相互情報量 I(X; Y ) を最大化する α を求めよ．またI(X; Y ) の最大値を 2 値エントロピー関数と α, β を用いて表現せよ．
(3) α, β をある値に固定する．ただし，0 < α < 1 とする．相互情報量 I(X; Y ) を最小化する γ の値を α, β を用いて表せ．また，その最小値を示せ．

(4) α, β をある値に固定する．ただし，0 < α < 1, β > 12 とする．相互情報量 I(X; Y )を最大化する γ の値を求めよ．

令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(9/29)
6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙 1 部を用いよ．また，
大問一つあたり一枚の解答用紙を用いよ．
Select 2 ﬁelds out of the 6 ﬁelds and answer the questions. Use a set of answer sheetsfor each of the ﬁelds you selected and use a separate answer sheet for each question.

【Q2】 Let X and Y be random variables taking values in {0, 1}. For parameters α, β, γ ∈ [0, 1],

put
P (X = 0) = α,P (X = 1) = 1 − α,

P (Y = 0|X = 0) = β,P (Y = 1|X = 0) = 1 − β,

P (Y = 0|X = 1) = γ,

P (Y = 1|X = 1) = 1 − γ.

Let the deﬁnition of the binary entropy function as−p log p − (1 − p) log(1 − p),h(p) =
0,

for 0 < p < 1,for p = 0, 1.

Answer the following questions.
(1) Express the conditional entropy H(Y |X) using the binary entropy function.
(2) Set β = 1 − γ. Find the value of α that maximizes the mutual information I(X; Y ).
Furthermore, express the maximum value of the I(X; Y ) using the binary entropy
function.
(3) Fix α and β to some values. Assume 0 < α < 1. Express γ that minimizes themutual information I(X; Y ) using α and β. Find the minimum value of the I(X; Y ).
(4) Fix α and β to some values and assume 0 < α < 1 and β > 12 . Find the value of γthat maximizes the mutual information I(X; Y ).

令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(10/29)6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙 1 部を用いよ．また，
大問一つあたり一枚の解答用紙を用いよ．
Select 2 ﬁelds out of the 6 ﬁelds and answer the questions. Use a set of answer sheetsfor each of the ﬁelds you selected and use a separate answer sheet for each question.

C. 【オートマトンと言語 (Automata and formal languages) 分野】
次の各問い（【問１】【問２】）に答えよ．
【問１】決定性有限オートマトン M1 = (P, Σ, δ1 , p1 , F1 ) を考える．ただし，P ，Σ，δ1 ，p1 ，F1はそれぞれ M1 の状態集合，アルファベット，遷移関数，初期状態，最終状態の集合を表す．P = {p0 , p1 , p2 , p3 }，Σ = {0, 1, 2, 3}，F1 = {p0 } であり，i = 1, 2, 3, 4 に対し

δ1 (pi , a) = p(i+n(a)) mod 4 である．ここで n(a) は記号 a ∈ Σ に対応する整数であり，n(0) =0，n(1) = 1，n(2) = 2，n(3) = 3 である．非負の整数 x と正の整数 y に対し，x mod y
は x を y で割ったときの余りを表す．たとえば δ1 (p1 , 3) = p0 となる．次の各問いに答
えよ．

(1) M1 の状態遷移図を与えよ．
(2) 決定性有限オートマトン M2 = (P, Σ, δ1 , p1 , F2 ) は，M1 と同じ状態集合，アルファベッ
ト，遷移関数，初期状態を持つ．M2 と等価な決定性有限オートマトンの最小状態数が 2であるとき，最終状態の集合 F2 ⊆ P の例をひとつ与えよ．

(3) Σ 上の文字列 u に対して，Y (u) =

1

u が空文字列のとき

Y (v) × n(a) u = va，v ∈ Σ∗ ，a ∈ Σ のときとする．Y (u) mod 6 = 0 かつ Y (u) = 0 となる u のみを受理する決定性有限オートマト
ン M3 を考える．ただし，M3 の状態集合を {q0 , q1 , q2 , q3 , q6 }，初期状態を q1 ，最終状態の集合を {q6 } とする．また，各状態は次のような文字列に対応する．

– q0 は Y (u) = 0 を満たす文字列 u に対応．
– q1 は Y (u) mod 2 = 0 かつ Y (u) mod 3 = 0 を満たす文字列 u に対応．
– q2 は Y (u) mod 2 = 0 かつ Y (u) mod 6 = 0 を満たす文字列 u に対応．
– q3 は Y (u) mod 3 = 0 かつ Y (u) mod 6 = 0 を満たす文字列 u に対応．
– q6 は Y (u) mod 6 = 0 かつ Y (u) = 0 を満たす文字列 u に対応．
M3 の状態遷移図を与えよ．

令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(11/29)6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙 1 部を用いよ．また，
大問一つあたり一枚の解答用紙を用いよ．
Select 2 ﬁelds out of the 6 ﬁelds and answer the questions. Use a set of answer sheetsfor each of the ﬁelds you selected and use a separate answer sheet for each question.

【問２】アルファベット Σ = {a, b} 上の文字列 w に対し，w の長さを |w| と表す．また，1 ≤ i ≤ |w|に対して w[i] は w の i 番目の文字を表す．w の逆文字列を wR と表す．|x| = |y| ≥ 1 を
満たす Σ 上の文字列 x と y に対して，d(x, y) = {i | 1 ≤ i ≤ |x|, x[i] = y[i]} とする．文字列 w に対し，w = xyz を満たす文字列 x, z ∈ Σ∗ が存在するとき，y を w の部分文字列という．# は Σ に含まれない文字とする．次の各言語を考える．
 

L 0 = w  w ∈ Σ∗ , w = w R
L1 = wxwR  w ∈ Σ∗ , x ∈ Σ}

L2 = uxvw  u, v, w ∈ Σ∗ , uv = wR , x ∈ Σ 
L3 = uv  u, v ∈ Σ∗ , |u| = |v| ≥ 1, d(uR , v) ≤ 1
L4 = x#w  x, w ∈ Σ∗ , xR は w の部分文字列
これらの言語はすべて文脈自由言語である．例えば，言語 L0 は以下の生成規則を持つ
文脈自由文法によって生成される．

S → aSa | bSb | a | b | ε
ただし，ε は空文字列を表す．
次の問いに答えよ．

(1) 言語 L1 を生成する文脈自由文法の生成規則を与えよ．ただし，非終端記号を S とし，開始記号を S とする．

(2) 言語 L2 を生成する文脈自由文法の生成規則を与えよ．ただし，非終端記号を S, Tとし，開始記号を S とする．

(3) 言語 L3 を生成する文脈自由文法の生成規則を与えよ．ただし，非終端記号を S, Tとし，開始記号を S とする．

(4) 言語 L4 を生成する文脈自由文法の生成規則を与えよ．ただし，非終端記号を S, T, Xとし，開始記号を S とする．

令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(12/29)6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙 1 部を用いよ．また，
大問一つあたり一枚の解答用紙を用いよ．
Select 2 ﬁelds out of the 6 ﬁelds and answer the questions. Use a set of answer sheetsfor each of the ﬁelds you selected and use a separate answer sheet for each question.

Answer the following questions (【Q1】【Q2】).
【Q1】 Consider a deterministic ﬁnite automaton M1 = (P, Σ, δ1 , p1 , F1 ), where P, Σ, δ1 , p1 ,and F1 respectively represent the set of states, the alphabet, the transition function,
the initial state, and the set of ﬁnal states of M1 . Here, P = {p0 , p1 , p2 , p3 }, Σ ={0, 1, 2, 3}, F1 = {p0 } and δ1 (pi , a) = p(i+n(a)) mod 4 for i = 1, 2, 3, 4, where n(a) represents
the integer that corresponds to symbol a ∈ Σ, that is, n(0) = 0, n(1) = 1, n(2) = 2,n(3) = 3. For a non-negative integer x and a positive integer y, x mod y represents
the remainder when we divide x by y. Thus, for instance, δ1 (p1 , 3) = p0 . Answer thefollowing questions.
(1) Give a transition diagram of M1 .
(2) A deterministic ﬁnite automaton M2 = (P, Σ, δ1 , p1 , F2 ) has the same set of states,alphabet, transition function, and initial state as M1 . Give an example of F2 ⊆ P
when the minimum number of the states of a deterministic ﬁnite automaton which isequivalent to M2 is 2.
(3) For a string u over Σ, let
Y (u) =

1

if u is the empty string,Y (v) × n(a) if u = va, v ∈ Σ∗ , a ∈ Σ.

Consider a deterministic ﬁnite automaton M3 which accepts only strings u such that
Y (u) mod 6 = 0 and Y (u) = 0. Here, let {q0 , q1 , q2 , q3 , q6 }, q1 , and {q6 } be the setof states, the initial state, and the set of ﬁnal states of M3 , respectively. Each statecorresponds to the following strings:– q0 corresponds to strings u such that Y (u) = 0,
– q1 corresponds to strings u such that Y (u) mod 2 = 0 and Y (u) mod 3 = 0,– q2 corresponds to strings u such that Y (u) mod 2 = 0 and Y (u) mod 6 = 0,– q3 corresponds to strings u such that Y (u) mod 3 = 0 and Y (u) mod 6 = 0,– q6 corresponds to strings u such that Y (u) mod 6 = 0 and Y (u) = 0.
Give a transition diagram of M3 .

令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(13/29)6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙 1 部を用いよ．また，
大問一つあたり一枚の解答用紙を用いよ．
Select 2 ﬁelds out of the 6 ﬁelds and answer the questions. Use a set of answer sheetsfor each of the ﬁelds you selected and use a separate answer sheet for each question.

【Q2】 For a string w over the alphabet Σ = {a, b}, |w| denotes the length of w. For 1 ≤ i ≤ |w|,w[i] denotes the ith symbol in w, and wR denotes the reversed string of w. For any strings
x and y over Σ such that |x| = |y| ≥ 1, let d(x, y) = {i | 1 ≤ i ≤ |x|, x[i] = y[i]}. Let #be a symbol not in Σ. For a string w, if there are strings x, z ∈ Σ∗ such that w = xyz,
then y is said to be a substring of w. Consider the following languages: 
L 0 = w  w ∈ Σ∗ , w = w R ,
L1 = wxwR  w ∈ Σ∗ , x ∈ Σ ,L2 = uxvw  u, v, w ∈ Σ∗ , uv = wR , x ∈ Σ , 
L3 = uv  u, v ∈ Σ∗ , |u| = |v| ≥ 1, d(uR , v) ≤ 1 ,
L4 = x#w  x, w ∈ Σ∗ , xR is a substring of w .
All these languages are context-free languages. For example, the language L0 is generated
by the context-free grammar with the following production rules:
S → aSa | bSb | a | b | ε,where ε denotes the empty string.
Answer the following questions.
(1) Give production rules of a context-free grammar which generates the language L1 ,with non-terminal symbol S and initial symbol S.
(2) Give production rules of a context-free grammar which generates the language L2 ,with non-terminal symbols S, T and initial symbol S.
(3) Give production rules of a context-free grammar which generates the language L3 ,with non-terminal symbols S, T and initial symbol S.
(4) Give production rules of a context-free grammar which generates the language L4 ,with non-terminal symbols S, T, X and initial symbol S.

令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(14/29)6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙 1 部を用いよ．また，
大問一つあたり一枚の解答用紙を用いよ．
Select 2 ﬁelds out of the 6 ﬁelds and answer the questions. Use a set of answer sheetsfor each of the ﬁelds you selected and use a separate answer sheet for each question.

D. 【電磁気学 (Electromagnetism) 分野】【問 1】〜【問 3】から2 問を選び，解答用紙の問題番号欄に解答した問題番号を記入せよ．

࠙ၥ㸯ࠚ ᅗ  ࡟♧ࡍࡼ࠺࡟㸪ㄏ㟁⋡ ε ࡢ┿✵୰࡟ 3 ಶࡢ༙ᚄ ࡢᑟయ⌫ $㸪%㸪& ࡀ 1 ㎶
ࡢ㛗ࡉ / << ࡢṇ୕ゅᙧࡢ㡬Ⅼ࡟㓄⨨ࡉࢀ࡚࠸ࡿ㸬ᑟయ⌫ $ ࡢ㟁Ⲵࡣ 㸪㟁఩ࡣ , ᑟయ⌫ % ࡢ㟁Ⲵࡣ 㸪㟁఩ࡣ 0, ᑟయ⌫ & ࡢ㟁Ⲵࡣ 㸪㟁఩ࡣ 0 ࡛࠶ࡿ㸬(1) 㟁఩ಀᩘࢆ⏝࠸࡚ྛ⌫ࡢ㟁఩ࢆ⾲ࡏ(2) ྛ㟁఩ಀᩘࢆ   ࢆ⏝࠸࡚⾲ࡏ㸬(3) ḟ࡟㸪3 ಶࡢᑟయ⌫ࡢ㟁఩ࡀ඲࡚ ࡟࡞ࡿࡼ࠺࡟ྛᑟయ⌫ࡢ㟁Ⲵࢆኚ໬ࡉࡏࡓ㸬ࡇࡢሙྜࡢྛ⌫ࡢ㟁Ⲵࢆ    ࢆ⏝࠸࡚⾲ࡏ㸬(4) ḟ࡟㸪3 ಶࡢᑟయ⌫ࡢ㟁Ⲵࢆ඲࡚ ࡟ኚ໬ࡉࡏࡓ㸬ࡇࡢሙྜࡢྛ⌫ࡢ㟁఩ࢆ   ࢆ⏝࠸࡚⾲ࡏ
0

a

a

Q1

L

Q2

Q1

V0

Q3

Q2

V0

V

Q1

Q2 V0 V

Q1

Q1

Q1, V0

ᑟయ⌫ A

ᑟయ⌫ B

ᑟయ⌫ C
Q2,

0

Q3,

ᅗ㸯

0

Q2

V0

令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(15/29)6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙 1 部を用いよ．また，
大問一つあたり一枚の解答用紙を用いよ．
Select 2 ﬁelds out of the 6 ﬁelds and answer the questions. Use a set of answer sheetsfor each of the ﬁelds you selected and use a separate answer sheet for each question.

࠙ၥ㸰ࠚ ௨ୗࡢၥ࠸࡟⟅࠼ࡼ㸬ࡓࡔࡋ㸪π = 3.14,┿✵ࡢㄏ㟁⋡ε = 8.85x10 F/m㸪⣲㟁Ⲵ e = 1.60x10 C ࡜ࡍࡿ㸬(1) ┿✵୰࡟⨨࠿ࢀࡓ༙ᚄaࡢᑟయ⌫ࡀ㟁ⲴQ࡛ᖏ㟁ࡋ࡚࠸ࡿ㸬ࡇࡢᑟయࡢ㟁఩࡜㟼㟁ᐜ㔞ࢆồࡵࡼ㸬
(2) ┿✵୰࡟⨨࠿ࢀࡓ༙ᚄ 2.00 nm ࡢᑟయ⌫ࡢ㟼㟁ᐜ㔞ࢆồࡵࡼ㸬ࡇࡢᑟయ⌫࡟㟁Ꮚ 1 ಶࡢ㟁Ⲵe ࢆ୚࠼ࡓሙྜࡢ㟁఩ࡢኚ໬࡜⵳✚ࡉࢀࡿ㟼㟁࢚ࢿࣝࢠ࣮ࢆồࡵࡼ㸬(3) ┿✵୰࡟⨨࠿ࢀࡓ༙ᚄ 2.00 m ࡢᑟయ⌫ࡢ㟼㟁ᐜ㔞ࢆồࡵࡼ㸬ࡇࡢᑟయ⌫࡟㟁Ꮚ 1 ಶࡢ㟁Ⲵe ࢆ୚࠼ࡓሙྜࡢ㟁఩ࡢኚ໬࡜⵳✚ࡉࢀࡿ㟼㟁࢚ࢿࣝࢠ࣮ࢆồࡵࡼ㸬(4) ༙ᚄ 2.00 nm ࡢᑟయ⌫࡜༙ᚄ 2.00 m ࡢᑟయ⌫ࡢ࡝ࡕࡽࡀ㟁఩ࡢᇶ‽࡟㐺ࡋ࡚࠸ࡿ࠿㸬ࡲࡓ㸪ࡑࡢ⌮⏤ࢆ㏙࡭ࡼ
-12

0

-19

令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(17/29)6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙 1 部を用いよ．また，
大問一つあたり一枚の解答用紙を用いよ．
Select 2 ﬁelds out of the 6 ﬁelds and answer the questions. Use a set of answer sheetsfor each of the ﬁelds you selected and use a separate answer sheet for each question.

Select two out of the three questions 【Q1】〜【Q3】and write the number of theselected question on the answer sheet.

࠙Q1ࠚ As shown in Fig. 1, three spherical conductors A, B and C of radius are placed at vertices ofan equilateral triangle of a side length  << in vacuum with permittivity ε . The electricalcharges of the spherical conductors A, B and C are   and , respectively. The electrostatic
a

L

a

0

L

Q1

Q2

Q3

potentials of the spherical conductors A, B and C are 0, 0 and 0, respectively.
(1) Give the electrostatic potential of each sphere using coefficients of potential.
(2) Give each coefficient of potential using 1 2 0.
(3) Next, the charge of each conductor is changed so that all the potential of three sphericalconductors become . Give the charge of each conductor using 1 2 0 .
(4) Next, all the charges of three spherical conductors are changed to be 1. Give the potential ofeach conductor using 1 2 0.
V

Q

Q

V

V

Q

Q

V

Q

Q

Q

V

Q1, V0Sphere A

Sphere B

Sphere C
Q2,

0

Q3,

Fig. 10V令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(18/29)6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙 1 部を用いよ．また，
大問一つあたり一枚の解答用紙を用いよ．
Select 2 ﬁelds out of the 6 ﬁelds and answer the questions. Use a set of answer sheetsfor each of the ﬁelds you selected and use a separate answer sheet for each question.

࠙Q2ࠚAnswer the following questions, where π= 3.14 permitvity of vacuumε = 8.85x10 F/m㸪elementary chargee = 1.60x10 C.
-12

0

-19

(1) A spherical conductor of radius a placed in vacuum is charged with a charge Q. Give electrostatic
potential and capacitance of this conductor.
(2) Give capacitance of a spherical conductor of radius 2.00 nm. Give the change of potential and thestored electrostatic energy when the charge of an electron -e is given to the conductor.
(3) Give capacitance of a spherical conductor of radius 2.00 m. Give the change of potential and thestored electrostatic energy when the charge of an electron -e is given to the conductor.
(4) Which is more appropriate for the potential reference, either a spherical conductor of radius 2.00
nm or 2.00 m? And give the reason.

令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(20/29)6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙 1 部を用いよ．また，
大問一つあたり一枚の解答用紙を用いよ．
Select 2 ﬁelds out of the 6 ﬁelds and answer the questions. Use a set of answer sheetsfor each of the ﬁelds you selected and use a separate answer sheet for each question.

E. 【アルゴリズム／プログラミング (Algorithms and programming) 分野】
次の各問い（【問 1】【問 2】）に答えよ．
【問 1】以下に示すアルゴリズムに関する各問いに答えよ．
アルゴリズム ALG(G = (V, E), s)

1: A = {s}.
2: B = {s}.
3: While A = ∅4:

Choose an element v ∈ A. A = A \ {v}.

5:For each w such that (v, w) ∈ E
If w ∈ B then

6:

Append w to A and B.

7:
8: Output B.

(1) 頂点集合 V ，辺集合 E の無向グラフ G = (V, E) と頂点 s ∈ V を入力として実行した時，このアルゴリズムが出力する B の内容を述べよ．

(2) A のデータ構造としてスタックを用いた場合，以下の無向グラフ G = (V, E) と s ∈ Vを入力としてこのアルゴリズムが出力する集合 B の要素を B に追加された順に答えよ．

V= {s, t, u, v}

E = {(s, t), (s, u), (t, u), (t, v), (u, v)}(3) このアルゴリズムを用いて，与えられたグラフ G = (V, E) の頂点をある頂点 s ∈ V
から距離の近い順に調べたい．A に用いるデータ構造を答え，その理由を述べよ．

(4) グラフ G と集合 A，B のデータ構造に注意しながら，このアルゴリズムの実行時間を答えよ．

令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(21/29)6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙 1 部を用いよ．また，
大問一つあたり一枚の解答用紙を用いよ．
Select 2 ﬁelds out of the 6 ﬁelds and answer the questions. Use a set of answer sheetsfor each of the ﬁelds you selected and use a separate answer sheet for each question.

【問 2】次の各問いに答えよ．

(1) 以下の関係 Item(id, name, price), User(uid, name, mail), Transaction(item,
uid, star), Follow(fid, uid1, uid2, time) に対し，次の各問いに答えよ．
Item
id | name | price------------------001 | abc |150
002 | def |120
003 | ghi |230
004 | jkl |180005 | mno |350
006 | pqr |140
007 | stu |
150

User
uid | name | mail--------------------u01 | A| s@a.com
u02 | B| t@b.com
u03 | C| u@c.com
u04 | D| v@d.com
u05 | E| w@e.com
u06 | F| x@f.com
u07 | G| y@g.com

Transaction
item| uid | star---------------001 | u01 | 3
001 | u03 | 4
001 | u06 | 5
002 | u03 | 4002 | u05 | 5002 | u06 | 5
003 | u02 | 2

Followfid| uid1| uid2| time---------------------------f0001 | u01 | u03 | 20190801
f0002 | u05 | u06 | 20190810
f0003 | u04 | u03 | 20190810
f0004 | u01 | u02 | 20190811
f0005 | u02 | u01 | 20190813
f0006 | u06 | u05 | 20190817
f0007 | u04 | u02 | 20190820(a) 関係 Follow は uid1 のユーザが uid2 のユーザを時刻 time にフォローしたという事実を集めた集合である．この関係の候補キーを全て答えよ．ただし，ある
ユーザがあるユーザをフォローできるのは高々一度だけであると仮定する．

(b) 関係 Transaction は uid のユーザが id の商品を購入し，1〜5 の値 star で商品を評価したという事実を集めた集合である．id が 002 である商品を買ったユー
ザの uid の集合を求める関係代数の演算を答えよ．

(c) 関係 User はユーザ ID が uid を持つユーザ name のメールアドレスが mail であることを表す集合である．id が 002 である商品を買ったユーザのメールアドレ
スの集合を求める関係代数の演算を答えよ．

(d) id が 002 である商品を買ったユーザをフォローしているユーザの集合を求める
関係代数の演算を答えよ．

(e) 関係 Item は商品の識別子 id，その名前 name，その価格 price を集めた集合であり，この関係から以下のような結果を得る属性 price と不等号を用いた関係

令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(22/29)6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙 1 部を用いよ．また，
大問一つあたり一枚の解答用紙を用いよ．
Select 2 ﬁelds out of the 6 ﬁelds and answer the questions. Use a set of answer sheetsfor each of the ﬁelds you selected and use a separate answer sheet for each question.

代数の演算を答えよ．
id | price-----------003 |
230
005 |
350

(f) 関係 R と Follow の自然結合 (R[uid = uid1]Follow)[fid, uid1, uid2] で，以下のような結果が得られた．この時の関係 R を，関係 Transaction と属性 star を用いて答えよ．
fid| uid1| uid2-----------------f0002 | u05 | u06
f0006 | u06 | u05(g) 関係 Follow と R の商 Follow[uid1, uid2] ÷ R で，以下のような結果が得られた．
この時の関係 R を答えよ．
uid1---u01u04(2) (a) 関係モデルにおけるスーパーキーの定義を答えよ．
(b) 関係モデルにおける候補キーの定義を答えよ．
(c) 関係モデルにおける主キーと候補キーの違いを答えよ．
(d) 関係モデルにおける任意の関係には候補キーがあることを証明せよ．ただし，関係モデルにおいては，関係内の要素は重複していないと仮定する．

(e) SQL における distinct 演算子の役目を説明せよ．

令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(23/29)6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙 1 部を用いよ．また，
大問一つあたり一枚の解答用紙を用いよ．
Select 2 ﬁelds out of the 6 ﬁelds and answer the questions. Use a set of answer sheetsfor each of the ﬁelds you selected and use a separate answer sheet for each question.

Answer the following questions (【Q1】【Q2】).
【Q1】 Answer the following questions for the following algorithm.

Algorithm ALG(G = (V, E), s)
1: A = {s}.
2: B = {s}.
3: While A = ∅4:

Choose an element v ∈ A. A = A \ {v}.

5:For each w such that (v, w) ∈ E
If w ∈ B then

6:

Append w to A and B.

7:
8: Output B.

(1) Explain what the output B is when we execute the algorithm for an undirected
graph G = (V, E) with vertex set V and edge set E, and s ∈ V .
(2) If we use a stack for A, answer the elements of the output B according to the order
they were added to B when executing the algorithm for the following undirected
graph G = (V, E) and s ∈ V .
V= {s, t, u, v}

E = {(s, t), (s, u), (t, u), (t, v), (u, v)}(3) We want to check the vertices of a given undirected graph G = (V, E) in the increasing order of distance from s ∈ V . Answer an appropriate data structure for A
and explain the reason.
(4) Answer the execution time of the algorithm with considering data structures for G,
A, and B.

令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(24/29)6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙 1 部を用いよ．また，
大問一つあたり一枚の解答用紙を用いよ．
Select 2 ﬁelds out of the 6 ﬁelds and answer the questions. Use a set of answer sheetsfor each of the ﬁelds you selected and use a separate answer sheet for each question.

【Q2】 Answer the following questions.

(1) For the following relations Item(id, name, price), User(uid, name, mail),
Follow(fid, uid1, uid2, time), and Transaction(item, uid, star), answer
the following questions.
Item
id | name | price------------------001 | abc |150
002 | def |120
003 | ghi |230
004 | jkl |180005 | mno |350
006 | pqr |140
007 | stu |
150

User
uid | name | mail--------------------u01 | A| s@a.com
u02 | B| t@b.com
u03 | C| u@c.com
u04 | D| v@d.com
u05 | E| w@e.com
u06 | F| x@f.com
u07 | G| y@g.com

Transaction
item| uid | star---------------001 | u01 | 3
001 | u03 | 4
001 | u06 | 5
002 | u03 | 4002 | u05 | 5002 | u06 | 5
003 | u02 | 2

Followfid| uid1| uid2| time---------------------------f0001 | u01 | u03 | 20190801
f0002 | u05 | u06 | 20190810
f0003 | u04 | u03 | 20190810
f0004 | u01 | u02 | 20190811
f0005 | u02 | u01 | 20190813
f0006 | u06 | u05 | 20190817
f0007 | u04 | u02 | 20190820(a) Relation Follow is a set of facts that a user of uid1 follows another user of uid2
at time of time. Answer all candicate keys, where we assume that a user canfollow one user at most once.
(b) Relation Transaction is a set of facts that a user of uid purchases an item of
id and puts a score from 1 to 5 as star. Answer operations of the relational
algebra to obtain the set of uids who purchase items whose ids are 002.
(c) Relation User is a set of facts that a user whose ID is uid and name is name has
a mail address mail. Answer operations of the relational algebra to obtain theset of mails of users who purchase items whose ids are 002.
(d) Answer operations of the relational algebra to obtain the set of users following
the users who purchase items whose ids are 002.
(e) Relation Item is a set of items whose IDs are id, their names names, and their令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(25/29)6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙 1 部を用いよ．また，
大問一つあたり一枚の解答用紙を用いよ．
Select 2 ﬁelds out of the 6 ﬁelds and answer the questions. Use a set of answer sheetsfor each of the ﬁelds you selected and use a separate answer sheet for each question.

prices. Answer operations of the relational algebra to obtain the following
result using attribute price and a sign of inequality.
id | price-----------003 |
230
005 |
350
(f) When the following result is obtained using the natural join
(R[uid = uid1]Follow)[fid, uid1, uid2] of two relations R and Follow, answer
relation R using relation Transaction and attribute star.
fid| uid1| uid2-----------------f0002 | u05 | u06
f0006 | u06 | u05(g) When the following result is obtained using the division Follow[uid1, uid2] ÷ Rof two relations Follow and R, answer relation R.
uid1---u01u04(2) (a) Answer the deﬁnition of super-keys of the relational algebra.
(b) Answer the deﬁnition of candidate keys of the relational algebra.
(c) Answer the diﬀerence between primary keys and candidate keys of the relational
algebra.
(d) Prove any relation of the relational algebra has a candidate key, where we assume
that a relation of the relational algebra does not have duplicate elements.
(e) Answer the role of distinct operation of SQL.

令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(26/29)6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙 1 部を用いよ．また，
大問一つあたり一枚の解答用紙を用いよ．
Select 2 ﬁelds out of the 6 ﬁelds and answer the questions. Use a set of answer sheetsfor each of the ﬁelds you selected and use a separate answer sheet for each question.

F. 【計算機アーキテクチャ(Computer architecture) 分野】
次の各問い (【問 1】〜【問 3】) に答えよ．
【問 1】論理関数 H(a, b, c, d) を図で示されるように関数 F (a, b, c, d)，G(a, b, c, d) および NAND
ゲートを使って実現することを考える．関数 H および関数 G の真理値表が以下のように与えられる時，関数 F の最簡積和形を示せ．

a

b

c

d

H

G

0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1

0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1

0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1

0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1

0
1
1
1
1
1
1
1
1
1
0
0
1
1
1
1

1
1
0
1
0
1
0
0
0
1
1
1
1
1
0
0

a
b
c
d

F
H
G

令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(27/29)6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙 1 部を用いよ．また，
大問一つあたり一枚の解答用紙を用いよ．
Select 2 ﬁelds out of the 6 ﬁelds and answer the questions. Use a set of answer sheetsfor each of the ﬁelds you selected and use a separate answer sheet for each question.

【問 2】 5 つのステージからなるパイプライン式データパスを有するマイクロプロセッサについて考える．実装されたパイプラインステージは，IF（命令取得），ID （命令デコード），

EX（実行），MEM（メモリアクセス），ならびに，WB（ライトバック）である．以下の各問いに答えよ．

(1) プログラム実行時間は，「実行命令数」「平均 CPI(Clock cycles Per Instruction)」「ク
ロックサイクル時間」の積で近似できる．シングルサイクル・データパス方式（1 命
令の実行を 1 クロックサイクルで実行する方式）と比較した場合，パイプライン処理がプログラム実行時間に与える影響を説明せよ．

(2) パイプライン式データパスで発生する RAW (Read After Write) ハザードを解消す
る代表的な実装として「パイプラインストール」と「データフォワーディング」がある．これらの実装法の利点と欠点を説明せよ．

(3) 命令発行幅は 1 と仮定する．このパイプラインで達成できる IPC (Instructions Per
Clock cycle) の上限を答えよ．
【問 3】 16 ビットのアドレス（adr[15:0]）を入力とする 2 ウェイ・セットアソシアティブキャッ
シュの設計について考える．バイトアドレッシング方式であり 1 語は 4 バイトとする．
各キャッシュアクセスにおいて，adr[15:8]，adr[7:4] ならびに adr[3:0] は，それぞれ，タグフィールド，インデックスフィールド，オフセットフィールドとして参照される．以下の問いに答えよ．

(1) キャッシュブロックサイズを答えよ．
(2) キャッシュサイズを答えよ．
(3) レベル 1 キャッシュと主記憶からなるメモリシステムを想定した場合，平均メモリ
アクセス時間（AMAT: Average Memory Access Time）は下の式で表される．ここで，キャッシュヒット時間はキャッシュアクセス時間と同義と考えて良い．より高い
キャッシュ連想度を採用することの利点と欠点を AMAT を用いて説明せよ．

AMAT = キャッシュヒット時間+キャッシュミス率×キャッシュミスペナルティ令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(28/29)6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙 1 部を用いよ．また，
大問一つあたり一枚の解答用紙を用いよ．
Select 2 ﬁelds out of the 6 ﬁelds and answer the questions. Use a set of answer sheetsfor each of the ﬁelds you selected and use a separate answer sheet for each question.

Answer the following questions (【Q1】〜【Q3】).
【Q1】 Let H(a, b, c, d) be a logic function. Consider that H is composed of another subfunctions

F (a, b, c, d), G(a, b, c, d) and a NAND gate as shown in the ﬁgure below. When thetruthtables of H and G are given below, show the minimum sum of products form of F .
a

b

c

d

H

G

0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1

0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1

0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1

0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1

0
1
1
1
1
1
1
1
1
1
0
0
1
1
1
1

1
1
0
1
0
1
0
0
0
1
1
1
1
1
0
0

a
b
c
d

F
H
G

令和２年度

情報学専攻
情報知能工学専攻（実施日 令和元年８月２６日）

九州大学大学院システム情報科学府
修士課程

入学試験問題専 門 科 目 (Specialized subjects)(29/29)6 分野から 2 分野を選び解答すること．選んだ分野毎に解答用紙 1 部を用いよ．また，
大問一つあたり一枚の解答用紙を用いよ．
Select 2 ﬁelds out of the 6 ﬁelds and answer the questions. Use a set of answer sheetsfor each of the ﬁelds you selected and use a separate answer sheet for each question.

【Q2】 Let us consider a microprocessor that has a 5-stage pipelined datapath. The imple-

mented pipeline stages are IF (Instruction Fetch), ID (Instruction Decode), EX (EXecution), MEM (MEMory access), and WB (Write Back). Answer the following questions.
(1) Program execution time can be approximated by the product of three items, “instruction count”, “average CPI (Clock cycles Per Instruction)”, and “clock cycletime”. Explain the impact of pipelining on the program execution time by comparing with a single-cycle datapath implementation where each instruction is executedin a single clock cycle.
(2) There are two implementations, called “pipeline stall” and “data forwarding”, toresolve RAW (Read After Write) hazards that occur in the pipelined datapath.
Explain the advantages and disadvantages of these implementations.
(3) Assume that the instruction issue width is one. Answer the upper limit of IPC(Instructions Per Clock cycle) that can be achieved by the pipelined datapath.
【Q3】 Consider designing a two-way set-associative cache memory that accepts a 16-bit address(adr[15:0]). Suppose a byte-addressing scheme and the word size is 4 bytes. On eachcache access, adr[15:8], adr[7:4], and adr[3:0] are referenced as a tag ﬁeld, an index ﬁeld,
and an oﬀset ﬁeld, respectively. Answer the following questions.
(1) Answer the cache block size.
(2) Answer the cache size.
(3) Assume a memory system which consists of the level-1 cache and main memory.
AMAT (Average Memory Access Time) can be expressed by the following equation.
Here, you can consider that the cache hit time is the same as the cache access time.
Explain the advantages and disadvantages of applying higher cache associativity
based on AMAT.
AMAT = cache hit time + cache miss rate × cache miss penalty