東京科学大 情報理工学院 数理・計算科学系 専門科目（数理・計算科学） 2022年度 院試 解答例・解説

像は二次元に入る

$Av$ は常に $x$ と $y$ の線形結合になる。非零固有値の固有ベクトルは $A^2v$ から復元できるため、 この二次元部分空間だけを調べればよい。

コーシー・シュワルツの使いどころ

$\|x\|^2\|y\|^2-(x^Ty)^2>0$ は、$x,y$ が一次独立であることから従う。 この正性により $A^3=A$ が不可能になる。

積の形は対数微分的に見る

$g=A(x)B(y)$ では、$x$ 微分と $y$ 微分が別々の因子に作用するため $g_{xy}g=g_xg_y$ という積の恒等式が出る。

変数変換の符号

$u=x+y,\ v=x-y$ では、$x$ 微分は $\partial_u+\partial_v$、$y$ 微分は $\partial_u-\partial_v$ になる。この差から混合微分だけが残る。

同時に充足可能とは限らない

二つの式が別々に充足可能でも、同じ割り当てで同時に真にできるとは限らない。 $x$ と $\neg x$ は最小の反例である。

補助変数の役割

$\phi^+$ の $x_i$ は、どこかで真になった $\phi_j$ の位置を後続の節へ伝えるスイッチとして働く。 全ての $\phi_i$ が偽なら、節を左から読むだけで矛盾が出る。

核は正規

$SL_2$ の正規性は、行列式準同型の核として見るのが最短である。 共役で行列式が変わらないことを直接計算してもよい。

位数2の行列

標数が2でない体では、$M^2=I$ の最小多項式は $(t-1)(t+1)$ を割る。 そのため非自明なものは $-I$ か、固有値 $1,-1$ の行列に限られる。

有限性を使う場所

有限ハウスドルフ空間が離散になる証明では，$\{x\}$ を 「$x$ を含み，他の各点を除く開集合」の共通部分で作る。 ここで共通部分が有限個であることが重要で，無限個の開集合の共通部分は一般には開とは限らない。

対角集合の判定

ハウスドルフ性と対角集合の閉性は標準的な同値条件である。 この問題では閉性からハウスドルフ性だけを使えばよいが，積位相の基本開集合 $U\times V$ を明示して，$U\cap V=\emptyset$ を対角集合との交わりで確認するのが安全である。

商空間の典型ミス

商写像 $p$ が開写像であることは自動ではない。最後の設問ではこの仮定により $p(U)$, $p(V)$ が商空間で開集合になる。ここを書かずに 「像だから開」としてしまうと，商位相の定義と混同した誤答になる。

線形性の見抜き方

積分の中に $f(y)$ だけでなく $y$ という固定項が入っているため，この写像は 線形作用素ではなくアフィン写像である。線形性を否定する最短の確認は $T0\ne0$ を示すことである。

縮小定数

縮小写像の評価では $e^{-x}\le1$ を使って $\int_0^1 e^{-(x+y)}dy\le\int_0^1e^{-y}dy$ とする。 厳密な値は $e^{-x}(1-e^{-1})$ であり，最大は $x=0$ で $1-e^{-1}$ である。定数が $1$ 未満であることが不動点定理適用の要である。

存在と一意性を同時に得る

積分方程式を直接解く必要はない。完備距離空間上の縮小写像であることを示せば， 反復列 $f_{n+1}=Tf_n$ が唯一の不動点に収束するため，存在と一意性が同時に従う。

同次制約の見方

$Ax=0,\ x\ge0$ は錐を作る。したがって正の目的関数値を持つ実行可能解が一つでもあれば， それを何倍にも伸ばせる。最適解が存在するという仮定は，この「無限に伸ばす」可能性を排除する役割を持つ。

最適性証明

候補解を見つけただけでは最適性は示せない。線形計画では双対実行可能解を一つ作り， 主問題の候補値と双対値が一致することを示すと，弱双対性により簡潔に最適性を証明できる。

典型ミス

双対変数の符号制約は，主問題の等式制約に対応するため自由変数である。 ここでは具体的な $y^\ast$ が正なので問題にならないが，機械的に $y\ge0$ を課すと 一般には別問題になる点に注意する。

最小密度の意味

$\int\min(f,g)$ は二つの分布が共有できる確率質量の総量である。 一致確率を大きくする結合を作っても，対角上に置ける質量は各点で小さい方の密度を超えられない。

全変動距離

$1-r$ は二つの分布の全変動距離である。 集合 $A=\{f\le g\}$ は差 $g-f$ が正になる領域を集めたものなので， 確率差の最大値を達成する集合になっている。

確認観点

最後の不等式では，$B$ に含まれる正の寄与だけを残すと最大になる。 $\int_B(f-g)$ を絶対値付きで直接 $\int_B|f-g|$ と評価すると 上界が $2(1-r)$ になり，設問の鋭い評価に届かない。

正規化定数

指数部を行列で書くと，これは平均ゼロの二次元正規分布であり， 精度行列の行列式だけで正規化定数が決まる。 $|\theta|<1$ はこの行列が正定値になるための条件でもある。

スコア方程式

対数尤度で $\theta$ に依存するのは $\log(1-\theta^2)$ と $\theta\sum X_iY_i$ だけである。二乗項 $\sum X_i^2,\sum Y_i^2$ を微分に残してしまうのは典型的な計算ミスである。

期待値計算の確認

$\theta=0$ では相関が消え，積 $X_iY_i$ は平均 $0$，分散 $1$ の独立同分布列になる。 したがって標本平均の二乗平均が $1/n$ に下がることは，分散の基本公式とも一致する。

差の閉包性

差 $A\setminus B$ は $A\cap \overline{B}$ と同じである。 DFA で補集合と積を作れるため，正則言語で閉じる。積オートマトンの受理状態を 明示すると，答案として十分に厳密になる。

$\{ww\}$ の非正則性

文字列 $0^p10^p1$ は中央の位置が明確で，ポンプできる範囲が最初の $0$ の列に閉じ込められる。 そのため，片側だけを変化させて「前半と後半が同じ」という条件を壊せる。

無限正則言語の分割

無限 DFA 受理言語では，ある受理計算の途中に状態の反復が必ず現れる。 その反復部分を偶数回だけ使う集合と，元の言語からそれを除いた集合に分けるのが自然である。 奇数回の反復語が補集合側に無限個残るので，両方が無限になる。

連結コスト

リスト連結は第1引数のセルをコピーするため，第1引数が長いほど高くつく。 平坦化で毎回左側の結果を連結すると，同じ要素が何度もコピーされ，二次的な回数になる。

蓄積引数の意味

$\mathrm{flat}(x,\mathrm{acc})$ は「$x$ を平坦化した結果を $\mathrm{acc}$ の前に付ける」関数と考えると正しさが見やすい。 右部分を先に処理し，その結果を左部分の蓄積先にすることで，左から右の順序を保ったまま 最後の連結を不要にできる。

確認観点

改良版で左部分から先に処理してしまうと，出力順序が逆転することがある。 再帰の順序が計算量だけでなく出力順序にも関わる点を確認する。

まず数える量

キャッシュ問題では，容量より先に「1 ブロックに何要素入るか」と 「何本のラインがあるか」を数える。ここでは 1 ブロック 4 要素，256 ラインである。

行優先配置の影響

C 言語風の二次元配列は行優先なので，添字の右側を増やすアクセスが連続アドレスになる。 行方向走査では 1 回のミスで持ってきた 4 要素を使い切れるが，列方向走査では 32768 バイトのストライドで同じラインに衝突し続ける。

追い出しの確認

直接写像では，同じインデックスに対応するブロックが来た瞬間に以前のブロックが追い出される。 $32768$ バイトはキャッシュ全体の 4 周分なので，列方向では同じ列の次の行が 常に同じラインへ写る。このため $A[0][0]$ のブロックは，同じブロック内の次要素を使う前に失われる。