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

核は方程式を減らして見る

この行列は行が強く従属しているため、最初から4本の方程式を全部扱う必要はない。独立な条件は 実質的に $x_4=0$ と $x_1-x_2+x_3=0$ の二つであり、ここから核の次元が2であることも同時に分かる。

直交補空間の求め方

$\ker A$ が線形方程式 $$u_1\cdot x=0,\qquad u_2\cdot x=0$$ で表されるとき、$(\ker A)^\perp$ は $u_1,u_2$ が張る空間になる。この問題では $(1,-1,1,0)$ と $(0,0,0,1)$ がそのまま直交しているため、正規化だけで済む。

典型ミス

$A^2$ の固有値を求める場面で、$A$ の固有値をそのまま二乗する方針自体は正しいが、 $A$ の固有構造を先に求めるよりも、$\ker A$ とその直交補に分けて $A^2$ を二次元化する方が計算ミスが少ない。 また、固有値 $0$ の固有空間は $\ker A^2$ であり、ここでは $\ker A$ と一致することを明示してから基底を選ぶ必要がある。

対称性は式の不変性で確認する

図形が $y=x$ に関して対称であることは、$(x,y)$ を入れ替えても方程式が変わらないことから従う。 図を描かなくても、$f(y,x)=f(x,y)$ と一行書けば十分である。

極値判定

$(0,0)$ は停留点だが極値ではない。ヘッセ行列の固有値は $3,-3$ なので不定であり、 原点近くで増える方向と減る方向がある。停留点をすべて列挙しただけで極値と判定しないことが重要である。

領域 $D$ の確認

$D$ は $f\le0$ で切り取った第一象限部分であるから、最大値は境界値 $0$ を超えられない。 最小値は内部停留点か境界で生じる。境界では $f=0$ であり、内部停留点では $-1$ なので、最小値は $-1$ である。

真理値表からの標準形

真理値表で $1$ になる行だけを取り出し、その行で真になるリテラルの積を作って論理和を取ればよい。 例えば $p=1,q=1,r=0$ の行からは $p\wedge q\wedge\neg r$ が出る。

シングル型が弱い理由

シングル型では同じ変数の正負を混在させられない。したがって矛盾を作ることができず、恒偽式を表せない。 ここを見落として、通常の論理和標準形の存在定理をそのまま使うと誤答になる。

ダブル型は恒偽項を足して調整できる

$p\wedge\neg p$ は常に偽なので、論理和に追加しても元の論理式を変えない。 この「値を変えない項」で不足している極性を補うのが、ダブル型の存在を示す簡潔な方法である。

見えている構造

この問題の $N$ は複素数 $a+bi$ を実 $2\times2$ 行列で表したものである。 ただし行列は標準的な $\begin{pmatrix}a&-b\\b&a\end{pmatrix}$ ではなく、$i$ を $\begin{pmatrix}0&1\\-1&0\end{pmatrix}$ に対応させているだけで、本質は同じである。

商環の元は一次式で代表できる

$X^2+1$ で割った商では、$X^2=-1$ と見なせる。したがって任意の元は $a+bX$ の形に直せる。この代表元の一意性を使うと、同型写像の核も簡単に確認できる。

体であることの直接確認

既約多項式と極大イデアルの一般論を使ってよいが、逆元を直接書く方法も有効である。 $$(a+bX)^{-1}=\frac{a-bX}{a^2+b^2}$$ と書けることを示せば、零でない元がすべて逆元を持つことが分かる。

Diniの定理そのもの

これはコンパクト空間上の単調収束が、極限関数の連続性と合わせて一様収束を与えるという Diniの定理の典型的な証明である。ポイントは、点ごとの収束を開被覆に変換することである。

増大する開被覆を使う理由

有限部分被覆が取れても、一般には一つの $O_k$ だけで全体を覆えるとは限らない。 しかし今回は $O_1\subset O_2\subset\cdots$ という増大性があるので、有限個の最大添字だけを残せばよい。

逆向きは一様極限の定理

問題文の条件は一見 $f_k$ の一つだけを評価しているように見えるが、単調性によりそれ以降のすべての $f_n$ に同じ評価が伝わる。したがって通常の一様収束の定義になる。

エネルギー法の核心

波動方程式のエネルギーでは、$\int u_tu_{xx}$ を部分積分して $\int u_xu_{xt}$ と打ち消すのが標準手順である。この問題では減衰項 $u_t$ があるため、 最後に $-\int |u_t|^2$ が残り、エネルギーが減少する。

境界項が消える理由

$[u_tu_x]_0^1$ が消えるのは、境界条件を時間微分して $u_t(t,0)=u_t(t,1)=0$ が分かるからである。 ここを書かないと、部分積分の正当化が不十分になる。

等号成立条件

エネルギーが少しも減らないためには、減衰で失われる量 $\int |u_t|^2$ が全時間で $0$ でなければならない。 そこから $u_t=0$、さらに方程式と境界条件から $u=0$ と進むのが自然な流れである。

双対の符号規則

最大化問題で制約が $\le$、変数が非負なら、双対は最小化問題で、双対変数は非負、双対制約は $\ge$ になる。目的関数と制約行列を転置して並べればよい。

相補性を使うと計算が短い

与えられた双対最適解では $y_2,y_4$ が正であるため、主問題の第2・第4制約は等号になる。 この二本から解を一次元の直線に落とし、残りの不等式で区間を切るのが最短である。

典型ミス

最適解を一つだけ求めて終わると、最後の集合表示を落とす。双対制約が三つとも等号であるため、 主変数が正であること自体は相補性に反しないが、主制約の残り二本が区間端点を決める点に注意する。

幾何分布の取り方

ここでの幾何分布は $1,2,\ldots$ 上の分布である。そのため確率母関数の先頭は $ps$ であり、 $p$ ではない。支持が $0,1,\ldots$ の型と混同しないようにする。

ランダム和は母関数に代入する

$N$ 個の独立同分布な和では、条件付きで見ると $$E[e^{tS}\mid N]=M_X(t)^N$$ である。したがって最後は $G_N(M_X(t))$ と計算できる。

分布の解釈

指数分布の和を幾何回数で止めると、再び指数分布になる。これは指数分布の無記憶性とも整合している。

対数を取れば正規分布

密度に $1/x$ が現れているのは、変数変換 $Z=\log X$ のヤコビアンによるものである。 この問題は対数を取ると通常の正規分布の推定問題になる。

最尤推定量

$\sigma_0$ が既知なら、$\mu$ については $\log X_i$ の二乗和を最小にする問題である。 したがって標本平均 $\frac1n\sum\log X_i$ が最尤推定量になる。

最小分散不偏線形推定

最後の係数は、分散が小さい観測値に大きい重みを与える逆分散重みである。 $\sigma_i^2$ ではなく $\sigma_i^{-2}$ に比例する点が典型的な確認ポイントである。

二の補数は下位ビットから読む

二の補数は「反転して1を足す」操作である。右から読むと、繰上りが残っている間は特別な処理をし、 最初の $1$ を越えた後は単なるビット反転になる。このため $A^R$ は少数状態で認識できる。

$01$ と $10$ の差

二進列を左から見ると、値が $0$ から $1$ に変わる回数と $1$ から $0$ に変わる回数の差は、 端点のビットだけで決まる。内部の往復は相殺されるため、最初と最後のビットだけ記憶すればよい。

ポンピング補題の文字列選び

$\binom01^p$ のように一文字が両方の個数に同時に寄与する列を選ぶと、ポンプしても等式が保たれてしまう。 片方の個数だけが変わるように、前半を $\binom00$、後半を $\binom11$ に分けるのが要点である。

値の大きさも計算量に入れる

単純な疑似コードだけを見ると Algo2 は $n$ 回のループに見えるが、扱う整数のビット長が増える。 各加算が定数時間ではなく $\Theta(i)$ 時間かかるため、全体は $\Theta(n^2)$ になる。

再帰版は呼び出し木で指数的

Algo1 は同じ値を何度も再計算する。加算コストを無視しても呼び出し数は指数的であり、加算コストを入れても 上界 $O(2^n)$ は保たれる。

高速化の本質

行列累乗に直すと、再帰的な依存を二分累乗でまとめられる。行列サイズが固定なので、計算量の主因は 「何回掛けるか」と「整数のビット長」であり、それぞれ $O(\log n)$、$O(n)$ である。

用語問題の書き方

指定キーワードを羅列するだけでは説明にならない。割込みでは「誰が発生させるか」、デッドロックでは 「何を待って進まないか」、ラウンドロビンでは「どのタイミングで交代するか」を入れると採点されやすい。

非プリエンプティブの影響

高優先度のプログラムが途中で実行可能になっても、現在のCPU処理は横取りされない。 例えば $A$ は時刻50 msにCPU待ちへ戻るが、時刻40--70 msの $C$ のCPU処理は継続する。

独立した入出力装置

I/O1 と I/O2 は同時に動ける。CPUだけを追うと誤りやすいので、各プログラムがCPUを離れた時点で どの入出力装置に並ぶかを別々に管理するのが安全である。