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

2. チェイン法によるハッシュ表

1. ハッシュ値の計算を定数時間とみなす。$N$ 個のデータが $M$ 個のリストへ一様に格納されているので、各リストの平均長は $$\alpha=\frac{N}{M}$$ である。この $\alpha$ はハッシュ表の負荷率である。 格納済みデータ $x_i$ を探索するときは、まず $h(x_i)$ を計算し、対応するリスト $L(h(x_i))$ を先頭から調べる。一様性を仮定すれば、調べるリストの長さの期待値は $N/M$ である。したがって、成功探索の平均計算時間は $$O\left(1+\frac{N}{M}\right)$$ である。より細かく比較回数で見れば、リスト内で目的の要素の位置が一様であると考えると平均比較回数はおよそ $(N/M+1)/2$ である。ただし最悪の場合には同じリストに多数の要素が集まり、$O(N)$ 時間かかる。
2. $M$ を大きくすると負荷率 $N/M$ が小さくなり、各リストが短くなる。したがって探索、挿入、削除の平均時間は定数時間に近づき、衝突も少なくなる。 一方で、$M$ 個のリストの先頭配列を確保する必要があるため、記憶領域と初期化コストが増える。空のリストが多いとメモリ効率が悪く、キャッシュ効率も落ちやすい。したがって、$M$ は単に大きくすればよいのではなく、許容したい負荷率に合わせて $N$ と同じオーダーで選ぶのが実用的である。

3. 出次数1の有向グラフとコインの移動

頂点集合を $V$ とし、各頂点 $v$ から出る唯一の辺の終点を $f(v)$ と書く。時刻 $t$ に頂点 $i$ にあるコイン数は $$n_i(t)=\#\{v\in V\mid f^t(v)=i\}$$ で表せる。

1. 有限集合上の写像 $f:V\to V$ を反復すると、各頂点の軌道は必ず最終的に周期軌道、すなわち有向閉路に入る。これは、$v,f(v),f^2(v),\ldots$ の列に同じ頂点が再び現れるためである。 各連結成分は、1つ以上の有向閉路と、それらへ流れ込む有向木からなる。各頂点から閉路に入るまでの長さの最大値を $T$ とし、全閉路の長さの最小公倍数を $P$ とする。時刻 $T$ 以降、すべてのコインは閉路上にある。閉路上では $P$ 回進むと元の頂点に戻るので、すべての頂点 $i$ とすべての $t\ge T$ について $$n_i(t+P)=n_i(t)$$ が成り立つ。
2. まず、頂点 $i$ を通る有向閉路が存在しないとする。出次数が1なので、$i$ はどの閉路上にもない。$i$ に到達し得る頂点は有限個であり、そのような各コインが $i$ にいる時刻も高々一回である。したがって、十分大きい $T$ を取れば $$n_i(T)=n_i(T+1)=\cdots=0$$ となる。 逆に、頂点 $i$ を通る有向閉路が存在するとする。その閉路の長さを $q$ とすれば、少なくとも $i$ から出発したコインは時刻 $0,q,2q,\ldots$ に再び $i$ に戻る。したがって $n_i(t)$ は無限に何度も正になり、ある時刻以降ずっと0になることはない。よって同値性が示された。
3. (1) の周期性が始まる最小時刻 $T$ は、閉路に入るまでに必要な最大ステップ数で決まる。これを最大にするには、できるだけ長い有向道を作り、その終点を閉路に入れればよい。 頂点数が $N$ のとき、最大値は $N-1$ である。これは、$N-1$ 本の辺からなる有向道を1つ作り、その終点を自己ループに入れる場合に達成される。すなわち $$v_1\to v_2\to \cdots \to v_N,\qquad v_N\to v_N$$ の形である。このとき $v_1$ のコインが閉路に入るまで $N-1$ ステップかかるので、これより小さい $T$ では全頂点のコイン数は周期状態にならない。
4. 周期 $P$ は有向閉路の長さの最小公倍数である。頂点数が9のとき、閉路長の和が9以下となるように正整数へ分割し、その最小公倍数を最大化すればよい。 代表的な分割を比べると $$\operatorname{lcm}(5,4)=20,\qquad \operatorname{lcm}(7,2)=14,\qquad \operatorname{lcm}(4,3,2)=12,\qquad \operatorname{lcm}(9)=9$$ であり、最大は $20$ である。したがって、9頂点を長さ5の有向閉路と長さ4の有向閉路に分ける場合に、(1) を満たす最小の $P$ が最大となる。

2. 単純な線形計画問題

目的関数の係数を $c_1,\ldots,c_n$ とし $$c_{\min}=\min_{1\le i\le n} c_i$$ とおく。

1. 最適解が存在するための必要十分条件は $$c_i\ge 0\qquad (i=1,\ldots,n)$$ である。 まず、ある $j$ について $c_j<0$ ならば、$x_j=t$, 他の成分を $0$ として $t\to\infty$ とすれば制約を満たしたまま目的関数値は $c_jt\to-\infty$ となる。したがって目的関数は下に有界でなく、最適解は存在しない。 逆にすべての $c_i$ が非負ならば、任意の実行可能解に対して目的関数値は $0$ 以上である。また $c_{\min}$ を達成する添字 $j$ を1つ選び、$x_j=1$, 他の成分を $0$ とすれば実行可能で、目的関数値は $c_{\min}$ である。よって最適解は存在する。
2. すべての $c_i$ が非負であるとする。このとき最適値は $$c_{\min}$$ である。 $c_{\min}>0$ の場合、実行可能解 $x$ について $$\sum_{i=1}^n c_ix_i \ge c_{\min}\sum_{i=1}^n x_i \ge c_{\min}$$ である。等号が成り立つのは、$\sum_i x_i=1$ であり、かつ $c_i>c_{\min}$ となる成分には $x_i=0$ が成り立つ場合である。したがって最適解全体は $$\left\{ x\in \mathbb{R}^n \,\middle|\, x_i\ge 0,\ \sum_i x_i=1,\ x_i=0\ \text{if }c_i>c_{\min} \right\}$$ である。 $c_{\min}=0$ の場合、目的関数値は常に $0$ 以上であり、$c_i=0$ の成分だけで制約を満たせば値 $0$ を達成する。したがって最適解全体は $$\left\{ x\in \mathbb{R}^n \,\middle|\, x_i\ge 0,\ \sum_i x_i\ge 1,\ x_i=0\ \text{if }c_i>0 \right\}$$ である。

3. 対称分布のモーメントと無相関化

$U=X-\mu$, $V=Y-\mu$ とおく。$X,Y$ は平均のまわりに対称な分布に従うので、必要な3次モーメントが存在する範囲で $$E(U)=0,\qquad E(U^2)=\sigma^2,\qquad E(U^3)=0$$ である。また相関係数が $\rho$ で分散がともに $\sigma^2$ だから $$\operatorname{Cov}(X,Y)=E(UV)=\rho\sigma^2$$ である。

1. $$E(X^2)=\operatorname{Var}(X)+\{E(X)\}^2 =\sigma^2+\mu^2.$$
2. $X=\mu+U$ と書くと $$\begin{aligned} E(X^3) &=E\{(\mu+U)^3\}\\ &=\mu^3+3\mu^2E(U)+3\mu E(U^2)+E(U^3)\\ &=\mu^3+3\mu\sigma^2. \end{aligned}$$
3. $X$ と $X^2+aY$ が無相関である条件は $$\operatorname{Cov}(X,X^2+aY)=0$$ である。ここで $$\begin{aligned} \operatorname{Cov}(X,X^2) &=E(X^3)-E(X)E(X^2)\\ &=(\mu^3+3\mu\sigma^2)-\mu(\mu^2+\sigma^2)\\ &=2\mu\sigma^2 \end{aligned}$$ であり、 $$\operatorname{Cov}(X,Y)=\rho\sigma^2$$ である。したがって $$2\mu\sigma^2+a\rho\sigma^2=0$$ となればよい。$\rho\ne 0$ より $$a=-\frac{2\mu}{\rho}$$ である。

2. 複素積分と Fourier 変換

関数 $$g(z)=\frac{2e^{-2\pi iuz}}{e^{\pi z}+e^{-\pi z}}$$ を考える。分母の零点は $$e^{2\pi z}=-1$$ で与えられるから、積分路の内部にある極は $$z=\frac{i}{2},\qquad z=\frac{3i}{2}$$ である。どちらも単純極であり、 $$\left(e^{\pi z}+e^{-\pi z}\right)' =\pi\left(e^{\pi z}-e^{-\pi z}\right)$$ を用いると $$\operatorname*{Res}_{z=i/2}g(z)=\frac{e^{\pi u}}{\pi i}, \qquad \operatorname*{Res}_{z=3i/2}g(z)=-\frac{e^{3\pi u}}{\pi i}$$ となる。したがって留数定理より $$I_{C_R} = 2\pi i\left( \frac{e^{\pi u}}{\pi i} -\frac{e^{3\pi u}}{\pi i} \right) = 2e^{\pi u}\left(1-e^{2\pi u}\right).$$

次に $R\to\infty$ とする。左右の縦辺の積分は分母の指数増大により $0$ に収束する。また $g(z+2i)=e^{4\pi u}g(z)$ であるから、上辺の向きを考慮すると $$I_{C_R} \longrightarrow \left(1-e^{4\pi u}\right) \int_{-\infty}^{\infty}g(x)\,dx .$$ $u\ne 0$ では $$\int_{-\infty}^{\infty}g(x)\,dx = \frac{2e^{\pi u}(1-e^{2\pi u})}{1-e^{4\pi u}} = \frac{2}{e^{\pi u}+e^{-\pi u}}.$$ 両辺は $u$ について連続なので、$u=0$ でも同じ式が成り立つ。

最後に $$h(x)=\frac{2}{e^{\sqrt{\pi/2}\,x}+e^{-\sqrt{\pi/2}\,x}}$$ とおく。$t=\sqrt{2\pi}\,x$ と変数変換すると $$\begin{aligned} \widehat{h}(w) &= \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{\infty} h(t)e^{-iwt}\,dt \\ &= \int_{-\infty}^{\infty} \frac{2e^{-iw\sqrt{2\pi}x}} {e^{\pi x}+e^{-\pi x}}\,dx . \end{aligned}$$ ここで $u=w/\sqrt{2\pi}$ とおけば、直前の積分公式から $$\widehat{h}(w) = \frac{2}{e^{\pi w/\sqrt{2\pi}}+e^{-\pi w/\sqrt{2\pi}}} = \frac{2}{e^{\sqrt{\pi/2}\,w}+e^{-\sqrt{\pi/2}\,w}} = h(w)$$ を得る。

3. 微分方程式

微分作用素 $D=d/dt$ を用いると $$pqD^{2}+(p+q)D+1=(pD+1)(qD+1)$$ である。特に同次方程式の解は、$p\ne q$ なら $$C_{1}e^{-t/p}+C_{2}e^{-t/q}$$ である。

$pq=1$ かつ $w(t)=1-e^{-t}$ の場合を解く。まず定数外力 $1$ に対する特解は $x=1$ である。$p\ne q$、すなわち $p+q\ne 2$ のときは、$-e^{-t}$ に対して $Ae^{-t}$ とおくと $$A\{pq-(p+q)+1\}e^{-t} = A(2-p-q)e^{-t}$$ であるから $$A=\frac{1}{p+q-2}$$ となる。したがって $$x(t) = 1+\frac{e^{-t}}{p+q-2} +C_{1}e^{-t/p}+C_{2}e^{-t/q} \qquad(pq=1,\ p\ne q)$$ である。

$p=q=1$ のときは $$(D+1)^{2}x=1-e^{-t}$$ であり、$-e^{-t}$ は二重根に対応する共鳴項である。$At^{2}e^{-t}$ とおくと $$(D+1)^{2}\left(At^{2}e^{-t}\right)=2Ae^{-t}$$ なので $A=-1/2$ である。従って $$x(t)=1+(C_{1}+C_{2}t)e^{-t}-\frac12 t^{2}e^{-t} \qquad(p=q=1)$$ となる。

次に $$y=p\frac{dx}{dt}+x$$ とおくと $$q\frac{dy}{dt}+y = q\left(p\frac{d^{2}x}{dt^{2}}+\frac{dx}{dt}\right) +p\frac{dx}{dt}+x = pq\frac{d^{2}x}{dt^{2}}+(p+q)\frac{dx}{dt}+x .$$ したがって $y$ が満たす微分方程式は $$q\frac{dy}{dt}+y=w(t)$$ である。

最後に $\lim_{t\to\infty}w(t)=W$ が存在するとする。一次方程式の解表示から $$y(t)=e^{-t/q}y(0)+\frac1q\int_{0}^{t}e^{-(t-s)/q}w(s)\,ds$$ である。指数核の全質量は $1$ で、過去の有限区間の寄与は $t\to\infty$ で消えるため $$\lim_{t\to\infty}y(t)=W$$ が成り立つ。さらに $$p\frac{dx}{dt}+x=y(t)$$ について同じ解表示を使うと $$x(t)=e^{-t/p}x(0)+\frac1p\int_{0}^{t}e^{-(t-s)/p}y(s)\,ds$$ であり、$y(t)\to W$ から $$\lim_{t\to\infty}x(t)=W$$ を得る。よって $\lim_{t\to\infty}w(t)$ が存在すれば $\lim_{t\to\infty}x(t)$ も存在する。