東大 情報理工学系研究科 数理情報学専攻 数理情報学 2024年度 院試 解答例・解説

方針

直交制約つきの最小二乗では、長さを保つ変換であることを利用して、定数項と相関項に分ける。 残るのは相関 $\operatorname{tr}(PXY^\top)$ の最大化であり、特異値分解で左特異ベクトルと右特異ベクトルをそろえればよい。

採点上の注意

$P=UV^\top$ と書くと向きが逆になる。実際に $Q=V^\top PU$ と置いて $Q=I$ を代入すると、$P=VU^\top$ であることが確認できる。 この向きは答案中で一度トレースの巡回性を使って確認しておくと安全である。

方針

この問題は、係数が不自然に見えても、エネルギーを微分または差分にかけた瞬間に 内積項が消えるように設計されている。計算では $\alpha_k=2hk+h+2$ と $a_k=(hk+1)^2$ を置くと、打ち消しの構造が見やすい。

典型ミス

離散版で $\delta^+\|v^{(k)}-x^*\|^2=2(v^{(k)}-x^*)^\top\delta^+v^{(k)}+\cdots$ のように左端点で展開すると、問題で必要な式と符号がずれる。今回の恒等式は 右端点 $v^{(k+1)}$ を使うことで、余りが $-h\|\delta^+v^{(k)}\|^2$ になり、単調性を強める形になる。

方針

$n^{-3}$ で関数が近似できるという仮定は、微分すると $n$ 倍されても $\sum n^{-2}$ が残る、という強さを持っている。この「差を微分しても総和可能」という点が本質である。

採点上の注意

導関数の一様収束だけでは、元の関数の極限が何であるかを結びつける一文が不足しやすい。 今回は $t_n\to f$ も一様に成り立つので、積分表示に極限を入れるのが最も短く確実である。

方針

指数分布の無記憶性から、最小値は「二つの時計の早い方」、差は「残った時計の待ち時間」と読める。 最後の $N$ は、指数待ち時間で構成される Poisson 過程の時刻 $a$ までの到着回数である。

典型ミス

$Z-Y$ の率を $2\lambda$ としてしまう誤りに注意する。二つのうち一つはすでに到着済みなので、 差の段階で動いている残りの待ち時間は一つだけであり、率は $\lambda$ である。

方針

処理時間がそろっている場合は、数値的な負荷ではなく「何個載せるか」の問題になる。 許可機械制約は二部マッチングの容量付き版として扱うと自然である。

採点上の注意

(2) の近似比では、最後に最大負荷を作った仕事に注目するのが定石である。 貪欲法の選択規則から「割当直前の負荷はその時点の平均以下」といえ、平均負荷下界と最大仕事長下界の二つを 最適値 $T^*$ に結びつける。