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

冪零性を使い切る

$A^3=O$ により、$A$ の3次以上の項はすべて消える。線形独立性も逆行列も、この打ち切りを使うと 低次の係数比較だけで処理できる。

固有値の見方

$X=I+N$ で $N$ が冪零なら、$X$ は「単位行列に冪零を足した行列」であり、固有値はすべて1になる。 固有ベクトルに $(X-I)^3$ を作用させる証明が最も短い。

補助関数の狙い

$J$ は、積分値とSimpson近似値の差を表す関数である。 $a$ における0次から4次までの微分が消えるように係数 $1,4,1$ が選ばれている。

3次式で厳密な理由

Simpson公式は3次多項式まで完全に積分する。剰余が $J^{(5)}$ で表され、3次式ではそれが0になるためである。

$O$ と $\omega$ は全てを二分しない

比 $f(n)/g(n)$ が振動する場合、上に有界でもなく、任意定数を最終的に超えるわけでもない。 そのため (2) のような二分法は成り立たない。

同時成立は不可能

$O$ は最終的な上界を与え、$\omega$ は任意の定数倍を最終的に超えることを要求する。 同じ定数を使うとただちに矛盾する。

共役類はサイクル型

対称群では共役類を数える問題は、整数の分割を数える問題に帰着する。 $S_4$ では $4$ の分割が5個なので共役類も5個である。

偶置換の判定

$\ell$-サイクルの符号は $(-1)^{\ell-1}$ である。 5サイクルと3サイクルは偶置換、互換は奇置換、二つの互換の積は偶置換である。

閉包は有限和と相性がよい

有限個の閉集合の和集合は閉なので、$\overline{A\cup B}=\overline A\cup\overline B$ が成り立つ。 無限和では閉性が壊れるため、(3) は一般には成り立たない。

開球の閉包と閉球

通常のユークリッド空間では一致することが多いが、一般の距離空間では一致しない。 離散距離はその標準的な反例である。

熱核の微分

時間微分と空間二階微分で同じ係数 $-1/(2t)+x^2/(4t^2)$ が出る。ここを明示すれば熱方程式の核であることが分かる。

初期値への収束

熱核は $t\to0+$ で原点に集中する確率密度である。連続性で原点近くを押さえ、有界性で遠方のガウス尾部を押さえる。

価値密度順の貪欲解

これは分数ナップサック問題である。$c_i/a_i$ が降順に並んでいるため、容量が尽きるまで順に入れ、 最後の一つだけを分数で入れる解が最適になる。

双対解で最適性を証明する

貪欲解を主問題側で示すだけでなく、同じ値を持つ双対実行可能解を構成することで、双対定理から最適性が確認できる。

二進小区間

最初の $n$ 桁を固定することは、長さ $2^{-n}$ の小区間を一つ選ぶことに等しい。 一様分布なので、その確率はそのまま区間の長さになる。

無限積への変換

$[-1,1]$ 上の一様分布を $2U-1$ と表し、その二進展開を独立な符号列に直すと、 特性関数が独立性により余弦の積に分解される。

対数尤度

$0<X_i<1$ なので $\log X_i<0$ である。最尤推定量の式では分母が負になるため、 $-n/\sum\log X_i$ は正である。

事象の変形

$\widehat\theta\le0$ を積 $\prod X_i$ の条件に直すと、マルコフの不等式を使える。 負のべき乗を取るため、条件 $s<n(\theta_0+1)$ が積分可能性に対応する。

$R(L_1)$ は正規

$01^n$ を反転して結合すると、中央の $1$ の個数が必ず偶数になる。 偶奇だけを覚えればよいのでDFAで認識できる。

$W(L_2)$ の分解

$0^m10^n$ を二回並べると $0^m10^{m+n}10^n$ になる。 これは $0^m10^m$ と $0^n10^n$ の連接として文法化できる。

二の因子を除く理由

奇数同士の差は偶数になる。最大公約数は奇数なので、差から2の因子を取り除いても最大公約数は変わらない。 これが二進GCD法の基本である。

長さの下限

和が毎回少なくとも半分になるため、長い列を作るには初期和が大きくなければならない。 長さ9では最終直前の和が少なくとも2なので、初期和は少なくとも256である。

配列方式の本質

配列中の出現回数を重みに一致させれば、一様な添字乱数を使って任意の整数比率を実現できる。

大きい共通単位をまとめる

$Nq_i+r_i$ と分けると、$q_i$ の配列の各要素に重み $N$ を持たせられる。 これにより、元の重みの総和に比例する巨大な配列を作らずに済む。