京大 情報学研究科 システム科学コース 2022年度 院試 解答例・解説

反復法は誤差伝播を見る

反復の収束性は $e_{n+1}=Ge_n$ の $G=P^{-1}Q$ で決まる。固有値が異なるため，固有値の絶対値がすべて $1$ 未満であることが必要十分になる。

最大ノルムで押さえる

非負かつ行和1の行列は最大ノルムを増やさない。この性質だけで固有値の絶対値上界が出る。

端点と無限遠を分ける

$f/g$ の有界性は，無限遠では極限から，中央の有界区間では単調性から押さえる。

楕円体を単位球へ移す

座標を半径で割ると単位球上の最適化になる。対称性とCauchy--Schwarzで計算が整理できる。

順序回路は両立集合で縮約する

出力が矛盾する状態対を除き，遷移先も両立するかを閉包的に確認する。極大両立集合を新状態にすると4状態まで減らせる。

係数の根判定

$n^{n-1}/n!$ はStirlingの公式により根の極限が $e$ になる。

実部は平面の内積

$F(z,w)=\operatorname{Re}(\overline zw)$ は複素平面を $\mathbb R^2$ と見たときの内積である。

ギャップ付き挿入ソート

コードはShell sortである。通常の挿入ソートを，離れた要素どうしの部分列に対して先に行う。

表はタイムスライス後に更新する

各時刻で最小の $p_t$ を持つプロセスを1スライス実行し，その後に $q_t,p_t$ を更新する。

正規化して標準正規へ戻す

既知分散の正規標本平均なので，すべて標準正規分布の上側確率で書ける。

混合正規のスコアは事後重みで書ける

$r_i$ は観測 $X_i$ が平均 $\mu$ 側の成分から来た事後確率である。尤度方程式は重み付き平均の固定点になる。

平衡点での傾きがゼロ

$\sin y$ の微分は $\cos y$ であり，$y=\pi/2$ では $0$ になる。そのため線形化では復元項が消える。

最大位相進みを交差周波数へ置く

位相を最も稼げる周波数 $\omega_m$ を指定された交差周波数に合わせ，ゲインは $k$ で合わせる。