名工大 工学研究科 情報工学系 2026年度 院試 解答例・解説

採点の置き所

木の問題では、走査列、スタック操作、探索停止条件、計算量を別々に答える。正規性の証明では、正規な例はオートマトンを示し、非正規な例は閉路反復またはポンピング補題で矛盾を作る。

典型ミス

二分探索木の計算量は木の高さに依存する。常に $O(\log N)$ と書くと、退化した木の $O(N)$ を落とすことになる。

採点の置き所

組合せ回路では、半加算器2個から全加算器を作る構成、MUXの選択信号ごとの出力、桁上げ先見の再帰式を順に示す。命令処理では、命令形式、制御信号、PC更新部の追加を分けて書くと読みやすい。

典型ミス

選択回路の式では、$s_1,s_0$ のどちらを上位選択信号として読むかを固定する必要がある。制御表では store 命令の RegWrite を0にしないと、不要なレジスタ書込みをする回路になる。

採点の置き所

相互情報量は、$P_X$、$P_Y$、$P(Y\mid X)$ を表にしてから $H(Y)-H(Y\mid X)$ に代入する。写像問題では、$p_a$ 単体の単射性と後段の線形写像を含めた全単射性を分けて判定する。

検算

無向グラフの次数和は常に偶数で、辺数の2倍になる。写像 $p_a$ は $a<0$ で正の部分が消える区間を持つため、単射でないことを具体例で確認できる。

採点の置き所

極値問題では、内点の停留点、Hessianによる分類、制約領域の境界比較を分ける。行列問題では、$J$ の固有空間を使って $A$ の固有値と $A^n$ を同時に出す流れが最も短い。

典型ミス

制約領域では、内点の極大値 $16/9$ より境界上の値 $3$ が大きい。停留点だけで最大値を決めると誤答になる。

採点の置き所

$1/f$ の積分では、零点の位置、単純零点であること、各零点での留数を順に書く。微分方程式の一般条件では、特解が境界値を満たす場合と同次解で補正できる場合を分ける。

典型ミス

特性方程式の根に正の実部がある成分は無限遠で発散するため使えない。境界条件の分類で、根の符号と特解の係数を同じ条件としてまとめないこと。

採点の置き所

独立集合族の判定では、空集合、部分集合閉性、交換性の3条件を順に確認する。ガンマ・ベータ関数では、領域変換、ヤコビアン、分離積分、恒等式の導出を一続きで書く。

検算

$x=uv,\ y=(1-u)v$ では $x+y=v$ なので、$v$ の範囲が元の $x+y$ の範囲に対応する。最後の積分は正値なので、$\Gamma(1/4)^2/(4\sqrt{\pi})$ も正になる。