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

2. 符号付き和の判定

1. $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<0$ の項は false とみなす。最後に $d[n,T]$ が true なら「あり」、false なら「なし」と答える。
2. 上の動的計画法では、表の大きさは $(n+1)(T+1)$ であり、各成分は定数時間で計算できる。したがって時間計算量は $$O(nT)=O\left(n\sum_{i=1}^n c_i\right)$$ である。入力整数の大きさを値そのものとして測ると擬多項式時間である。
3. 判定問題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に属する。

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

1. 図のグラフでは、最長の最短距離は例えば $v_8$ と $v_4$ の間で達成され、長さは $$4$$ である。したがって直径は $4$ である。 各頂点から最も遠い頂点までの距離を調べると、$v_2$ からはすべての頂点へ距離 $2$ 以下で到達できる。一方、他の頂点では最大距離が少なくとも $3$ になる。よって中心は $$v_2$$ であり、半径は $$2$$ である。最大次数は、$v_3$ が $v_2,v_4,v_6,v_5$ と接続しているので $$4$$ である。
2. 成り立つ。中心を $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$$ が成り立つ。
3. 成り立つ。中心からの幅優先探索を考えると、距離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$$ が成り立つ。

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

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

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}$$ である。
2. $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}.$$
3. $$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}$$ である。
4. $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$ に集中する。

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

1. 対数尤度は $$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]$$ なので、与えられた式が従う。
2. 最尤推定では尤度方程式から、モデルの期待値が標本平均に一致する。与えられた度数から $$\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}$$
3. $$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$ も独立である。
4. $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.$$

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}$$

3. Haar型関数系

1. 各 $\phi_k$ は値が $\pm1$ なので $$\int_0^1 \phi_k(x)^2\,dx=1$$ である。また $j<k$ とする。$\phi_j$ が一定である各小区間を、$\phi_k$ はさらに等分して正負を同じ長さだけ取る。したがってその小区間上の積分は0であり、全体でも $$\int_0^1 \phi_j(x)\phi_k(x)\,dx=0$$ である。さらに定数関数 $1$ と各 $\phi_k$ の内積も、正の部分と負の部分の長さが等しいため0である。よって $$\{1,\phi_1,\phi_2,\ldots\}$$ は正規直交系である。
2. 正規直交系への最小二乗近似では、係数は内積で与えられる。したがって $$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$ が近似空間の各基底関数に直交するという正規方程式から従う。
3. $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)$$ である。

2. 透明薄膜の反射

1. 入射振幅を $a_0$ とする。薄膜表面で直接反射する光の振幅は $$a_1=a_0r_1$$ である。薄膜内へ透過し、底面で1回反射して空気中に戻る光は、透過、反射、逆向き透過を1回ずつ受け、さらに1往復分の位相差を持つので $$a_2=a_0t_1r_2t_1'e^{i\delta}$$ である。
2. 空気中に戻る反射光の総振幅は、薄膜内での繰り返し反射の等比級数で $$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}$$ である。
3. $r_1=r_2=r$ のとき、分子は $$2r^2(1+\cos\delta)$$ である。無反射となるには $$1+\cos\delta=0$$ であればよい。したがって $$\delta=(2m+1)\pi\qquad (m\in\mathbb{Z})$$ が条件である。
4. 垂直入射で $$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$ である。

3. 自然界で見られる色

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