
۟य୉ָ୉ָӅεητϞ৚ๅՌָැ
৚ๅཀྵ޽ָ઒ߊ
ྫ࿪̔೧ౕ೘ָࢾ‫ݩ‬໲ୌʴྫ࿪̓೧̖݆̗̐ೖʤՒʥɼ̑̎ೖʤਭʥʵ
৘ใཧ޻ֶઐ߈
ి‫ֶ޻ࢠిؾ‬ઐ߈म࢜՝ఔɹೖֶࢼ‫ݧ‬໰୊ʢྩ࿨̑೥݄̔̎̕೔ʣ

‫۝‬भେֶେֶӃγεςϜ৘ใՊֶ෎

਺ ֶ (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. ઢ‫ܗ‬୅਺ɼղੳֶɾඍੵ෼ͷ 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

෼໺
ઢ‫ܗ‬୅਺
ղੳֶɾඍੵ෼
ϕΫτϧղੳ
֬཰ɾ౷‫ܭ‬ﬁeld
Linear algebra
Analysis and calculus
Vector analysis
Probability and statistics

page
2
4
6
7

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)
ʢ7 ຕதͷ 2ʣ෼໺ຖʹղ౴༻ࢴΛผʹ͢Δ͜ͱɽ
Use a separate answer sheet for each ﬁeld.

1. ʲઢ‫ܗ‬୅਺ (Linear algebra) ෼໺ʳ
m × n ࣮ߦྻ A ͱ m ࣍‫࣮ݩ‬ϕΫτϧ b ʹରͯ͠ɼS = {x ∈ Rn | Ax = b}ɼf (x) = Ax Λఆٛ͢Δɽ͜ͷͱ͖ɼҎԼͷ໰͍ʹ౴͑Αɽͨͩ͠ɼҎԼͷࣄ࣮͸ূ໌ͳ͠ʹ༻͍ͯΑ͍ɽ
ࣄ࣮. R ্ͷϕΫτϧۭؒ (ઢ‫)ۭؒܗ‬V ͷ෦෼ू߹ W ͕ V ͷ෦෼ۭؒͰ͋Δඞཁे෼৚݅͸ҎԼͷ৚͕݅ຬͨ͞ΕΔ͜ͱͰ͋Δɽ

C1. 0 ∈ W ɽ
C2. u, v ∈ W ͳΒ͹ u + v ∈ W ɽ
C3. u ∈ W, c ∈ R ͳΒ͹ cu ∈ W ɽ⎤
2 0 2 0⎥⎢
(1) A = ⎣0 8 24 24⎦ Ͱ͋Δͱ͖ɼf ͷ֩ Ker(f ) ͷ࣍‫جͱݩ‬ఈΛҰ૊‫ٻ‬ΊΑɽ
0 2 6 6⎡(2) Ұൠʹ Ker(f ) ͕ Rn ͷ෦෼ۭؒͰ͋Δ͜ͱΛࣔͤɽ(3) S ͕ Rn ͷ෦෼ۭؒͰ͋Δͱ͖ɼb = 0 Ͱ͋Δ͜ͱΛࣔͤɽ(4) S ͕ Rn ͷ෦෼ۭؒɼA ͕ਖ਼ํߦྻͰ͋Δͱ͢Δɽ͜ͷͱ͖ɼA ͕ਖ਼ଇߦྻͰ͋ΔͳΒ͹ɼS = {0} Ͱ͋Δ͜ͱΛࣔͤɽ৘ใཧ޻ֶઐ߈
ి‫ֶ޻ࢠిؾ‬ઐ߈म࢜՝ఔɹೖֶࢼ‫ݧ‬໰୊ʢྩ࿨̑೥݄̔̎̕೔ʣ

‫۝‬भେֶେֶӃγεςϜ৘ใՊֶ෎

਺ ֶ (Mathematics)
ʢ7 ຕதͷ 3ʣ෼໺ຖʹղ౴༻ࢴΛผʹ͢Δ͜ͱɽ
Use a separate answer sheet for each ﬁeld.

For an m×n real matrix A and an m-dimensional real vector b, deﬁne S = {x ∈ Rn | Ax = b}
and f (x) = Ax. Answer the following questions. Note that the following fact can be usedwithout proof.
Fact. A subset W of a vector space (linear space) V over R is a subspace of V if and only if
the following conditions hold.
C1. 0 ∈ W .
C2. If u, v ∈ W , then u + v ∈ W .
C3. If u ∈ W and c ∈ R, then cu ∈ W .
⎤⎡2 0 2 0⎥⎢
(1) When A = ⎣0 8 24 24⎦, ﬁnd the dimension of the kernel Ker(f ) of f and a basis of
0 2 6 6
the kernel.
(2) Show Ker(f ) is a subspace of Rn in general.
(3) Suppose that S is a subspace of Rn . Show b = 0 .
(4) Suppose that S is a subspace of Rn and A is a square matrix. Show S = {0} if A isinvertible.

৘ใཧ޻ֶઐ߈
ి‫ֶ޻ࢠిؾ‬ઐ߈म࢜՝ఔɹೖֶࢼ‫ݧ‬໰୊ʢྩ࿨̑೥݄̔̎̕೔ʣ

‫۝‬भେֶେֶӃγεςϜ৘ใՊֶ෎

਺ ֶ (Mathematics)
ʢ7 ຕதͷ 4ʣ෼໺ຖʹղ౴༻ࢴΛผʹ͢Δ͜ͱɽ
Use a separate answer sheet for each ﬁeld.

2. ʲղੳֶɾඍੵ෼ (Analysis and calculus) ෼໺ʳ(1) ੵ෼ ∞I=Λ‫ͤࢉܭ‬Αɽͨͩ͠ɼ

x5 exp(−x4 )dx0√∞exp(−x2 )dx = π Λূ໌ͳ͠ʹ༻͍ͯΑ͍ɽ−∞(2) ࣍ͷඍ෼ํఔࣜͷҰൠղΛ‫ٻ‬ΊΑɽdy+ y = x sinh xdx(3) ෳૉؔ਺ f (z) =1
z4 + 1Λߟ͑Δɽ࣍ͷ֤໰͍ʹ౴͑Αɽ(a) f (z) ͷ‫ۃ‬Λ͢΂ͯ‫ٻ‬ΊΑɽ(b) Լਤʹࣔ͢൒ԁ C ʹԊͬͨෳૉੵ෼

f (z)dz Λ‫ٻ‬ΊΑɽͨͩ͠ɼR > 1 ͱ͢Δ.
C৘ใཧ޻ֶઐ߈
ి‫ֶ޻ࢠిؾ‬ઐ߈म࢜՝ఔɹೖֶࢼ‫ݧ‬໰୊ʢྩ࿨̑೥݄̔̎̕೔ʣ

‫۝‬भେֶେֶӃγεςϜ৘ใՊֶ෎

਺ ֶ (Mathematics)
ʢ7 ຕதͷ 5ʣ෼໺ຖʹղ౴༻ࢴΛผʹ͢Δ͜ͱɽ
Use a separate answer sheet for each ﬁeld.

(1) Calculate the integral ∞I=

where you can use

x5 exp(−x4 )dx,0√∞2exp(−x)dx=
π without proving it.
−∞(2) Find the general solution to the following diﬀerential equation.
dy+ y = x sinh x.
dx(3) Consider the complex function f (z) =1
z4 + 1. Answer the following questions.

(a) Find all the poles of f (z).
(b) Calculate the complex integral
ﬁgure below, and R > 1.

f (z)dz, where C is a semicircle as shown in theC৘ใཧ޻ֶઐ߈
ి‫ֶ޻ࢠిؾ‬ઐ߈म࢜՝ఔɹೖֶࢼ‫ݧ‬໰୊ʢྩ࿨̑೥݄̔̎̕೔ʣ

‫۝‬भେֶେֶӃγεςϜ৘ใՊֶ෎

਺ ֶ (Mathematics)
ʢ7 ຕதͷ 6ʣ෼໺ຖʹղ౴༻ࢴΛผʹ͢Δ͜ͱɽ
Use a separate answer sheet for each ﬁeld.

3. ʲϕΫτϧղੳ (Vector analysis) ෼໺ʳ௚ަ࠲ඪ‫͍͓ͯʹܥ‬ɼxɼy ࣠ํ޲ͷ୯ҐϕΫτϧΛͦΕͧΕiɼj ͱ͢Δɽ࣍ͷ (1)ɼ(2) ʹࣔ͢ϕΫτϧ৔ F ͱ‫ܦ‬࿏ C ʹ͍ͭͯɼઢੵ෼

C

F · dr ΛͦΕͧΕ‫ٻ‬ΊΑɽ(1) ϕΫτϧ৔ F Λ F = (2xy 3 − y) i + (3x2 y 2 − x) j ͱ͠ɼ‫ܦ‬࿏ C Λ‫ۂ‬ઢ y 3 + x2 − 2xy = 1ͷ఺ (−13, −4) ͔Β఺ (5, −4) ·Ͱͷ෦෼ͱ͢Δɽ(2) ϕΫτϧ৔ F Λ F = (3e2x + 4y) i + (x + 7yey ) j ͱ͢Δɽ ‫ܦ‬࿏ C ͸ɼ఺ P(0, 0)ɼ఺Q(2, 2)ɼ఺ R(4, 6)ɼ఺ S(1, 3) Λ௖఺ͱ͢Δ࢛ล‫Ͱܗ‬ɼPɼQɼRɼSɼP ͷॱʹ޲͖͚ͮΒΕ͍ͯΔͱ͢Δɽ

The unit vectors on x and y axes of Cartesian coordinates are denoted by i and j, respectively.
Find each line integralCF · dr of the vector ﬁeld F along the path C deﬁned in (1) and (2).

(1) Let F = (2xy 3 − y) i + (3x2 y 2 − x) j, and C be the curve y 3 + x2 − 2xy = 1 from(−13, −4) to (5, −4).
(2) Let F = (3e2x + 4y) i + (x + 7yey ) j, and C be the quadrilateral with vertices at points
P(0, 0), Q(2, 2), R(4, 6) and S(1, 3), which is directed from P to Q, Q to R, R to S and
S to P.

৘ใཧ޻ֶઐ߈
ి‫ֶ޻ࢠిؾ‬ઐ߈म࢜՝ఔɹೖֶࢼ‫ݧ‬໰୊ʢྩ࿨̑೥݄̔̎̕೔ʣ

‫۝‬भେֶେֶӃγεςϜ৘ใՊֶ෎

਺ ֶ (Mathematics)
ʢ7 ຕதͷ 7ʣ෼໺ຖʹղ౴༻ࢴΛผʹ͢Δ͜ͱɽ
Use a separate answer sheet for each ﬁeld.

4. ʲ֬཰ɾ౷‫( ܭ‬Probability and statistics) ෼໺ʳശͷதʹ N1 ‫ݸ‬ͷന͍Ϙʔϧͱ N2 ‫ݸ‬ͷࠇ͍Ϙʔϧ͕͋Γɼͦͷ૯਺Λ N = N1 + N2 ͱ͢
Δɽ͜ͷശ͔Β 2 ͭͷϘʔϧΛϥϯμϜʹબͼɼ྆ํ͕ന͍ϘʔϧͰ͋Δ֬཰͸ 1/2 Ͱ͋Δͱ͢Δɽ(1) N2 ͕‫਺ح‬ͷͱ͖ N1 ͷ࠷খ஋Λ‫ٻ‬ΊΑɽ(2) N2 ͕‫਺ۮ‬ͷͱ͖ N1 ͷ࠷খ஋Λ‫ٻ‬ΊΑɽ(3) N Λ஋ͷখ͍͞ॱʹ 3 ͭ‫ٻ‬ΊΑɽ

A box contains N1 white and N2 black balls, and the total number of balls is N = N1 + N2 .
When two balls are randomly drawn from the box, the probability that both balls are whiteis 1/2.
(1) Find the minimum value of N1 when N2 is an odd number.
(2) Find the minimum value of N1 when N2 is an even number.
(3) Find the three smallest values of N .

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

専 門 科 目 (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
14
18
24

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】〜【問 3】から2 問を選び，解答用紙の問題番号欄に解答した問題番号を記入せよ．
【問 1】 図 1 の回路について，以下の問いに答えよ．ただし，端子間には e(t) =sin 2t [V] の交流電圧が印加されているとする．

(1) 端子間のインピーダンスを求めよ．















(2) 電流 i(t) を求めよ．

(3) i(t)，i1 (t) のフェーザ表記をそれぞれ I ，I1 としたとき， II1 はいくらになるか答えよ．



図1

【問 2】 図 2 の回路において，ZG を変えることで負荷インピーダンス ZL で消費される電

力を最大化したい．以下の問いに答えよ．た‫܈‬૚だし，J は交流電流源であり，Z1 で表される
二端子対網は以下に示すインピーダンス行列（Z 行列）のように表されるとする．また，図

‫ܬ‬

ͳ

ܼீ
݆

内の破線で囲まれた部分に示された数値は全てインピーダンスを示すものである．
√

Z1 =

1+j
−1 + 7√1−j−1 + 7

ܼ௅
െ݆
b

b

図2

(1) 破線で囲まれた部分を二端子対網と見なし，この部分に相当する:::::::::::::::::::
アドミタンス行列（Y行列）Y2 を求めよ．ただし，破線内の数値はインピーダンスであることに留意せよ．さらに 1-1’ 端子と 2-2’ 端子からなる二端子対網の Z 行列 Z0 を求めよ．

(2) 2-2’ 端子から左側を見た出力インピーダンス Zout を ZG を含む式として求めよ．
(3) ZL = 1 + j2 のとき，ZL での消費電力が最大になる ZG を求めよ．

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

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

S【問 3】 図 3 の回路について，以下の問いに答えよ．ただし，E = 5 [V]，R1 = 1 [Ω]，R2 = 2 [Ω]，R3 = 3 [Ω]，R4 = 4 [Ω]，C = 2 [F] であり，スイッチ S を閉じる前の回路は定常状態にあるとする．

(1) 時刻 t = 0 でスイッチ S を閉じた直後の電荷量 q(0) を求めよ．

t=0
i(t)

R1

R2
R4
R3

‫ܧ‬

q(t)
C

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

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

専 門 科 目 (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 three questions 【Q1】〜【Q3】and write the number of theselected question on the answer sheet.
【Q1】 Consider the circuit shown in
Fig. 1, where the alternating voltage e(t) =sin 2t [V] is applied to the terminals. Answer the following questions.









(1) Find the impedance at the terminals.







(2) Find the current i(t).

(3) The phaser expressions of i(t) andi1 (t) are I and I1 , respectively. Find
the value of II1 .
【Q2】 Consider the circuit shown in Fig. 2. The
objective is to maximize the power consumed at
the load impedance ZL by optimizing ZG . Find
the solution by answering to the following questions, where J is the alternative current source,
and the two-port pair network represented by Z1
has the impedance matrix (Z-matrix) parameters
as follows. Note that all values shown in thedashed line in the ﬁgure are impedances.
Z1 =

√
1+j
−1 + 7√−1 + 71−jFig. 1‫܈‬૚

‫ܬ‬

ͳ

ܼீ
݆

ܼ௅
െ݆
b

b

Fig. 2(1) Consider the area enclosed by the dashed line as a two-port pair network described byadmittancematrix (Y-matrix) Y2 , and ﬁnd Y2 , where note that all values in the dashed:::::::::::::::::::
line are impedances. Furthermore, ﬁnd the Z-matrix Z0 of the two-port pair network
between 1-1’ and 2-2’ ports.
(2) Find the output impedance Zout considering left side from 2-2’ port as an expression
involving ZG .
(3) Find ZG that maximizes power consumption at ZL when ZL = 1 + j2.

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

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

S【Q3】 Consider the circuit shown in Fig.
3, where E = 5 [V], R1 = 1 [Ω], R2 = 2 [Ω],R3 = 3 [Ω], R4 = 4 [Ω], C = 2 [F], and thecircuit is in steady state before the switch
S is closed.

(1) Find the charge q(0) just after theswitch S is closed at t = 0.

t=0
i(t)

R1

R2
R4
R3

‫ܧ‬

q(t)
C

(2) Find the current i(t) at t > 0.
Fig. 3

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

専 門 科 目 (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】アルファベット {s1 , s2 , s3 , s4 , s5 , s6 } 上の無記憶情報源 S の符号化に関して，以下の問いに答えよ．ただし，符号語アルファベットを {0, 1} とする．

(1) 無記憶情報源 S に関して，各符号語長を 3, 3, 3, 2, 2, 2 とする符号が瞬時に復号可能になり得るかどうかを述べよ．なり得る場合，瞬時に復号可能な符号の一例を示せ．

(2) 無記憶情報源 S に関して，各符号語長を 3, 3, 3, 3, 2, 2 とする符号が瞬時に復号可能になり得るかどうかを述べよ．なり得る場合，瞬時に復号可能な符号の一例を示せ．
以後の問いにおいて， 無記憶情報源 S に関して，その確率分布が P (s1 ) = 0.18, P (s2 ) =0.2, P (s3 ) = 0.3, P (s4 ) = 0.13, P (s5 ) = 0.11, P (s6 ) = 0.08 であるとする．次の問いに答えよ．

(3) 無記憶情報源 S に関して，ハフマン符号化により符号化せよ．このときのハフマン符号化の符号の木を図示せよ．

(4) ハフマン符号化により得られた符号の平均符号長を求めよ．
【問 2】アルファベット X = {1, 2, 3} 上の確率分布 p1 と p2 を

(p1 (1), p1 (2), p1 (3)) = (1, 0, 0)(p2 (1), p2 (2), p2 (3)) = (0, b, 1 − b)で定める．ただし，b ∈ (0, 1) を定数とする．p1 と p2 の重み付き平均で表される確率分
布 q のうち，X 上の一様分布 u との Kullback-Leibler ダイバージェンス

D(u||q) =x∈Xが最小となるものを求めよ．

u(x) log

u(x)
q(x)

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

専 門 科 目 (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】Consider coding of a memoryless information source S over the alphabet{s1 , s2 , s3 , s4 , s5 , s6 }. Here, let the alphabet of codewords be {0, 1}. Answer the following
questions.
(1) Determine whether a code with codeword lengths of 3, 3, 3, 2, 2, 2 in the memoryless
information source S can be instantaneously decodable or not. If it is possible, show
an example of instantaneously decodable codes.
(2) Determine whether a code with codeword lengths of 3, 3, 3, 3, 2, 2 in the memoryless
information source S can be instantaneously decodable or not. If it is possible, show
an example of instantaneously decodable codes.
Consider the memoryless information source S whose probability distribution is given as
P (s1 ) = 0.18, P (s2 ) = 0.2, P (s3 ) = 0.3, P (s4 ) = 0.13, P (s5 ) = 0.11, and P (s6 ) = 0.08.
Answer the following questions.
(3) Construct a Huﬀman code of S and show its code tree.
(4) Find the expected code length of the Huﬀman code.
【Q2】Deﬁne probability distributions p1 and p2 over the alphabet X = {1, 2, 3} by(p1 (1), p1 (2), p1 (3)) = (1, 0, 0),(p2 (1), p2 (2), p2 (3)) = (0, b, 1 − b),where b ∈ (0, 1) is a constant. Find the weighted average q of p1 and p2 which minimizes
the Kullback-Leibler divergence
D(u||q) =u(x) logx∈X

between q and the uniform distribution u over X .

u(x)
q(x)

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

専 門 科 目 (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) 分野】

次の各問い（【問１】【問２】）に答えよ．解答用紙の問題番号欄に解答した問題番号を記入すること．
【問１】アルファベット Σ = {a, d} 上の言語 L を

L = {w ∈ Σ∗ | ある x ∈ Σ∗ について w ∈ {xad, xadd, xdad}}とする．以下の図は L を受理する非決定性有限オートマトン M = (K, Σ, δ, q0 , F ) の状
態遷移図である．ただし，K = {q0 , q1 , . . . , q8 }，Σ = {a, d}，δ ，q0 ，F = {q2 , q5 , q8 } は，それぞれ M の状態の集合，アルファベット，遷移関数，初期状態，受理状態の集合を表す．次の各問いに答えよ．

, 
0




1
3




2
4



5


6



7



8

(1) L を受理する状態数 4 の非決定性有限オートマトンの状態遷移図を示せ．
(2) L を表す正規表現を示せ．
(3) L を受理する状態数 4 の決定性有限オートマトンの状態遷移図を示せ．
(4) L を受理する決定性有限オートマトンの状態数は必ず 4 以上であることを証明せよ．

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

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

【問２】アルファベット Σ = {→, ←, ↑ , ↓ } 上の文字列 a = a[1]a[2] · · · a[n]（各 i に対し a[i] ∈ Σ）
に対し，2 次元ベクトルの系列 f (a) = (p[0], p[1], . . . , p[n])（各 i に対し p[i] = (x[i], y[i])，x[i], y[i] は整数）を次のように定義する．p[0] = (0, 0) とし，各 i = 1, 2, . . . , n に対し，⎧⎪
p[i − 1] + (1, 0) a[i] = → のとき，⎪⎪⎪⎪
⎨p[i − 1] − (1, 0) a[i] = ← のとき，
p[i] =⎪
p[i − 1] + (0, 1) a[i] = ↑ のとき，⎪⎪⎪⎪
⎩p[i − 1] − (0, 1) a[i] = ↓ のとき．
すなわち，f (a) は，原点からスタートして a の矢印の向きに従って 2 次元格子点上を遷移したときの軌跡を表す．また，各 i = 1, 2, . . . , n に対し，|x[i]|+|y[i]| > |x[i−1]|+|y[i−1]|のとき（a[i] によって原点から遠ざかる方向に遷移したとき）i を前進ステップ，そうでないとき（a[i] によって原点に近づく方向に遷移したとき）i を後進ステップと呼び，文字列 a が往復的であることを，任意の後進ステップ i に対し，

i0 = max{j | j ≤ i − 1, p[j] = p[i − 1], j は前進ステップ }が存在し，p[i] = p[i0 − 1] が成り立つことと定義する．すなわち，往復的な文字列 a においては，後進ステップ i による p[i − 1] から p[i] への遷移は，i に対応する前進ステッ
プ i0 による p[i0 − 1] から p[i0 ] への遷移を逆にたどるものとなっている．往復的で f (a)の最後の要素が原点であるような文字列 a からなる言語L={a ∈ Σn | a は往復的, p = f (a), p[n] = (0, 0)}n≥0について，次の各問いに答えよ．

(1) 以下の文字列 a1 ，a2 ，a3 ，a4 が L の要素であるか否かをそれぞれ判定せよ．
a1 = ↑ ↑ ↓ → ↓ ↑ ← ↓a3 = ↓ ← ↑ →a2 = →→←←← ↑ ↓ →a4 = ← ↑ ↑ ↓ ←→ ↓ ← ↓ ↑(2) 次の図は，アルファベットを {→, ←} に限定した言語 L ∩ {→, ←}∗ を最終状態によって受理するプッシュダウンオートマトン（PDA）の状態遷移図の一部である．空欄①，②，③を埋めよ．
（２か所の③には同じものが入る．）

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

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

遷移規則 a,b / s は，遷移元の状態で読んだ入力文字が a，スタックの先頭文字が bのとき，遷移先の状態に遷移し，スタックの先頭を文字 b から文字列 s に置き換える動作を表す．ただし， は空文字列を表す．初期状態では，スタックは，空である
ことを表す特殊文字 Z のみを保持しているとする．S0 は初期状態であり唯一の最終状態でもある．
ヒント：状態 S0 ，S+ ，S− は，それぞれ，x[i] = 0，x[i] > 0，x[i] < 0 であることを表す．

(3) 次の図は，言語 L を最終状態で受理する PDA の状態遷移図の一部である．ただし，②と③は，(2) で求めたものと同じである．④と⑤を埋めよ．

ヒント：この PDA は，x[i] と y[i] の全ての符号の組に対応する 9 個の状態を持つ．
このうち，x[i] = y[i] = 0 を表す状態 S0 （初期状態であり唯一の最終状態でもある），x[i] = 0，y[i] > 0 を表す状態 S0+ ，x[i] > 0，y[i] = 0 を表す状態 S+0 ，x[i] > 0，y[i] > 0 を表す状態 S++ の 4 つの状態間の状態遷移図のみ示してある．

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

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

Answer the following questions (【Q1】【Q2】) and write the number of the selected question
on the answer sheet.
【Q1】We deﬁne a language L on the alphabet Σ = {a, d} as

L = {w ∈ Σ∗ | w ∈ {xad, xadd, xdad} for some x ∈ Σ∗ }.
The following ﬁgure is a state transition diagram of a nondeterministic ﬁnite automaton
M = (K, Σ, δ, q0 , F ) that accepts L. Here, K = {q0 , q1 , . . . , q8 }, Σ = {a, d}, δ, q0 , andF = {q2 , q5 , q8 } are the set of states, the alphabet, the state transition function, theinitial state, and the set of accept states, respectively. Answer the following questions.
, 
0




1
3




2
4



5


6



7



8

(1) Draw a state transition diagram of a nondeterministic ﬁnite automaton that accepts
L and has four states.
(2) Give a regular expression that represents L.
(3) Draw a state transition diagram of a deterministic ﬁnite automaton that accepts Land has four states.
(4) Prove that any deterministic ﬁnite automaton that accepts L has at least four states.

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

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

【Q2】For a string a = a[1]a[2] · · · a[n] over the alphabet Σ = {→, ←, ↑ , ↓ } (a[i] ∈ Σ foreach i), we deﬁne a sequence of two-dimensional vectors f (a) = (p[0], p[1], . . . , p[n])(p[i] = (x[i], y[i]) with integers x[i], y[i] for each i) as follows: Let p[0] = (0, 0) and let⎧⎪
p[i − 1] + (1, 0) if a[i] = →,⎪⎪⎪⎪⎨p[i − 1] − (1, 0) if a[i] = ←,p[i] =⎪
p[i − 1] + (0, 1) if a[i] = ↑ ,⎪⎪⎪⎪⎩p[i − 1] − (0, 1) if a[i] = ↓for each i = 1, 2, . . . , n. In other words, f (a) represents the trajectory when startingfrom the origin and then moving over the two-dimensional grid points according to thearrow directions designated by a. For each i = 1, 2, . . . , n, we call i a forward step if|x[i]|+|y[i]| > |x[i−1]|+|y[i−1]| (if moving away from the origin by a[i]) and a backward
step otherwise (if moving closer to the origin by a[i]). Furthermore, the string a is said
to be round-trip if for each backward step i, there exists
i0 = max{j | j ≤ i − 1, p[j] = p[i − 1], j is a forward step}and it satisﬁes p[i] = p[i0 − 1]. The condition says that the transition from p[i − 1] top[i] by a backward step i should be the reverse of the transition from p[i0 − 1] to p[i0 ]by the corresponding forward step i0 . For the languageL={a ∈ Σn | a is round-trip, p = f (a), p[n] = (0, 0)}n≥0which consists of all round-trip strings a such that f (a) ends up in the origin, answer
the following questions.
(1) Decide whether each of the following strings a1 , a2 , a3 and a4 is a member of L.
a1 = ↑ ↑ ↓ → ↓ ↑ ← ↓a3 = ↓ ← ↑ →a2 = →→←←← ↑ ↓ →a4 = ← ↑ ↑ ↓ ←→ ↓ ← ↓ ↑(2) The following ﬁgure is a state transition diagram of a pushdown automaton (PDA)
that accepts L ∩ {→, ←}∗ (the language restricted to alphabet {→, ←}) by ﬁnal
state. Fill in ①, ② and ③. (The two blanks of ③ are the same.)九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和５年８月２９日）

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

The transition rule a,b / s designates the action in the source state that if the input
character read is a and the top character of the stack is b, then the PDA moves tothe destination state while replacing b on the top of the stack with the string s,
where  denotes the empty string. Initially, the stack only has the special symbol
Z which represents the empty stack. S0 is the initial state as well as the (unique)ﬁnal state.
Hint: The states S0 , S+ and S− represent that x[i] = 0, x[i] > 0, and x[i] < 0,respectively.
(3) The following ﬁgure is a part of a state transition diagram of a PDA that accepts
L by ﬁnal state, where ② and ③ are the same as in (2). Fill in ④ and ⑤.

Hint: The PDA has nine states for all combinations of the signs of x[i] and y[i]. The
ﬁgure only shows the transitions among four states: S0 representing x[i] = y[i] = 0(the initial state as well as the unique ﬁnal state), S0+ representing x[i] = 0, y[i] > 0,
S+0 representing x[i] > 0, y[i] = 0, and S++ representing x[i] > 0, y[i] > 0.

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

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

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

௨ୗࡢྛၥ࠸ ࠙ၥࠚ࠙ၥࠚ ࡟⟅࠼ࡼ㸬ゎ⟅⏝⣬ࡢၥ㢟␒ྕḍ࡟ゎ⟅ࡋࡓၥ㢟␒ྕࢆグධࡍࡿࡇ࡜
࠙ၥࠚ ᅗ 1 䛾䜘䛖䛻䠈༙ᚄ a䠈b䠈c 䛾 3 䛴䛾ྠᚰᑟయ⌫Ẇ䛛䜙ᡂ䜛ᑟయ 1 䛸䠈༙ᚄ a䠈c 䛾 2 䛴䛾ྠᚰᑟయ⌫Ẇ䛛䜙ᡂ䜛ᑟయ 2 䜢䠈┿✵୰䛻୰ᚰ㛫㊥㞳 d 䛷⨨䛟䠊䛭䜜䛮䜜᭱䜒ෆഃ䛻䛒䜛༙ᚄ a 䛾ᑟయ⌫Ẇ䛻㟁Ⲵ Q1䠈Q2 䜢୚䛘䛯䠊䛣䛣䛷䠈⌫Ẇ䛾ཌ䜏䛿↓ど䛷䛝䠈≫ , , 䛷䛒䜚䠈┿✵䛾ㄏ㟁⋡䜢 䛸䛩䜛䠊
䠄1䠅㻌 ᭱䜒እ䛻䛒䜛༙ᚄ c 䛾ᑟయ⌫Ẇ䛾እ㠃䛻⌧䜜䜛㟁Ⲵ䜢䠈ᑟయ 1 䛸ᑟయ 2 䛭䜜䛮䜜䛻䛴䛔䛶♧䛫䠊
䠄2䠅㻌 ᭱䜒እ䛻䛒䜛༙ᚄ c 䛾ᑟయ⌫Ẇ䛾㟁఩䜢䠈ᑟయ 1 䛸ᑟయ 2 䛻䛴䛔䛶ồ䜑䜘䠊䛯䛰䛧↓㝈㐲䛷䛾㟁఩䜢 0 䛸䛩䜛䠊䠄3䠅㻌 ᑟయ 1 䛸ᑟయ 2 䛾㟼㟁䜶䝛䝹䜼䞊䜢䛭䜜䛮䜜ồ䜑䜘䠊
䠄4䠅㻌 ᑟయ 1 䛸ᑟయ 2 䛾᭱䜒እ䛻䛒䜛༙ᚄ c 䛾ᑟయ⌫Ẇ㛫䜢ᑟ⥺䛷᥋⥆䛧䛯䠊඘ศ᫬㛫䛜⤒䛳䛯ᚋ䛾䛣䛾⣔䛾඲㟼㟁䜶䝛䝹䜼䞊䜢ồ䜑䜘䠊䛯䛰䛧䠈ᑟ⥺䛻⵳䛘䜙䜜䜛㟁Ⲵ䛿↓ど䛷䛝䜛䜒䛾䛸䛩䜛䠊
ᑟయ 

ᑟయ 

ᅗ 

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

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

࠙ၥࠚ ᅗ㸰࡟♧ࡍࡼ࠺࡟㸪 ≧ 0 ࡢ㡿ᇦ࡟࠾࠸࡚㸪 ㍈ࡢṇࡢྥࡁ࡟୍ᵝ࠿ࡘ᫬㛫ኚ໬ࡢ࡞࠸☢᮰ᐦᗘ B ࡀ࠶ࡿ㸬 < 0 ࡢ㡿ᇦ࡛ࡣ☢᮰ᐦᗘࡣ 0 ࡛࠶ࡿ㸬᢬ᢠࡀ ࡛ 1 ㎶ࡢ㛗ࡉࡀ ࡢṇ᪉ᙧࢥ࢖ࣝ ABCD ࡀⅬ P (0, 0, ) ࢆ୰ᚰ࡜ࡋ࡚㸪 - ᖹ㠃ෆ࡟㸪㎶ AB ࡀ ㍈࡟ᖹ⾜࡟࡞ࡿࡼ࠺࡟┿✵୰࡟⨨࠿ࢀ࡚࠸ࡿ㸬ㄏᑟ㟁ὶ࡟ࡼࡗ࡚Ⓨ⏕ࡍࡿ☢⏺ࡣ↓ど࡛ࡁࡿ࡜ࡍࡿ㸬(1) ࢥ࢖ࣝ࡟እຊࢆຍ࠼㸪 ㍈ࡢ㈇ࡢྥࡁ࡟୍ᐃࡢ㏿ࡉ ࡛㐠ືࡉࡏࡓ㸬ࡇࡢ᫬㸪ࢥ࢖ࣝ࡟⏕ࡌࡿㄏᑟ㉳㟁ຊ㸪࡞ࡽࡧ࡟ㄏᑟ㟁ὶࡢ኱ࡁࡉࢆồࡵࡼ㸬(2) (1)࡟࠾࠸࡚㸪ࢥ࢖ࣝࡢ୰ᚰ P ࡢ ᗙᶆࡀ − /2 < < /2 ࡢ㛫࡟࠶ࡿ᫬㸪ࢥ࢖ࣝࢆ㏿ࡉ࡛ື࠿ࡍࡓࡵ࡟ᚲせ࡞እຊࡢ኱ࡁࡉࢆồࡵࡼ㸬ࡇࡇ࡛ࡣ㸪ṇ᪉ᙧࢥ࢖ࣝࡢ㉁㔞ࡣ↓ど࡛ࡁࡿ࡜ࡍࡿ.
(3) (1)࡟࠾࠸࡚㸪ࢥ࢖ࣝࡢ୰ᚰ P ࡢᗙᶆࡀ (0, 0, /2) ࠿ࡽ (0, 0, − /2) ࡲ࡛ືࡃ᫬㸪እຊ࡟ࡼࡾࢥ࢖ࣝ࡟࡞ࡉࢀࡿ௙஦㸪࡞ࡽࡧ࡟ࢥ࢖ࣝ࡟Ⓨ⏕ࡍࡿࢪ࣮ࣗࣝ⇕ࢆồࡵࡼ㸬ࡲࡓࡑࢀࡽ
ࡢᑟฟ㐣⛬ࡶ♧ࡏ㸬ࡇࡇ࡛ࡣ㸪ṇ᪉ᙧࢥ࢖ࣝࡢ㉁㔞ࡣ↓ど࡛ࡁࡿ࡜ࡍࡿ.
(4) ࢥ࢖ࣝࢆ㔜ຊࡢࡶ࡜࡛ⴠୗࡉࡏࡿ㸬㔜ຊࡣ ㍈ࡢ㈇ࡢྥࡁ࡟ാࡁ㸪㔜ຊຍ㏿ᗘࡣ ࡛࠶ࡿ㸬ࢥ࢖ࣝࡢ୰ᚰ P ࡢ ᗙᶆࡀ − /2 < < /2 ࡢ㛫࡟࠶ࡿ᫬㸪᫬้ ࡟࠾ࡅࡿࢥ࢖ࣝࡢ
㏿ࡉ ( ) ࢆồࡵࡼ㸬ࡇࡇ࡛ࡣ㸪ࢥ࢖ࣝࡢ㉁㔞ࡣ↓ど࡛ࡁ࡞࠸࡜ࡋ㸪ࡑࡢ኱ࡁࡉࡣ ࡜ࡍࡿ㸬ࡲࡓ = 0 ࡟࠾࠸࡚㸪ࢥ࢖ࣝࡢ㏿ࡉࡣ ( ) = 0 ࡜ࡋ㸪ࡑࡢ᫬ࢥ࢖ࣝࡢ୰ᚰ P ࡢ ᗙᶆ
ࡣ − /2 < < /2 ࡢ㛫࡟࠶ࡿ࡜ࡍࡿ㸬ᅗ㸰九州大学大学院システム情報科学府 情報理工学専攻
修士課程 入学試験問題（実施日 令和５年８月２９日）

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

Answer the following questions ([Question 1] [Question 2]) and write the number of the selected
question on the answer sheet.
[Question 1] As shown in Fig. 1, Conductor 1 consists of three concentric spherical shells with radii
a, b, and c, and Conductor 2 consists of two concentric spherical shells with radii a and c, where they areplaced with a center-to-center distance of d in vacuum. The innermost shells of radius a in both
Conductor 1 and Conductor 2 are charged with Q1 and Q2, respectively. All spherical shells havenegligibly small thickness, ≫ , , , and the electrical permittivity in vacuum is .
(1) Give the electric charges which appear on the outside surfaces of the outermost spherical shells ofradius c for each of Conductor 1 and Conductor 2.
(2) Give the electric potentials of the outermost spherical shells of radius c for each of Conductor 1 andConductor 2. The electric field at infinity is taken as zero.
(3) Give the values of the electrostatic energy of Conductor 1 and Conductor 2, respectively.
(4) Two outermost spheres of radius c were connected to each other with a conductive wire. Find theelectrostatic energy of the system. Assume that the electric charge stored in the wire is negligible.
Conductor 1

Conductor 2






Fig. 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.

[Question 2]  As shown in Fig. 2, a uniform static magnetic field B is in the positive direction in theregion ≧ 0. The magnetic field is zero in the region < 0. A square coil ABCD of resistance andside length is placed in vacuum in the - plane, and the side AB is parallel to the axis. The centerof the coil, P, is at the point (0, 0, ). Assume that the magnetic field generated by the induced current
flowing in the coil is negligible.
(1) Let an external force be applied so that the coil moves at a constant speed in the negative
direction. Show the magnitude of the induced electromotive force and the magnitude of the induced
current in the coil.
(2) In the case of (1), show the magnitude of the external force needed to make the coil move at the
speed when the coordinate of the point P, the center of the coil, is in the range − /2 < </2. Here, the mass of the coil is negligible.
(3) In the case of (1), show the work done by the external force on the coil and the Joule heat generated
in the coil when the coordinate of the point P, the center of the coil, is moved from (0, 0, /2) to(0, 0, − /2). Also, show how to derive them. Here, the mass of the coil is negligible.
(4) The coil is released and falls under the influence of gravity. The gravity is in the negative direction,and the acceleration of gravity is . Find the speed ( ) of the coil at a time when the coordinateof the point P, the center of the coil, is in the range − /2 < < /2. Here, the mass of the coil, ,is not negligible. Assume that at = 0, ( ) = 0 and the coordinate of the point P is in the range− /2 < < /2.

Fig. 2

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

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

E. 【アルゴリズム／プログラミング (Algorithms and programming) 分野】
次の各問い（【問１】【問２】【問３】）に答えよ．解答用紙の問題番号欄に解答した問題番号を記入すること．
【問１】次の各問いに答えよ．フィボナッチ数列 f0 , f1 , f2 , . . . は以下のように定義される．

f0 = 1
f1 = 1
fn = fn−1 + fn−2 (n ≥ 2 のとき)
フィボナッチ数列の一般項は以下の通り．
⎧√ n+1
1 ⎨ 1+ 5
fn = √
−
2
5⎩

√

1− 5
2

n+1

⎫
⎬
⎭

(1) フィボナッチ数 fn を計算する以下のアルゴリズムの実行時間を評価したい．
Fibonacci1(n)1:

If n = 0 or n = 1 then

2:
3:
4:

Return 1
Else
Return Fibonacci1(n − 1) + Fibonacci1(n − 2)(a) Fibonacci1(n) を実行した時，Fibonacci1(n − i) を呼び出す回数を gi とする．g0 = 1 と仮定し，g1 = 1 である．i ≥ 2 に対して，gi , gi−1 , gi−2 が満たす関係を表す式を答えよ．

(b) Fibonacci1(n) の実行時間を n に関する O 表記で答えよ．また，その理由を答えよ．

(2) 行列を用いるとフィボナッチ数列を以下のように表記できる．
fn
fn−1= An−1f1
f0

上記の表記をもとにフィボナッチ数を計算する以下のアルゴリズムを考える．A[0..1][0..1]
は 2 次元の配列である．

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

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

Fibonacci2(n)1:

If n = 0 or n = 1 then2:
3:

Return 1
Else

4:

A[0..1][0..1] = Power(n − 1)

5:

Return A[0][0] + A[0][1](a) 2 × 2 型の行列 A を答えよ．
(b) フィボナッチ数をより高速に計算したい．Fibonacci2(n) の 4 行目で呼び出
すアルゴリズム Power(n) は引数 n に対して An を計算する．An を計算す
る Power(n) の疑似コードを答えよ．より高速なアルゴリズムをより高く評価する．

(c) (b) で回答したアルゴリズム Power(n) の実行時間を n に関する O 表記で答えよ．また，その理由を答えよ．
【問２】B 木に関する次の各問いに答えよ．ただし，図 1, 2, 3 中の B 木にはレコード全体ではな
くキーのみ表記する．B 木は次数を持ち，図 1, 2, 3 中の B 木は 1 次 B 木である．また，

d 次 B 木の非ルートノードは d 以上 2d 以下のレコードを持つ．
(1) 次の各問いに答えよ．
(a) 図 1 の B 木に対し，キーが 6 のレコードを追加した後の B 木 T1 を答えよ．
2
図 1: 一つのノードからなる 1 次 B 木(b) (a) で得られた T1 にキーが 11 のレコードを追加した後の B 木を答えよ．
(c) 図 2 の B 木に対し，キーが 14 のレコードを追加した後の B 木を答えよ．

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

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

(2) 次の各問いに答えよ．
(a) 1 次 B 木の深さ 2 のすべてのノードで保持できる総レコード数の最大値を答えよ．例えば，図 3 の 1 次 B 木のように，深さ 1 のすべてのノードで保持できる
総レコード数は最大 6 個である．

図 3: 深さ 1 のノードすべてで保持できる総レコード数が最大となる 1 次 B 木(b) d 次 B 木において，深さ h > 0 のすべてのノードで保持できる総レコード数の最大値を答えよ．

(c) 高さ H の d 次 B 木の全てのノードで保持できる総レコード数の最大値を答えよ．
【問３】関係代数には和，差，共通部分，直積，選択，射影，結合，商の 8 つの演算が存在する．

R, S を関係とし，以下の各問いに答えよ．
(1) 共通部分 R ∩ S を関係代数の他の演算を用いて表せ．
(2) A, B をそれぞれ R と S の属性とした時，R と S の等結合 R[A = B]S を関係代数の他の演算を用いて表せ．

(3) A1 , . . . , An と B1 , . . . , Bm を，それぞれ関係 R と S の属性とする．ただし，n > m,dom(An−m+i ) = dom(Bi ) (i = 1, 2, . . . , m) とし，dom(X) は属性 X のドメインとする．この時，商 R ÷ S を関係代数の他の演算を用いて表せ．

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

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

Answer the following questions (【Q1】【Q2】【Q3】) and the write the number of the question
on the answer sheet.
【Q1】Answer the following questions. Fibonacci sequence f0 , f1 , f2 , . . . is deﬁned as follows.

f0 = 1,
f1 = 1, and
fn = fn−1 + fn−2 (n ≥ 2).
The general term of Fibonacci sequence is⎧√ n+1
1 ⎨ 1+ 5
fn = √
−
2
5⎩

√

1− 5
2

n+1

⎫
⎬
⎭

.

(1) We consider the execution time of the following algorithm, that computes Fibonacci
number fn .
Fibonacci1(n)1:

If n = 0 or n = 1 then

2:
3:
4:

Return 1
Else
Return Fibonacci1(n − 1) + Fibonacci1(n − 2)(a) Let gi be the number of calls of Fibonacci1(n−i) when we execute Fibonacci1(n).
We assume g0 = 1 and we have g1 = 1. Answer an equation that represents therelation between gi , gi−1 , gi−2 for i ≥ 2.
(b) Answer the execution time of Fibonacci1(n) in O-notation with respect to nwith reasons.
(2) We have the following description of Fibonacci sequence with a matrix.
fn
fn−1= An−1

f1
f0

We consider the following algorithm that computes a Fibonacci number based on
the above description. Let A[0..1][0..1] be a two-dimensional array.

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

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

Fibonacci2(n)1:

If n = 0 or n = 1 then2:
3:

Return 1
Else

4:

A[0..1][0..1] = Power(n − 1)

5:

Return A[0][0] + A[0][1](a) Answer 2 × 2 matrix A.
(b) We would like to compute a Fibonacci number faster. The algorithm Power(n)called in the fourth line of Fibonacci2(n) computes An for a given n. Answer
a pseudo code of Power(n) that computes An . A faster algorithm receives ahigher score.
(c) Answer the execution time of your algorithm Power(n) for (b) in O-notation
with respect to n with reasons.
【Q2】Answer the following questions about B-trees. In the B-trees of Figures 1, 2, and 3, only

the keys are shown, instead of the whole records. A B-tree has the order and the orderof the B-trees of Figures 1, 2, and 3 is 1. And a non-root node of B-trees of order d has
more than or equal to d and less than or equal to 2d records.
(1) Answer the following questions.
(a) Answer the B-tree T1 obtained by adding a record whose key is 6 to the tree
in Fig. 1.

2

Fig. 1: A B-tree of order 1 with one node(b) Answer the B-tree obtained by adding a record whose key is 11 to T1 obtainedin (a).
(c) Answer the B-tree obtained by adding a record whose key is 14 to the B-tree in
Fig. 2.

Fig. 2: A B-tree of order 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) Answer the following questions.
(a) Answer the maximum total number of records in all nodes of depth 2 in a B-treeof order 1. For example, the maximum total number of records in all nodes ofdepth 1 in a B-tree of order 1 is 6, as shown in Fig. 3.

Fig. 3: A B-tree of order 1 with the maximum number of records in all nodes ofdepth 1(b) Answer the maximum total number of records in all nodes of depth h > 0 in a
B-tree of order d.
(c) Answer the maximum total number of records in all nodes in a B-tree of order dwith height H.
【Q3】There exist 8 operators in relational algebra, union, diﬀerence, intersection, Cartesian

product, selection, projection, join, and division. For relations R and S, answer thefollowing questions.
(1) Answer an equivalent expression to intersection R ∩ S, using other operators ofrelational algebra.
(2) Let A and B be attributes in R and S, respectively. Then answer an equivalent
expression to equijoin of R and S, R[A = B]S, using other operators of relational
algebra.
(3) Let A1 , . . . , An and B1 , . . . , Bm be attributes of R and S, respectively, where n > m,dom(An−m+i ) = dom(Bi ) (i = 1, 2, . . . , m), and dom(X) denotes the domain of
attribute X. Then answer an equivalent expression to division R ÷ S, using otheroperators of relational algebra.

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

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

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

a
b
c
d

H

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

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

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

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

【問 2】5 つのステージからなるパイプライン式データパスを有するインオーダ型マイクロプロ
セッサについて考える．実装されたパイプラインステージは，IF（命令取得），ID（命令デコード），EX（実行），MEM（メモリアクセス），ならびに，WB（ライトバック）
である．また，同時発行可能な命令数は 1 と仮定する．以下の各問いに答えよ．

(1) プログラム実行時間 ET の式を IC ，CPI ，ならびに，F を用いて示せ．なお，IC は実行された命令の総数，CPI は 1 命令実行に要する平均クロックサイクル数，F はクロック周波数である．

(2) データ依存には「フロー依存」「出力依存」「逆依存」がある．このパイプライン式
データパスでデータハザードを引き起こす可能性のあるものを全て答えよ．

(3) フォワーディング技術の導入が IC ，CPI ，F に与える影響とその理由をそれぞれ述
べよ．なお，各パラメータにおいて影響がない場合は「影響なし」と答えること．
【問 3】コンピュータのメモリシステムについて，以下の各問いに答えよ．

(1) L1 キャッシュメモリを有するプロセッサを考える．動作周波数は 2 GHz，L1 キャッシュのアクセス時間は 1 クロックサイクル，L1 キャッシュヒット率は 70%，L1 キャッシュミスペナルティは 200 クロックサイクルである．このときの平均メモリアクセ
ス時間を求めよ．

(2) (1) に示したプロセッサの平均メモリアクセス時間を改善するため，L2 キャッシュメ
モリを L1 キャッシュメモリとメインメモリの間に追加した．L2 キャッシュのアク
セス時間は 20 クロックサイクル，L2 キャッシュのヒット率は 90%，L2 キャッシュ
ミスペナルティは 200 クロックサイクルであった．ただし，L2 キャッシュのヒット率は次式で与えられるものとする．

L2 キャッシュのヒット数
× 100
L2 キャッシュの総アクセス数
このプロセッサの平均メモリアクセス時間を求めよ．

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

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

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 the logic function H(a, b, c, d), which
represents the output of the subcircuit H. The minimum sum of products form of a logic
function means that having the smallest number of product terms 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 are chosen as the minimum
forms.

a
b
c
d

H

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

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

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

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

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

implemented pipeline stages are IF (Instruction Fetch), ID (Instruction Decode), EX(EXecution), MEM (MEMory access), and WB (Write Back). Assume the number of
instructions that can be issued in parallel is one. Answer the following questions.
(1) Show the equation of program execution time ET by using the three parameters,
IC, CPI, and F. Here, IC is the total number of instructions executed, CPI is theaverage number of clock cycles required to execute one instruction, and F is theclock frequency.
(2) There are three types of data dependencies, “ﬂow dependency,” “output dependency,” and “anti-dependency.” Answer all dependencies that could cause data
hazards in this pipelined datapath.
(3) Explain the eﬀects of introducing forwarding technique on IC, CPI, and F. If there
are no eﬀects on each parameter, answer “no eﬀects.”【Q3】Answer the following questions relating to computer memory systems.

(1) Consider a processor with an L1 cache memory. The operating frequency is 2 GHz,
the L1 cache access time is 1 clock cycle, the L1 cache hit rate is 70% and the L1
cache miss penalty is 200 clock cycles. Find the average memory access time of theprocessor.
(2) To improve the average memory access time of the processor shown in (1), an L2
cache memory is added between the L1 cache memory and the main memory. The
L2 cache access time is 20 clock cycles, the L2 cache hit rate is 90%, and the L2
cache miss penalty is 200 clock cycles. Where the L2 cache hit rate is given by thefollowing equation.
The number of L2 cache hits
× 100
The total number of L2 cache accesses
Find the average memory access time of the processor.