九州大学大学院システム情報科学府
情報理工学専攻

令和５年度入学試験問題【令和４年８月２９日（月）、３０日（火）】情報理工学専攻
電気電子工学専攻修士課程 入学試験問題（令和４年８月２９日）

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

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

解答上の注意 (Instructions):

1. 問題用紙は，『始め』の合図があるまで開いてはならない．
Do not open this cover sheet until the start of examination is announced.
2. 問題用紙は表紙を含め 6 枚，解答用紙は 3 枚つづり (1 分野につき 1 枚) である．
You are given 6 problem sheets including this cover sheet, and 3 answer sheets (1 sheet foreach ﬁeld).
3. 線形代数，解析学・微積分の 2 分野に加えて，ベクトル解析および確率・統計から 1 分野を選択し，合計 3 分野について解答すること．選んだ分野毎に解答用紙を別にすること．

Answer three ﬁelds in total, including Linear algebra and Analysis and calculus, and either
Vector analysis or Probability and statistics. You must use a separate answer sheet for eachof the ﬁelds you selected.

1
2
3
4

分野
線形代数
解析学・微積分
ベクトル解析
確率・統計

field
Linear algebra
Analysis and calculus
Vector analysis
Probability and statistics

page
2
3
5
6

4. 解答用紙の全部に，専攻名，受験番号および氏名を記入すること．3 枚目の解答用紙について
は，選択した分野番号（3 または 4）を○で囲むこと．

Fill in the designated blanks at the top of each answer sheet with the department name, yourexaminee number and your name. Mark the selected ﬁeld number (3 or 4) with a circle on
the third answer sheet.
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)（6 枚中の 2）
分野毎に解答用紙を別にすること．
Use a separate answer sheet for each field.

1. 【線形代数 (Linear algebra) 分野】

n × n 実対称行列 A = [aij ]n×n ∈ Rn×n に対して，A の各要素 aij が aij ∈ {0, 1} (1 ≤ i, j ≤ n)∑n
かつ aii = 0 (1 ≤ i ≤ n) を満たすとする．A に対して，D = [δij ( k=1 aik )]n×n と定義する．
ただし δij は，1 ≤ i, j ≤ n に対して，i = j のとき δij = 1，そうでないとき δij = 0 によって定義される．さらに，L = D − A と定義する．以下の各問いに答えよ．

(1) 以下の A に対して，L = D − A を求めよ．

0 1
1 0

A=
1 1
0 0

1
1
0
0


0
0


0
0

(2) (1) で求めた L の固有値を全て求めよ．
(3) (2) で求めた L の各固有値に対する固有空間を求めよ．
(4) 一般に L は固有値 0 を持つことを示せ．
For an n × n real symmetric matrix A = [aij ]n×n ∈ Rn×n , suppose that each element aij of A∑
satisﬁes that aij ∈ {0, 1} (1 ≤ i, j ≤ n) and aii = 0 (1 ≤ i ≤ n). Deﬁne D = [δij ( nk=1 aik )]n×n
for A, where δij is deﬁned by δij = 1 if i = j and δij = 0 otherwise for 1 ≤ i, j ≤ n.
Furthermore, deﬁne L = D − A. Answer the following questions.
(1) For the following matrix A, ﬁnd L = D − A.

0 1
1 0

A=
1 1
0 0

1
1
0
0


0
0

.
0
0

(2) Find all eigenvalues of L obtained in (1).
(3) Find the eigenspace for each eigenvalue of L obtained in (2).
(4) Prove that L has an eigenvalue 0 in general.

情報理工学専攻
電気電子工学専攻修士課程 入学試験問題（令和４年８月２９日）

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

数 学 (Mathematics)（6 枚中の 3）
分野毎に解答用紙を別にすること．
Use a separate answer sheet for each field.

2. 【解析学・微積分 (Analysis and calculus) 分野】(1) R 上の関数 f (x) = cos x の k 階導関数を f (k) (x) で表す．ただし，R は実数全体の集合である．以下の各問いに答えよ．

(a) 全ての k ≥ 1 について f (k) (0) を求めよ．
(b) f (x) の原点周りでのテイラー級数を
∞
∑

ak xk

k=0

とするとき，全ての k ≥ 0 に関する ak を求めよ．

(c) 全ての x ∈ R について∞∑

|ak xk |k=0が収束することを示せ．

(2) 次の微分方程式の一般解を求めよ．なお，y ′ は関数 y(x) の x に関する 1 階導関数を表している．

y ′′′′ − 2y ′′′ − y ′′ − 4y ′ + 12y = 0

I(3) 閉曲線 C に沿った複素積分
つ r ̸= 1 とする.

1dz を求めよ．ただし，C は円 |z| = r , r > 0 か
2
C z(z − 1)

情報理工学専攻
電気電子工学専攻修士課程 入学試験問題（令和４年８月２９日）

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

数 学 (Mathematics)（6 枚中の 4）
分野毎に解答用紙を別にすること．
Use a separate answer sheet for each field.

(1) Let f (k) (x) denote the kth order derivative of the function f (x) = cos x over R, where
R denotes the set of all real numbers. Answer the following questions.
(a) Find f (k) (0) for all k ≥ 1.
(b) Let

∞
∑

ak xk

k=0

be the Taylor expansion of f (x) around the origin. Find ak for all k ≥ 0.
(c) Prove that∞∑|ak xk |k=0

converges for all x ∈ R.

(2) Find the general solution to the following diﬀerential equation. Here, y ′ denotes thederivative of ﬁrst order with respect to x for a function y(x).
y ′′′′ − 2y ′′′ − y ′′ − 4y ′ + 12y = 0.

I(3) Calculate the complex integralCa circle |z| = r, r > 0, and r ̸= 1.

1
z(z 2 − 1)dz, where the closed contour C is given by

情報理工学専攻
電気電子工学専攻修士課程 入学試験問題（令和４年８月２９日）

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

数 学 (Mathematics)（6 枚中の 5）
分野毎に解答用紙を別にすること．
Use a separate answer sheet for each field.

3. 【ベクトル解析 (Vector analysis) 分野】
直交座標系において，x，y ，z 軸方向の単位ベクトルをそれぞれ i，j ，k とする．ベクトル場 F を F = yi − xj + zk とする．次の各問に答えよ．

(1) C を x2 + y 2 = 4, z = 0 で定義される円とする．次に示す C1 および C2 に沿った線積分∫∫
F · dr および C2 F · dr を求めよ．
C1√√(a) C1 : C 上を点 A(1, 3, 0) から 点 B(− 3, 1, 0) まで反時計回りに向かう曲線√√(b) C2 : C 上を点 A(1, 3, 0) から 点 B(− 3, 1, 0) まで時計回りに向かう曲線(2) S を半球面 x2 + y 2 + z 2 = 4 (0 ≤ z) と平面 z = 0 で囲まれた領域の境界とする．面積分∫∇ × F · dS を求めよ．外向き法線ベクトルを用いよ．
SThe unit vectors on x, y and z axes of Cartesian coordinates are denoted by i, j and k,
respectively. Let F be the vector ﬁeld F = yi − xj + zk. Answer the following questions.
∫(1) Let C be deﬁned by the circle x2 + y 2 = 4, z = 0. Find the line integrals C1 F · dr and∫
F · dr, where C1 and C2 are deﬁned as follows.
C2√√(a) C1 : the curve along C from point A(1, 3, 0) to point B(− 3, 1, 0) in the counterclockwise direction.

√√(b) C2 : the curve along C from point A(1, 3, 0) to point B(− 3, 1, 0) in the clockwise
direction.
(2) Let S be the boundary of the region enclosed by the hemisphere x2 + y 2 + z 2 = 4 (0 ≤ z)∫
and the plane z = 0. Find the surface integral S ∇ × F · dS. Use the outward pointing
normal vector.

情報理工学専攻
電気電子工学専攻修士課程 入学試験問題（令和４年８月２９日）

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

数 学 (Mathematics)（6 枚中の 6）
分野毎に解答用紙を別にすること．
Use a separate answer sheet for each field.

4. 【確率・統計 (Probability and statistics) 分野】
箱の中に５枚のコイン（コイン１〜コイン５）がある．箱から一様ランダムにコインを１枚選んで何度か投げる試行を考える．ただし，それぞれのコイン i の表が出る確率 pi は次の通りである．

p1 = 0, p2 = 1/4, p3 = 1/2, p4 = 3/4, p5 = 1
表が出る事象を H とし，コイン i が選ばれる事象を Ci とする．

(1) 選んだコインを１回投げるとする．表が出る確率 p(H) を答えよ．
(2) 選んだコインを１回投げたところ表が出たとする．条件付き確率p(Ci | H)を i = 1, . . . , 5についてそれぞれ求めよ．

(3) 選んだコインを２回投げるとする．条件付き確率p(H2 | H1 )を求めよ．ただし Hj は j 回目に表が出る事象であり，j = 1, 2 である.

(4) 選んだコインを４回投げるとする．p(Ci | B4 )を i = 1, . . . , 5 についてそれぞれ求めよ．
ただし B4 は４回目に初めて表が出る事象を表す．

A box contains 5 coins (coin 1, . . . , coin 5). Consider a trial in which we select a coin uniformly
at random, and toss it for a certain number of times. Let pi denote the probability of gettinga head on each coin i, and they are given as follows:
p1 = 0, p2 = 1/4, p3 = 1/2, p4 = 3/4, p5 = 1
Let H denote the event that a head shows up, and let Ci denote the event that coin i isselected.
(1) Select a coin and toss it once. Find the probability of getting a head p(H).
(2) Suppose a head was obtained after tossing the selected coin once. Find the conditional
probability p(Ci | H) for each i = 1, . . . , 5.
(3) Suppose we toss the selected coin twice. Find the conditional probability p(H2 | H1 ).
Here Hj (j = 1, 2) means that a head is obtained on the j-th toss.
(4) Suppose we toss the selected coin four times. Find p(Ci | B4 ) for each i = 1, . . . , 5. HereB4 means that the ﬁrst head is obtained on the fourth toss.

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(1/27)

解答上の注意 (Instructions):

1. 問題用紙は，『始め』の合図があるまで開いてはならない．
Do not open this cover sheet until the start of examination is announced.
2. 問題用紙は表紙を含め 27 枚，解答用紙は 3 枚つづり 2 部 (1 分野につき 1 部) である．
You are given 27 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. One sheet in a set is for one question.
You may not use one sheet for two or more questions.

A
B
C
D
E
F

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

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

page
2
6
8
12
16
22

4. 解答用紙の全部に，選択分野名，受験番号，氏名および問題番号を記入すること．
Fill in the designated blanks at the top of each answer sheet with the selected ﬁeld, yourexaminee 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 it clearly on the sheet.
6. 解答は，日本語，英語のいずれかで記入すること．
Your answers must be written in Japanese or English.

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(2/27)
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 an answer sheet for each question.

A. 【電気回路 (Circuit theory) 分野】【問 1】〜【問 4】から2 問を選び，解答用紙の問題番号欄に解答した問題番号を記入せよ．
【問 1】 図 1 の回路について，以下の問いに答えよ．ただし，Z = R2 + jX2 ，|I1 | = |I2 | = |I3 |であり，各素子値の単位は Ω である．

(1) arg Z = π/6 のとき，E ，I ，I1 ，I2 ，I3 のE とI
位相関係を表すフェーザ図を描き，
 
Iの位相差 arg
を求めよ．
E

I3

I

E

I1

I2

-jX1

R1

R2
Z
jX2

(2) R2 = X2 = 2 [Ω]，E = 4 [V] のとき，|I|の値を求めよ．

図1

I1

I2

M
L

L
【問 2】 図 2 の回路について，以下の問いに答えよ．ただし，L，L0 ，L1 ，L2 を自己インダク
タンス，M を相互インダクタンス，電源電圧 Eの角周波数を ω とする．

ER
(a)
I1 L 1(1) 図 2(a) の回路が図 2(b) と等価であるとき，
L0 ，L1 ，L2 を L，M を用いて表せ．
(2) 抵抗 R に流れる電流 IR を L，M ，R，ω ，
E を用いて表せ．

IR

L2
L0

E

IR
R
(b)
図2

I2

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(3/27)
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 an answer sheet for each question.

【問 3】 図 3(a) のような，Z1 , Z2 , Z3 , Z12 のイ
ンピーダンスをもつ ∇ 型と Y 型が重なった回路をもつ二端子対網 A(1-1’ 端子対と 2-2’ 端子対) がある．以下の問いに答えよ．ただし，Z1 , Z2 , Z3 ,
Z12 は図に示した値を持ち，二端子対網の左右の電圧と電流 V1 , V2 , I1 , I2 に対し，インピーダンス
行列 (Z 行列)Z とアドミタンス行列 (Y 行列)Y は



=Z

I1
I2

1

2

1’

のようにそれぞれ定義されるとする．

2’

図 3(a)
1

y

2

1

2

図 3(b)【問 4】 図 4 の回路について，以下の問いに答えよ．
ただし，e(t) = 25 sin 3t [V]，R = 0.25 [Ω]，C = 1 [F]，q(0) = 4 [C] とし，時刻 t = 0 でスイッチ S を閉じるとする．

(1) スイッチ S を閉じた直後の電流 i(0) を求めよ．また，回路が定常状態に達した後の電流 i(t) を求
めよ．

1

2

2

1

(2) 二端子対網 A の Z 行列 ZA を求めよ．必要であれば，図 3(b) に示す二つの二端子対網の Y 行列，Z 行列を用いても良い．

t=0

R

S

q(t)

e(t)

C

図4

(2) t > 0 における電流 i(t) を求めよ．

2

3

3’

 



I1
V1
,
=Y
I2
V2

(1) 端子 3 と 3’ を追加し，二端子対網 (1-3’ 端子
対と 2-3 端子対) を，Y 行列 Y∇ をもつ二端子対網の等価回路と見なした．このときのY∇ をもとめよ．

2

z

V1
V2

2

12

1

3



1/2

1

i(t)

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(4/27)
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 an answer sheet for each question.

Select two out of the four questions 【Q1】〜【Q4】and write the number of the selected
question on the answer sheet.
【Q1】 Consider the circuit shown in Fig. 1,
where Z = R2 + jX2 , |I1 | = |I2 | = |I3 |, andthe values of elements are Ω in unit. Answer
the following questions.

(1) Draw a phasor diagram representing thephase relation of E, I, I1 , I2 , I3 , whenarg Z = π/6. Also
 ﬁnd the phase difI.
ference of arg
E

I3

I

E

I1

I2

-jX1

R1

R2
Z
jX2

Fig. 1(2) Find the value of |I|, when R2 = X2 =2 [Ω] and E = 4 [V].

I1

I2

M
L

L
【Q2】 Consider the circuit shown in Fig. 2,
where L, L0 , L1 and L2 represent the selfinductances, M represents the mutual inductance and the source voltage E has the angularfrequency ω. Answer the following questions.

(1) When the ciruit shown in Fig. 2(a) is
equivalent to the circuit shown in Fig. 2(b),express the inductances L0 , L1 and L2 using L and M .
(2) Express the current IR through the resistance R using L, M , R, ω and E.

E

IR
R
(a)
I1 L 1

L2
L0

E

IR
R
(b)
Fig. 2

I2

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(5/27)
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 an answer sheet for each question.

【Q3】 Consider the two-port network A (port 11’ and port 2-2’) with a network of overlapping ∇type and Y-type circuits with Z1 , Z2 , Z3 , and Z12
in impedance, as shown in Fig. 3(a). Answer thefollowing questions. Here, Z1 , Z2 , Z3 , and Z12 havethe values shown in the ﬁgure, and for the voltages
and currents V1 , V2 , I1 , I2 on the left and right of a
two-port network, the impedance matrix (Z-matrix)
Z and admittance matrix (Y-matrix) Y are deﬁned
as follows, respectively.
V1
V2




=Z

I1
I2

 



I1
V1
,
=Y
I2
V2

(1) When terminals 3 and 3’ are added, the twoport network (port 1-3’ and port 2-3) is considered as an equivalent circuit with Y-matrix
Y∇ . Find Y∇ .

2

12

1

2

1’

2’

Fig. 3(a)
1

1

2

y

2

1

1

2

Fig. 3(b)【Q4】 Consider the circuit shown in Fig. 4, wheree(t) = 25 sin 3t [V], R = 0.25 [Ω], C = 1 [F], q(0) =4 [C] and the switch S is closed at t = 0 . Answer
the following questions.

t=0

R

S

q(t)

e(t)

C

Fig. 4(2) Find the current i(t) for t > 0.

2

3

3’
3

1

(2) Find the Z-matrix ZA of the two-port network A. If necessary, it can be referred theY-matrix and Z-matrix of the two-port networks in Fig. 3(b).

(1) Find the current i(0) just after the switch S isclosed. Also ﬁnd the current i(t) when steadystate is reached.

2

z



1/2

1

i(t)

2

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(6/27)
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 an answer sheet for each question.

B. 【情報理論 (Information theory) 分野】
次の各問い（【問 1】【問 2】）に答えよ．解答用紙の問題番号欄に解答した問題番号を記入すること．
【問 1】以下の各問いに答えよ．

(1) 区間 [0, a] (a > 0) 上の一様分布に従う確率変数の微分エントロピーを求めよ．
(2) 区間 [0, a] (a > 0) 上で定義された確率密度関数 p(x) = 2x/a2 に従う確率変数の微分
エントロピーを求めよ．
【問 2】時刻 t の入力 Xt ∈ {0, 1} (t = 1, 2, . . .) に対し，入力と独立な誤り源 SE から発生した
記号 Zt ∈ {0, 1} が加わった値 Yt = Xt ⊕ Zt が出力される加法的 2 元通信路 W を考える．ただし，⊕ は排他的論理和を表し，0 ⊕ 1 = 1, 1 ⊕ 1 = 0 である．誤り源 SE が，

P (Zt+1 = 1|Zt = 0) = 0.25，P (Zt+1 = 1|Zt = 1) = 0.5 となる定常な単純マルコフ情報源である場合について，以下の問いに答えよ．

(1) 誤り源 SE の定常確率分布を求めよ．
(2) 誤り源 SE のエントロピーレート H(SE ) を求めよ．
(3) X n = (X1 , . . . , Xn ) が P (Xt = 1) = 1/2 (t = 1, 2, . . . , n) である離散無記憶情報源からの出力であり，Z n = (Z1 , . . . , Zn ) が定数 z n ∈ {0, 1}n に固定されていると仮定す
る．Y n = (Y1 , . . . , Yn ) が P (Yt = 1) = 1/2 (t = 1, 2, . . . , n) である離散無記憶情報源の出力であることを示せ．

(4) 通信路 W の通信路容量は以下の式で定義される．
1
I(X n ; Y n )n→∞ PX n ∈Pn n

C = lim max

ただし，I(X n ; Y n ) は X n と Y n の間の相互情報量を，PX n は入力 X n の確率分布を，

Pn は {0, 1}n 上の確率分布全てからなる集合を表す．このとき，C = 1 − H(SE ) となることを示せ．

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(7/27)
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 an answer sheet for each question.

Answer the following questions (【Q1】【Q2】) and write the number of the question
on the answer sheet.
【Q1】 Answer the following questions.

(1) Find the diﬀerential entropy of the uniform random variable over the section [0, a],where a > 0.
(2) Find the diﬀerential entropy of the random variable which follows the probability
density function p(x) = 2x/a2 over the section [0, a], where a > 0.
【Q2】 Let W be an additive binary channel that outputs Yt = Xt ⊕Zt given an input Xt ∈ {0, 1}

at time t (t = 1, 2, . . .), where Zt ∈ {0, 1} is an error outputted from an error source
SE independent of the inputs, and ⊕ denotes exclusive-or (e.g., 0 ⊕ 1 = 1, 1 ⊕ 1 = 0).
Suppose that SE is the 1-st order stationary Markov information source which satisﬁes
P (Zt+1 = 1|Zt = 0) = 0.25 and P (Zt+1 = 1|Zt = 1) = 0.5. Answer the following
questions.
(1) Find the stationary probability distribution of the Markov information source SE .
(2) Find the entropy rate of SE , denoted H(SE ).
(3) Suppose that X n = (X1 , . . . , Xn ) is an output of the discrete memoryless sourcewith P (Xt = 1) = 1/2 (t = 1, 2, . . . , n) and that Z n = (Z1 , . . . , Zn ) is ﬁxed to a
constant z n ∈ {0, 1}n . Prove that Y n = (Y1 , . . . , Yn ) is an output of the discrete
memoryless source with P (Yt = 1) = 1/2 (t = 1, 2, . . . , n).
(4) The channel capacity of W is deﬁned as
1
I(X n ; Y n ),n→∞ PX n ∈Pn n

C = lim max

where I(X n ; Y n ) is the mutual information between X n and Y n , PX n is a probability
distribution of X n , and Pn denotes the set of all probability distributions over{0, 1}n . Prove C = 1 − H(SE ).

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(8/27)
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 an answer sheet for each question.

C. 【オートマトンと言語 (Automata and formal languages) 分野】

次の各問い（【問１】【問２】）に答えよ．解答用紙の問題番号欄に解答した問題番号を記入す
ること．
【問１】白玉が k 個，赤玉が l 個入っている袋から 1 つずつ玉を取り出すという操作を，袋が空になるまで繰り返す．
（全部で n = k + l 回の操作が行われる．
）このとき，取り出された順に玉の色を並べることによって得られる長さ n の文字列 a = a[1]a[2] · · · a[n] を次のように定義する．各 i ∈ {1, 2, . . . , n} に対し，i 回目の操作で白玉が取り出されたとき a[i] = w，赤玉が取り出されたとき a[i] = r とする．このようにして得られるすべての文字列 a からなる集合を Lk,l とする．すなわち，Σ = {w, r} としたとき Lk,l ⊆ Σn である．また，i 回目の操作で白玉が取り出されたとき，その時点で袋の中に残っている赤玉の個数を p[i]，赤玉が取り出されたとき，その時点で袋の中に残っている白玉の個数を p[i] とし，報酬 p[i]が与えられるとする．このようにして得られるすべての報酬の系列 p = p[1]p[2] · · · p[n]からなる集合を Pk,l とする．例えば，k = l = 3 で，赤，白，白，赤，赤，白の順に玉を袋から取り出したとき，a = rwwrrw，p = 322110 となるので，a ∈ L3,3 ，p ∈ P3,3 であるが，rwwwrw ∈/ L3,3 （w と r の出現数は等しいはず），322111 ∈/ P3,3 （最後に受け取る
報酬は必ず 0 のはず）である．

(1) k = l = 3 のとき，集合 Lk,l を受理する状態数最小の決定性有限オートマトンの状態
遷移図を示せ．ただし，受理状態に到達することのない状態，および，そのような状態への遷移は省略してもよい．

(2) k = l = 3 のとき，集合 Pk,l (⊆ {0, 1, 2, 3}6 ) を受理する状態数最小の決定性有限オー
トマトンの状態遷移図を示せ．ただし，受理状態に到達することのない状態，および，そのような状態への遷移は省略してもよい．

(3) 任意の白玉数 k ，赤玉数 l に対し，玉の取り出し方によらず，報酬の総和がkl となることを示せ．
（ヒント：n に関する帰納法を用いよ．
）

ni=1 p[i] =九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(9/27)
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 an answer sheet for each question.

【問２】文脈自由文法を４つ組 (N, Σ, P, S) で表す．ただし，N ，Σ，P ，S をそれぞれ非終端記号の集合，終端記号の集合，生成規則の集合，開始記号とする．Σ = {a, b} とする．

(1) L1 = {ai bj | 0 ≤ i < j} とする．言語 L1 を生成する文脈自由文法 G1 = (N1 , Σ, P1 , S)の生成規則の集合 P1 を与えよ．ただし |N1 | = 1 とする．

(2) L2 を以下の条件を満たす言語とする．
• L2 ∪ {ai bj | 0 ≤ i < j} ∪ {ai bj | i > j ≥ 0} = Σ∗ \ {ai bi | i ≥ 0}
• L2 ∩ {ai bj | 0 ≤ i < j} = L2 ∩ {ai bj | i > j ≥ 0} = ∅言語 L2 を生成する文脈自由文法 G2 = (N2 , Σ, P2 , S) の生成規則の集合 P2 を与えよ．
ただし |N2 | ≤ 2 とする．

(3) L3 = Σ∗ \ {ai bi | i ≥ 0} とする．以下のような生成規則の集合を持ち，かつ言語 L3を生成する文脈自由文法 G3 = (N3 , Σ, P3 , S) を考える．ただし N3 = {S, X} であり，

ε は空文字列を表す．(i), (ii), (iii) を与えよ．
S →

(i)

|

|

(ii)

(iii)

X → bX | aX | ε(4) 以下の状態遷移図を持つ決定性有限オートマトン M = (K, Σ, δ, q0 , F ) で受理される
言語を L(M ) とする．ただし，K = {q0 , q1 , q2 }，Σ，δ ，q0 ，F = {q0 } は，それぞれM の状態の集合，アルファベット，遷移関数，初期状態，受理状態の集合を表す．
L4 = Σ∗ \ L(M ) とする．言語 L4 を生成する文脈自由文法 G4 = (N4 , Σ, P4 , S) の生
成規則の集合 P4 を与えよ．ただし |N4 | ≤ 2 とする．

q0

b

a
b
q2

q1

a
a,b

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(10/27)
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 an answer sheet for each question.

Answer the following questions (【Q1】【Q2】）and write the number of the selected question
on the answer sheet.
【Q1】 You have a bag that contains k white balls and l red balls. Consider the following

repeated process: you take a ball from the bag one by one until the bag is empty (youthus take n = k + l balls in all). We then deﬁne a string a = a[1]a[2] · · · a[n] of lengthn obtained by arranging the colors of the balls in the order in which they were takenout. Formally, for each i ∈ {1, 2, . . . , n}, a[i] = w if your ith ball is white and a[i] = r if
your ith ball is red. Let Lk,l denote the set consisting of all strings a deﬁned in this way.
Note that Lk,l ⊆ Σn , where Σ = {w, r}. You also receive for each i a reward p[i], which
is deﬁned as the number of red (white, resp.) balls remaining in the bag if your ith ballis white (red, resp.). Let Pk,l denote the set consisting of all strings p = p[1]p[2] · · · p[n]deﬁned in this way. For example, when k = l = 3 and you happened to take balls fromthe bag in the order of red, white, white, red, red, white, then a = rwwrrw (and thusa ∈ L3,3 ) and p = 322110 (and thus p ∈ P3,3 ). On the other hand, we have rwwwrw ∈/ L3,3(the number of occurrences of w should be the same as that of r), and 322111 ∈/ P3,3(the reward you receive last should be 0).
(1) Assume that k = l = 3. Draw a state transition diagram of a deterministic ﬁnite
automaton that accepts the set Lk,l with the minimum number of states. You may
omit such states, together with the transitions to them, that are unreachable to an
accept state.
(2) Assume that k = l = 3. Draw a state transition diagram of a deterministic ﬁnite
automaton that accepts the set Pk,l (⊆ {0, 1, 2, 3}6 ) with the minimum number ofstates. You may omit such states, together with the transitions to them, that are
unreachable to an accept state.
(3) Show that for any initial numbers k and l of white and red balls, the total reward
you receive is ni=1 p[i] = kl no matter how you obtain the balls. (Hint: Use an
induction on n.)

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(11/27)
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 an answer sheet for each question.

【Q2】 We represent a context-free grammar by a quadruple (N, Σ, P, S), where N , Σ, P , andS represent the set of non-terminal symbols, the set of terminal symbols, the set of
production rules, and the start symbol, respectively. Let Σ = {a, b}.
(1) Let L1 = {ai bj | 0 ≤ i < j}. Give a set P1 of production rules of a context-freegrammar G1 = (N1 , Σ, P1 , S) which generates the language L1 with |N1 | = 1.
(2) Let L2 be the language which satisﬁes the following conditions:• L2 ∪ {ai bj | 0 ≤ i < j} ∪ {ai bj | i > j ≥ 0} = Σ∗ \ {ai bi | i ≥ 0}, and• L2 ∩ {ai bj | 0 ≤ i < j} = L2 ∩ {ai bj | i > j ≥ 0} = ∅.
Give a set P2 of production rules of a context-free grammar G2 = (N2 , Σ, P2 , S)
which generates the language L2 with |N2 | ≤ 2.
(3) Let L3 = Σ∗ \ {ai bi | i ≥ 0}. Consider a context-free grammar G3 = (N3 , Σ, P3 , S)
which generates the language L3 with a set of production rules in the following form,
where N3 = {S, X} and ε denotes the empty string. Give (i), (ii), and (iii).
S →

(i)

|

|

(ii)

(iii)

X → bX | aX | ε(4) Let L(M ) be the language accepted by the deterministic ﬁnite automaton M =(K, Σ, δ, q0 , F ) with the following state transition diagram, where K = {q0 , q1 , q2 },Σ, δ, q0 , and F = {q0 } are the set of states, the alphabet, the transition function,
the initial state, and the set of accept states, respectively. Let L4 = Σ∗ \L(M ). Givea set P4 of production rules of a context-free grammar G4 = (N4 , Σ, P4 , S) which
generates the language L4 with |N4 | ≤ 2.

q0

b

a
b
q2

q1

a
a,b

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(12/27)
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 an answer sheet for each question.

D. 【電磁気学 (Electromagnetism) 分野】

௨ୗࡢྛၥ࠸ ࠙ၥࠚ࠙ၥࠚ ࡟⟅࠼ࡼ㸬ゎ⟅⏝⣬ࡢၥ㢟␒ྕḍ࡟ゎ⟅ࡋࡓၥ㢟␒ྕࢆグධࡍࡿࡇ࡜
ၥ㸯 ㄏ㟁⋡ߝଵ ࡢㄏ㟁య  ࡜ㄏ㟁⋡ߝଶ ࡢㄏ㟁య  ࡛‶ࡓࡉࢀ࡚࠸ࡿ✵㛫ࢆ⪃࠼ࡿࠋㄏ㟁య  ࡜ㄏ㟁య  ࡜ࡣᅗ㸯ࡢࡼ࠺࡟᥋ࡋ࡚࠾ࡾ㸪ࡑࡢ୰࡟ㄏ㟁యࡢቃ⏺㠃࡟୰ᚰࡀ࠶ࡿ༙
ᚄܽࡢᑟయ⌫ࡀ⨨࠿ࢀ࡚࠸ࡿ㸬ᑟయ⌫࡟ࡣ㟁Ⲵܳࢆ୚࠼ࡓ㸬ࡇࡢ⣔࡟㛵ࡋ࡚㸪௨ୗࡢၥ࠸
࡟⟅࠼ࡼ㸬௞ ᑟయ⌫ࡢ୰ᚰ࠿ࡽࡢ㊥㞳ࢆ‫࡜ࡿࡍ࡜ݎ‬㸪‫ ݎ‬൐ ܽ࡛ࡢ㟁఩ࡣܸ ൌ ࡢᙧ࡛୚࠼ࡽࢀࡿ㸬ࡓࡔࡋ㸪݇ࡣᐃᩘ࡛࠶ࡿ㸬࢞࢘ࢫࡢἲ๎ࢆ⏝࠸࡚݇ࢆồࡵࡼ㸬 ⣔ࡢ㟼㟁ᐜ㔞ࢆồࡵࡼ㸬 ᑟయ⌫ࡀㄏ㟁య  ࡜᥋ࡋ࡚࠸ࡿ㠃ୖࡢ඲㟁Ⲵࢆồࡵࡼ㸬 ⣔ࡢ㟼㟁࢚ࢿࣝࢠ࣮ࢆồࡵࡼ㸬















ᅗ 




௥

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(13/27)
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 an answer sheet for each question.

ၥ㸰 ᅗ㸰࡟♧ࡍࡼ࠺࡞㸪㉳㟁ຊܸ଴ ࡢ㟁ụ㸪᢬ᢠܴ㸪ࢯࣞࣀ࢖ࢻࢥ࢖ࣝࡀ┤ิ࡟᥋⥆ࡉࢀࡓᅇ㊰ࡀ┿✵୰࡟⨨࠿ࢀ࡚࠾ࡾ㸪㟁ὶࡀὶࢀ࡚࠸ࡿ㸬ࢯࣞࣀ࢖ࢻࢥ࢖ࣝࡢ㛗ࡉ㸪༙ᚄ㸪༢఩㛗ࡉᙜࡓࡾࡢᕳࡁᩘࡣࡑࢀࡒࢀ݈㸪ܽ㸪࡛݊࠶ࡿ㸬ࡓࡔࡋ㸪݈ ‫ࡋ࡜ܽ ب‬㸪➃ຠᯝࡣ↓ど࡛ࡁࡿ࡜ࡍ
ࡿ㸬┿✵ࡢ㏱☢⋡ࡣߤ଴ ࡜ࡍࡿ㸬㸬 ᅗ㸰 D  ࡟♧ࡍࡼ࠺࡟㸪ࢫ࢖ࢵࢳࡀ➃Ꮚ 3 ࡟ࡘ࡞ࡀࢀ㸪୍ᐃ㟁ὶࡀὶࢀ࡚࠸ࡿሙྜ࡟ࡘ
࠸࡚⪃࠼ࡿ㸬ࢯࣞࣀ࢖ࢻࢥ࢖ࣝෆࡢ☢᮰ᐦᗘࡢ኱ࡁࡉࢆồࡵࡼ㸬 ࢯࣞࣀ࢖ࢻࢥ࢖ࣝࡢ⮬ᕫ࢖ࣥࢲࢡࢱࣥࢫࢆồࡵࡼ㸬 ᫬้‫ ݐ‬ൌ Ͳ࡟ࢫ࢖ࢵࢳࢆ➃Ꮚ 3 ࠿ࡽ 4 ࡟ษࡾ᭰࠼ࡓᚋ㸪ᅇ㊰࡟‫ܫ‬ሺ‫ݐ‬ሻ ൌ ‫ܫ‬଴ ݁ ିఉ௧ ሺ‫ ݐ‬൒ Ͳሻࡢ㟁ὶࡀὶࢀࡓ ᅗ㸰 E 㸬ࢯࣞࣀ࢖ࢻࢥ࢖ࣝ࡟Ⓨ⏕ࡍࡿㄏᑟ㉳㟁ຊࢆ᫬㛫‫ࡢݐ‬㛵ᩘ࡜ࡋ࡚⾲ࡏ㸬ࡲࡓߚࢆồࡵࡼ㸬  ࡢሙྜ࡟࠾࠸࡚㸪ࢯࣞࣀ࢖ࢻࢥ࢖ࣝෆ࡟Ⓨ⏕ࡍࡿ㟁⏺ࢆ㸪ࢯࣞࣀ࢖ࢻࢥ࢖ࣝࡢ୰ᚰ㍈
࠿ࡽࡢ㊥㞳‫࡜ݎ‬᫬㛫‫ࡢݐ‬㛵ᩘ࡜ࡋ࡚⾲ࡏ㸬  ࡢሙྜ࡟࠾࠸࡚㸪ࢯࣞࣀ࢖ࢻࢥ࢖ࣝࡢ୰ᚰ㍈࠿ࡽࡢ㊥㞳‫ ݎ‬ൌ ܽ࡟࠾ࡅࡿ࣏࢖ࣥࢸ࢕ࣥ
ࢢ࣋ࢡࢺࣝࡢ኱ࡁࡉࢆ᫬㛫‫ࡢݐ‬㛵ᩘ࡜ࡋ࡚⾲ࡏ㸬ࡲࡓࡑࡢྥࡁࢆồࡵࡼ㸬  ࡢሙྜ࡟࠾࠸࡚㸪༢఩᫬㛫ᙜࡓࡾ࡟ࢯࣞࣀ࢖ࢻࢥ࢖ࣝ࠿ࡽὶฟࡍࡿ࢚ࢿࣝࢠ࣮ࢆ᫬㛫‫ࡢݐ‬㛵ᩘ࡜ࡋ࡚⾲ࡏ㸬ࡲࡓ㸪᫬้‫ ݐ‬ൌ Ͳ࠿ࡽ‫ ݐ‬ൌ λࡢ㛫࡟ࢯࣞࣀ࢖ࢻࢥ࢖ࣝ࠿ࡽὶฟࡋࡓ
࢚ࢿࣝࢠ࣮ࡢ⥲࿴ࢆồࡵ㸪ࡑࢀࡀ࡝ࡇ࡛ᾘ㈝ࡉࢀࡓ࠿⟅࠼ࡼ㸬D  E 

ᅗ㸰




九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(14/27)
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 an answer sheet for each question.

ȋȏͳȐȏʹȐȌ ǤȏͳȐ   ͳ  ʹǤ  ͳߝଵ   ʹߝଶ Ǥ   Ǥͳǡ
 ܽ   Ǥ  
 ܳǤǤ௞ȋͳȌ ‫ ݎ‬൐ ܽǡ         ܸ ൌ  ǡ  ‫      ݎ‬௥  ݇ Ǥ ݇ ǯǤȋʹȌ    Ǥȋ͵Ȍ     ǡ    ͳǤȋͶȌ   ɿ
















Ǥͳ
九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(15/27)
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 an answer sheet for each question.

ȏʹȐ Ǥʹǡ     ܸ଴ǡ ܴǡ ǡ  ǡ   
  Ǥǡǡ 
݈ǡܽǡ݊ǡ Ǥ ǡ݈ ‫ܽ ب‬ǡ Ǥ ߤ଴ ǤȋͳȌ      Ǥ ʹȋȌ          ǡ     Ǥ  
 ǤȋʹȌ Ǧ   Ǥȋ͵Ȍ               ‫ ݐ‬ൌ Ͳǡ   ‫ܫ‬ሺ‫ݐ‬ሻ ൌ‫ܫ‬଴ ݁ ିఉ௧ ሺ‫ ݐ‬൒ Ͳሻ  ȋ ǤʹȋȌȌǤ   
  ‫ݐ‬ǤǡߚǤȋͶȌ  ȋ͵Ȍǡ    ‫ݐ‬ ‫  ݎ‬ǤȋͷȌ    ȋ͵Ȍǡ        ‫ݐ‬ ‫ ݎ‬ൌ ܽ  Ǥǡ  Ǥȋ͸Ȍ  ȋ͵Ȍǡ  
‫ݐ‬Ǥǡ ‫ ݐ‬ൌ Ͳ‫ ݐ‬ൌ λǡ  ǤȋȌȋȌǤʹ

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(16/27)
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 an answer sheet for each question.

E. 【アルゴリズム／プログラミング (Algorithms and programming) 分野】
次の各問い（【問 1】【問 2】）に答えよ．解答用紙の問題番号欄に解答した問題番号を記入すること．
【問 1】図 1 は Python 言語で書かれた文字列照合のプログラムである．次の問いに答えよ．

(1) 関数 compute prefix function(P) をパターン P = "abcab"に対して実行した時，返り値 pi に含まれる要素を答えよ．

(2) 関数 kmp matcher(T, P) をテキスト T = "abccabcabcab"，パターン P = "abcab"に対して実行した時，この関数内の print(q) が出力する結果を示せ．
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def kmp_matcher(T, P):
ret = []
n = len(T)m = len(P)pi = compute_prefix_function(P)q = 0
for i in range(0, n): # i = 0,...,n-1
while q > 0 and P[q] != T[i]:q = pi[q - 1]
if P[q] == T[i]:q = q + 1
if q == m:ret.append(i - (q - 1))
q = pi[q - 1]
print(q)return ret
def compute_prefix_function(P):m = len(P)pi = [0] * mfor q in range(1, len(P)):
k = pi[q - 1]
while k > 0 and P[k] != P[q]:k = pi[k - 1]
if P[k] == P[q]:k = k + 1
pi[q] = kreturn pi

図1

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(17/27)
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 an answer sheet for each question.

【問 2】 (1) テーブル Student(uid, name, dept), Subject(sid, name, credit), Regist(uid,sid, score) がある．ただし，テーブル Student は学生の ID (uid) と名前 (name)，所属 (dept) を，Subject は科目の ID (sid) と名前 (name)，単位数 (credit) を，Regist
はどの学生 (uid) がどの科目 (sid) を受講し，その得点 (score) が何点だったかを管理しているものとする．以下の各問いに答えよ．

(a) 単位数が 3 である科目の科目 ID と科目名の一覧を求める SQL 文を書け．
(b) sid=0001 である科目を受講している学生の ID と名前の一覧を求める SQL 文を書け．

(c) sid=0001 である科目を受講している学生の所属を重複なく求める SQL 文を書け．
(d) sid=0001 である科目の平均点を求める SQL 文を書け．
(e) sid=0001 である科目に対して，その科目の平均点以下の点数を取った学生の IDと名前の一覧を求める SQL 文を書け．

(2) 次の各問いに答えよ．
(a) S を任意の関係とし，その属性集合を X, Y とする．このとき，S の関数従属性
X → Y を定義せよ．
(b) 下記の関係 R の非自明で完全な関数従属性 X → Y で，X は Student またはSubject を含み，X の要素数は 2 または 1，Y の要素数は 1 となるものを全て列挙せよ．ここで，関数従属性 X → Y は Y ⊆ X を満たす時，自明であると言い，X   X となる任意の X  に対して X  → Y の時，完全であると言う．
R
Student | Subject | Department | Instructor | Faculty-----------------------------------------------------------001| LA| Engineering | Suzuki| Comp. Center
001| AI| Engineering | Lee| Comp. Center
001| DB| Engineering | Lee| Comp. Center002| LA| Science| Suzuki| Comp. Center
002| DB| Science| Tanaka| Engineering003| AI| Agriculture | Lee| Comp. Center
003| DB| Agriculture | Tanaka| Engineering004| LA| Science| Satoh| Science
005| AI| Engineering | Lee| Comp. Center(c) Lee 先生が Comp. Center から Engineering に Faculty を異動したことに伴い，関係 R は以下のように修正された．(b) で列挙した関数従属性のうち，この修正で九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(18/27)
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 an answer sheet for each question.

R の関数従属性ではなくなったものを全て列挙せよ．
R
Student | Subject | Department | Instructor | Faculty-----------------------------------------------------------001| LA| Engineering | Suzuki| Comp. Center
001| AI| Engineering | Lee| Engineering001| DB| Engineering | Lee| Engineering002| LA| Science| Suzuki| Comp. Center
002| DB| Science| Tanaka| Engineering003| AI| Agriculture | Lee| Engineering003| DB| Agriculture | Tanaka| Engineering004| LA| Science| Satoh| Science
005| AI| Engineering | Lee| Engineering(d) 第３正規形を満たすように (c) の関係 R を複数の関係に分割せよ．

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(19/27)
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 an answer sheet for each question.

Answer the following questions (【Q1】【Q2】) and write the number of the question on theanswer sheet.
【Q1】 Figure 1 shows a program written in Python which implements string matching. Answer

the following questions.
(1) When function compute prefix function(P) is executed for the pattern P = "abcab",
answer the elements of the return value pi．
(2) When function kmp matcher(T, P) is executed for the text T = "abccabcabcab"
and the pattern P = "abcab", show the outputs of print(q) in the function．
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

def kmp_matcher(T, P):
ret = []
n = len(T)m = len(P)pi = compute_prefix_function(P)q = 0
for i in range(0, n): # i = 0,...,n-1
while q > 0 and P[q] != T[i]:q = pi[q - 1]
if P[q] == T[i]:q = q + 1
if q == m:ret.append(i - (q - 1))
q = pi[q - 1]
print(q)return ret
def compute_prefix_function(P):m = len(P)pi = [0] * mfor q in range(1, len(P)):
k = pi[q - 1]
while k > 0 and P[k] != P[q]:k = pi[k - 1]
if P[k] == P[q]:k = k + 1
pi[q] = kreturn pi

Figure 1

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(20/27)
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 an answer sheet for each question.

【Q2】 (1) There are three tables: Student(uid, name, dept), Subject(sid, name, credit),

and Regist(uid, sid, score), where Student manages student IDs (uid), theirnames (name), and their departments (dept), Subject manages subject IDs (sid),
their names (name), and their credits (credit), and Regist manages which student(uid) takes which class (sid) with the score of the student (score). Answer thefollowing questions.
(a) Write an SQL statement to list the subject IDs and the names of the subjects
whose credits are 3.
(b) Write an SQL statement to list the student IDs and the names of the students
who take the subject sid=0001.
(c) Write an SQL statement to list the departments, without duplicates, of thestudents who take the subject sid=0001.
(d) Write an SQL statement to calculate the average score of the subject sid=0001.
(e) Write an SQL statement to list the student IDs and the names of the students
whose scores of the subject sid=0001 are equal to or less than the average scoreof the subject.
(2) Answer the following questions.
(a) Let S be a relation, and X and Y be its attribute sets. Deﬁne the functional
dependency X → Y in S.
(b) Enumerate all the non-trivial full functional dependencies X → Y in R below,
satisfying X contains either Student or Subject, the number of elements in X
is 1 or 2, and the number of elements in Y is 1.
Here a functional dependency X → Y is said to be trivial if Y ⊆ X, and said
to be full if X  → Y for any X   X.
R
Student | Subject | Department | Instructor | Faculty-----------------------------------------------------------001| LA| Engineering | Suzuki| Comp. Center
001| AI| Engineering | Lee| Comp. Center
001| DB| Engineering | Lee| Comp. Center002| LA| Science| Suzuki| Comp. Center
002| DB| Science| Tanaka| Engineering

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(21/27)
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 an answer sheet for each question.

003
003
004
005

| AI
| DB
| LA
| AI

| Agriculture | Lee| Agriculture | Tanaka| Science| Satoh| Engineering | Lee| Comp. Center| Engineering| Science| Comp. Center(c) According to Prof. Lee’s transfer from Comp. Center to Faculty of Engineering,R has been modiﬁed as follows. Enumerate all functional dependencies fromthose enumerated in (b) such that the enumerated functional dependencies are
no longer functional dependencies in R after this modiﬁcation.
R
Student | Subject | Department | Instructor | Faculty-----------------------------------------------------------001| LA| Engineering | Suzuki| Comp. Center
001| AI| Engineering | Lee| Engineering001| DB| Engineering | Lee| Engineering002| LA| Science| Suzuki| Comp. Center
002| DB| Science| Tanaka| Engineering003| AI| Agriculture | Lee| Engineering003| DB| Agriculture | Tanaka| Engineering004| LA| Science| Satoh| Science
005| AI| Engineering | Lee| Engineering(d) Decompose R in (c) into relations which are in the third normal form.

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(22/27)
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 an answer sheet for each question.

F. 【計算機アーキテクチャ(Computer architecture) 分野】
次の各問い (【問 1】〜【問 3】) に答えよ．解答用紙の問題番号欄に解答した問題番号を記入すること．
【問 1】下図の様にいくつかの論理ゲートと部分回路 H から構成される論理回路の出力の論理関
数 F (a, b, c, d) が以下の様な真理値表で表される時，部分回路 H の論理関数 H(s, t, u, v)の最簡積和形を示せ．ただし，論理関数の最簡積和形とはその論理関数を表す積和形論
理式のうち，積項数が最小のものを指す．積項数が等しい積和形論理式が複数ある場合にはそのなかでリテラル数が最小のものを指す．

a
b
c
d

s
t H
u
v

F

a

b

c

d

F

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
0
0
0
0
0
0
1
1
0
0
0
1
0
1
1

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(23/27)
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 an answer sheet for each question.

【問 2】パイプライン式データパスを有するマイクロプロセッサについて考える．以下の式で示すように，プログラム実行時間 ET は，プログラム実行のために処理される総命令数 IC ，
クロックサイクル当り実行命令数 IPC ，ならびに，動作周波数 F ，の 3 つのパラメータを用いて表現できる．

ET =

IC
IPC × F以下の各問いに答えよ．

(1) 命令発行幅が 1 のインオーダマイクロプロセッサを考える．シングルサイクル・デー
タパス方式（1 命令の実行を 1 クロックサイクルで処理する方式）と比較した場合，
パイプライン式データパスの実装が IC ，IPC ，F に与える影響をそれぞれ説明せよ．なお，各パラメータにおいて影響がない場合は「影響なし」と答えること．

(2) このパイプライン式データパスにおいて命令発行幅を 2 へ増加し，インオーダ命令
実行のスーパスカラ方式へと拡張した（依存関係のない命令を最大で 2 個同時に実行できる）．この拡張が IC ，IPC ，F に与える影響をそれぞれ説明せよ．なお，各パラメータにおいて影響がない場合は「影響なし」と答えること．

(3) 命令発行幅は 4 と仮定する．このパイプラインで達成できる IPC の上限を答えよ．

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(24/27)
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 an answer sheet for each question.

【問 3】コンピュータのメモリシステムについて考える．マイクロプロセッサにダイレクトマッ
プ・キャッシュが搭載されているものとする．ワードアドレッシング方式を採用しており，ワードサイズは 4 バイト，キャッシュ・サイズは 16 バイト，ブロックサイズは 4 バ
イト，アドレス長は 4 ビットである．キャッシュの初期状態は空であったが，これまでに 1101 ⇒ 1010 ⇒ 1111 ⇒ 1101 のワードアドレス（2 進表現）に対してメモリアクセ
1 〜○
5 が順次発生したとする．
スが順次発生している．このとき，メモリアクセス○

メモリアクセス

ワードアドレス（2 進表現）

1
○
2
○
3
○
4
○
5
○

1010
1001
1000
0011
1111

以下の各問いに答えよ．
1 〜○
5 のうち，キャッシュ・ヒットとなるメモリアクセスをすべて(1) メモリアクセス○

答えよ．該当するメモリアクセスがない場合は「該当なし」と答えること．
1 〜○
5 のうち，初期参照ミスとなるメモリアクセスをすべて答えよ．
(2) メモリアクセス○

該当するメモリアクセスがない場合は「該当なし」と答えること．

(3) 競合ミスを削減するためにはこのキャッシュをどのように改良すれば良いか説明せよ．また，改良によるデメリットがあればあわせて説明せよ．

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(25/27)
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 an answer sheet for each question.

Answer the following questions (【Q1】〜【Q3】) and write the number of the question on
the answer sheet.
【Q1】 Suppose a logic circuit in the below ﬁgure is composed of several logic gates and subcir-

cuit H. The logic function of the output F (a, b, c, d) is deﬁned by the truthtable shown
below. Show the minimum sum of products form of H(s, t, u, v). The minimum sumof products form of a logic function means that having the smallest number of productterms among those which represent the function. If there are two or more forms having
the smallest number of product terms, forms having the smallest number of literals arechoosen as the minimum forms.

a
b
c
d

s
t H
u
v

F

a

b

c

d

F

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
0
0
0
0
0
0
1
1
0
0
0
1
0
1
1

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(26/27)
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 an answer sheet for each question.

【Q2】 Let us consider a microprocessor having a pipelined datapath. Program execution time

ET can be represented by using the three parameters, instruction count required tocomplete the whole program execution IC, the number of executed instructions per
clock cycle IPC, and clock frequency F, as shown in the following equation.
ET =IC
IPC × F

Answer the following questions.
(1) Consider an in-order microprocessor whose instruction issue width is one. Explain
the eﬀects of pipelined datapath implementation on IC, IPC, and F, compared to asingle-cycle datapath implementation where each instruction is executed in a single
clock cycle, respectively. If there are no eﬀects on each parameter, answer “noeﬀects.”(2) We extend the pipelined datapath by increasing the instruction issue width from
one to two that forms an in-order superscalar microprocessor, i.e., at most two
independent instructions can be executed in parallel. Explain the eﬀects of thisextension on IC, IPC, and F, respectively. If there are no eﬀects on each parameter,answer “no eﬀects.”(3) Assume that the instruction issue width is four. Answer the upper limit of IPC thatcan be achieved by the pipelined datapath.

九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和４年８月２９日）

専 門 科 目 (Specialized subjects)(27/27)
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 an answer sheet for each question.

【Q3】 Consider computer memory systems. Assume a direct-mapped cache memory imple-

mented in a microprocessor chip. The microprocessor uses word addressing, the word
size is 4 bytes, the cache size is 16 bytes, the block size is 4 bytes, and the address width
is 4 bits. Suppose the cache was initially empty, and the memory access sequence forthe following word addresses (represented in the binary numeral system) has occurred.
1101 ⇒ 1010 ⇒ 1111 ⇒ 1101
1 - ○)
5
Then we have the following ﬁve memory accesses (memory access ○consecutively.

Memory access

Word address (the binary numeral system)

1
○
2
○
3
○
4
○
5
○

1010
1001
1000
0011
1111

Answer the following questions.
1 - ○5 that cause a cache hit. If there is(1) Find all of the memory accesses among ○no corresponding memory access, answer “not applicable.”
1 - ○5 that cause a compulsory miss. If(2) Find all of the memory accesses among ○there is no corresponding memory access, answer “not applicable.”(3) Explain how to modify this cache memory to reduce the conﬂict miss. Also, if there
are any demerits to the modiﬁcation, explain them.