北大 情報科学院 情報科学専攻 情報理工学コース 専門科目 2025年度 院試 解答例・解説

非斉次解と斉次解

連立一次方程式 $Ax=b$ では，特解に $Ay=0$ の解を足しても右辺は変わらない。第3小問はこの事実そのものを問うている。数値計算だけでなく，$A(x_0+y^*)=Ax_0+Ay^*$ と一行で理由を書くと答案として強い。

三角化された行列

$B$ は下三角行列なので，固有値は対角成分からすぐ読める。べき乗では，固有値だけでなく $B^2=r^2I$ という関係に気づくと，対角化を使わずに偶奇で一気に求まる。

広義積分の典型ミス

$\log x/x$ は原始関数が $(\log x)^2/2$ 型になるため，$x\to0+0$ で有限値に近づかない。符号だけを見て「面積が小さい」と判断しないこと。微分方程式では，$(2x-1)(1+y^2)$ にまとめてから変数分離するのが最短である。

包除原理の整理

人数問題は，ベン図に「三つ同時」の人数を最初に置くと計算が安定する。特に第2小問では，帽子着用者からマフラー着用者とセーター着用者を引くと，両方を着用した人を二重に引くため，最後に三者共通部分を戻す必要がある。

恒真式の確認

恒真式でないことを示すには，反例となる真理値割当を一つ出せば十分である。恒真式であることを示す側は，真理表を全行書いてもよいが，本問の二つ目は前件が真と仮定して結論が必ず真になることを追う方が短い。

オートマトン設計

「少なくとも一つの $a$ と少なくとも一つの $b$」という条件では，記憶すべき情報は「見た文字の集合」である。したがって $2^2=4$ 状態で十分であり，受理状態に入った後はどの文字を読んでも受理状態に留まる。

片側検定との取り違え

平均点はB組の方が高いが，問題が「B組の方が高いか」ではなく「差があるか」を問う場合は両側検定で判定する。片側5\%の臨界値を使うと結論が変わり得るので，答案では検定の向きを明記する。

不偏分散とプール分散

標本分散を $n$ で割るか $n-1$ で割るかの取り違えが頻出である。2標本 $t$ 検定のプール分散は不偏分散を自由度で重み付けして作るため，$(n_1-1)s_1^2+(n_2-1)s_2^2$ を分子に置く。

特性関数の使いどころ

独立和を扱うとき，密度の畳み込みを直接計算するよりも特性関数を掛け算に変える方が簡単である。中心極限定理の証明でも，標準化和の特性関数が標準正規分布の特性関数に近づくことを示せばよい。

Big-Oは支配項を見る

$O$ 記法では十分大きい $n$ での成長率だけを見る。三角関数の恒等式で定数に落ちる式と，$\sqrt n$ や指数関数のように $\log n$ や $2^n$ を上回る式を区別することが重要である。

走査順の確認

先行順，中間順，後行順は「根をいつ読むか」だけが違う。部分木ごとに括って処理すると，節点数が多くても混乱しにくい。配列表現では完全二分木の位置関係から，親は $\lfloor i/2\rfloor$，左子は $2i$，右子は $2i+1$ になる。

ダイクストラ法の検算

最短路問題では，距離が確定した頂点から隣接頂点を緩和する。今回のように同じ最短距離を与える経路がある場合，最短距離は一意でも最短路木は一意とは限らない。答案では距離と，最短路木の一例を分けて書くとよい。

Transformerの構成

Transformerは，系列を逐次処理する再帰構造ではなく，Attention機構を中心に並列計算しやすい構造を取る。Encoderは入力系列を表現に変換し，Decoderは出力系列を生成する。Self-Attentionと全結合フィードフォワードネットワークの組が基本単位である。

Q学習とTD学習

TD誤差 $$R_{t+1}+\gamma V(S_{t+1})-V(S_t)$$ は「現在の推定」と「一歩先を見た目標値」の差である。Q学習ではこの考え方を行動価値に拡張し，次状態での最大行動価値を目標に使う。オンポリシーとオフポリシーの違いを言葉で説明できるようにしておきたい。

指標名の対応

再現率は実際の正例をどれだけ拾えたか，適合率は正例と予測したものがどれだけ当たったか，正解率は全体のうち正しく分類した割合である。式の分母を見れば，混同行列のどの観点を測っているかが分かる。

ドントケアの利用

4ビットでは16通りを表せるが，10進1桁として有効なのは0から9だけである。10から15をドントケアにすると，カルノー図で大きなまとまりを作れ，$X=A_1\overline{A_2}+A_2A_0$ まで簡単化できる。

基数変換

整数部は基数で割った余りを下から読む。小数部は基数を掛けて整数部を順に読む。$0.3125$ は $5/16$ なので2進では有限小数になる。

最長プレフィックス一致

ルーティング表では，単に最初に一致した経路を選ぶのではなく，最も具体的な経路を選ぶ。今回の $172.18.10.5$ は /24 には入るが /28 の範囲には入らないため，Cが正しい。TTLの説明では，「ループを防ぐ」だけでなく「0になったら破棄される」まで書くと十分である。