京大 情報学研究科 数理工学コース 2023年度 院試 解答例・解説

指数関数への直し方

$\sqrt[n]{n}$ は $\exp((\log n)/n)$ と直すのが最短である。 対数を取って極限を調べる典型問題で，$\log n$ は $n$ より遅く増えることを明記すれば十分である。

2変数の極値

$(0,\pm1)$ は停留点だが極値ではない。停留点を列挙したあと，方向を変えて値の増減を見ることが重要である。 ここでは $a>b$ なので，$y$ 軸上の候補点は $x$ 方向へ動くと値が増える。

対角化の並べ方

固有値が相異なるので，対応する固有ベクトルは自動的に線形独立である。 $P$ の列の順番を変えれば $B$ の対角成分の順番も同じように変わるため，組として整合していればよい。

自由変数の残し方

連立方程式は1自由度をもつ。第3式から $x=-z$ と置くと，残りはすぐ $y=1+z$ と分かる。 最後に任意定数 $t$ を明示して全解であることを示す。

単位円上の置換

$z=e^{i\theta}$ と置いたとき， $1-2r\cos\theta+r^2=(1-rz)(1-r/z)$ に分解するのが中心である。極の位置は $|r|<1,\ |s|<1$ から一つだけ内側にある。

Bellman--Ford の判定条件

$n-1$ 回の緩和後にさらに改善できる枝があることは，負閉路が到達可能であることを意味する。 この問題では有向グラフが強連結なので，負閉路が存在すれば始点から到達可能であり，通常の Bellman--Ford 判定をそのまま使える。

双対問題の符号

最小化問題で $\mathbf1^\top y\le1$ をそのまま Lagrangian に入れると，双対目的が $-\lambda$ になる。 符号を間違えやすいので，停留条件 $c+\lambda\mathbf1-\mu=0$ まで書いて確認するのが安全である。

制御の最後の設問

初期状態が指定されていない入力最適化では，通常の入出力評価と同じ零初期状態で読むのが自然である。 その場合，評価関数は非負で，零入力が評価値0を達成するため大域最適である。

相関は $\min(i,j)$

ランダムウォークの位置 $x_i$ と $x_j$ は，最初の $\min(i,j)$ 個の増分だけを共有している。 このため $\langle x_i x_j\rangle=\min(i,j)$ となり，重心の2乗平均は $\sum\min(i,j)$ の計算に帰着する。

分散型の整理

$\sum (x_i-\bar x)^2$ は展開して平均2乗から重心の2乗を引く形にする。 この一行を入れると，最後の期待値は既に求めた $\langle\bar x^2\rangle$ を再利用できる。

定数項比較で $k$ が決まる

$x=t^k$ を代入した後，$k(k-1)+kta(t)+t^2b(t)=0$ を多項式恒等式として見る。 $ta(t)$ と $t^2b(t)$ は定数項を持たないため，すぐに $k=1$ が出る。

Wronskian の使いどころ

2階線形方程式で既知解が一つあるとき，独立な第2解の存在は Wronskian で調べるのが強い。 ここでは有理関数であるはずの Wronskian が非定数多項式の指数関数になってしまうため，矛盾が出る。