名大 情報学研究科 数理情報学 2020年2月実施 院試 解答例・解説

この問題では、$W$ を直接パラメータ表示するより、直交補空間を 先に求める方が速い。$W$ が $\mathbb{R}^4$ 内の3次元空間である ことが分かれば、$W^\perp$ は1次元であり、射影行列は $uu^T/(u^Tu)$ に落ちる。

(2) では $w_i$ を $v_i$ の一次結合で表そうとするより、 「$W=u^\perp$」を使う方が計算が短い。ただし、$u\cdot w_i=0$ だけでは $w_i$ が張る空間の次元が3とは限らないため、 $b=1/2$ の後に一次独立性を確認する必要がある。

ガウス積分の片側版は、正方形を四分円で挟む定番の方法で処理する。 ポイントは $[0,a]^2$ を半径 $a$ と半径 $\sqrt2a$ の四分円で挟む ことで、極座標積分に直接変換できる。

後半は「各値をちょうど2回とる」という条件が、連続関数の端点と 極値の振る舞いに合わないことを示す問題である。最小値を2回しか とれないなら、その2点は端点に追い込まれる。すると最大値の逆像が 1点、区間、または複数点のいずれであっても、逆像数2という条件と 矛盾する。

Iは $\varphi(n)$ の乗法性と、$p-1\mid24$ から候補素数を絞るのが 核心である。候補素数が少ないので、指数条件まで見ると有限の列挙に 落ちる。

IIはハフマン符号化の正当性を木の言葉で証明する問題である。最小の 2重みを最深の兄弟葉に置いてよいこと、その2葉を合併しても最適性が 保存されることが分かれば、通常のハフマン併合手順がそのまま導ける。