# 京大 情報学研究科 通信情報システムコース 2023年度 院試 過去問 解答例・解説

> 京大 情報学研究科 通信情報システムコース 2023年度の院試過去問、10項目の解説。テーマは正規表現・形式言語、固有値・固有ベクトル。大問1問の途中式・最終答を無料公開。解答PDFは5年分収録で2,880円。問題本文は非収録。

- Web版: https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/communications-and-computer-engineering/2023
- 解答・解説PDF: https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/communications-and-computer-engineering（税込2,880円、5年分を収録）
- 最終更新: 2026-11-16
- 公式の過去問: https://www.i.kyoto-u.ac.jp/admission/examarchive/（2021〜2025、公式の解答例: 解答例の掲載なし）
- 問題本文は収録していません。公式の問題と照らして読んでください。
- 大問ごとの解説は無料公開です。途中式と最終答は、ここに載っている大問を除き解答PDFに収録しています。

## 第1問 — A-1 微積分・線形代数

### 解説

**極座標の公式を覚えるだけにしない**

勾配の式は、$(z_r,z_\theta/r)$ が $(z_x,z_y)$ を回転したものだと見ると一行で示せる。
ラプラシアンは係数 $1/r$ が出る点が落とし穴である。これは基底ベクトルの長さが
$\theta$ 方向で $r$ 倍になることに対応している。

**ベータ関数の条件**

恒等式の証明で $q>1$ が必要なのは、$x=1$ における
$(1-x)^{q-1}$ の境界項を 0 にするためである。単に部分積分するだけでなく、境界項の消滅を
明記すると答案として安定する。

**固有空間の確認**

$A$ は対称行列なので異なる固有値の固有空間は直交する。
$\lambda=3$ の二次元空間 $x=y+z$ と、$\lambda=-3$ の方向 $(1,-1,-1)^T$ は実際に直交しており、
計算結果の検算になる。

### 解答

**(1) 極座標表示の微分公式**

$x=r\cos\theta,\ y=r\sin\theta$ とおく。連鎖律より

$$
z_r=z_x\cos\theta+z_y\sin\theta,\qquad
  z_\theta=-r z_x\sin\theta+r z_y\cos\theta
$$

である。したがって

$$
\begin{pmatrix} z_r\\ z_\theta/r \end{pmatrix}
  =
  \begin{pmatrix}
    \cos\theta&\sin\theta\\
    -\sin\theta&\cos\theta
  \end{pmatrix}
  \begin{pmatrix}z_x\\z_y\end{pmatrix}.
$$

右辺の行列は直交行列なのでノルムを保ち、

$$
z_x^2+z_y^2=z_r^2+\frac{1}{r^2}z_\theta^2
$$

が従う。

また

$$
\frac{\partial}{\partial x}
  =\cos\theta\frac{\partial}{\partial r}
   -\frac{\sin\theta}{r}\frac{\partial}{\partial\theta},
  \qquad
  \frac{\partial}{\partial y}
  =\sin\theta\frac{\partial}{\partial r}
   +\frac{\cos\theta}{r}\frac{\partial}{\partial\theta}
$$

である。これを $z$ に二度作用させ、$\theta_x=-\sin\theta/r$,
$\theta_y=\cos\theta/r$, $r_x=\cos\theta$, $r_y=\sin\theta$ を用いて
$x,y$ 方向の二階微分を足すと、一階微分係数の微分から出る項が整理されて

$$
z_{xx}+z_{yy}
  =z_{rr}+\frac{1}{r}z_r+\frac{1}{r^2}z_{\theta\theta}
$$

となる。

**(2) ベータ関数**

定義から

$$
B\!\left(\frac12,1\right)
  =\int_0^1 x^{-1/2}\,dx
  =2.
$$

また $x=\sin^2 u$ とおくと、$dx=2\sin u\cos u\,du$ であり、

$$
B\!\left(\frac12,\frac12\right)
  =\int_0^1\frac{dx}{\sqrt{x(1-x)}}
  =\int_0^{\pi/2}2\,du
  =\pi.
$$

最後に $p>0,\ q>1$ とする。部分積分により

$$
\begin{aligned}
  pB(p,q)
  &=\int_0^1 p x^{p-1}(1-x)^{q-1}\,dx\\
  &=\left[x^p(1-x)^{q-1}\right]_0^1
    +(q-1)\int_0^1 x^p(1-x)^{q-2}\,dx\\
  &=(q-1)B(p+1,q-1).
\end{aligned}
$$

境界項は $p>0,\ q>1$ の仮定により 0 である。

**(3) 固有値と固有ベクトル**

$$
A=\begin{pmatrix}
    1&2&2\\
    2&1&-2\\
    2&-2&1
  \end{pmatrix}
$$

について

$$
\det(\lambda I-A)
  =(\lambda-3)^2(\lambda+3)
$$

である。したがって固有値は

$$
\lambda=3\quad(\text{重複度 }2),\qquad \lambda=-3
$$

である。

$\lambda=3$ では

$$
(A-3I)\begin{pmatrix}x\\y\\z\end{pmatrix}=0
  \quad\Longleftrightarrow\quad x=y+z
$$

なので、固有ベクトル全体は

$$
\left\{\,s\begin{pmatrix}1\\1\\0\end{pmatrix}
    +t\begin{pmatrix}1\\0\\1\end{pmatrix}
    \;\middle|\; (s,t)\ne(0,0)\,\right\}.
$$

$\lambda=-3$ では固有空間は一次元であり、

$$
\left\{\,u\begin{pmatrix}1\\-1\\-1\end{pmatrix}
    \;\middle|\; u\ne0\,\right\}
$$

である。

### 最終答

$$
B\!\left(\frac12,1\right)=2,\qquad
B\!\left(\frac12,\frac12\right)=\pi,\qquad
\det(\lambda I-A)=(\lambda-3)^2(\lambda+3).
$$

固有値は $3,3,-3$。$\lambda=3$ の固有空間は $x=y+z$、$\lambda=-3$ の固有空間は
$\operatorname{span}\{(1,-1,-1)^T\}$。

## 第2問 — A-2 論理回路・順序回路

### 解説

**NAND 実現の見方**

積和形を NAND--NAND 形に直すときは、各積項の否定を先に作り、最後の NAND で
$\overline{\overline{P_1}\,\overline{P_2}\,\overline{P_3}}=P_1+P_2+P_3$
を使う。3 入力 NAND で 2 入力積項を扱う場合は、同じ入力を 2 本に複製してよい。

**Mealy 型が状態を減らせる理由**

Moore 型は出力を状態に持たせるため、認識直後の出力状態が必要になる。Mealy 型は遷移に出力を
持たせられるので、接頭辞 $1,11,111$ を覚える状態だけで済む。今回の符号は prefix-free なので、
認識後は必ず初期状態へ戻せる。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/communications-and-computer-engineering

## 第3問 — A-3 情報理論・符号化

### 解説

**2 次拡大情報源の平均符号長**

ハフマン符号の平均長は、2 記号を 1 ブロックとして計算した後、最後に 2 で割る。
この割り算を忘れると、情報源記号 1 個あたりの平均符号長ではなくブロックあたりの値になる。

**状態付き情報源のエントロピー**

状態遷移が出力記号に依存していても、状態が分かれば出力分布は $S_A$ または $S_B$ の
どちらかである。したがってエントロピー率は、定常分布で重み付けした条件付きエントロピーに
なる。

**巡回符号の検算**

$\deg G=4$ なので次元は $7-4=3$、符号語数は $2^3=8$ 個である。表に 8 個ちょうど並んで
いること、各多項式の次数が 6 以下であることが基本的な検算になる。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/communications-and-computer-engineering

## 第4問 — A-4 浮動小数点・パイプライン

### 解説

**非正規化数の指数**

非正規化数では仮数の暗黙の 1 が消える一方、指数は $1-\text{bias}$ を使う。
今回なら $2^{-2}$ に仮数 $F/16$ を掛けるため、最小刻みは $2^{-6}$ である。

**分岐予測の比較**

ループ分岐は最後だけ不成立になることが多い。常に成立と予測する方式は最後に 3 サイクル払う
だけなので、反復回数が多い場合に強い。一方、反復回数が少ない場合は、成立を外すたびに
1 サイクルだけ払う常に不成立方式が有利になる。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/communications-and-computer-engineering

## 第5問 — B-1 フーリエ変換・微分方程式

### 解説

**偶関数の利用**

どちらのフーリエ変換も偶関数なので、虚部は消え、$\cos$ 積分だけで計算できる。
$\omega=0$ は式に代入せず、面積または極限で扱う。

**留数計算の符号**

$\cosh z$ の零点は $i\pi/2$ から $i\pi$ 間隔で並ぶ。
分母の微分が $\sinh z$ であること、上半平面では $e^{iz}=e^{ix-y}$ が減衰することを
押さえると、閉路積分の向きと符号を誤りにくい。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/communications-and-computer-engineering

## 第6問 — B-2 電気回路

### 解説

**ブリッジ平衡の立て方**

中央枝に電流が流れないとき、中央上下の節点は同電位である。したがって左右それぞれの分圧比が
一致する。抵抗だけのホイートストンブリッジと同じ考え方を、複素インピーダンスに拡張すればよい。

**有限入力抵抗の影響**

増幅器の入力抵抗 $r_i$ が有限だと、帰還分圧点 $V_b$ から入力側へ電流が流れる。
そのため単純な $V_b=R_1V_2/(R_1+R_F)$ にはならない。理想利得の極限を取ると
非反転増幅器の標準利得 $1+R_F/R_1$ に戻る。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/communications-and-computer-engineering

## 第7問 — B-3 OFDM・待ち行列

### 解説

**CP 比率の扱い**

CP 長が最大遅延以上であることから $T_{\mathrm{CP}}\ge1\,\mu\mathrm{s}$ が先に決まる。
比率が $1:9$ なので有効シンボル長はその 9 倍であり、総シンボル長は 10 倍になる。
伝送速度の計算では CP を含む総時間で割る点が重要である。

**有限容量待ち行列**

状態 3 にいるときの到着はシステムに入らない。滞在時間に Little の法則を使うときは、
外部到着率 $\lambda$ ではなく、受理された実効到着率 $\lambda(1-P_{\mathrm{B}})$ を使う。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/communications-and-computer-engineering

## 第8問 — B-4 プロセッサ・キャッシュ

### 解説

**分岐即値**

分岐先オフセットはバイト差ではなく、左 2 ビットシフト前の word 単位の即値で指定する。
今回の戻り先は $PC+4$ から 12 byte 戻るため、即値は $-12/4=-3$ である。

**列優先アクセスの衝突**

ダイレクトマップでは「容量が足りそうか」だけでなく「同じ index に写るか」が重要である。
今回の 8 KiB キャッシュでは列方向ストライドが 16 ブロックで、32 行離れたブロックが同じ index
に写るため、同じブロックの隣接列を読む前に追い出される。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/communications-and-computer-engineering

## 第9問 — B-5 オートマトン・計算量

### 解説

**NFA の読み取り**

開始状態に $a,b$ の自己ループがあるため、受理に使う分岐を任意の位置まで遅らせられる。
その後に上側の $aa$ または下側の $bab$ を読み切って終わる必要があるので、言語は
「末尾条件」として表せる。

**NP と co-NP の関係**

$P$ は補集合で閉じている。したがって $P=NP$ が成り立つ世界では、NP も補集合で閉じて
$NP=co\text{-}NP$ になる。これと矛盾する $NP\ne co\text{-}NP$ が分かれば、$P=NP$ は否定される。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/communications-and-computer-engineering

## 第10問 — B-6 文脈自由文法・構文木

### 解説

**具象構文と抽象構文**

具象構文では括弧や優先順位が問題になるが、抽象構文では演算子の木構造だけを保存する。
そのため NNF 変換のような意味を保つ変換は、文字列ではなく AST 上で実装すると単純になる。

**NNF 変換の不変条件**

`nnf(e, neg)` は、`neg=False` なら $e$ と同値な NNF、`neg=True` なら $\neg e$ と同値な NNF を
返す関数である。この不変条件を置くと、二重否定、ド・モルガン律、原子命題への否定の停止条件が
自然に整理される。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/communications-and-computer-engineering

---

出典: 院試hub（https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/communications-and-computer-engineering/2023）。引用するときはWeb版のURLを示してください。
