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

2. 強平衡二分木と整列

1. 通常の整列木として用いる二分木、すなわち内部頂点が左右の子を持つ二分木を考える。高さを $h$ とする。すべての葉の深さの差が1以下なので、葉は深さ $h$ または $h-1$ にしか現れない。したがって、深さ $0,\ldots,h-2$ の頂点はすべて内部頂点であり、少なくとも $$1+2+2^2+\cdots+2^{h-2}=2^{h-1}-1$$ 個の頂点が存在する。よって $$n\ge 2^{h-1}-1$$ であり、 $$h\le 1+\log_2(n+1)=O(\log n)$$ が従う。
2. 強平衡二分木を二分探索木として用い、数を1個ずつ挿入する。各頂点では、挿入する値を頂点の値と比較し、小さければ左、大きければ右へ進む。木の高さが $O(\log n)$ なので、1回の挿入は $O(\log n)$ 時間でできる。$n$ 個すべてを挿入した後、左部分木、頂点、右部分木の順に中間順走査を行うと昇順の列が得られる。 したがって、挿入全体が $O(n\log n)$、走査が $O(n)$ であり、全体の計算量は $$O(n\log n)$$ である。

3. 有向グラフの最短路

1. 始点から到達可能な負閉路があり、その負閉路から頂点 $j$ へ到達できるとき、$s$ から $j$ への経路の途中でその閉路を何度でも回れる。閉路を1周するたびに経路長はさらに小さくなるので、最小値は有限の値として定まらない。 すべての頂点への最短距離を同時に考えるなら、始点から到達可能な負閉路が存在する場合が問題である。負閉路の影響を受ける頂点では、距離を $-\infty$ 方向へいくらでも小さくできる。
2. 辺の長さに負の値があり得る場合は、Bellman--Ford 法を用いる。まず $$d_s=0,\qquad d_v=\infty\quad (v\ne s)$$ と初期化する。次に、すべての辺 $(i,j)$ について $$d_j > d_i+c_{ij}$$ なら $d_j\leftarrow d_i+c_{ij}$ と更新する操作を、$|V|-1$ 回繰り返す。負閉路がなければ、最短路は高々 $|V|-1$ 本の辺からなる単純路として取れるため、この時点ですべての最短距離が得られる。 計算量は、各反復で全辺を見るので $$O(|V||E|)$$ である。さらに1回全辺を調べて更新可能な辺が残っていれば、到達可能な負閉路を検出できる。
3. 負の長さの辺がない場合は、Dijkstra 法を用いる。未確定頂点のうち暫定距離 $d_v$ が最小の頂点を選び、その頂点を確定する。非負辺では、未確定頂点を経由してその距離を後から小さくすることができないため、この貪欲な確定が正しい。 優先度付きキューを用いれば、各頂点の取り出しと各辺の緩和により $$O((|V|+|E|)\log |V|)$$ で実行できる。単純な配列で最小頂点を探す実装では $O(|V|^2+|E|)$ である。

2. 指数分布と条件付き分布

1. $X,Y$ は独立で平均1の指数分布なので、密度は $x\ge 0$ で $e^{-x}$ である。$Z=X+Y$ の密度は畳み込みにより $$f_Z(z)=\int_0^z e^{-x}e^{-(z-x)}\,dx =ze^{-z}\qquad (z\ge 0)$$ であり、$z<0$ では $0$ である。これは形状母数2、率1のガンマ分布である。
2. 確率分布の再生性とは、同じ種類の分布に従う独立な確率変数の和が、再び同じ種類の分布族に属する性質である。例えば正規分布や、同じ率を持つガンマ分布族はこの性質を持つ。 指数分布どうしの和は上で見たように密度 $ze^{-z}$ のガンマ分布になり、指数分布そのものではない。したがって、指数分布だけを1母数分布族として見れば再生性はない。ただし、指数分布を形状母数1のガンマ分布と見れば、ガンマ分布族の中では再生性がある。
3. $0\le x\le z$ で同時密度は $$f_{X,Z}(x,z)=f_X(x)f_Y(z-x)=e^{-x}e^{-(z-x)}=e^{-z}$$ である。したがって $$f_{X\mid Z=z}(x) =\frac{f_{X,Z}(x,z)}{f_Z(z)} =\frac{e^{-z}}{ze^{-z}} =\frac1z$$ である。ゆえに、条件付き分布は区間 $[0,z]$ 上の一様分布である。

3. 逐次推定量

1. $\hat{\mu}_0=1$ は定数であり、$E[x_1]=\mu$ である。したがって $$E[\hat{\mu}_1]=\alpha_1+\beta_1\mu$$ である。これが任意の $\mu$ に対して $\mu$ に等しいためには $$\alpha_1=0,\qquad \beta_1=1$$ でなければならない。
2. (1)より $\hat{\mu}_1=x_1$ である。$\hat{\mu}_2=\alpha_2\hat{\mu}_1+\beta_2x_2$ が不偏である条件は $$\alpha_2+\beta_2=1$$ である。$x_1,x_2$ は独立で分散 $\sigma^2$ なので $$\operatorname{Var}(\hat{\mu}_2) =(\alpha_2^2+\beta_2^2)\sigma^2$$ である。$\beta_2=1-\alpha_2$ として最小化すると $$\alpha_2=\beta_2=\frac12$$ となる。
3. (2)より $\hat{\mu}_2=(x_1+x_2)/2$ で、分散は $\sigma^2/2$ である。不偏条件は $$\alpha_3+\beta_3=1$$ であり、独立性から $$\operatorname{Var}(\hat{\mu}_3) =\alpha_3^2\frac{\sigma^2}{2}+\beta_3^2\sigma^2.$$ $\beta_3=1-\alpha_3$ とおいて最小化すると $$\frac{d}{d\alpha_3}\left(\frac{\alpha_3^2}{2}+(1-\alpha_3)^2\right)=3\alpha_3-2$$ なので $$\alpha_3=\frac23,\qquad \beta_3=\frac13$$ である。
4. 帰納的に、$\hat{\mu}_{k-1}$ が $x_1,\ldots,x_{k-1}$ の標本平均で、分散が $\sigma^2/(k-1)$ であるとする。不偏条件は $$\alpha_k+\beta_k=1$$ であり、$x_k$ は過去の標本と独立なので $$\operatorname{Var}(\hat{\mu}_k) =\alpha_k^2\frac{\sigma^2}{k-1}+\beta_k^2\sigma^2.$$ $\beta_k=1-\alpha_k$ として最小化すると $$\alpha_k=\frac{k-1}{k},\qquad \beta_k=\frac1k$$ を得る。このとき $$\hat{\mu}_k=\frac{k-1}{k}\hat{\mu}_{k-1}+\frac1k x_k =\frac{x_1+\cdots+x_k}{k}$$ であり、分散は $\sigma^2/k$ で最小になる。

2. 複素平面上の閉曲線と留数

1. $z=\phi(t)$ とおくと $$I=\int_{\phi}\frac{dz}{z(z-i)}.$$ 部分分数分解により $$\frac{1}{z(z-i)}=\frac{i}{z}-\frac{i}{z-i}.$$ 曲線の回転数を $N(\phi,a)$ と書くと $$I=i\cdot 2\pi i\,N(\phi,0)-i\cdot 2\pi i\,N(\phi,i) =2\pi\{N(\phi,i)-N(\phi,0)\}.$$ 図および曲線の通り方から、原点の周りの回転数は $2$、点 $i$ の周りの回転数は $1$ である。したがって $$I=2\pi(1-2)=-2\pi.$$

3. フーリエ変換と積分

フーリエ変換を $$\widehat{f}(\omega)=\int_{-\infty}^{\infty} f(t)e^{-i\omega t}\,dt$$ で定める。

1. 与えられた三角形型関数は $$f=\mathbf{1}_{[-1,1]}*\mathbf{1}_{[-1,1]}$$ と書ける。畳み込み定理より $$\widehat{f}(\omega) =\left(\int_{-1}^{1}e^{-i\omega t}\,dt\right)^2 =\left(\frac{2\sin\omega}{\omega}\right)^2$$ である。$\omega=0$ では極限値として $\widehat{f}(0)=4$ とする。
2. (1)の式を $\omega$ で積分する。フーリエ反転公式から、連続点 $t=0$ で $$f(0)=\frac{1}{2\pi}\int_{-\infty}^{\infty}\widehat{f}(\omega)\,d\omega$$ である。$f(0)=2$、また $\widehat{f}$ は偶関数なので $$2=\frac{1}{2\pi}\int_{-\infty}^{\infty}\left(\frac{2\sin\omega}{\omega}\right)^2d\omega =\frac{4}{\pi}\int_0^\infty \frac{\sin^2\omega}{\omega^2}\,d\omega.$$ したがって $$I_2=\int_0^\infty \frac{\sin^2 x}{x^2}\,dx=\frac{\pi}{2}.$$
3. Parseval の等式を用いると $$\int_{-\infty}^{\infty}|\widehat{f}(\omega)|^2\,d\omega =2\pi\int_{-\infty}^{\infty}|f(t)|^2\,dt.$$ 右辺の積分は $$\int_{-\infty}^{\infty}|f(t)|^2dt =2\int_0^2(2-t)^2\,dt =\frac{16}{3}$$ である。一方 $$|\widehat{f}(\omega)|^2 =16\frac{\sin^4\omega}{\omega^4}.$$ よって $$16\int_{-\infty}^{\infty}\frac{\sin^4\omega}{\omega^4}\,d\omega =2\pi\cdot\frac{16}{3}$$ であり、偶関数性から $$I_4=\int_0^\infty\frac{\sin^4 x}{x^4}\,dx=\frac{\pi}{3}$$ を得る。

2. マイケルソン・モーリー実験

1. エーテルに対して装置が速度 $v$ で動くと仮定する。運動方向の腕では、往路の光速は装置から見て $c-v$、復路は $c+v$ なので $$t_{\parallel}=\frac{\ell}{c-v}+\frac{\ell}{c+v} =\frac{2\ell c}{c^2-v^2}.$$ 運動方向に垂直な腕では、鏡に戻るために光は横方向成分 $\sqrt{c^2-v^2}$ で進む必要があるので $$t_{\perp}=\frac{2\ell}{\sqrt{c^2-v^2}}.$$ 共通部分の時間は差に効かない。したがって $$\Delta t=t_{\parallel}-t_{\perp} =\frac{2\ell}{c}\left\{ \frac{1}{1-v^2/c^2} -\frac{1}{\sqrt{1-v^2/c^2}} \right\}.$$ $v\ll c$ では $$\Delta t\simeq \frac{\ell v^2}{c^3}$$ である。
2. 振動数は $\nu=c/\lambda$ なので、時間差 $\Delta t$ に対応する位相差は $$\Delta\phi=2\pi\nu\Delta t=\frac{2\pi c}{\lambda}\Delta t.$$ したがって近似的には $$\Delta\phi\simeq \frac{2\pi\ell v^2}{\lambda c^2}$$ である。
3. 観測面に現れる干渉縞を観測する。装置を90度回転すると、運動方向に平行な腕と垂直な腕が入れ替わるため、予想される時間差の符号が反転する。したがって、エーテル風が存在すれば干渉縞が移動するはずであり、その縞の移動量から位相差を測定できる。
4. 予想された位相差が検出されなかったことは、光速が地球の運動方向に依存するという静止エーテル仮説を支持しない。実験結果は、真空中の光速が慣性系や伝播方向によらず同じであるという考え方、すなわち特殊相対性理論の基本的な仮定と整合する。

3. フラウンホーファー回折

1. 光学的変位とは、光波を表す振動量である。電磁波として見れば電場ベクトルまたは磁場ベクトルの一成分を表す複素振幅と考えればよい。実際に観測される光強度は、複素振幅の絶対値の2乗に比例する。
2. $$r=\sqrt{R^2+(x_0-x)^2+(y_0-y)^2}$$ である。$R$ が十分大きく、開口の大きさが観測距離に比べて小さいとき、 $$r=\sqrt{R^2+x_0^2+y_0^2-2x_0x-2y_0y+x^2+y^2}$$ のうち、開口内で変化する2次項 $x^2+y^2$ を無視する。$R_0=\sqrt{R^2+x_0^2+y_0^2}$ とおくと一次近似により $$r\simeq R_0-\frac{x_0}{R_0}x-\frac{y_0}{R_0}y =R_0-\ell x-my$$ である。ただし $\ell=x_0/R_0,\ m=y_0/R_0$ である。したがって $$e^{ikr}\simeq e^{ikR_0}e^{-ik(\ell x+my)}$$ となり、観測点によらない係数 $e^{ikR_0}$ を比例定数に吸収すれば $$u_P\propto \iint f(x,y)e^{-ik(\ell x+my)}\,dxdy$$ を得る。
3. (2)の式は、開口面上の光学的変位 $f(x,y)$ の2次元フーリエ変換である。観測方向を表す変数 $\ell,m$ によって振幅が決まるので、遠方のスクリーン上の明暗分布は開口関数のフーリエ変換の絶対値2乗になる。これはフラウンホーファー回折であり、開口の形が遠方回折像を決める。
4. 開口は半径 $a=\sqrt{\rho}$ の円形開口である。$q=\sqrt{\ell^2+m^2}$ とおく。極座標を用いると、振幅は円対称となり $$u_P(q)\propto \int_0^a\int_0^{2\pi}e^{-ikqr\cos\theta}r\,d\theta dr =2\pi\int_0^a J_0(kqr)r\,dr =2\pi a\frac{J_1(kqa)}{kq}$$ である。したがって光強度は $$I(q)\propto \left(\frac{2J_1(kqa)}{kqa}\right)^2$$ の形になる。中央に強い明るい円盤があり、その外側に暗環と明環が交互に現れる Airy パターンである。