# 阪大 情報科学研究科 情報数理学専攻 専門科目（情報数理学） 2022年度 院試 過去問 解答例・解説

> 阪大 情報科学研究科 情報数理学専攻 専門科目（情報数理学） 2022年度の院試過去問、4項目の解説。テーマはフーリエ変換、静電場。大問1問の途中式・最終答を無料公開。解答PDFは6年分収録で3,200円。問題本文は非収録。

- Web版: https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-and-physical-sciences/2022
- 解答・解説PDF: https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-and-physical-sciences（税込3,200円、6年分を収録）
- 最終更新: 2026-11-16
- 公式の過去問: https://www.ist.osaka-u.ac.jp/japanese/examinees/admission/past-exam.php（専攻・科目別に掲載（情報基礎数学は2005〜2026年度、情報数理・生物情報は2022〜2026年度など）、公式の解答例: 解答例の掲載なし）
- 問題本文は収録していません。公式の問題と照らして読んでください。
- 大問ごとの解説は無料公開です。途中式と最終答は、ここに載っている大問を除き解答PDFに収録しています。

## 第1問 — 情報基礎

### 解説

**中央の配列で分解する**

条件 $X_i

**なぜ二分探索で十分か**

`sort` 後の配列では、条件 $D_mc$ を満たす部分は末尾側に連続する。この境界位置だけを見つければ個数が分かるため、全要素を数える必要がない。

#### 2. 符号付き和の判定

- $s_i\in\{1,-1\}$ で

$$
\sum_{i=1}^n c_i s_i=0
$$

となるかを調べる。これは、$s_i=1$ とする添字集合を $S$ とおくと

$$
\sum_{i\in S}c_i-\sum_{i\notin S}c_i=0
$$

すなわち

$$
\sum_{i\in S}c_i=\frac12\sum_{i=1}^n c_i
$$

となる部分集合があるかを調べる問題である。
したがって、全体和 $C=\sum_i c_i$ が奇数なら直ちに「なし」と判定する。$C$ が偶数のとき、目標値 $C/2$ に対する部分和問題として動的計画法を用いる。$T=C/2$ とし、$d[i,t]$ を「先頭 $i$ 個の整数からいくつか選んで和 $t$ を作れるか」とする。初期条件を

$$
d[0,0]=\text{true},\qquad d[0,t]=\text{false}\quad (t>0)
$$

とし、

$$
d[i,t]=d[i-1,t]\lor d[i-1,t-c_i]
$$

で更新する。ただし $t-c_i
- 上の動的計画法では、表の大きさは $(n+1)(T+1)$ であり、各成分は定数時間で計算できる。したがって時間計算量は

$$
O(nT)=O\left(n\sum_{i=1}^n c_i\right)
$$

である。入力整数の大きさを値そのものとして測ると擬多項式時間である。
- 判定問題DがNPに属することを示すには、証拠を多項式時間で検証できればよい。証拠として符号列

$$
(s_1,\ldots,s_n)\in\{1,-1\}^n
$$

を与える。この長さは $n$ で入力長に対して多項式である。検証者は各 $s_i$ が $1$ または $-1$ であることを確認し、和 $\sum_i c_i s_i$ を計算して $0$ かどうかを調べる。これは $n$ 回の加算と乗算で済むので、多項式時間である。よって判定問題DはNPに属する。

**符号問題は分割問題**

$+1$ を付ける整数と $-1$ を付ける整数に分けると、両群の和が等しいかを問う形になる。したがって、全体和が奇数ならそもそも不可能であり、偶数なら半分の和を作れるかを調べればよい。

**NP所属で示すこと**

NPに属することは「速く解ける」ことではない。解候補が与えられたとき、それが正しいことを速く確認できることを示す。ここでは符号列を受け取り、和が0かどうかを計算するだけでよい。

#### 3. 連結無向グラフの直径・半径・次数

- 図のグラフでは、最長の最短距離は例えば $v_8$ と $v_4$ の間で達成され、長さは

$$
4
$$

である。したがって直径は $4$ である。
各頂点から最も遠い頂点までの距離を調べると、$v_2$ からはすべての頂点へ距離 $2$ 以下で到達できる。一方、他の頂点では最大距離が少なくとも $3$ になる。よって中心は

$$
v_2
$$

であり、半径は

$$
2
$$

である。最大次数は、$v_3$ が $v_2,v_4,v_6,v_5$ と接続しているので

$$
4
$$

である。
- 成り立つ。中心を $c$ とし、直径を実現する2頂点を $u,v$ とする。中心の定義から

$$
\operatorname{dist}(u,c)\le r,\qquad
  \operatorname{dist}(c,v)\le r
$$

である。三角不等式より

$$
d=\operatorname{dist}(u,v)
  \le \operatorname{dist}(u,c)+\operatorname{dist}(c,v)
  \le 2r
$$

なので $d/2\le r$ である。また、半径はある頂点から他の頂点までの距離の最大値であり、直径は任意の2頂点間距離の最大値なので、任意の頂点の離心度は $d$ 以下である。したがって $r\le d$ である。以上より

$$
\frac d2\le r\le d
$$

が成り立つ。
- 成り立つ。中心からの幅優先探索を考えると、距離0の層は1個、距離1の層は高々 $p$ 個、距離 $i\ge2$ の層は、親へ戻る辺を除いて高々

$$
p(p-1)^{i-1}
$$

個である。したがって

$$
|V|\le 1+p\sum_{i=0}^{r-1}(p-1)^i
$$

である。この右辺は $p\ge2$ なら

$$
1+p+p^2+\cdots+p^r
$$

以下である。$p=1$ の連結グラフは高々2頂点なので、$r=0$ または $r=1$ で直接確認できる。よって任意の連結グラフについて

$$
|V|\le \sum_{i=0}^r p^i
$$

が成り立つ。

**中心は平均的に近い頂点ではない**

中心は、他の頂点までの距離の平均ではなく、最大距離を最小にする頂点である。したがって全頂点への距離を見て、最も遠い頂点までの距離だけを比較する。

**半径と直径の関係**

$r\le d$ は定義から直ちに分かる。$d\le2r$ は中心を経由する道で直径を実現する2頂点を結ぶ、という三角不等式の使い方が核心である。

**最大次数による頂点数評価**

中心から幅優先探索木を伸ばすと、距離1では高々 $p$ 個、距離2以降では親へ戻る辺を除いて高々 $p-1$ 本ずつ枝分かれする。このため精密な上界は $1+p+p(p-1)+\cdots$ であり、$p^i$ を用いた和はそれより粗いが扱いやすい上界である。

### 解答

1. 3配列の大小関係の数え上げ

- アルゴリズムAは、添字の三つ組 $(i,j,k)$ のうち

$$
X_i
- $Y_j$ を中央の値として固定すると、条件を満たす $X_i$ の個数は

$$
e=\operatorname{less}(X,Y_j)
$$

であり、条件を満たす $Z_k$ の個数は

$$
z=\operatorname{greater}(Z,Y_j)
$$

である。これらは独立に選べるので、その $j$ に対する三つ組の個数は $ez$ である。したがって空欄は

$$
p\leftarrow p+e z
$$

とすればよい。
- 配列が昇順に整列済みなので、$\operatorname{less}(D,c)$ は二分探索で求める。具体的には、$D_mc$ となる最初の位置を二分探索し、そこから末尾までの要素数を返す。
いずれも探索範囲を各反復で半分にできるため $O(\log n)$ 時間で実行できる。アルゴリズムBでは整列に $O(n\log n)$、各 $j$ に対して二分探索を2回行う部分に $O(n\log n)$ かかるので、全体は

$$
O(n\log n)
$$

である。

### 最終答

Aは $X_i部分集合和 $\sum_{i\in S}c_i=(1/2)\sum_i c_i$ に帰着し、動的計画法で $O(n\sum_i c_i)$ 時間。符号列を証拠として和を検証できるためNPに属する。

図のグラフは直径 $4$、中心 $v_2$、半径 $2$、最大次数 $4$。一般に $d/2\le r\le d$ は成り立つ。最大次数 $p$ と半径 $r$ からは幅優先探索で $|V|\le 1+p\sum_{i=0}^{r-1}(p-1)^i\le\sum_{i=0}^r p^i$ と評価できる。

## 第2問 — 数理基礎

### 解説

**尤度比順に選ぶ**

$x_i$ は「状態 $i$ のときに $Z=1$ と判定する確率」と読める。$Q$ の下での期待値を $\theta$ 以下に抑えながら $P$ の下での期待値を最大にするので、効率 $p_i/q_i$ が高い状態から採用するのが自然である。

**双対の意味**

双対変数 $\lambda$ は制約 $E_Q[Z]\le\theta$ の価格である。$\lambda$ を固定すると、$p_i-q_i\lambda$ が正の状態だけが採用される。これは比 $p_i/q_i$ がしきい値 $\lambda$ を超える状態を選ぶという形で、(2) の解と対応している。

#### 2. 超立方体内の2点間距離

$X=(X_1,\ldots,X_n)$, $Y=(Y_1,\ldots,Y_n)$ とする。各座標について $X_i,Y_i$ は独立な $[0,1]$ 上一様分布である。

- $D_1=|X_1-Y_1|$ とおく。$D_1$ の密度は

$$
f_{D_1}(d)=2(1-d)\qquad (0\le d\le1)
$$

である。したがって

$$
E[D_1]=\int_0^1 2d(1-d)\,dd=\frac13
$$

であり、

$$
E[D_1^2]=\int_0^1 2d^2(1-d)\,dd=\frac16
$$

なので

$$
V[D_1]=\frac16-\left(\frac13\right)^2=\frac1{18}
$$

である。
- $D_1^2$ の期待値は上で求めた通り

$$
E[D_1^2]=\frac16
$$

である。また

$$
E[D_1^4]=\int_0^1 2d^4(1-d)\,dd=\frac1{15}
$$

なので

$$
V[D_1^2]=E[D_1^4]-\{E[D_1^2]\}^2
  =\frac1{15}-\frac1{36}
  =\frac7{180}.
$$

-

$$
D_n^2=\sum_{i=1}^n (X_i-Y_i)^2
$$

であり、各項は独立同分布である。したがって

$$
E[D_n^2]=nE[D_1^2]=\frac n6
$$

であり、

$$
V[D_n^2]=nV[D_1^2]=\frac{7n}{180}
$$

である。
- $D_n^2/n$ は独立同分布な確率変数 $(X_i-Y_i)^2$ の標本平均である。大数の法則により

$$
\frac{D_n^2}{n}\to \frac16
$$

に確率収束する。さらに中心極限定理より

$$
\sqrt{n}\left(\frac{D_n^2}{n}-\frac16\right)
  \Rightarrow N\left(0,\frac7{180}\right)
$$

である。したがって $n$ が大きいとき、$D_n^2/n$ は近似的に

$$
N\left(\frac16,\frac{7}{180n}\right)
$$

に従い、極限では $1/6$ に集中する。

**1次元の差から始める**

高次元距離の2乗は座標ごとの差の2乗の和である。したがって、まず1次元で $|X-Y|$ の分布を求め、独立な和として期待値と分散を足し上げるのが最短である。

**距離の集中**

高次元では、距離の2乗を次元で割った量が平均値 $1/6$ の近くに集中する。これは高次元立方体内のランダムな2点間距離が、次元で正規化するとほぼ一定になることを意味する。

#### 3. 3変数二値分布の最尤推定

- 対数尤度は

$$
L=\sum_{k=1}^N f(s_1^{(k)},s_2^{(k)},s_3^{(k)})-N\log Z
$$

である。例えば $\theta_i$ で微分すると

$$
\frac{\partial L}{\partial\theta_i}
  =\sum_{k=1}^N s_i^{(k)}
  -N\frac1Z\frac{\partial Z}{\partial\theta_i}.
$$

ここで

$$
\frac1Z\frac{\partial Z}{\partial\theta_i}
  =
  \sum_{x\in\{0,1\}^3}x_i p(x)
  =E[X_i]
$$

であるから

$$
\frac{\partial L}{\partial\theta_i}
  =\sum_{k=1}^N s_i^{(k)}-NE[X_i]
$$

を得る。$\theta_{ij}$ についても同様に

$$
\frac1Z\frac{\partial Z}{\partial\theta_{ij}}=E[X_iX_j]
$$

なので、与えられた式が従う。
- 最尤推定では尤度方程式から、モデルの期待値が標本平均に一致する。与えられた度数から

$$
\begin{aligned}
  E[X_1]&=\frac{2+1+5}{16}=\frac12,\\
  E[X_2]&=\frac{3+3+1+5}{16}=\frac34,\\
  E[X_3]&=\frac{2+3+5}{16}=\frac58,
\end{aligned}
$$

また

$$
\begin{aligned}
  E[X_1X_2]&=\frac{1+5}{16}=\frac38,\\
  E[X_2X_3]&=\frac{3+5}{16}=\frac12,\\
  E[X_3X_1]&=\frac{5}{16}.
\end{aligned}
$$

-

$$
E[X_1]E[X_2]=\frac12\cdot\frac34=\frac38=E[X_1X_2]
$$

である。二値変数では $P(X_i=1,X_j=1)=P(X_i=1)P(X_j=1)$ が成り立てば、残りの組合せの確率も周辺確率から決まるため独立である。よって $X_1$ と $X_2$ は独立である。
同様に

$$
E[X_1]E[X_3]=\frac12\cdot\frac58=\frac5{16}=E[X_1X_3]
$$

なので、$X_1$ と $X_3$ も独立である。
- $t=E[X_1X_2X_3]=p(1,1,1)$ とおく。上で求めた1次・2次モーメントから各同時確率は

$$
\begin{array}{c|c}
(x_1,x_2,x_3) & p(x_1,x_2,x_3)\\ \hline
(1,1,1) & t\\
(1,1,0) & \frac38-t\\
(1,0,1) & \frac5{16}-t\\
(0,1,1) & \frac12-t\\
(1,0,0) & t-\frac3{16}\\
(0,1,0) & t-\frac18\\
(0,0,1) & t-\frac3{16}\\
(0,0,0) & \frac5{16}-t
\end{array}
$$

と表せる。
このモデルには3体相互作用項がないので、対数確率の3次交互作用は0である。すなわち

$$
\log p_{111}-\log p_{110}-\log p_{101}-\log p_{011}
  +\log p_{100}+\log p_{010}+\log p_{001}-\log p_{000}=0
$$

であり、

$$
p_{111}p_{100}p_{010}p_{001}
  =
  p_{110}p_{101}p_{011}p_{000}
$$

が成り立つ。上の表を代入すると

$$
t\left(t-\frac3{16}\right)^2\left(t-\frac18\right)
  =
  \left(\frac38-t\right)
  \left(\frac5{16}-t\right)^2
  \left(\frac12-t\right).
$$

非負性から $3/16\le t\le5/16$ であり、この範囲の解は

$$
t=\frac14
$$

である。したがって

$$
E[X_1X_2X_3]=\frac14.
$$

**指数型分布族の最尤方程式**

指数型分布族では、自然パラメータで微分すると「観測された十分統計量の合計」から「モデルの期待値に $N$ を掛けたもの」を引いた形になる。最尤点ではこれが0になるため、十分統計量の経験平均とモデル平均が一致する。

**二値変数の独立性**

0/1変数では、$E[X_i]=P(X_i=1)$、$E[X_iX_j]=P(X_i=1,X_j=1)$ である。したがって積率の等式 $E[X_iX_j]=E[X_i]E[X_j]$ は、1になる事象どうしの積の確率が積に分解することを意味し、二値の場合は独立性そのものになる。

**3体項がないことの使い方**

1次と2次の期待値だけでは一般には $E[X_1X_2X_3]$ は決まらない。しかし本問のモデルは2体相互作用までしか持たないため、対数線形モデルの3次交互作用が0という追加条件が入る。これが最後の方程式になり、三重積の期待値を決める。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-and-physical-sciences

## 第3問 — 数学解析

### 解説

**複素数化で一変数にする**

係数行列

$$
\begin{pmatrix}-1&-1\\1&-1\end{pmatrix}
$$

は、複素数 $w=x+iy$ に対する掛け算 $(-1+i)w$ に対応する。外力も $\cos t+i\sin t=e^{it}$ と書けるため、連立方程式を一つの複素一次方程式として解ける。

**軌跡の読み取り**

初期値0の解は $w=(1-e^{-t})e^{it}$ である。角度は $t$ とともに増え、半径は $0$ から $1$ へ単調に増える。したがって単なる円運動ではなく、単位円を極限円とする螺旋である。

#### 2. パラメータ付き定積分

$$
\sin^2(tx)=\frac{1-\cos(2tx)}2
$$

を用いる。標準積分

$$
\int_0^\infty \frac{\cos(bx)}{x^2+a^2}\,dx
  =\frac{\pi}{2a}e^{-ab}\qquad (a>0,\ b\ge0)
$$

を使うと、$a=\pi$, $b=2t$ に対して

$$
\int_0^\infty \frac{dx}{x^2+\pi^2}=\frac12,\qquad
  \int_0^\infty \frac{\cos(2tx)}{x^2+\pi^2}\,dx=\frac12e^{-2\pi t}.
$$

したがって

$$
\begin{aligned}
  \int_0^\infty \frac{\sin^2(tx)}{x^2+\pi^2}\,dx
  &=\frac12\left(
    \frac12-\frac12e^{-2\pi t}
  \right)\\
  &=\frac14\left(1-e^{-2\pi t}\right).
\end{aligned}
$$

**偶関数のフーリエ変換**

$1/(x^2+a^2)$ の余弦変換は指数関数 $e^{-ab}$ になる。$\sin^2$ を $1-\cos$ に直すと、この公式をそのまま使える。$t>0$ なので減衰因子は $e^{-2\pi t}$ である。

#### 3. Haar型関数系

- 各 $\phi_k$ は値が $\pm1$ なので

$$
\int_0^1 \phi_k(x)^2\,dx=1
$$

である。また $j
- 正規直交系への最小二乗近似では、係数は内積で与えられる。したがって

$$
a_0=\int_0^1 f(x)\,dx,\qquad
  a_k=\int_0^1 f(x)\phi_k(x)\,dx\quad (k\ge1)
$$

である。これは、誤差 $f-g$ が近似空間の各基底関数に直交するという正規方程式から従う。
- $f(x)=x$ のとき

$$
a_0=\int_0^1 x\,dx=\frac12.
$$

また $\phi_k$ は長さ $2^{-k}$ の小区間ごとに符号を交互に変える。1周期の長さを $2^{-(k-1)}$ とすると、その前半と後半の寄与の差は

$$
-\frac{1}{2^{2k}}
$$

であり、周期は $2^{k-1}$ 個ある。よって

$$
a_k=-\frac{1}{2^{k+1}}\qquad (k\ge1)
$$

である。

**直交性は正負の打ち消し**

高い番号の関数は、低い番号の関数が一定である区間の中で正負を同じ長さだけ取る。そのため積を積分すると必ず打ち消し合う。この構造を言葉で説明できれば、細かい図を完全に描けなくても得点しやすい。

**最小二乗係数は射影**

正規直交系では、最小二乗近似の係数は単に内積である。基底が直交しているため、連立方程式を解く必要がなく、各係数が独立に決まる。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-and-physical-sciences

## 第4問 — 情報物理

### 解説

**divの右辺の違い**

電場側には電荷密度が現れるが、磁場側は0である。この非対称性は、通常の電磁気学では磁気単極子を仮定しないことを表している。磁力線が閉曲線として描かれる理由もこの点にある。

**波動方程式の導出**

回転をもう一度取って、$\operatorname{rot}\operatorname{rot}$ の恒等式を使うのが定石である。自由空間では $\operatorname{div}E=0$ なので勾配項が消え、ラプラシアンと時間2階微分だけが残る。

#### 2. 透明薄膜の反射

- 入射振幅を $a_0$ とする。薄膜表面で直接反射する光の振幅は

$$
a_1=a_0r_1
$$

である。薄膜内へ透過し、底面で1回反射して空気中に戻る光は、透過、反射、逆向き透過を1回ずつ受け、さらに1往復分の位相差を持つので

$$
a_2=a_0t_1r_2t_1'e^{i\delta}
$$

である。
- 空気中に戻る反射光の総振幅は、薄膜内での繰り返し反射の等比級数で

$$
a_r
  =a_0\left\{
    r_1+
    t_1t_1'r_2e^{i\delta}
    \sum_{m=0}^{\infty}(r_1'r_2e^{i\delta})^m
  \right\}.
$$

したがって

$$
\frac{a_r}{a_0}
  =r_1+\frac{t_1t_1'r_2e^{i\delta}}
  {1-r_1'r_2e^{i\delta}}.
$$

ストークスの関係 $r_1'=-r_1$, $t_1t_1'=1-r_1^2$ を用いると

$$
\frac{a_r}{a_0}
  =
  \frac{r_1+r_2e^{i\delta}}
       {1+r_1r_2e^{i\delta}}
$$

となる。振幅反射率を実数として扱えば、強度は

$$
I_r=|a_r|^2
  =
  a_0^2
  \frac{r_1^2+r_2^2+2r_1r_2\cos\delta}
       {1+r_1^2r_2^2+2r_1r_2\cos\delta}
$$

である。
- $r_1=r_2=r$ のとき、分子は

$$
2r^2(1+\cos\delta)
$$

である。無反射となるには

$$
1+\cos\delta=0
$$

であればよい。したがって

$$
\delta=(2m+1)\pi\qquad (m\in\mathbb{Z})
$$

が条件である。
- 垂直入射で

$$
r_1=\frac{1-n_0}{1+n_0},\qquad
  r_2=\frac{n_0-n_g}{n_0+n_g}
$$

である。$r_1=r_2$ より

$$
\frac{1-n_0}{1+n_0}
  =
  \frac{n_0-n_g}{n_0+n_g}
$$

となり、整理して

$$
n_0^2=n_g
$$

を得る。したがって

$$
n_0=\sqrt{n_g}
$$

である。
薄膜中の波長を $\lambda_0$ とすると、1往復による位相差は

$$
\delta=\frac{4\pi h}{\lambda_0}
$$

である。無反射条件 $\delta=(2m+1)\pi$ から

$$
h=\frac{(2m+1)\lambda_0}{4}
$$

である。最も薄い膜は $h=\lambda_0/4$ である。

**等比級数として見る**

薄膜内で1往復するたびに、振幅は $r_1'r_2e^{i\delta}$ 倍される。したがって多重反射は等比級数で和を取れる。直接反射の項と、薄膜内に入ってから戻る項を分けると符号を間違えにくい。

**反射を消す二つの条件**

無反射には、2つの反射波の大きさがそろうことと、位相が反対になることが必要である。屈折率条件 $n_0^2=n_g$ が大きさをそろえ、膜厚条件 $h=\lambda_0/4$ が位相を反対にする。

#### 3. 自然界で見られる色

- 花火の色は主に炎色反応による。金属原子や金属イオンが加熱されると、電子が高いエネルギー準位へ励起される。その電子が低い準位へ戻るとき、準位差に対応する波長の光を放出する。ストロンチウムは赤、バリウムは緑、銅は青緑など、元素ごとに準位構造が異なるため、固有の発光色が現れる。
- シャボン玉の色は薄膜干渉による。膜の表面で反射した光と、膜の裏面で反射して戻ってきた光が重ね合わさる。膜厚や屈折率によって光路差が変わり、ある波長は強め合い、別の波長は弱め合う。膜厚が場所によって少しずつ違うため、見る位置や時間に応じて虹色の模様が変化する。
- 牛乳が白く見える主因は散乱である。牛乳中には脂肪球やカゼインミセルなど、可視光の波長と同程度の粒子が多数分散している。入射光はこれらの粒子で多方向に散乱され、特定の波長だけでなく可視域の広い波長が混ざって目に届く。そのため透明ではなく白濁して見える。

**発光・干渉・散乱を区別する**

花火は物質が自ら光を出す発光、シャボン玉は同じ光が重なって強弱を作る干渉、牛乳は外から来た光が粒子で散らされる散乱である。現象名だけでなく、色が選ばれる物理的理由まで書くと答案として強い。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-and-physical-sciences

---

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