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

全成分1の行列を見る

この行列は $(a-1)I+J$ と分解できる。成分和が0のベクトルは $J$ で消え、 $(1,1,1)^T$ は $J$ で3倍される。この観察だけで固有値計算がほぼ終わる。

階数は非零固有値の個数

$v_1,v_2,v_3$ が基底なので、$B$ の階数は対応する固有値のうち非零のものの個数を重複度込みで数えればよい。 $a(a-1)$ は重複度2を持つ点を落とさないことが重要である。

不等式は新変数で読む

$y\le0$ は $u-v\le0$、つまり $u\le v$ に変わる。これを忘れると長方形 $(0,1]\times[0,1]$ と誤って積分してしまう。

収束性は $u=0$ だけを見る

領域は $0<u\le v\le1$ なので、特異性は $u^a$ の $u=0$ だけである。 $\int_0 u^a\,du$ が収束する条件 $a>-1$ がそのまま答えになる。

有限操作と可算操作の違い

決定可能集合は有限回の論理演算には閉じているが、可算無限和には一般に閉じていない。 各集合が個別に決定可能でも、それらを一様に判定する手続きが与えられているとは限らない。

還元の向き

$A\le_m B$ は「$B$ が判定できれば $A$ が判定できる」という向きの情報である。 $A$ が簡単だからといって、還元先 $B$ が簡単になるわけではない。

半直積として見る

この群は線形変換と平行移動からなるアフィン群であり、 $\mathbb R^2\rtimes GL_2(\mathbb R)$ と見られる。正規部分群 $H$ は平行移動部分である。

剰余群で残る情報

$H$ で割ると、平行移動の違いは同一視される。残るのは線形部分 $A$ であり、 その積は行列積なので一般には可換でない。

定理の仮定と結論は別

ウリゾーンの距離付け定理の仮定を満たさないことは、距離付け不可能であることを意味しない。 この問題はその違いを確認する典型例である。

非可算性の使いどころ

離散位相では一点集合が全て開であり、基は各一点集合を含まなければならない。 そのため非可算集合上では可算基を持てない。

減衰項を消す変換

$u_t+u$ の形では、$e^t$ を掛けると左辺が $(e^tu)_t$ になる。 これにより通常の熱方程式へ変換できる。

一様収束の確認

点ごとの収束ではなく、$\sup_x |u(x,t)|$ を直接 $Me^{-t}$ で押さえる。 この評価が $x$ に依存しないため、一様収束が従う。

最適解集合は面で切ったもの

線形計画の最適解集合は、実行可能多面体を目的関数の等高面で切った集合である。 そのため凸性は、制約の線形性と目的関数の線形性から直接従う。

端点がない例

最適解集合が直線全体になるようにすると端点がなくなる。非ゼロ目的関数でも、実行可能集合を $x_1=0$ の直線にすれば目的関数 $x_1$ は全点で最適値を取る。

独立性で母関数が積になる

和 $S$ の指数母関数は、独立性により各 $X_i$ の母関数の積になる。 この積を $1+u\le e^u$ で指数型に直すのがChernoff評価の入口である。

最適な $t$ の選択

上側確率では $t>0$ を自由に選べる。指数部 $e^t-1-(1+\epsilon)t$ を最小にする $t=\log(1+\epsilon)$ を選ぶと、 明示的な正の $\delta$ が得られる。

標本平均との関係

指数分布の最尤推定量は標本平均の逆数である。したがって $1/\widehat\theta_n=Y_n$ と書くと、 中心極限定理やデルタ法をそのまま使える。

分散を1にする変換

$Y_n$ の漸近分散は $1/\theta_0^2$ である。$h'(1/\theta_0)=\theta_0$ となる $\log t$ を選べば、漸近分散が1に正規化される。

$L_1$ は例外条件を分ける

$i=1$ のときだけ制約があるので、$i=0$、$i=1$、$i\ge2$ に分けると簡単に文法化できる。

$L_3$ は二つの独立した等式

一見すると二つの文脈自由条件を同時に満たすだけに見えるが、文脈自由言語は一般に共通部分に閉じていない。 四つのブロックを使ったポンピングで、二つの等式を同時に保てないことを示す。

番兵の扱い

$-999$ が出た時点で後続要素は見ない。例の最後の $86$ は平均に含めない。

ゼロ除算の条件

ゼロ除算は、非負整数を一度も数えないまま18行目に到達したときに起こる。 ループを一度も回らない空リストも該当する。

再帰化

while ループの状態変数は、残りのリスト、個数、和の三つである。 これらをそのまま $g(li,c,s)$ の引数にすれば、自然な末尾再帰になる。

ミス時間は周波数で縮まらない

キャッシュミスは100 ns固定なので、クロック周波数を上げてもミス分の時間は残る。 このため半分の実行時間をHWだけで達成することはできない。

I3をヒットとミスに分ける

I3命令は1種類としてまとめず、ヒット率とミス率で分けて時間を足す。 2 GHz では10サイクルが5 nsである一方、ミスは100 nsであり、ここが支配的になる。