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

直交化の見通し

$[0,1]$ 上の多項式内積では、$1,\ x-\frac12,\ x^2-x+\frac16$ はLegendre型の直交多項式になっている。正規化は要求されていないので、長さを $1$ にそろえる必要はない。

表現行列の読み方

線形写像の表現行列は、各基底ベクトルの像を同じ基底で座標表示し、その座標を列に並べたものである。今回、直交基底を上の取り方にすると微分で $$g_1\mapsto0,\qquad g_2\mapsto g_1,\qquad g_3\mapsto2g_2$$ となり、標準基底の場合と同じ形の行列が出る。これは偶然ではなく、低次から高次へ作ったモニック直交基底では、微分が次数を一つ下げるためである。

内点で最大を取るときの符号

最大値の議論では、右差分商と左差分商の向きが逆になる。左側では分母 $-h$ が負になるため、不等号の向きを間違えないことが重要である。

積分の分母を見る

三次式の分母は、$x=-1/4$ が根であることに気づけば $$(4x+1)(x^2+1)$$ に分かれる。二次因子 $x^2+1$ は実数上ではこれ以上一次因子に分解しないので、分子を $Bx+C$ と置くのが標準形である。

球帯の面積

単位球では高さ方向の幅 $h$ の球帯面積が常に $2\pi h$ になる。$a$ に依存しない点は、回転面の面積要素で $r(z)$ と $\sqrt{1+r'(z)^2}$ がちょうど打ち消し合うことから確認できる。

積公式の本質

$n$ と互いに素でない数は、$n$ の素因子の少なくとも一つで割り切れる数である。したがって、Euler関数の積公式は「素因子ごとに割り切れるものを除く」という包除原理そのものである。

Möbius関数が現れる理由

$$\prod_{p\mid n}\left(1-\frac1p\right)$$ を展開すると、同じ素数を二度使う項は出ない。平方因子をもつ約数の係数が $0$ になり、平方因子をもたない約数の符号だけが残るため、自然にMöbius関数になる。

乗法性の証明の型

互いに素な法に分ける問題では、中国剰余定理で剰余類を直積に分解するのが最も安全である。単に積公式から示してもよいが、剰余類の全単射を明示すると、なぜ個数が積になるかが明確になる。

極大と最大の違い

極大は「これ以上一本も追加できない」という局所的な条件であり、最大は「辺数が最も多い」という大域的な条件である。上の $M_3$ は未被覆頂点が残るが、未被覆頂点同士を結ぶ利用可能な辺がないため極大である。一方、$M_4$ が存在するので $M_3$ は最大ではない。

Hall条件の使いどころ

最大でないことを示すには、Hall条件を破る部分集合を探すのが速い。この図では下側の三つの頂点が二つの頂点にしか接続していないため、全被覆は不可能である。

帰納法の二つのケース

Hall条件がすべての空でない真部分集合で厳しい場合は、任意の一辺を先に選んでも残りにHall条件が残る。等号を満たす部分集合がある場合は、その部分と補集合に分割してそれぞれ帰納法を適用する。この二分がHallの結婚定理の標準的な証明である。

有限個なら交差してよい

「ほとんど含まれる」は有限個の例外を許す関係である。有限個の集合に同時にほとんど含まれることは、例外集合の有限和を取ればよいので簡単に扱える。(3)はこの事実をそのまま使っている。

可算個では対角化が必要

可算個すべての条件を一度に満たすには、最初の $n$ 個の条件だけを第 $n$ 段階で満たすように区間を区切る。$X_i$ をほとんど含む性質は、十分後の区間では必ず $X_i$ が採用対象に入ることで保証される。$Y_j$ にほとんど含まれる性質は、十分後の区間では $j$ 番目までの制約がすべて有効になることで保証される。

否定の実現子集合

この実現可能性では、$\neg B$ は $B$ の実現子から $\bot$ の実現子を作る関数である。しかし $\bot$ の実現子は存在しない。したがって、$B$ に実現子が一つでもあれば $\neg B$ は実現不能であり、$B$ に実現子がなければ任意の数が空虚に $\neg B$ を実現する。

$\Sigma_1$ と探索

$\Sigma_1$ 式は、計算可能に確認できる条件を満たす witness が存在する、という形である。真であれば総当たり探索がいつか止まる。この性質が、二重否定から実際の実現子を取り出す手続きの核になる。

一様排中律が強すぎる理由

$A(n)\vee\neg A(n)$ をすべての $n$ について実現できる一つのプログラムがあると、選言のタグを見るだけで $A(n)$ の真偽を判定できる。停止問題を $A(n)$ に選ぶと、これは停止問題の決定可能性を意味してしまう。

Pauli行列の反交換

この問題の中心は、Pauli行列が二乗して単位行列になり、異なるもの同士は反交換する点である。これにより $(\mathbf{v}\cdot\boldsymbol{\sigma})^2=I$ が一行で出る。

指数関数の扱い

$A^2=I$ なら、$A$ の偶数乗は $I$、奇数乗は $A$ である。したがって行列指数関数は三角関数と同じ級数に分かれる。固有値分解を使わなくても、級数だけで十分に示せる。

分散の検算

$Z$ の固有値は $\pm1$ なので、任意の正規化状態で $\langle Z^2\rangle=1$ である。したがって分散は $1-\langle Z\rangle^2$ に簡約される。$t=0$ では初期状態が $Z$ の固有状態なので分散は $0$ になり、得られた式とも一致する。

Big-Oで分かること

$T_1,T_2$ が同じ上界 $O(f)$ をもつことから言えるのは、和も $O(f)$ であることまでである。差、比、相互の優劣は下界の情報がないため決まらない。

LISの標準解法

$L[\ell]$ は長さ $\ell$ の候補のうち末尾が最も小さいものだけを残す。末尾が小さいほど後続の値をつなげやすいので、他の候補を捨てても最適性を失わない。これが二分探索による $O(n\log n)$ 解法の不変条件である。

値域が小さい場合

値が定数種類しかないとき、二分探索よりも値ごとのDPが直接効く。狭義増加なので、値 $v$ に接続できるのは $v$ より小さい値で終わる列だけである。値域が定数であることを計算量に反映させるのがポイントである。