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

情報理工学専攻

令和３年度入学試験問題【令和２年１２月５日（土）、６日（日）】令和３年度

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

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

数 学 (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
Calculus
Diﬀerential equation
Vector analysis
Complex function theory
Probability and statistics

page
2
3
4
5
6
7

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

Fill in the designated blanks at the top of each answer sheet with the department name, theselected ﬁeld number (mark with a circle), 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) 分野】
n × m 実行列 A ∈ Rn×m の第 j 列 (j = 1, 2, . . . , m) を aj ∈ Rn とする．各部分集合 J ⊆{1, 2, . . . , m} について，その要素数を |J| で表し，aj (j ∈ J) を j に関する昇順で左から並べて得られる A の部分行列を A[J] ∈ Rn×|J| で表す．このとき，以下の問いに答えよ．

(1) 以下の行列 A に対し，{ aj | j ∈ J } が線形独立であるような部分集合 J ⊆ {1, 2, 3, 4, 5, 6}
をすべて求めよ．


1
0 0 −2 0
0


A= 0
1 0 −2 −3 −5 
−2 −2 0 4
60(2) (1) の行列 A に対し，rank(A[J]) < |J| を満たす部分集合 J ⊆ {1, 2, 3, 4, 5, 6} であって，J の任意の真部分集合 I ⊊ J について rank(A[I]) = |I| が成り立つものをすべて求めよ．
ただし，空集合 ∅ に対しては rank(A[∅]) = 0 と定義する．

(3) 一般の A ∈ Rn×m について，I ⊆ J ⊆ {1, 2, . . . , m} かつ rank(A[J]) = |J| のとき，rank(A[I]) = |I| が成り立つことを示せ．
For an n × m real matrix A ∈ Rn×m , let aj ∈ Rn (j = 1, 2, . . . , m) be the j-th column of
A. For each subset J ⊆ {1, 2, . . . , m}, let A[J] ∈ Rn×|J| denote the submatrix of A obtainedby arranging aj (j ∈ J) in the ascending order of j, where |J| denotes the cardinality of J.
Answer the following questions.
(1) For the following matrix A, ﬁnd all subsets J ⊆ {1, 2, 3, 4, 5, 6} such that { aj | j ∈ J }is linearly independent:
10 0 −2 0
0


A= 0
1 0 −2 −3 −5  .
−2 −2 0 4
6
0(2) For the matrix A in (1), ﬁnd all subsets J ⊆ {1, 2, 3, 4, 5, 6} such that rank(A[J]) < |J|and rank(A[I]) = |I| for any proper subset I ⊊ J, where rank(A[∅]) = 0 for the empty
set ∅.
(3) Prove for any A ∈ Rn×m that, if I ⊆ J ⊆ {1, 2, . . . , m} and rank(A[J]) = |J|, thenrank(A[I]) = |I|.

令和３年度

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

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

数 学 (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. 【微分積分 (Calculus) 分野】

R2 上の関数( x2 + y 2 )f (x, y) = (x + y) exp −2について次の各問いに答えよ．
(1) f の停留点を全て求めよ．
(2) f の極大点と極小点を全て求めよ．
(3) f の最大値または最小値が存在する場合，それらを求めよ．
For the function( x2 + y 2 )f (x, y) = (x + y) exp −2
over R2 , answer the following questions.
(1) Find all the stationary points of f .
(2) Find all the local maximum and the local minimum points of f .
(3) Find the maximum and the minimum values of f , if they exist, respectively.

令和３年度

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

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

数 学 (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. 【微分方程式 (Diﬀerential equation) 分野】

次の微分方程式の一般解を求めよ．

dy x2 + 6y 2
(1)
=
dx
4xy
(2)

dy
= e2x+y+1 − 1dxFind general solutions to the following diﬀerential equations.
(1)

dy x2 + 6y 2
=
dx
4xy

(2)

dy
= e2x+y+1 − 1dx令和３年度

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

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

数 学 (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. 【ベクトル解析 (Vector analysis) 分野】
直交座標系において，x，y ，z 軸方向の単位ベクトルをそれぞれ i，j ，k とする．次の各問に答えよ．

(1) 3 点 (2, −6, 2), (1, −10, −1) および (−1, 2, 3) が決定する平面と点 (2, −2, −2) との距離
を求めよ.

(

)
xy
y2
(2) ベクトル場 F を F = −i + (z − x) j + (x + y) k とする．曲線 C: x =, y = −z
4
8
(
)
∫
9
に沿って, (0, 0, 0) から, 6, −6 までの線積分
F × dr を計算せよ.
2
C
The unit vectors on x, y and z axes of Cartesian coordinates are denoted by i, j and k,
respectively. Answer the following questions.
(1) Find the distance from the point (2, −2, −2) to the plane determined by the points(2, −6, 2), (1, −10, −1) and (−1, 2, 3).
()xy(2) Let the vector ﬁeld F = −i + (z − x) j + (x + y) k. Evaluate the line integral
4
(
)
∫
9
y2
F × dr along the curve C: x =, y = −z, from (0, 0, 0) to, 6, −6 .
82C令和３年度

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

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

数 学 (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. 【複素関数論 (Complex function theory) 分野】
次の各問に答えよ．

1を z = 0 でローラン展開せよ．
z(z − 2)21
(2) 複素関数 g(z) = z sin
を z = −2 でローラン展開し，級数が収束する領域を示せ．
z+2
次に，z = −2 における留数を求めよ．
(1) 複素関数 f (z) =Answer the following questions.
1in a Laurent series about z = 0.
z(z − 2)21
(2) Expand the complex function g(z) = z sin
in a Laurent series about z = −2 andz+2give the region of convergence of the series. Then, ﬁnd the residue at z = −2.

(1) Expand the complex function f (z) =令和３年度

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

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

数 学 (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. 【確率・統計 (Probability and statistics) 分野】
実数 p は 0 < p < 1 を満たすものとする．確率変数 X と Y は独立に同一の確率関数

f (k) ={
p(k = 1)

1 − p (k = −1)に従うものとする．Z = XY として，以下の各問に答えよ．

(1) 期待値 E[Z] を求めよ．
(2) X と Z の共分散 E[(X − E[X])(Z − E[Z])] を求めよ．
(3) X と Z が独立となる p を求めよ．求めた p に対し，Y と Z も独立であることを示せ．
(4) (3) で求めた p に対し，確率 Pr[X + Y + Z ≤ 2] を求めよ．

Let p be a real satisfying 0 < p < 1. Let X and Y be independent random variables which
respectively follow the identical probability function{p(k = 1),f (k) =
1 − p (k = −1).
Let Z = XY , and answer the following questions.
(1) Find the expectation E[Z].
(2) Find the covariance E[(X − E[X])(Z − E[Z])] between X and Z.
(3) Find p such that X and Z are independent. Prove that Y and Z are also independent
for the same p.
(4) Find the probability Pr[X + Y + Z ≤ 2] for p obtained in (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. 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
10
14
20
26

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 so clearly on the sheet.
6. 解答は，日本語，英語のいずれかで記入すること．
Your answers must be written in Japanese or English.

令和３年度

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

専 門 科 目 (Specialized subjects)(2/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. 【電気回路 (Circuit theory) 分野】【問 1】〜【問 4】から2 問を選び，解答用紙の問題番号欄に解答した問題番号を記入せよ．

√【問 1√】 図 1 に示す回路において，C = 3 F，
L = 63 H，電源の角周波数 ω = 2 rad/s，端子間電圧 V と電流 I の位相差は arg( VI ) = − π6 rad
であり，回路は定常状態にあるとする．以下の問いに答えよ．









(1) R の値を求めよ．
(2) 電流 I の時間関数が i(t) = sin(2t + π6 ) A であり，これに対応するフェーザ電流を I =πej 6 A と表すとき，フェーザ電圧 V を求め，その時間関数 v(t) を答えよ．

図1



【問 2】 図 2 の回路について，以下の問いに答えよ．ただし，図 2(a) と図 2(b) は等価である．

(1) 図 2(b) のインピーダンス Z1 ，Z2 ，Z3 を求めよ．
(2) 図 2(b) において，端子対 1-1’ から右側を見たときのインピーダンス ZR および左側を見たときのインピーダンス ZL を記号 Z0 ，
Z1 ，Z2 ，Z3 を用いずに表せ．ただし，インピーダンス Z0 = R + jX である．
(3) 図 2(b) の Z0 において，R も X も可変であるとき，Z0 における消費電力を最大とする
R および X を求めよ．











 










 

 

図2





令和３年度

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

専 門 科 目 (Specialized subjects)(3/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】 図 3 の回路について，以下の問いに答えよ．ただし，電源の角周波数を ω とする．

(1) 図 3(b) が図 3(a) の端子対 1-1’ の左側の 2 端子回路と等価なとき，電流源 J0 とアドミタ
ンス Y0 を求めよ．

(2) 図 3(a) の電流 I を求めよ．
1

1

ܴ

‫ܫ‬

‫ܧ‬

ܴ
‫ܬ‬

ܴ

‫ܮ‬

‫ܬ‬଴

ܻ଴

‫ܧ‬
(a)

1’

(b)

1’

図3

【問 4】 図 4 の回路について，以下の問いに答えよ．ただし，e(t) = 50 sin t V とし，スイッチ S を閉じる前の回路は定常状態にあるとする．

(1) t = 0 でスイッチ S を閉じた直後の電流 i(+0) を求めよ．
(2) t > 0 における電流 i(t) を求めよ．






図4

令和３年度

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

専 門 科 目 (Specialized subjects)(4/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 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√C = 3 F, L = 63 H, the angular frequency of thesource ω = 2 rad/s, the phase diﬀerence arg( VI ) =− π6 rad, and the circuit is in steady state. Answer
the following questions.

(1) Find the resistance R.







(2) The current I in the time domain expressionis i(t) = sin(2t + π6 ) A and the correspondπing phasor is I = ej 6 A. Find the phasor V
and the corresponding time domain expression v(t).

【Q2】 Consider the circuit shown in Fig. 2. Here, thecircuit shown in Fig. 2(b) is equivalent to Fig. 2(a).
Answer the following questions.

Fig. 1









(1) Find the impedance Z1 , Z2 , and Z3 of Fig. 2(b).
(2) In Fig. 2(b), express ZR and ZL without using
symbols Z0 , Z1 , Z2 , and Z3 , where ZR is deﬁned
as the impedance measured rightward from theterminals 1-1’, ZL is deﬁned as the impedance
measured leftward from the terminals 1-1’, andthe impedance Z0 = R + jX.
(3) When R and X are variable, ﬁnd the value of R
and X which maximize the power consumption
at the impedance Z0 .





 












 

 



Fig. 2令和３年度

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

専 門 科 目 (Specialized subjects)(5/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.

【Q3】 Consider the circuit shown in Fig. 3, where the sources have the angular frequency ω.

Answer the following questions.
(1) Find the current source J0 and the admittance Y0 when the circuit in Fig. 3(b) is equivalent to the circuit seen from the terminals 1-1’ to the left in Fig. 3(a) .
(2) Find the current I.
1

1

ܴ

‫ܫ‬

‫ܧ‬

ܴ
‫ܬ‬

ܴ

‫ܮ‬

‫ܬ‬଴

ܻ଴

‫ܧ‬
(a)

1’

(b)

1’

Fig. 3【Q4】 Consider the circuit shown in Fig. 4, wheree(t) = 50 sin t V and the circuit is in steady state
before the switch S is closed.






(1) Find the current i(+0) just after the switch S isclosed at t = 0.
(2) Find the current i(t) for t > 0.

Fig. 4令和３年度

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

専 門 科 目 (Specialized subjects)(6/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.

B. 【情報理論 (Information theory) 分野】
次の各問い（【問 1】【問 2】）に答えよ．
【問 1】入力アルファベットと出力アルファベットがともに {1, 2, 3, 4} である無記憶な通信路

W (y|x) の通信路行列が⎛⎞0.5 0.5 00⎜ 0 0.5 0.5 0 ⎟
⎜
⎟
⎜
⎟
⎝0
0 0.5 0.5⎠
0.5 0
0 0.5

で与えられているとする．ただし，(i, j) 成分は W (j|i) を表す．この通信路の通信路容量を求めよ．また，それを達成する入力分布を全て求めよ．

令和３年度

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

専 門 科 目 (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】定常無記憶情報源 X1 X2 · · · を考える．この情報源のアルファベットを有限集合 X とし，各 Xi は確率分布 p(x) に従うものとする．任意に固定された  > 0 に対し，系列(x1 , x2 , . . . , xn ) ∈ X n が2−n(H(X1 )+) ≤ p(x1 , x2 , . . . , xn ) ≤ 2−n(H(X1 )−)を満たすとき，この系列を p(x) に関する典型系列であると言う．ここで，H(X1 ) は X1のエントロピーを表し，p(x1 , x2 , . . . , xn ) は同時確率分布を表す．全ての典型系列からな(n)る集合を Aと表記する．次の各問いに答えよ．ただし，X = {0, 1}，p(0) = 1 − α，p(1) = α とする．ここで α ∈ (0, 1) は定数である．
(1) (x1 , x2 , . . . , x10 ) = (0, 1, 1, 0, 0, 0, 0, 1, 0, 0) に対し，p(x1 , x2 , . . . , x10 ) を求めよ．
(2) i = 1, 2, . . . , n に対する H(Xi ) および H(X1 , X2 , . . . , Xn ) を求めよ．
(3) x = (x1 , x2 , . . . , xn ) に対し，S(x) = ni=1 xi とおく．α = 0.2, n = 200,  = 0.01 と(n)

する．A に属する系列 x に対する S(x) の範囲を求めよ．

令和３年度

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

専 門 科 目 (Specialized subjects)(8/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】 Suppose that the channel matrix of a memoryless channel W (y|x) with the input andoutput alphabets {1, 2, 3, 4} is given by⎛⎞
0.5 0.5 00⎜ 0 0.5 0.5 0 ⎟
⎜
⎟
⎜
⎟,
⎝0
0 0.5 0.5⎠
0.5 0
0 0.5
where the (i, j) component denotes W (j|i). Find the channel capacity of the channel
and all the input distributions which achieve the capacity.

令和３年度

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

専 門 科 目 (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】 Consider a stationary memoryless source X1 X2 · · · . Let the alphabet of this source

be a ﬁnite set X and suppose each Xi follows a probability distribution p(x). For an
arbitrarily ﬁxed constant  > 0, a sequence (x1 , x2 , . . . , xn ) ∈ X n is said to be a typicalsequence with respect to p(x), if it satisﬁes2−n(H(X1 )+) ≤ p(x1 , x2 , . . . , xn ) ≤ 2−n(H(X1 )−) ,where H(X1 ) denotes the entropy of X1 and p(x1 , x2 , . . . , xn ) denotes the joint prob(n)ability distribution. The set of all typical sequences is denoted by A . Answer thefollowing questions. Here, let X = {0, 1}, p(0) = 1 − α, and p(1) = α, where α ∈ (0, 1)
is a constant.
(1) Find p(x1 , x2 , . . . , x10 ) for (x1 , x2 , . . . , x10 ) = (0, 1, 1, 0, 0, 0, 0, 1, 0, 0).
(2) Find H(Xi ) for i = 1, 2, . . . , n and H(X1 , X2 , . . . , Xn ).
(3) Let S(x) = ni=1 xi for x = (x1 , x2 , . . . , xn ). Put α = 0.2, n = 200, and  = 0.01.
(n)Find the range of S(x) for sequences x belonging to A .

令和３年度

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

専 門 科 目 (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) 分野】
次の各問い（【問 1】【問 2】）に答えよ．
【問 1】状態数 2 の決定性有限オートマトンを考える．決定性有限オートマトン M = (K, Σ, δ, q0 , F )において，K = {q0 , q1 }, Σ = {a, b}, F = {q0 } とする．ただし，K, Σ, δ, q0 , F はそれ
ぞれ M の状態集合，アルファベット，遷移関数，初期状態，最終状態の集合を表し，aと b は文字である．なお δ(p, x) = r (p, r ∈ K, x ∈ Σ) は，M が文字 x を読むことで状
態 p から状態 r に移ることを表す．M によって受理される言語を L(M ) で表す．

Σ 上の正規表現 e(a, b) が表す言語を，e(a, b) で表す．次の各問いに答えよ．

図 1: δ(q0 , a) = q0 , δ(q0 , b) = q1 である 4 種類のオートマトン M(1) 図 1 は，δ(q0 , a) = q0 , δ(q0 , b) = q1 である 4 種類の δ に対応する M の状態遷移図である．図 1 の各 M について L(M ) に含まれる文字列を説明せよ．

(2) δ(q0 , a) = δ(q0 , b) = q1 のとき，可能な M の状態遷移図を図 1 にならって全て与えよ．さらに，各 M について L(M ) に含まれる文字列を説明せよ．

(3) 言語 L = e(a, b) について，e(b, a) を L の交換言語と呼ぶ．たとえば，L0 が文
字 a を偶数個含む文字列から構成される言語であるとき，L0 の交換言語は文字 b を偶数個含む文字列から構成される言語である．

(1) と (2) とは異なる δ に対応する各 M に対し，(1) あるいは (2) の言語の交換言語とならない L(M ) に含まれる文字列を説明せよ．

令和３年度

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

専 門 科 目 (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.

【問 2】文脈自由文法を４つ組 (N, Σ, P, S) で表す．ただし，N ，Σ，P ，S をそれぞれ非終端記号の集合，終端記号の集合，生成規則の集合，開始記号とする．Σ 上の文字列 w と終端
記号 x ∈ Σ に対して，|w|x を w 中の x の出現回数とする．以下の各問いに答えよ．

(A) 以下に示す言語 Li (i = 1, 2, 3) を導出する文脈自由文法 (Ni , Σi , Pi , S) の生成規則の集合 Pi を与えよ．

(1) L1 = {w ∈ {a, b}∗ | |w|a ≥ 3}．ただし Σ1 = {a, b} である．答えには N1 = {S, X}
を用いよ.

(2) L2 = {w ∈ {a, b}∗ | |w|a ≥ 2|w|b }．ただし Σ2 = {a, b} である．答えには
N2 = {S} を用いよ.
(3) L3 = {ai bj ck | i, j, k ≥ 0 かつ (2i = j または 3j = k)}．ただし Σ3 = {a, b, c} である．答えには N3 = {S, V, X, Y, Z} を用いよ.

(B) 以下に示す言語 L4 , L5 は文脈自由言語であるか否か．証明せよ．
(4) L4 = ∅．
(5) 有限個の有限長文字列から構成される空でない任意の言語 L5 ．

令和３年度

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

専 門 科 目 (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 with 2 states. For a deterministic ﬁnite au-

tomaton M = (K, Σ, δ, q0 , F ), we deﬁne K = {q0 , q1 }, Σ = {a, b}, F = {q0 }, whereK, Σ, δ, q0 , and F represent the set of states, the alphabet, the transition function, theinitial state, and the set of ﬁnal states of M , respectively. Here, a and b are characters.
By δ(p, x) = r (p, r ∈ K, x ∈ Σ), we represent that M reads character x, and transits
from state p to state r. We denote by L(M ) the language that is accepted by M .
We denote by e(a, b) the language represented by a regular expression e(a, b) over Σ.
Answer the following questions.

Figure 1: Four diﬀerent automata M such that δ(q0 , a) = q0 and δ(q0 , b) = q1 .
(1) Figure 1 shows four diﬀerent automata M such that δ(q0 , a) = q0 and δ(q0 , b) = q1 .
For each M in Figure 1, describe the strings in the language L(M ).
(2) Let δ(q0 , a) = δ(q0 , b) = q1 . Give the state transition diagrams of possible ﬁnitestate automata M in a similar way as in Figure 1. In addition, for each M , describe
the strings in the language L(M ).
(3) For language L = e(a, b), we call e(b, a) the ﬂipped language of L. For instance,
let L0 be the language which consists of strings that contain an even number of a’s.
Then the ﬂipped language of L0 is the language which consists of strings that containan even number of b’s.
For each M with δ which is diﬀerent from those in (1) and (2), describe the stringsin the language L(M ) which is not the ﬂipped language of a language in (1) or (2).

令和３年度

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

専 門 科 目 (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】 We represent a context-free grammar by a quartet (N, Σ, P, S), where N , Σ, P , andS represent the set of non-terminal symbols, the set of terminal symbols, the set of
productions, and the start symbol, respectively. For a string over Σ and a terminal
symbol x ∈ Σ, let |w|x denote the number of occurrences of x in w. Answer thefollowing questions.
(A) For the following languages Li (i = 1, 2, 3), give a set Pi of production rules of acontext-free grammar (Ni , Σi , Pi , S) which generates Li .
(1) L1 = {w ∈ {a, b}∗ | |w|a ≥ 3}, where Σ1 = {a, b}. Use N1 = {S, X} in youranswer.
(2) L2 = {w ∈ {a, b}∗ | |w|a ≥ 2|w|b }, where Σ2 = {a, b}. Use N2 = {S} in youranswer.
(3) L3 = {ai bj ck | i, j, k ≥ 0 and (2i = j or 3j = k)}, where Σ3 = {a, b, c}. Use
N3 = {S, V, X, Y, Z} in your answer.
(B) Prove whether each of the languages L4 and L5 is a context-free language, or not.
(4) L4 = ∅．
(5) Any non-empty language L5 which consists of a ﬁnite number of ﬁnite-length
strings.

令和３年度

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

専 門 科 目 (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 問を選び，解答用紙の問題番号欄に解答した問題番号を記入せよ．

࠙ၥ㸯ࠚ(1) ㄏ㟁⋡ ߝ଴ ࡢ┿✵୰࡟࠶ࡿ↓㝈࡟㛗࠸༙ᚄ a ࡢ┤⥺ᑟ⥺ࡀ༢఩㛗ᙜࡓࡾ O ࡢ㟁Ⲵࢆ᭷ࡋ࡚࠸ࡿ㸬㟁⏺ศᕸࢆồࡵࡼ(2) ㄏ㟁⋡ ߝ଴ ࡢ┿✵୰࡟↓㝈࡟㛗࠸༙ᚄ a ࡢ  ᮏࡢ┤⥺ᑟ⥺ࡀ㛫㝸d (d >> a)࡛ᖹ⾜࡟タ⨨ࡉࢀ࡚࠸ࡿ㸬༢఩㛗ᙜࡓࡾࡢ㟼㟁ᐜ㔞ࢆồࡵࡼ㸬(3) ㄏ㟁⋡ ߝ ࡢ኱Ẽ୰࡟ᆅୖ h ࡢ㧗ࡉ࡟↓㝈࡟㛗࠸༙ᚄ a ࡢ┤⥺ᑟ⥺ࡀタ⨨ࡉࢀ࡚࠸ࡿ㸬༢఩㛗ᙜࡓࡾࡢ㟼㟁ᐜ㔞ࢆồࡵࡼ㸬(4) (3)࡛h = 5.0 m,a = 1.0 mm ࡢሙྜ࡟༢఩㛗ᙜࡓࡾࡢ㟼㟁ᐜ㔞ࢆồࡵࡼ㸬ࡓࡔࡋ㸪኱Ẽࡢㄏ㟁⋡ࡣ ߝ = 8.85 × 10-12 F/m ࡛࠶ࡾ㸪log ௘ 10 = 2.3 ࡜ࡍࡿ

令和３年度

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

専 門 科 目 (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.

࠙ၥ㸰ࠚ ᅗ 2 ࡢࡼ࠺࡞༙ᚄ a, b, c ࡢ 3 ಶࡢⷧ࠸ྠᚰ⌫Ẇᑟయ A㸪B㸪C ࡀ┿✵୰࡟࠶ࡿ㸬AB 㛫ࡣㄏ㟁⋡ ߝଵ 㸪ߝଶ ࡢㄏ㟁యࡀᕥྑ༙ศࡎࡘ‶ࡓࡉࢀ㸪BC 㛫ࡣㄏ㟁⋡ ߝଷ ࡢㄏ㟁య࡛ࡍ࡭࡚‶ࡓࡉࢀ࡚࠸ࡿ㸬┿✵୰ࡢㄏ㟁⋡ࢆ ߝ଴ ࡜ࡍࡿ㸬ḟࡢྛၥ࡟⟅࠼ࡼ㸬(1) ᑟయ B ࡟㟁Ⲵ Q ࢆ୚࠼ࡓሙྜ㸪ᅗ࡟♧ࡍ㡿ᇦ 1㸦ᑟయ A ࡜ᑟయ B 㛫ࡢᕥ༙ศ㸧㸪㡿ᇦ 2
㸦ᑟయ A ࡜ᑟయ B 㛫ࡢྑ༙ศ㸧㸪㡿ᇦ 3㸦ᑟయ B ࡜ C ࡢ㛫㸧㸪࠾ࡼࡧ㡿ᇦ 4㸦ᑟయ Cࡢእഃ㸧࡟࠾ࡅࡿྛ㟁⏺ࡢ኱ࡁࡉࢆồࡵࡼ㸬(2) ᑟయ B ࡢ㟼㟁ᐜ㔞ࢆồࡵࡼ㸬(3) ᑟయ B ࡛ࡣ࡞ࡃ㸪ᑟయ A ࡟㟁Ⲵ Q ࢆ୚࠼ࡓሙྜ㸪ᑟయ A ࡢ㡿ᇦ 1 ࡟᥋ࡍࡿ㒊ศ࡟ศᕸࡍࡿ㟁Ⲵ㔞 Q1㸪࠾ࡼࡧ㡿ᇦ 2 ࡟ศᕸࡍࡿ㟁Ⲵ㔞 Q2 ࢆồࡵࡼ㸬(4) (3)ࡢሙྜ㸪㡿ᇦ 1㸪㡿ᇦ 2㸪㡿ᇦ 3㸪࠾ࡼࡧ㡿ᇦ 4 ࡢྛ㟁⏺ࡢ኱ࡁࡉࢆồࡵࡼ㸬(5) ᑟయ A ࡢ㟼㟁ᐜ㔞ࢆồࡵࡼ㸬

ᅗ2令和３年度

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

専 門 科 目 (Specialized subjects)(16/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.

࠙ၥ㸱ࠚ ௨ୗࡢၥ࡟⟅࠼ࡼ㸬(1) ᅗ㸱(a)࡟♧ࡍࡼ࠺࡞㸪㛗ࡉ " ࡢ┤⥺ᑟ⥺ AB ࡟㟁ὶ I ࢆὶࡍ㸬ᑟ⥺࠿ࡽ㊥㞳 d ࡢⅬ P ࡟⏕ࡌࡿ☢⏺ H ࡟ࡘ࠸࡚⪃࠼ࡿ㸬ࡓࡔࡋ㸪㟁ὶࡣ B ࠿ࡽ A ࡢྥࡁ࡟ὶࡍࡶࡢ࡜ࡋ㸪Ⅼ P ࠿ࡽ AB ࡟ୗࢁࡋࡓᆶ⥺ࡀ AB ࡜஺ࢃࡿⅬࢆ O㸪҆PAO ࢆߠଵ 㸪҆PBO ࢆߠଶ ࡜ࡍࡿ㸬O ࠿ࡽ㊥㞳 s ࡢⅬ Q ࡟࠾ࡅࡿ㟁ὶ⣲∦ I ds ࡀⅬ P ࡟సࡿ☢⏺ dH ࡢྥࡁ࡜኱ࡁࡉࢆồࡵࡼ㸬ࡓࡔࡋ㸪҆AQP ࢆߠ࡜࠾ࡃ㸬(2) ๓ၥࡢ⤖ᯝࢆ⏝࠸࡚㸪ᅗ㸱(a)ࡢ BA ࢆὶࢀࡿ㟁ὶ I ࡀⅬ P ࡟సࡿ☢⏺ H ࡢྥࡁ࡜኱ࡁࡉࢆồࡵࡼ㸬(3) ḟ࡟ᅗ㸱(b)࡟♧ࡍᵝ࡟ᑟ⥺ AB ࡟ᖹ⾜࡟㸪ྠࡌࡃ㛗ࡉ " ࡢ┤⥺ᑟ⥺ CD ࢆ㛫㝸 d 㝸࡚࡚⨨ࡁ㸪B ࠿ࡽ A ࡢྥࡁ࡟㟁ὶ I1㸪D ࠿ࡽ C ࡢྥࡁ࡟㟁ὶ I2 ࢆࡑࢀࡒࢀὶࡍ㸬ᑟ⥺ CD ୖ
࡛Ⅼ D ࠿ࡽ㊥㞳 x ࡢⅬ P’࡟࠾ࡅࡿᚤᑠ༊㛫 dx ࡀཷࡅࡿຊ dF ࡢྥࡁ࡜኱ࡁࡉࢆồࡵࡼ㸬(4) (3)࡟࠾࠸࡚஧ᮏࡢᑟ⥺㛫࡟స⏝ࡍࡿຊ F ࡢྥࡁ࡜኱ࡁࡉࢆồࡵࡼ㸬

(a)

(b)
ᅗ㸱

令和３年度

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

専 門 科 目 (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ࠚ(1) In vacuum of permittivity ߝ଴ , there is an infinitely long straight wire of radius a that carries acharge O per unit length. Give the electric field distribution.
(2) In vacuum of permittivity ߝ଴ , there are two infinitely long straight wires of radius a placedparallel with a distance d (d >> a). Give the capacitance per unit length.
(3) In the air of permittivity ߝ , there is an infinitely long straight wire of radius a, which is locatedat a height h above the ground. Give the capacitance per unit length.
(4) In the case of (3), give the capacitance per unit length for h = 5.0 m, a = 1.0 mm, wherepermittivity of air ߝ = 8.85 × 10-12 F/m and log ௘ 10 = 2.3.

令和３年度

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

専 門 科 目 (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ࠚAs shown in Fig.2, three thin concentric spherical shell conductors A, B and C with radii a, b
and c are located in vacuum space. Dielectric with electric permittivity H1 is filled in the left half partof the area between the conductors A and B. Dielectric with electric permittivity H2 is filled in theright half part of the area. Dielectric with electric permittivity H3 is filled in the space between the
conductors B and C. Electric permittivity in vacuum is H0. Answer the following questions.

(1) When electric charge Q is applied to the conductor B, give the magnitude of electric fields of theregion 1 (the left half part of the area between the conductors A and B), the region 2 (the righthalf part of the area between the conductors A and B), the region 3 (the spherical shell between
B and C) and the region 4 (outside of the conductor C), respectively.
(2) Give the capacitance of the conductor B.
(3) When an electric charge Q is applied to the conductor A, not to the conductor B, give charge
quantity Q1 distributed on the conductor A in contact with the region 1 and charge quantity Q2
distributed on the conductor A in contact with the region 2.
(4) In the case of (3), give the magnitude of each electric field in the region 1, the region 2, theregion 3 and the region 4, respectively.
(5) Give the capacitance of the conductor A.

Fig. 2令和３年度

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

専 門 科 目 (Specialized subjects)(19/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.

࠙Q3ࠚ Answer the following questions.
(1) As shown in Fig. 3(a), a current I flows through the straight conductor AB of length " . Consider
the magnetic field H at the point P of the distance d from the conductor. The current flows in the
direction from B to A. O is the point where the perpendicular line from point P intersects withAB, ߠଵ is the angle ҆PAO, and ߠଶ is the angle ҆PBO, respectively. Find the direction andmagnitude of the magnetic field dH generated at point P by a piece of current I ds at point Q
with a distance s from O, where the angle ҆AQP is T.
(2) Using the previous results, find the direction and magnitude of the magnetic field H generated atpoint P by the current I flowing through BA in Fig. 3(a).
(3) Next, in parallel to the conductor AB, straight conductor CD of the same length " is placed atintervals d as shown in Fig. 3(b), where the current I1 flows from B to A and the current I2 flows
from D to C, respectively. Find the direction and magnitude of the force dF experienced by theshort interval dx at point P’ which is in distance x from point D on the conductor CD.
(4) In the case of (3), find the direction and magnitude of the force F acting between the two
conductors.

(a)

(b)
Fig. 3令和３年度

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

専 門 科 目 (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) 与えられた d1 × d2 行列 A と d2 × d3 行列 B に対し，アルゴリズム 1 はそれらの積
C = AB を求める．アルゴリズム 1 の時間計算量を答えよ．
アルゴリズム 1.
入力: d1 × d2 行列 A = (aij ) と d2 × d3 行列 B = (bij )1 for i ← 1 to d1
2
for j ← 1 to d33
cij ← 0
4
for k ← 1 to d2
5
cij ← cij + aik bkj
6 return C = (cij )(2) 10 × 100 行列 A と 100 × 1 行列 B と 1 × 100 行列 C と 100 × 10 行列 D が与えられたとき，積 E = ABCD をアルゴリズム 1 をサブルーチンとして用いて求めたい．

(a) 数式 E = (A(BC))D で表される積の順に従う場合，行列 E の計算における加算と乗算の回数の合計を答えよ．

(b) E の計算にかかる時間が最小となる積の順を，問 (a) に倣った数式で記述せよ．
また，その積の順に従う E の計算における加算と乗算の回数の合計を答えよ．

(3) Mi (i = 1, . . . , n) は di × di+1 行列とし，積 X = M1 · · · Mn をアルゴリズム 1 を用いて求めたい．積 X の計算について，すべての積の順の中で最小の時間計算量をアル
ゴリズム 2 が与えることを証明せよ．またアルゴリズム 2 の時間計算量を答えよ．
アルゴリズム 2.
入力: 正整数 d1 , . . . , dn+1
1 for j ← 1 to n
2f (j, j) ← 0
3 for i ← 1 to n
4
for j ← 1 to n − i
5f (j, j + i) ← min {f (j, k) + f (k + 1, j + i) + dj dk+1 dj+i+1 }j≤k<j+i6

return f (1, n)

令和３年度

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

専 門 科 目 (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 は Python 言語で書かれたマージソートのプログラムである．図 1 の 32 行目で下記の入力が与えられている．次の問いに答えよ．

32: list_input = [8, 3, 6, 5, 2, 7, 4, 1](1) merge sort は，リスト result の要素を start から end の範囲で昇順に並び替える関数である．空欄 (A)-(G) を埋め，関数 merge sort を完成せよ．
(2) sort は，リスト list input の要素を昇順に並び替える関数である．関数 sort が呼び出されて完了するまでに，関数 merge が呼び出される回数を答えよ．また，関数merge に与えられる実引数のリスト copy と result の要素を関数 merge の呼び出しごとに答えよ．
(3) 8 行目から 11 行目の文を削除した場合を想定する．関数 sort が呼び出された時，リスト list input の要素は，昇順に並び替えられているか否かを答えよ．また，関数 sort が実行完了するまでに，関数 merge sort が呼び出される回数を答えよ．
(4) 関数 sort を，リスト list input を降順に並び替えるように変更したい．行番号を示しながら，変更すべき式と，その内容を記せ．

令和３年度

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

専 門 科 目 (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.

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
32
33
34

def sort (list_input):copy = list(list_input)
merge_sort(copy, list_input, 0, len(list_input)-1)
def merge_sort(copy, result, start, end):
if end - start < 1:
returnif end - start == 1:
if result[start] > result[end]:
result[start], result[end] = result[end], result[start]
returnmid = int((end + start) / 2)
merge_sort(result, copy, (A), (B))
merge_sort(result, copy, (C), (D))
merge(copy, result, (E), (F), (G))
def merge(copy, result, start, end, mid):i = start
j = mid
idx = start
while idx <= end:
if j > end or (i < mid and copy[i] < copy[j]):result[idx] = copy[i]i += 1else:
result[idx] = copy[j]j += 1
idx += 1
list_input = [8, 3, 6, 5, 2, 7, 4, 1]
sort(list_input)
print(list_input)

図 1 (Figure 1)令和３年度

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

専 門 科 目 (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】 Suppose that each of additions, multiplications and comparisons of two numbers takes

a unit time. Answer the following questions.
(1) Given a d1 ×d2 matrix A and a d2 ×d3 matrix B, Algorithm 1 computes the product
C = AB. Show the time complexity of Algorithm 1.
Algorithm 1.
Input: d1 × d2 matrix A = (aij ) and d2 × d3 matrix B = (bij )1 for i ← 1 to d1
2
for j ← 1 to d33
cij ← 0
4
for k ← 1 to d2
5
cij ← cij + aik bkj
6 return C = (cij )(2) Given a 10 × 100 matrix A, a 100 × 1 matrix B, a 1 × 100 matrix C and a 100 × 10
matrix D, we wish to compute E = ABCD using Algorithm 1 as a subroutine.
(a) Show the total number of additions and multiplications in the computation of E
according to the multiplying order represented by the equation E = (A(BC))D.
(b) Show in the form of an equation similar to that in the question (a) the multiplying order of E minimizing the execution time. Also, show the total numberof additions and multiplications in the computation of E according to the order.
(3) We wish to compute X = M1 · · · Mn using Algorithm 1 where Mi is a di ×di+1 matrix
for each i = 1, . . . , n. Prove that Algorithm 2 ﬁnds the minimum time complexity
over the multiplying orders of X. Also, show the time complexity of Algorithm 2.
Algorithm 2.
Input: positive integers d1 , . . . , dn+1
1 for j ← 1 to n
2f (j, j) ← 0
3 for i ← 1 to n
4
for j ← 1 to n − i
5f (j, j + i) ← min {f (j, k) + f (k + 1, j + i) + dj dk+1 dj+i+1 }j≤k<j+i6

return f (1, n)

令和３年度

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

専 門 科 目 (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】 Figure 1 shows a program written in Python which implements the merge sort. The

following input is given at line 32 in Figure 1. Answer the following questions.
32: list_input = [8, 3, 6, 5, 2, 7, 4, 1](1) merge sort is a function that sorts the elements of list result in the range fromstart to end in ascending order. Fill in the blanks from (A) to (G) to complete
function merge sort.
(2) sort is a function that sorts the elements of list list input in ascending order.
Answer how many times the function merge will have been called by the time thefunction sort has executed to completion. In addition, show the elements of lists
copy and result that are given as actual arguments to the function merge eachtime when the function merge is called.
(3) Suppose that the statements from line 8 to line 11 are deleted. Answer whether or
not the function sort can sort the elements of the list result in ascending order.
In addition, answer how many times the function merge sort will have been calledby the time the function sort has executed to completion.
(4) To make function sort sort the elements in the list list input in descending order,
which lines should be modiﬁed? Indicate the line numbers that need to be modiﬁed
and explain how to modify them.

令和３年度

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

専 門 科 目 (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.

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
32
33
34

def sort (list_input):copy = list(list_input)
merge_sort(copy, list_input, 0, len(list_input)-1)
def merge_sort(copy, result, start, end):
if end - start < 1:
returnif end - start == 1:
if result[start] > result[end]:
result[start], result[end] = result[end], result[start]
returnmid = int((end + start) / 2)
merge_sort(result, copy, (A), (B))
merge_sort(result, copy, (C), (D))
merge(copy, result, (E), (F), (G))
def merge(copy, result, start, end, mid):i = start
j = mid
idx = start
while idx <= end:
if j > end or (i < mid and copy[i] < copy[j]):result[idx] = copy[i]i += 1else:
result[idx] = copy[j]j += 1
idx += 1
list_input = [8, 3, 6, 5, 2, 7, 4, 1]
sort(list_input)
print(list_input)

図 1 (Figure 1)令和３年度

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

専 門 科 目 (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】与えられた真理値表で表される論理関数 F (a, b, c, d) が以下の論理式を満たす時，論理関数 G(X, Y, Z, W ) の最簡積和形を示せ．ただし，最簡積和形とは積和形論理式のうち，積項数が最小のものを指す．積項数が等しい積和形論理式が複数ある場合にはそのなかでリテラル数が最小のものを指す．

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

X = āb̄c̄ + b̄d + abd¯
Y = ācd¯ + bcd + ab̄d + ac̄d¯Z = ābc̄ + bc̄d + b̄d
W = ābd¯ + abd + cd + āc
F (a, b, c, d) = G(X, Y, Z, W )令和３年度

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

専 門 科 目 (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) IF，ID，EX，MEM，WB の遅延時間は，それぞれ，240 ps，400 ps，200 ps，250
ps，180 ps である．このデータパスの最大動作周波数を答えよ（単位は GHz）．
(2) IF，ID，EX，MEM，WB のいずれか 1 つを 2 つのステージに分割し，パイプラ
インステージ数を 5 から 6 へと増加することを考える．ここで，分割された各パイ
プラインステージの遅延時間は，分割前のパイプラインステージの遅延時間の半分になると仮定する．パイプラインの動作周波数を最大にするために分割すべきパイ
プラインステージを選択せよ．また，この設計最適化により達成できる最大動作周
波数を答えよ（単位は GHz）．

(3) あるプログラムの実行において，上記 (2) のパイプラインステージの分割により CPI（Clock cycles Per Instruction）が 10 % 増加した．ここで，パイプラインステージ
分割は CPI の増加以外の悪影響は生じないと仮定する．このパイプラインステージ
分割によって得られた性能向上比を答えよ．

(4) パイプライン段数を増加することの利点と欠点を説明せよ．
【問 3】キャッシュタグ・フィールド，キャッシュインデックス・フィールド，キャッシュブロッ
クオフセット・フィールドからなる 32 ビットのメモリアドレスを入力とするダイレク
トマップ・キャッシュメモリについて考える．バイトアドレッシング方式を採用しており， 1 語は 4 バイト，キャッシュサイズは 16 キロバイト，キャッシュブロックサイズは

32 バイトとする．キャッシュタグ・フィールドのビット幅を答えよ．

令和３年度

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

専 門 科 目 (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 F (a, b, c, d) be a logic function whose truthtable is shown below. When the following

logic equations hold, show the minimum sum of products form of the logic function
G(X, Y, Z, W ). The minimum sum of products form of a logic function f has the smallest
number of product terms among those which represent f . If there are more than one
forms having the smallest number of product terms, forms with the minimum numberof literals are chosen.
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
1
0
1
0
0
1
1
1
0
1
0
0
0

X = āb̄c̄ + b̄d + abd¯
Y = ācd¯ + bcd + ab̄d + ac̄d¯Z = ābc̄ + bc̄d + b̄d
W = ābd¯ + abd + cd + āc
F (a, b, c, d) = G(X, Y, Z, W )令和３年度

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

専 門 科 目 (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) The latency of pipeline stages, IF, ID, EX, MEM, and WB, is 240 ps, 400 ps, 200
ps, 250 ps, and 180 ps, respectively. Answer the maximum clock frequency of thisdatapath (unit is GHz).
(2) Consider increasing the number of pipeline stages from 5 to 6 by partitioning asingle pipeline stage, IF, ID, EX, MEM, or WB, to two stages. Assume the latencyof the partitioned pipeline stages is half of that of the original stage. Choose one
pipeline stage that should be partitioned for maximising the clock frequency of thedatapath, and answer the maximum clock frequency we can achieve by this design
optimization (unit is GHz).
(3) For the execution of a program, the pipeline stage partitioning presented in (2)caused 10 % increase in CPI (Clock cycles Per Instruction). Assume there are no
negative eﬀects caused by the pipeline stage partitioning except for the CPI increase.
Answer the performance improvement rate achieved by applying the pipeline stage
partitioning.
(4) Explain the advantages and disadvantages of increasing the number of pipeline
stages.
【Q3】 Consider a direct-mapped cache memory that accepts a 32-bit memory address consistingof a cache tag ﬁeld, a cache index ﬁeld, and a cache block oﬀset ﬁeld. Suppose a byteaddressing scheme, the word size is 4 bytes, the cache size is 16 Kilo-bytes, and the cache
block size is 32 bytes. Answer the bit-width of the cache tag ﬁeld.