# 九大 システム情報科学府 情報理工学専攻 専門科目（情報系4分野） 2022年度 院試 過去問 解答例・解説

> 九大 システム情報科学府 情報理工学専攻 専門科目（情報系4分野） 2022年度の院試過去問、4項目の解説。テーマは正規表現・形式言語。大問1問の途中式・最終答を無料公開。解答PDFは5年分収録で2,880円。問題本文は非収録。

- Web版: https://inshihub.com/exam-solutions/kyushu-university/graduate-school-of-information-science-and-electrical-engineering/information-science-specialized-subjects/2022
- 解答・解説PDF: https://inshihub.com/exam-solutions/kyushu-university/graduate-school-of-information-science-and-electrical-engineering/information-science-specialized-subjects（税込2,880円、5年分を収録）
- 最終更新: 2026-11-16
- 公式の過去問: https://www.isee.kyushu-u.ac.jp/admissions_master.html（令和4〜8年度（直近5年）、公式の解答例: 解答例の掲載なし）
- 問題本文は収録していません。公式の問題と照らして読んでください。
- 大問ごとの解説は無料公開です。途中式と最終答は、ここに載っている大問を除き解答PDFに収録しています。

## 第1問 — 情報理論

### 解説

**加法雑音通信路の見方**

第1問は、出力が入力から必ず1ビットだけ反転したベクトルになる、という通信路である。どのビットが反転するかを表す雑音 $Z$ を導入すると、対称な加法雑音通信路になる。対称通信路では一様入力が容量を達成するため、$H(Y)$ の最大値 $k$ から雑音の不確実性 $\log_2 k$ を引けばよい。

**エントロピーレートの計算**

マルコフ情報源では、現在状態 $i$ が分かっているときの次状態の不確実性を、定常確率 $\pi_i$ で平均する。行列全体のエントロピーを一度に計算しようとするより、各行の分岐だけを見る方がミスが少ない。

**ハフマン符号**

$(X_1,X_2)$ の確率は $\Pr(X_1=i,X_2=j)=\pi_i P_{ij}$ で求まる。ハフマン符号は同確率の項の結合順に自由度があるため、符号語そのものは一意ではない。重要なのは、確率の高い $(4,4)$ に短い符号を割り当て、接頭語条件と平均符号長を確認することである。

### 解答

**1. 通信路容量**

入力と出力を $\mathbb{F}_2^k$ 上のベクトルとみなす。この通信路は

$$
Y=X\oplus Z
$$

と書ける。ただし雑音 $Z$ はハミング重み $1$ の $k$ 個のベクトルのうち一つを等確率 $1/k$ でとる。したがって

$$
H(Y\mid X)=H(Z)=\log_2 k
$$

である。

任意の入力分布に対して

$$
I(X;Y)=H(Y)-H(Y\mid X)\leq k-\log_2 k
$$

である。一方、$X$ を $\mathbb{F}_2^k$ 上の一様分布にすると、加法雑音との和 $Y=X\oplus Z$ も一様分布になり $H(Y)=k$ となる。よって上限が達成される。

$$
C=k-\log_2 k \quad \text{bits/use}
$$

である。

**2. マルコフ情報源**

遷移確率行列を

$$
P=
\begin{pmatrix}
1/2&1/2&0&0\\
0&1/2&0&1/2\\
1/2&1/2&0&0\\
0&0&y&1-y
\end{pmatrix}
$$

とおく。

(1) 状態遷移は、非零確率だけを並べれば

$$
\begin{array}{c|c}
\text{状態} & \text{遷移先と確率}\\ \hline
1 & 1(1/2),\ 2(1/2)\\
2 & 2(1/2),\ 4(1/2)\\
3 & 1(1/2),\ 2(1/2)\\
4 & 3(y),\ 4(1-y)
\end{array}
$$

である。

(2) 定常分布を $\pi=(1/8,1/4,1/8,1/2)$ とする。第3成分について

$$
\pi_3=(\pi P)_3=\pi_4 y=\frac12 y
$$

であるから

$$
y=\frac14
$$

を得る。

(3) エントロピーレートは定常分布で平均した条件付きエントロピー

$$
H_{\infty}=\sum_i \pi_i H(P_{i,\cdot})
$$

である。第1,2,3行の分岐は二分岐等確率なので各 $1$ bit、第4行は $(1/4,3/4)$ なので $h_2(1/4)$ bit である。従って

$$
H_{\infty}
  =\frac18+\frac14+\frac18+\frac12 h_2\!\left(\frac14\right)
  =\frac12+\frac12 h_2\!\left(\frac14\right)
$$

である。数値では

$$
h_2(1/4)\simeq 0.8113,\qquad
  H_{\infty}\simeq 0.9056\ \text{bits/symbol}.
$$

(4) 定常状態から始めたときの $(X_1,X_2)$ の非零確率は

$$
\begin{array}{c|c}
(X_1,X_2) & \Pr(X_1,X_2)\\ \hline
(1,1),(1,2),(3,1),(3,2) & 1/16\\
(2,2),(2,4),(4,3) & 1/8\\
(4,4) & 3/8
\end{array}
$$

である。ハフマン符号の一例は次である。

$$
\begin{array}{c|c}
(X_1,X_2) & \text{符号語}\\ \hline
(4,4) & 11\\
(4,3) & 100\\
(2,2) & 010\\
(2,4) & 011\\
(3,1) & 000\\
(3,2) & 001\\
(1,1) & 1010\\
(1,2) & 1011
\end{array}
$$

この符号は接頭語条件を満たす。平均符号長は

$$
\frac38\cdot 2
  +3\cdot \frac18\cdot 3
  +2\cdot\frac1{16}\cdot 3
  +2\cdot\frac1{16}\cdot 4
  =\frac{11}{4}
$$

である。

### 最終答

$C=k-\log_2 k$ bits/use。定常分布条件から $y=1/4$、エントロピーレートは
$\frac12+\frac12 h_2(1/4)\simeq 0.9056$ bits/symbol。$(X_1,X_2)$ には上表のようなハフマン符号を与えればよい。

## 第2問 — オートマトンと言語

### 解説

**状態対の意味**

構成されたオートマトンでは、各入力記号が二つの成分を異なる速度で進める。$0$ は両成分を1ステップずつ、$1$ は第1成分を1ステップ、第2成分を2ステップ進める。この「ステップ数」に言い換えれば、複雑に見える遷移式を単なる剰余計算として処理できる。

**部分文字列数の差**

$L_2$ で使う事実は、文字列を左から右へ見たとき、$a$ から $b$ への切替回数が $\#_{ab}$、$b$ から $a$ への切替回数が $\#_{ba}$ になることである。切替回数の差は先頭と末尾の組だけで決まるため、有限オートマトンで判定できる。

**文脈自由文法の確認**

$L_5$ の文法では、$A$ が $a$ と対応する $b$ を作り、$C$ が $c$ と対応する $b$ を作る。連結すると $a^i b^i b^k c^k=a^i b^{i+k}c^k$ となり、条件 $j=i+k$ をちょうど満たす。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/kyushu-university/graduate-school-of-information-science-and-electrical-engineering/information-science-specialized-subjects

## 第3問 — アルゴリズム・プログラミング

### 解説

**再帰処理の不変量**

recur_NumList(alist, newL) では、newL に「すでに見た部分から取り出した数値」を蓄積する、と決めておくと空欄が自然に決まる。先頭がリストなら、そのリストを先に再帰処理してから残りに進む。

**自然結合でタプルが増える理由**

射影で $\mathrm{Id}$ を落とした $S_2$ は、同姓同名の区別を失う。したがって $\mathrm{Tanaka}$ の行が自然結合時に組合せとして増え、元の $S$ より大きい関係になる。可逆に分解するには、結合キーとして一意に行を識別できる属性を残す必要がある。

**関係除算**

$R\div T$ は「$T$ に含まれる全ての値に対して、対応する組が $R$ に存在するもの」を返す演算である。全称条件を処理していると考えると、$(R\times S)\div T$ の答えも $R$ の $A1=02$ と $A1=04$ に共通する $A2$ を探す問題に帰着する。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/kyushu-university/graduate-school-of-information-science-and-electrical-engineering/information-science-specialized-subjects

## 第4問 — 計算機アーキテクチャ

### 解説

**ドントケアを使う理由**

部分回路 $F$ の出力 $f$ は直接表で与えられていない。$G_1,G_2$ の表を通して、指定された $X,Y$ を再現できる $f$ を逆算する。入力によっては $f=0$ でも $f=1$ でも同じ $X,Y$ になるため、その入力はドントケアとして簡単化に利用できる。

**ストール数の数え方**

RAW ハザードは、消費命令の ID が生産命令の WB より前に来ると発生する。この問題では「WB と同じサイクルの ID 読み出しは可能」と明記されているため、消費命令の ID を生産命令の WB と同じサイクルまで遅らせればよい。

**性能向上率**

サイクル数だけなら $14/12$ 倍だが、拡張でクロック周波数が下がる。実行時間で比較し、$T_{\mathrm{old}}/T_{\mathrm{new}}$ を取ると、周波数低下を含む実効的な速度向上が得られる。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/kyushu-university/graduate-school-of-information-science-and-electrical-engineering/information-science-specialized-subjects

---

出典: 院試hub（https://inshihub.com/exam-solutions/kyushu-university/graduate-school-of-information-science-and-electrical-engineering/information-science-specialized-subjects/2022）。引用するときはWeb版のURLを示してください。
