静岡大 総合科学技術研究科 情報学専攻 情報科学 2025年度 院試 過去問 解答例・解説（全5問）

問1

探索の平均計算量と最悪計算量は次の通りである。ハッシュはチェイン法で、ハッシュサイズ $B$ がデータ数 $N$ に比べて十分大きいと仮定する。 $$\begin{array}{c|cc} \text{アルゴリズム} & \text{平均計算量} & \text{最悪計算量}\\ \hline \text{線形探索} & O(N) & O(N)\\ \text{二分探索} & O(\log N) & O(\log N)\\ \text{ハッシュ（チェイン法）} & O(1) & O(N) \end{array}$$ 線形探索は平均でも半分程度の要素を調べるため $O(N)$ である。二分探索は整列済み配列を仮定し、候補範囲を半分ずつ狭めるため $O(\log N)$ である。チェイン法のハッシュは負荷率が小さいなら平均 $O(1)$ だが、すべてが同じバケットに入る最悪ケースでは $O(N)$ になる。

探索がほとんどで新規登録が少ない場合は、整列済み配列を維持して二分探索を使うのが適している。探索が $O(\log N)$ と速く、登録のための整列維持コストが頻繁には発生しないからである。

新規登録の方が多い場合は、線形探索を前提に未整列配列へ末尾追加する方が適している。末尾追加なら登録は $O(1)$ で済み、二分探索のために毎回整列位置を探して要素をずらす $O(N)$ の負担を避けられるからである。

二分探索木と B 木の探索計算量は次の通りである。 $$\begin{array}{c|cc} \text{データ構造} & \text{平均計算量} & \text{最悪計算量}\\ \hline \text{二分探索木} & O(\log N) & O(N)\\ \text{B 木} & O(\log N) & O(\log N) \end{array}$$ 二分探索木は平均的に高さが $\log N$ 程度なら速いが、挿入順によって一直線に偏ると高さが $N$ になる。B 木は各ノードの分岐数と最小占有数が保たれ、すべての葉が同じ深さにある平衡木なので、最悪でも高さが $O(\log N)$ に抑えられる。

5 階の B 木を、最大 5 子、最大 4 キーを持つ B 木として考える。ノード数をできるだけ少なくするには、各ノードをできるだけ満たす。このとき深さ $d$ で格納できるキー数は $$4(1+5+5^2+\cdots+5^{d-1})=5^d-1$$ である。$10000\le 5^d-1$ より $$d\ge \log_5 10001 \simeq 4\log_5 10=5.72$$ なので、深さは $6$ と推定できる。

逆にノード数をできるだけ多くするには、根以外のノードを最小占有に近づける。5 階では根以外の内部ノードは少なくとも 3 子、すなわち少なくとも 2 キーを持つ。深さ $d$ の最小キー数は $$1+4(1+3+\cdots+3^{d-2})=2\cdot3^{d-1}-1$$ である。最大深さは $$2\cdot3^{d-1}-1\le10000$$ を満たす最大の $d$ であり、 $$d-1\le \log_3(5000.5)\simeq \log_3 5+3\log_3 10 \simeq 1.47+6.30=7.77$$ だから、深さは $8$ と推定できる。

問2

フィボナッチ数列は $$F(0)=0,\quad F(1)=1,\quad F(n)=F(n-2)+F(n-1)$$ である。したがって $$F(2)=1,\ F(3)=2,\ F(4)=3,\ F(5)=5,\ F(6)=8,\ F(7)=13$$ となる。

再帰関数の呼び出し回数を $C(n)$ とすると、基底部も一回の呼び出しなので $$C(0)=C(1)=1,\qquad C(n)=1+C(n-2)+C(n-1)$$ である。よって $$C(2)=3,\ C(3)=5,\ C(4)=9,\ C(5)=15$$ となり、$F(5)$ の計算では 15 回呼び出される。

呼び出し回数を減らす工夫として、メモ化または動的計画法がある。一度求めた $F(k)$ を表に保存して再利用すれば、同じ部分問題を繰り返し計算しない。$F(5)$ では $F(0),F(1),\ldots,F(5)$ の 6 個の値を一度ずつ計算すればよい。なお、キャッシュヒットで関数入口までは呼ぶ実装では呼び出し数の数え方が変わるが、重複計算をなくすという意味では 6 個の部分問題で済む。

問3

方策とは、状態を観測したときにどの行動を選ぶかを定める規則であり、確率的方策なら $\pi(a\mid s)$ と表せる。状態価値関数とは、ある方策のもとで状態 $s$ から開始したときに得られる割引累積報酬の期待値であり、$V^\pi(s)$ と書く。

TD 誤差を $\delta_t$、学習率を $\alpha$ とすると、Q 学習の更新式は $$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha\delta_t$$ すなわち $$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha\{r_{t+1}+\gamma\max_{a\in A}Q(s_{t+1},a)-Q(s_t,a_t)\}$$ である。

与えられた表では、現在状態で行動「前進」をとったときの値は $Q(s_t,\text{前進})=7$ である。次状態での最大値は $$\max(4,10,8,6)=10$$ である。報酬 $3$、割引率 $0.9$ より $$\delta_t=(3+0.9\cdot10)-7=5$$ である。学習率 $\alpha=0.5$ なら更新量は $$\alpha\delta_t=0.5\cdot5=2.5$$ なので、更新されるのは $Q(s_t,\text{前進})$ だけであり、 $$7\to 9.5$$ となる。

問4

訓練データに適合しすぎ、未知データへの汎化性能が落ちる現象は過学習である。

最小二乗直線 $y=ax+b$ を求める。データ数を $n=4$ とすると $$\sum x=10,\quad \sum y=12,\quad \sum x^2=30,\quad \sum xy=33$$ である。よって $$a=\frac{n\sum xy-(\sum x)(\sum y)} {n\sum x^2-(\sum x)^2} =\frac{4\cdot33-10\cdot12}{4\cdot30-10^2} =0.6$$ であり、 $$b=\bar y-a\bar x=3-0.6\cdot2.5=1.5$$ である。したがって、直線は $$y=0.6x+1.5$$ である。

線形回帰モデルの出力を $h_\theta(x_i)$ とする。各 $y_i$ が平均 $h_\theta(x_i)$、分散 $\sigma^2$ の正規分布から独立に生成されるなら、 $$p(D\mid\theta)=\prod_{i=1}^{N} \frac{1}{\sqrt{2\pi}\sigma} \exp\left\{-\frac{(y_i-h_\theta(x_i))^2}{2\sigma^2}\right\}$$ である。対数尤度は $$l(\theta) =-\frac{N}{2}\log(2\pi\sigma^2) -\frac{1}{2\sigma^2}\sum_{i=1}^{N}(y_i-h_\theta(x_i))^2$$ となる。第 1 項は $\theta$ に依存せず、$\sigma^2$ は固定なので、$l(\theta)$ を最大化することは残差平方和 $$\sum_{i=1}^{N}(y_i-h_\theta(x_i))^2$$ を最小化することと等価である。