京大 情報学研究科 知能情報学コース 2023年度 院試 解答例・解説

射影として見る

後半の $B$ は抽象的な行列計算ではなく，直和分解に沿った射影である。射影では「一度取り出した成分をもう一度取り出しても変わらない」ため，$B^2=B$ が自然に出る。相似標準形も，$W_1$ の基底を先に，$W_2$ の基底を後に並べればただちに得られる。

不等式の扱い

$\log(1+x)$ の評価は，微分して単調性を見る方法と，積分表示 $$\log(1+x)=\int_0^x\frac{1}{1+t}\,dt$$ を使う方法が安定している。上界との差が $\int_0^x t^3/(1+t)\,dt$ になる形まで変形できれば，符号判定で迷わない。

降順入力でも速くならない理由

降順配列はヒープ構築だけを見ると有利である。しかしヒープソート全体では，最大値を末尾へ送った直後に根へ小さい値が来る。そこから下へ落とす処理が各段階で起こるため，支配項は取り出し部分の $O(n\log n)$ のままである。

4葉木はトポロジーを先に固定する

4葉の根なし二分木は，どの2葉が同じ内部頂点側に付くかで3通りに尽きる。各トポロジーごとに枝長の一次方程式を立て，負の枝長や矛盾が出るものを捨てれば，重複なく列挙できる。

共通点と相違点を両方書く

用語説明では，一方ずつ定義するだけだと比較問題への答えとして弱い。各ペアについて「同じ大分類に属する理由」と「何が違うか」を明示すると，採点者が比較軸を確認しやすい答案になる。

Fisherの正確検定

周辺度数を固定すると自由に動くのは薬A群の「効果あり」人数 $a$ だけである。各表の確率を超幾何分布で並べ，観察表以下の確率を合計する，という順序で書くと両側 $p$ 値の定義に沿った答案になる。

分散比の見方

クラス内平方和 $W$ は同じクラスに入れた点のまとまりを表し，クラス間平方和 $B$ はクラス中心の離れ具合を表す。全体の散らばりが同じなら，$W$ が小さく $B$ が大きい分類ほど分離がよい。

容量は出力エントロピー最大化

今回の通信路では，各入力行のエントロピーが等しい。したがって $I(X;Y)=H(Y)-H(Y\mid X)$ の最大化は，実質的に出力分布のエントロピー最大化になる。対称な行列では一様入力をまず試すのが最短である。

DFT高速化の基本

実数列のDFTには共役対称性がある。2本の実数列を1本の複素列に詰める方法も，偶奇分解で $2N$ 点DFTを作る方法も，この対称性と $W_{2N}^{2kr}=W_N^{kr}$ を使っている。

閉包性の証明

閉包性は「新しい開始記号を1つ足す」構成で示すのが基本である。一方，非閉包性は既知の非文脈自由言語 $a^kb^kc^k$ に帰着する。今回の補集合と差は，この2つの型を組み合わせる問題である。