名大 情報学研究科 数理情報学 2025年度 院試 解答例・解説

部分空間の読み取り

2本の一次条件で定義された部分空間では、自由変数を選んで基底を出すのが最短である。ここでは $x,y$ を自由変数にすると全成分が直ちに表せる。得られた2本のベクトルが一次独立であることまで書けば、単に「張る」だけでなく「基底」であることが確認できる。

直交補空間

$W=\{v:Av=0\}$ と見れば $W^\perp$ は $A$ の行空間である。今回の2本の法線ベクトルは一次独立なので、$\dim W^\perp=2$ と合わせてそのまま基底になる。正規直交基底では、$W$ 側と $W^\perp$ 側を別々に正規直交化すればよい。

線形写像の行列

直交分解 $\mathbb{R}^4=W\oplus W^\perp$ に沿って作用が定まっているので、射影を使うと $$L=4P_W+8P_{W^\perp}$$ と一行で表せる。$P_{W^\perp}=I-P_W$ を使えば計算量が少ない。検算として、求めた行列を $W$ の基底ベクトルに掛けると $4$ 倍、$W^\perp$ の基底ベクトルに掛けると $8$ 倍になる。

微分可能性と導関数の連続性は別

$x^2\sin(1/x)$ 型では、原点での微分可能性は差商を見る。差商が $h\sin(1/h)$ になり、これははさみうちで $0$ に落ちる。一方、導関数には $-\cos(1/x)$ が残るため、導関数の連続性は失われる。この2段階を分けて書くことが重要である。

定積分の置換

分母に $\sin x$ と $\cos x$ が混在しているため、$t=\tan x$ が有効である。変形後に $$\frac{1}{\sqrt{1+t^2}+t}=\sqrt{1+t^2}-t$$ と有理化すると、標準的な積分に帰着する。

級数判定

(a) は符号が素数判定で変わるが、絶対値を取ると単純な幾何級数である。(b) は $1/\sqrt n$ と同程度なので発散する。(c) は交代級数判定法の典型例であり、絶対収束しないことまで述べると判定が完全になる。

同型で代数的閉性は保たれる

代数的閉性は「任意の非定数多項式が根を持つ」という性質であり、体同型で係数を移せば保存される。根を $\Omega$ 側で見つけてから同型の逆で $K$ に戻す、という流れを明示するのが要点である。

有限体の大きさ

標数 $p$ の有限体は必ず素体 $\mathbb{F}_p$ を含む。有限次元ベクトル空間として次元が $m$ なら、元の個数は $p^m$ である。この $m$ がそのまま拡大次数である。

Frobenius と固定体

$p$ 乗写像は Frobenius 写像である。標数 $p$ では $(x+y)^p=x^p+y^p$ が成り立つため、加法も保つ。固定体の計算では $$\{x:x^{p^n}=x\}=\mathbb{F}_{p^n}$$ という有限体の基本事実と、有限体の交わり $$\mathbb{F}_{p^m}\cap\mathbb{F}_{p^n} =\mathbb{F}_{p^{\gcd(m,n)}}$$ を使う。

閉集合と木

Baire 空間の基本開集合は有限始切片で決まる。閉集合 $A$ から「$A$ の元として実現する有限始切片」を集めると木になる。閉性は、全ての有限始切片が $A$ に近づけるなら極限点も $A$ に入る、という形で使われる。

コンパクト性と有限分岐

有限分岐性は、各節点の直後に許される値が有限個しかないという条件である。コンパクト集合から作った木で分岐が無限にあると、離散空間 $\omega$ への連続射影の像が無限になり、コンパクト性に反する。逆向きは、各レベルが有限になるので有限集合の直積の閉部分集合としてコンパクト性を得る。

連続像の座標ごとの有界性

最後の設問は、Cantor 空間の閉部分集合がコンパクトであることと、離散空間のコンパクト部分集合が有限であることを組み合わせる。$\omega^\omega$ 全体への像が一様に有限集合へ入るわけではないが、各座標ごとには有限個の値しか取らない。この有限な座標像を上から押さえる関数が $g$ である。

観測量とエルミート性

量子力学で測定値が実数になることに対応して、観測量はエルミート作用素で表される。$2\times2$ 行列では、対角成分が実数、非対角成分が互いに複素共役、という条件に直すとよい。

行列指数関数

$A=A^\dagger$ のとき $itA$ は反エルミートである。その指数関数はユニタリになる。これは時間発展がノルムを保つことに対応している。

全体位相

今回の初期状態は $B$ の固有ベクトルになっているため、時間発展は全体位相 $e^{2it}$ を掛けるだけである。期待値や分散は全体位相に依存しないので、計算は大幅に簡単になる。

エンタングル判定

二量子ビット純粋状態 $$\sum_{i,j}c_{ij}|ij\rangle$$ が積状態であることは、係数行列 $(c_{ij})$ が階数 $1$ であることと同値である。行列式が非零なら積には分解できないので、エンタングル状態と判定できる。

増加率の比較

オーダー表記では定数倍を落とし、最終的に支配的な項だけを残す。$(\log n)^{\log n}$ は多項式より遅いように見えやすいが、指数表示すると $\exp((\log n)(\log\log n))$ であり、任意の固定べき $n^\varepsilon$ を超える点に注意する。

再帰木

$T(n)=2T(n/2)+cn$ は各レベルの合計コストが常に $cn$ になる。レベル数が $\log_2 n$ なので $n\log n$ が出る。葉の合計 $n$ は低次なので、全体は $\Theta(n\log n)$ である。

棒分割の DP

長さ $j$ の最適値は、最後に選ぶ最初の切断長 $i$ によって $p_i+r[j-i]$ と分解できる。この「最適部分構造」があるため、短い長さから順に最適値を埋めればよい。カットコストがある場合は、実際に切るたびに $c$ を1回だけ引く recurrence に変える。分割しない選択 $p_j$ を残すことが、カットコスト付き問題での典型的な落とし穴である。