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

2. 有向グラフ

1. 任意の頂点から出辺を一つ選んで進み続ける。各頂点の出次数は1以上なので、途中で止まることはない。頂点数は有限であるから、ある頂点が再び現れる。その最初の反復部分を取り出すと、向きに沿った閉路である。したがって有向閉路をもつ。弱連結性はこの主張には本質的には不要である。
2. 入次数と出次数が各頂点で等しい有向グラフが弱連結であるとき、まず強連結であることを示す。強連結成分を縮約して得られる有向非巡回グラフを考える。成分が二つ以上あれば、弱連結性により成分間の辺が存在し、縮約グラフには入次数0の源成分が存在する。その源成分には外から入る辺がない一方、他成分へ出る辺が少なくとも1本ある。ところが成分内の頂点について「出次数の総和」と「入次数の総和」は等しく、成分内部の辺は両方に1ずつ数えられるので、外へ出る辺数と外から入る辺数も等しくなければならない。これは矛盾である。従って全体は強連結である。 強連結で、かつ各頂点の入次数と出次数が等しい有限有向グラフにはオイラー閉路が存在する。よって、すべての辺をちょうど一度通る有向閉路をもつ。
3. (2) の前半で示した通り、弱連結かつ各頂点で入次数と出次数が等しいなら、強連結成分の縮約が二つ以上あることは不可能である。従って $G$ は強連結である。

3. 平方根を求めるプログラム

1. どちらのプログラムも、正の実数 $x$ に対して $$b=\frac{1}{2}\left(a+\frac{x}{a}\right)$$ という更新を繰り返している。これは方程式 $u^2-x=0$ に対するニュートン法である。実際、$F(u)=u^2-x$ とおくと $$u-\frac{F(u)}{F'(u)} =u-\frac{u^2-x}{2u} =\frac{1}{2}\left(u+\frac{x}{u}\right)$$ となる。従って、これらのプログラムは $\sqrt{x}$ の近似値を求めようとしている。
2. 修正後のプログラムで直されている主な欠点は次の通りである。 itemize
3. $x<0$ のとき、実数の平方根を返すべきでないので未定義として扱う。
4. $x=0$ のとき、初期値 $a=x/2$ が0になり、旧プログラムでは $x/a$ によって0除算が起こる。修正後は先に0を返す。
5. ラベルと `goto' による反復を、条件付き反復として書き直しており、終了条件と更新箇所が読みやすくなっている。 itemize
6. 修正後の停止条件は、ニュートン更新による変化量 $$\left|\frac{x/b-b}{2}\right|$$ が絶対許容誤差 TOL 未満かどうかを見ている。しかし、絶対誤差だけで判定すると、$x$ が非常に大きい場合には相対精度が低くても停止し得るし、$x$ が非常に小さい場合には必要以上に反復することがある。また、最終的に欲しい精度を「$b$ の変化量」で測るのか、「残差 $|b^2-x|$」で測るのかも明確ではない。 例えば、次のように相対誤差と残差のどちらかを基準にするとよい。 $$|b_{\mathrm{new}}-b| < \varepsilon \max(1,|b_{\mathrm{new}}|)$$ または $$|b^2-x| < \varepsilon \max(1,x).$$ 実装としては、$b_{\mathrm{new}}=(x/b+b)/2$ を先に計算し、上の条件を満たしたら $b_{\mathrm{new}}$ を返し、満たさなければ $b\leftarrow b_{\mathrm{new}}$ として続ける形が明確である。

2. 正規分布から定まる半径

$X,Y$ は独立な標準正規分布に従う。平面上の同時密度は $$\frac{1}{2\pi}\exp\left(-\frac{x^2+y^2}{2}\right)$$ である。極座標 $x=r\cos\theta,\ y=r\sin\theta$ を用いると、ヤコビアンは $r$ であり、半径方向の密度は $$f_R(r)=r\exp\left(-\frac{r^2}{2}\right)\qquad(r\ge 0)$$ となる。

1. $r<0$ では $F_R(r)=0$ である。$r\ge 0$ では $$F_R(r)=\int_0^r s e^{-s^2/2}\,ds =1-e^{-r^2/2}.$$
2. 期待値は $$E[R]=\int_0^\infty r\cdot r e^{-r^2/2}\,dr =\int_0^\infty r^2 e^{-r^2/2}\,dr.$$ ガンマ積分 $$\int_0^\infty r^m e^{-r^2/2}\,dr =2^{(m-1)/2}\Gamma\left(\frac{m+1}{2}\right)$$ を $m=2$ に適用すると $$E[R]=\sqrt{\frac{\pi}{2}}$$ である。
3. $R^2=X^2+Y^2$ なので、$R^2$ は自由度2のカイ二乗分布に従い、 $$E[R^2]=E[X^2]+E[Y^2]=2$$ である。よって $$V[R]=E[R^2]-E[R]^2 =2-\frac{\pi}{2} =\frac{4-\pi}{2}.$$

3. 両側指数型分布の最尤推定

密度を $$f(x)=C e^{-|x-\mu|}$$ とする。まず正規化条件から $$1=C\int_{-\infty}^{\infty}e^{-|x-\mu|}\,dx =C\left(\int_{-\infty}^{\mu}e^{-(\mu-x)}\,dx +\int_{\mu}^{\infty}e^{-(x-\mu)}\,dx\right) =2C$$ なので $$C=\frac12$$ である。

独立標本 $x_1,\ldots,x_n$ に対する尤度は $$L(\mu)=\left(\frac12\right)^n \exp\left(-\sum_{i=1}^n |x_i-\mu|\right)$$ である。したがって最尤推定は $$\sum_{i=1}^n |x_i-\mu|$$ を最小にする $\mu$ を求める問題である。

順序統計量を $$x_{(1)}\le x_{(2)}\le\cdots\le x_{(n)}$$ と書く。$n=2m+1$ が奇数なら、絶対偏差和は標本中央値 $$\hat{\mu}=x_{(m+1)}$$ で一意に最小となる。分布は $\mu$ を中心に対称であるから、中央値の分布も $\mu$ を中心に対称である。期待値が存在するので $$E[\hat{\mu}]=\mu$$ となり、奇数標本サイズの標本中央値は不偏である。

$n=2m$ が偶数なら、絶対偏差和を最小にする $\mu$ は一意ではなく、 $$x_{(m)}\le \mu\le x_{(m+1)}$$ の任意の値が最尤推定量になる。したがって「最尤推定量の不偏性」は、区間の中からどの値を選ぶかという規則を決めないと一つの性質としては定まらない。例えば $$\hat{\mu}_{\mathrm{mid}}=\frac{x_{(m)}+x_{(m+1)}}{2}$$ を選べば対称性から不偏である。一方、常に下側中央値 $x_{(m)}$ を選ぶ規則は一般に $\mu$ より小さい方向に偏り、上側中央値 $x_{(m+1)}$ を選ぶ規則は大きい方向に偏る。

2. Euler 型微分方程式

$s=\log t$ とおき、$X(s)=x(e^{s})$ と書く。$t=e^{s}$ であり、 $$\frac{dx}{dt}=\frac{1}{t}X'(s),\qquad \frac{d^{2}x}{dt^{2}}=\frac{1}{t^{2}}\{X''(s)-X'(s)\}$$ である。したがって $$t^{2}\ddot{x}(t)-2t\dot{x}(t)+2x(t) = X''(s)-3X'(s)+2X(s)$$ となる。また右辺は $4t^{3}\log t=4se^{3s}$ なので、変換後の方程式は $$X''-3X'+2X=4se^{3s}$$ である。

同次方程式の特性方程式は $$\lambda^{2}-3\lambda+2=(\lambda-1)(\lambda-2)=0$$ であるから、同次解は $$X_h(s)=C_{1}e^{s}+C_{2}e^{2s}$$ である。非同次項が $se^{3s}$ なので $$X_p(s)=e^{3s}(as+b)$$ とおく。作用素 $D=d/ds$ を用いると $$(D^{2}-3D+2)\{e^{3s}(as+b)\} =e^{3s}(D^{2}+3D+2)(as+b)$$ であり、 $$(D^{2}+3D+2)(as+b)=2as+2b+3a$$ である。これが $4s$ に等しいため $$2a=4,\qquad 2b+3a=0$$ より $$a=2,\qquad b=-3$$ を得る。従って $$X(s)=C_{1}e^{s}+C_{2}e^{2s}+e^{3s}(2s-3)$$ であり、元の変数に戻すと $$x(t)=C_{1}t+C_{2}t^{2}+t^{3}(2\log t-3) \qquad(t>0)$$ である。

3. 畳み込みとラプラス変換

畳み込み $$(f*g)(t)=\int_{0}^{t}f(\tau)g(t-\tau)\,d\tau$$ のラプラス変換を示す。$F(s)=\mathcal{L}\{f\}(s)$、$G(s)=\mathcal{L}\{g\}(s)$ とすると、収束条件が満たされる範囲で Fubini の定理により $$\begin{aligned} \mathcal{L}\{f*g\}(s) &= \int_{0}^{\infty}e^{-st} \int_{0}^{t}f(\tau)g(t-\tau)\,d\tau\,dt\\ &= \int_{0}^{\infty}f(\tau)e^{-s\tau} \int_{\tau}^{\infty}e^{-s(t-\tau)}g(t-\tau)\,dt\,d\tau. \end{aligned}$$ ここで $u=t-\tau$ とおくと内側の積分は $G(s)$ になるので $$\mathcal{L}\{f*g\}(s)=F(s)G(s)$$ である。

次に、$x(0)=0$ のもとで未知関数のラプラス変換を $$X(s)=\mathcal{L}\{x(t)\}(s)$$ とおく。$\mathcal{L}\{\sin t\}=1/(s^{2}+1)$、$\mathcal{L}\{\cos t\}=s/(s^{2}+1)$ であり、畳み込み定理から $$(sX(s))-3X(s)+8X(s)\frac{1}{s^{2}+1} = 10\frac{s}{s^{2}+1}.$$ したがって $$X(s) = \frac{10s}{(s-3)(s^{2}+1)+8} = \frac{10s}{s^{3}-3s^{2}+s+5}.$$ 分母は $$s^{3}-3s^{2}+s+5=(s+1)(s^{2}-4s+5)$$ と因数分解できる。部分分数分解すると $$\frac{10s}{(s+1)(s^{2}-4s+5)} = -\frac{1}{s+1} +\frac{s+5}{s^{2}-4s+5}.$$ さらに $$s^{2}-4s+5=(s-2)^{2}+1,\qquad s+5=(s-2)+7$$ より $$X(s) = -\frac{1}{s+1} +\frac{s-2}{(s-2)^{2}+1} +7\frac{1}{(s-2)^{2}+1}.$$ 逆変換して $$x(t)=-e^{-t}+e^{2t}\cos t+7e^{2t}\sin t$$ を得る。実際に $x(0)=-1+1=0$ であり、初期条件も満たす。