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

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

- Web版: https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/communications-and-computer-engineering/2024
- 解答・解説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 解析・線形代数

### 解説

**ガウス積分の使い方**

二重積分では平面全体を極座標で積分できるため、$\int e^{-x^2}dx$ を直接計算せずに、その二乗を先に求めるのが標準的である。ここでは $I=J^2$ とできること、さらに $J>0$ であることを明記して平方根の符号を決める。

**ガンマ関数への接続**

$\Gamma(1/2)$ は $t=u^2$ の置換でガウス積分そのものに帰着する。$t^{-1/2}$ と $dt=2u\,du$ が打ち消し合うため、特異性を気にせず積分できる。

**行列冪の考え方**

固有値が互いに異なるので行列は対角化可能である。固有ベクトルを列に並べた $P$ を作り、$A^n=PD^nP^{-1}$ とすれば、各成分は $1^n,2^n,3^n$ の線形結合として求まる。最後に $n=1$ を代入して元の $A$ に戻ることを確認すると、符号ミスを検出しやすい。

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

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

### 解説

**組合せ論理の最小化**

最小積和形で「すべて求めよ」とある場合は、1つの式を出すだけでなく、同じコストの別解がないことにも触れると答案として強い。ここでは必須主項が3つあり、それらだけで全ミン項を覆うため一意性まで言える。

**NAND 実現**

NAND-NAND 形では、各積項の否定を1段目で作り、最後の NAND でド・モルガンにより和を作る。入力の否定が与えられているため、インバータ用の追加ゲートは不要である。

**順序回路の状態数**

この回路では「連続したか」を判定するために直前入力が必要であり、「反転後の現在出力」を保持する必要もある。したがって $(p,z)$ の4通りが自然な状態である。同じ出力を持つ状態同士も次入力で区別できるため、状態最小化で統合できない。

### 解答

- 変数の順を $a,b,c,d$ とする。与えられた関数を真理値表に直すと、$f=1$ となるミン項は

$$
m(0,1,2,4,6,10,12,14)
$$

である。カルノー図または Quine--McCluskey 法で主項を整理すると、主項は

$$
c\bar d,\qquad b\bar d,\qquad \bar a\bar d,\qquad \bar a\bar b\bar c
$$

であり、ミン項 $10,12,1$ をそれぞれ覆うために

$$
c\bar d,\qquad b\bar d,\qquad \bar a\bar b\bar c
$$

が必須である。したがって最小積和形は一意に

$$
f=c\bar d+b\bar d+\bar a\bar b\bar c
$$

である。
3入力 NAND ゲートだけで実現するには、2リテラル項では同じ入力を2本に結線する。次の4個の NAND ゲートでよい。

$$
\begin{aligned}
  u_1&=\operatorname{NAND}(c,\bar d,\bar d)=\overline{c\bar d},\\
  u_2&=\operatorname{NAND}(b,\bar d,\bar d)=\overline{b\bar d},\\
  u_3&=\operatorname{NAND}(\bar a,\bar b,\bar c)=\overline{\bar a\bar b\bar c},\\
  f&=\operatorname{NAND}(u_1,u_2,u_3).
\end{aligned}
$$

3個の積項が必要なので各積項の否定を作るゲートが少なくとも3個、さらに和を作る最後の NAND が1個必要であり、4ゲートが最小である。
$\bar f$ の最小積和形を求めて双対を取ると、最小和積形は

$$
f=(\bar c+\bar d)(\bar b+\bar d)(\bar a+b+c)
$$

である。これも各和項が必須なので一意である。
最後に $f=(g\oplus h)+r$ を満たす $h$ を求める。$r=1$ の入力では右辺が必ず1になるため、まず $r=1\Rightarrow f=1$ が必要である。この条件は満たされる。$r=0$ の入力では

$$
h=f\oplus g
$$

が強制され、$r=1$ の入力は $h$ のドントケアとして使える。これを最小化すると

$$
h=c\bar d+\bar b\bar d+\bar a b c
$$

が、積項数最小かつリテラル数最小の積和形である。
- 状態を「直前の入力 $p$」と「現在の出力 $z$」の組 $(p,z)$ で表す。入力 $x$ が直前入力と等しいときだけ次サイクルの出力が反転するので、遷移は

$$
(p,z)\xrightarrow{x}(x,\ z\oplus [x=p])
$$

である。したがって状態遷移表は次のようになる。

$$
\begin{array}{c|cc|c}
\text{状態 }(p,z)&x=0&x=1&\text{出力}\\ \hline
S_0=(0,0)&S_1&S_2&0\\
S_1=(0,1)&S_0&S_3&1\\
S_2=(1,0)&S_0&S_3&0\\
S_3=(1,1)&S_1&S_2&1
\end{array}
$$

出力が異なる状態は同値でない。さらに、同じ出力を持つ $S_0,S_2$ は入力0で次状態の出力が異なり、$S_1,S_3$ も入力0で次状態の出力が異なる。よって4状態が最小である。
最小の D フリップフロップ数は $\lceil\log_2 4\rceil=2$ である。状態割当を

$$
q_1=p,\qquad q_2=z
$$

とすれば、出力は

$$
z=q_2
$$

であり、D入力は

$$
d_1=x
$$

および

$$
d_2=\bar x\,\bar q_1\,\bar q_2+\bar x\,q_1q_2
      +x\,\bar q_1q_2+x\,q_1\bar q_2
$$

である。

### 最終答

$$
f=c\bar d+b\bar d+\bar a\bar b\bar c
  =(\bar c+\bar d)(\bar b+\bar d)(\bar a+b+c),
$$

3入力 NAND では

$$
u_1=\overline{c\bar d},\quad
u_2=\overline{b\bar d},\quad
u_3=\overline{\bar a\bar b\bar c},\quad
f=\overline{u_1u_2u_3}
$$

の4ゲート構成が最小である。また

$$
h=c\bar d+\bar b\bar d+\bar a b c.
$$

順序回路は4状態、2個の D フリップフロップで実現でき、

$$
d_1=x,\qquad
  d_2=\bar x\,\bar q_1\,\bar q_2+\bar x\,q_1q_2+x\,\bar q_1q_2+x\,q_1\bar q_2,\qquad
  z=q_2.
$$

## 第3問 — A-3 情報理論

### 解説

**表の対数値の使い方**

確率を分数に直すと、表にある $\log_2 3,\log_2 5,\log_2 7,\log_2 13$ だけで計算できる。たとえば $0.65=13/20$ なので $\log_2(1/0.65)=\log_2(20/13)$ と変形する。

**適中率と相互情報量の違い**

適中率は最も多い天気に寄せるだけでも高くなる場合がある。一方、相互情報量は $X$ と $Y$ の統計的依存を測る。今回の値は小さいが正なので、予報は完全に無意味ではない。ただし適中率という実用指標では常時晴予測を上回っていない。

**マルコフ誤り源の容量**

ビット誤り率だけから $1-\mathcal H(p_e)$ としてしまうと、誤りの時間相関を捨てることになる。マルコフ誤り源では状態ごとの遷移エントロピーを定常分布で平均したエントロピー率を使う。

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

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

### 解説

**2の補数の範囲**

$n$ ビットの2の補数では最上位ビットの重みが $-2^{n-1}$ になる。5ビットなら範囲は $[-16,15]$ であり、正数同士の加算で符号ビットが1になる場合はオーバーフローを疑う。

**分岐予測は周期列で考える**

このコードでは各分岐の結果が $i\bmod 7$ だけで決まる。したがって、無限大に近い $N$ では初期状態の影響は無視でき、周期7の中で何回外れるかを数えればよい。共有カウンタでは、同じ $i$ の中でも $L2$ の結果が $L3$ に、$L3$ の結果が $L4$ に影響する点が重要である。

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

## 第5問 — B-1 フーリエ解析と複素積分

### 解説

**矩形関数と sinc 型積分**

矩形関数のフーリエ変換は sinc 型になる。パーセバルの等式を使うと、直接扱いにくい $(\sin x/x)^2$ の広義積分を、時間領域の区間長から一気に求められる。

**同次形微分方程式**

$x^2$ と $y^2$ と $xy\,dy/dx$ が同じ次数で現れるため、$y=vx$ が自然な置換である。最後の $x^2+y^2=Cx$ は円族を表し、暗黙微分で元の方程式に戻ることを確認できる。

**留数計算の符号**

$\sin x$ を扱うときは、まず $e^{ix}$ の積分を計算し、最後に虚部を取ると極の選択が明確になる。上半平面を使うのは $e^{iz}=e^{ix-y}$ が減衰するからである。

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

## 第6問 — B-2 電磁気・回路・アンテナ

### 解説

**等電位線は距離比で決まる**

電位0の条件では、電荷量の比 $1:3$ が距離の比に変換される。すなわち $3/\rho_2=1/\rho_1$ なので、強い正電荷からの距離が負電荷からの距離の3倍になる点の軌跡である。これはアポロニウスの円である。

**演算増幅器回路の見方**

理想演算増幅器では入力電流が0、負帰還時に $V_+=V_-$ とみなせる。したがって、まず受動RC網だけで $V_+$ を $V_1,V_2$ の関数として求め、最後に $V_+=V_2$ を代入するのが最短である。

**アレーの位相差**

アレーファクタは、観測方向に対する素子間の経路差を位相差に直したものを足し合わせるだけで得られる。等振幅・同位相・等間隔アレーでは等比数列の和になるため、主ローブとサイドローブの形が $\sin N\psi/2$ と $\sin\psi/2$ の比で表される。

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

## 第7問 — B-3 変復調とポアソン過程

### 解説

**搬送波の有無**

AMとDSB-SCの違いは、式では定数項1があるかどうか、スペクトルでは $\pm f_c$ の線スペクトルがあるかどうかに現れる。情報を運ぶのは側波帯であり、搬送波成分自体はベースバンド信号を含まない。

**同期検波で残る雑音**

同相成分 $n_I(t)$ は信号と同じ $\cos2\pi f_ct$ に乗っているため、同期検波後にベースバンドへ落ちる。一方、直交成分 $n_Q(t)$ は $\sin2\pi f_ct$ に乗っており、理想的な同相検波では低域成分として残らない。

**ポアソン過程の基本性質**

到着回数の平均は $\lambda t$、到着間隔は指数分布で平均 $1/\lambda$ である。独立なポアソン過程の和が再びポアソン過程になることは、二項定理で確率を畳み込むとすぐに分かる。

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

## 第8問 — B-4 二部グラフとマッチング

### 解説

**完全マッチングを否定する方法**

二部グラフで完全マッチングがないことを示すには、Hall条件を破る部分集合を1つ示せばよい。$G_b$ では右側の $\{6,7,8\}$ が左側の $\{1,2\}$ だけにしか接続しないため、3個の頂点を2個の頂点でしか受けられない。

**増大道の役割**

マッチングの大きさを増やす操作は、増大道に沿って辺の採否を反転することに尽きる。未飽和頂点から未飽和頂点へ、非マッチング辺とマッチング辺を交互にたどる道を見つけるのがアルゴリズムの中心である。

**最大独立集合の対称差**

$A\triangle B$ による誘導部分グラフでHall条件を証明するときは、近傍が足りないと仮定して、$B$ の一部を $A$ 側の頂点で置き換える。この置き換えでより大きい独立集合が作れてしまう、という矛盾が本質である。

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

## 第9問 — B-5 形式言語と計算量

### 解説

**NFAとDFAの違い**

NFAでは遷移が存在しない入力があってもよく、最後の $a$ を非決定的に選ぶような簡潔な設計ができる。DFAではすべての入力に対して次状態が一意に決まる必要があるため、沈み状態や「最後の文字」を覚える状態が必要になる。

**言語クラスの見分け方**

有限長制限や偶奇だけの条件は正規言語で扱える。回文は中央を境に左右を照合するためスタックで扱え、文脈自由である。平方数長やコピー言語は、有限オートマトンや1本のスタックでは必要な情報を保持できない典型例である。

**時間と空間の関係**

時間制限は空間制限より強い条件である。多項式時間で止まる計算は、多項式個を超えるセルを訪問する前に時間切れになるため、多項式空間にも収まる。

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

## 第10問 — B-6 文脈自由文法とインタプリタ

### 解説

**曖昧性の示し方**

曖昧性は、同じ終端記号列に対して異なる構文木を2つ示せば十分である。優先順位のない式文法では、$+$ と $*$ のどちらを根にするかが選べてしまうため、典型的に曖昧になる。

**優先順位と結合性**

非曖昧文法では、加算を扱う非終端 $E$、乗算を扱う非終端 $T$、原子式 $F$ に層を分ける。上位の $E$ から下位の $T$ を呼ぶ構造にすると、$*$ が $+$ より先にまとまる。

**環境つき評価**

変数を持つ式では、変数名を値へ対応させる環境が必要である。let は環境を拡張して本体を評価する構文であり、束縛の有効範囲を明確に扱える。

途中式と最終答は解答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/2024）。引用するときはWeb版のURLを示してください。
