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

行列式の積

逆行列を含む積では，$\det(AB^{-1})=\det A/\det B$ を使う。 条件 $c\ne0,\ d\ne24$ は，右側の行列が正則であることを保証するために与えられている。

二次形式の勾配

対称行列 $Q$ に対して $\frac12x^{\mathsf T}Qx$ の勾配は $Qx$ である。 停留点の一意存在は線形方程式 $Qx=-c$ の一意解の問題であり，最小性はヘッセ行列 $Q$ の正定値性で決まる。

密度の変数変換

ロジスティック変換は単調なので，逆関数とヤコビアンで密度を移せる。 値域の端点を入れ忘れると，密度の式は正しくても確率分布として不完全になる。

採点の置き所

行列式では逆行列を展開せず，分子と分母の行列式へ分けることが第一の得点源である。 二次形式では勾配，一意性，最小性をそれぞれ $Qx+c$，正則性，正定値性に対応させる。 変数変換では，逆関数，ヤコビアン，値域の三つを漏らさず書く。

検算

停留点は，求めた $(-9/7,-4/7)$ を $2x_1-x_2+2=0$，$-x_1+4x_2+1=0$ に代入して確認できる。 $f_Y$ は値域全体で積分すると，単調変換の公式により元の一様分布の全確率 1 に戻る。

導出木の左右順

文法にある乗算規則は $T\to T\times F$ であり，左側が再び $T$，右側が $F$ である。 木のラベルが同じでも，左右が入れ替わると別の規則を使ったことになる。

正規文法とNFA

右線形文法の規則 $X\to aY$ は，状態 $X$ から入力 $a$ で状態 $Y$ へ進む遷移に対応する。 規則 $X\to a$ は，入力 $a$ で受理状態に入る遷移と考えればよい。

無矛盾性の示し方

矛盾しないことを示すには，導出が存在しないことを直接示すより，すべての仮定を真にする真理値割当てを一つ与える方が簡潔で確実である。

採点の置き所

導出木の正誤判定では，葉の文字列だけでなく，内部節点が許された生成規則に合うかを確認する。 正規文法とNFAの対応では，非終端記号を状態，終端記号をラベル付き遷移と見て空欄を埋める。 無矛盾性では，矛盾する集合は導出列，無矛盾な集合はモデルを示すと明快である。

典型ミス

整数や有理数の大小関係では「共通上界」が存在するだけでよく，最小上界を要求していない。 じゃんけん型関係は循環するため推移性が壊れる。この点を共通上界条件と混同しない。

計算量の支配項

多項式同士では次数が最大の項が支配し，$n^{\log n}$ は任意の固定次数の多項式より速く増える。 $\sin^2 n$ は 1 以下なので，上界評価では $n^2 2^n$ で押さえるのが自然である。

BST の重複値

挿入コードは `data > p->data` のときだけ右へ進み，それ以外は左へ進む。 したがって等しい値は左部分木へ入る。この条件を読み落とすと，重複を含む配列の高さが変わる。

AVL 回転

右右型は左回転，左左型は右回転で直せる。 右左型・左右型では，まず子側を逆向きに回転してから親を回転する二重回転になる。 回転後も二分探索木の大小関係を保つよう，子の部分木を親側へ付け替える点がコード上の要である。

採点の置き所

計算量比較では，対数，多項式，指数，階乗の階層関係を使って並べる。 BST では重複値の扱いをコード条件から読み，挿入順に木を描くと高さの根拠になる。 AVL 木では不平衡の型を判定してから，単回転か二重回転かを選ぶ。

検算

通常 BST の高さは，挿入後の最長根葉パスを実際にたどって確認する。 AVL 木の高さが通常 BST より小さくなること，かつ各節点の左右部分木高さ差が 1 以下になることを確認すると， 回転の向きの誤りに気づきやすい。