名工大 工学研究科 情報工学系 2024年度 院試 過去問 解答例・解説（全6問）

採点の置き所

TSP では、全探索の候補数、MST が下界になる理由、2近似の上界を別々に書くと部分点を拾いやすい。数値例では Kruskal 法で選んだ3辺の重み合計、近似巡回路の重み、最適巡回路の重みを混ぜずに示す。

典型ミス

文脈自由文法では、末尾の $a$ の個数が初めの $a$ と中央の $b$ の合計になる。$a^p b^q a^q$ と読んでしまうと、長さ8の列挙と非正規性の証明が両方ずれる。

採点の置き所

数値表現は、答だけでなく範囲判定の不等式を1つ添えると安全である。カウンタ設計では、現状態、次状態、入力値の表を先に作り、そこから論理式を簡単化した流れを残すと減点されにくい。

典型ミス

算術右シフトを論理右シフトとして扱うと負数の答が変わる。MIPS では添字をバイトアドレスに変換するため、要素数の加算とアドレスの4バイト加算を区別する。

採点の置き所

通信路では $H(Y\mid X)$ を雑音分布のエントロピーとして求め、次に $H(Y)\le \log 3$ で上界を置き、最後に一様入力で達成できることを示す。この3段階が容量計算の答案になる。

典型ミス

反復符号の多数決では、正しい記号が2回以上出ればよい。3回すべて正しい場合だけを数えると $8/27$ で止まり、$20/27$ にならない。

採点の置き所

接平面では、点の $z$ 座標、$f_x$、$f_y$ をそれぞれ明示してから平面式に代入する。行列式では $n=2$ の初期値と漸化式を両方書くと、一般式の根拠が明確になる。

検算

重積分の integrand は上半円板で正なので、答も正でなければならない。非自明解条件は $|A_n|=0$ と同値であり、$a=-1/(2^n-2)$ を代入すると一般式が0になることを確認できる。

採点の置き所

複素積分は、極の位置、極の位数、留数の3点を分けて書く。$n=1$ と $n=2$ だけ場合分けが必要になる理由を明示すると、一般式との混同を避けられる。

典型ミス

Parseval では $a_0^2$ の係数が $1/2$ になる。ここを落とすと $\sum 1/k^4$ の係数がずれるので、左辺の平均値積分と右辺の係数を同じ正規化で書く。

採点の置き所

補間では、3点を代入した連立方程式の解と、一般の Vandermonde 行列が正則である理由を別に示す。後半の級数では、比の極限、比較判定、項が0に近づかないことを問題ごとに使い分ける。

典型ミス

$\rho>1$ なら比判定で発散だが、$\rho=1$ では何も言えない。$\rho=1$ を発散条件として使う答案は、$1/n^2$ の反例で崩れる。