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

漸化式は行列の極限に落とす

2 項漸化式では $(a_{k+1},a_k)^T$ を状態ベクトルにするのが定石である。 絶対値が 1 未満の固有値に対応する成分は消え，固有値 1 の成分だけが極限に残る。

歪対称行列の固有値

実歪対称行列は，実数上では回転成分を表す行列であり，非零固有値は実軸上には現れない。 行列式の非負性は，固有値が $\pm i\mu$ の対で現れることから積を見れば分かる。

採点の置き所

漸化式では状態ベクトルの取り方，遷移行列，固有値分解，初期値への適用までが採点対象になる。 歪対称行列の小問では，実ベクトルに対する $x^TAx=0$ と，複素固有値の議論を分けて書く。 行列式の非負性は固有値対の積まで示すと，結論だけよりも答案として強い。

検算

$\lim B^n$ の各行が同じになるのは，漸化式の極限で $a_{k+2}=a_{k+1}=a_k$ となることと整合する。 $\lim a_k=2/3$ は，初期ベクトル $(1,0)^T$ に極限行列を掛けた第2成分でも確認できる。

否定された含意

$\neg(A\to B)$ は $A\land\neg B$ と同値である。 この変形を先に行うと，真理値表も選言標準形もほぼ同時に求まる。

自然数の表現と全称除去

後者関数 $s$ を用いる表現では，$1=s(0)$，$2=s(s(0))$ である。 証明図では，全称命題から必要な具体項を代入した式を取り出し，最後に含意除去を使う。

あいまい性の見抜き方

元の規則 $S\to SaS$ と $S\to Sb$ は，末尾の $b$ を大きな部分木の外側に付けるか， 右側の $S$ の内側に付けるかで導出が分かれる。 非あいまい化では，生成語を $c(b\mid ac)^*$ と見て，末尾から一意に規則を決められる形にする。

採点の置き所

真理値表は行順を明示し，最少リテラルの形は同値変形から導く。 自然演繹の空欄は番号だけでなく，どの公理または全称除去で出た式かを追えるようにする。 文法のあいまい性は，二つの異なる導出を具体的に示して初めて十分な説明になる。

典型ミス

$\neg(p\to(q\land r))$ を $\neg p\lor(q\land r)$ としてしまうと，全ての後続答案が崩れる。 非あいまい文法では同じ言語を生成していることが必要なので，単に導出を一つに制限して語を減らさないようにする。

スタックは右端が上

この記法では最後に追加されたデータが右端にある。 POP は右端を取り除く操作なので，途中状態を書き出すと選択肢の取り違えを防げる。

substring と subsequence の違い

最長共通部分文字列は連続性が必要なので，不一致なら長さは 0 に戻る。 最長共通部分列では連続性が不要なため，不一致でも「一方の末尾を使わない」場合の最大値を引き継ぐ。

編集距離の三つの遷移

置換は左上，削除は上，挿入は左から来る。 境界条件は空文字列との変換コストであり，挿入・削除のコストが 2 なので $2i$ になる。

採点の置き所

スタック問題では，PUSH/POP の途中状態を列で書くと選択肢の根拠が明確になる。 動的計画法では，表の意味，初期条件，遷移式をそれぞれ示すと空欄以外でも部分点が入る。 編集距離は操作コストが通常と異なるため，境界値と三つの遷移のコストを明記する。

検算

最長共通部分文字列では，不一致セルが 0 になるため，表に長い値が連続して現れないかを見ると確認できる。 編集距離の最終値は，削除・挿入だけで変換する上界より小さいこと，かつ負にならないことを確認しておく。

時間スケーリングと遅れ

$f(at-b)$ は $1/a$ の時間スケーリングと $b/a$ の遅れを同時に含む。 変数変換を直接行うと，係数 $1/a$ と指数因子 $e^{-bs/a}$ の両方が自然に出る。

Bode 線図

$(1+s/2)^{-1}$ と $(1+s/10)^{-1}$ の 2 つの一次遅れを足し合わせて考える。 ゲイン線図では各極で $-20$ dB/dec ずつ傾きが増え，位相線図では各極が約 $-90^\circ$ を寄与する。

Routh 条件と根軌跡

3 次多項式 $s^3+a_2s^2+a_1s+a_0$ では，係数正と $a_2a_1>a_0$ が安定条件になる。 根軌跡では，ゲインを上げると応答速度だけでなく振動性も変わるため，定常偏差だけを見て $K_0$ を大きくしすぎるのは危険である。

採点の置き所

時間遅れのラプラス変換では，積分下限が変わる理由を $f(\tau)=0$ と結びつけて書く。 Bode 線図は折点，傾き，位相の三点がそろえば十分に採点される。 根軌跡では実軸上の存在区間，分岐点，漸近線重心，角度をセットで整理する。

検算

ステップ応答 $y(t)$ は $y(0)=0$，$\lim_{t\to\infty}y(t)=1$ を満たす。 定常偏差 $5/(5+K_0)$ は $K_0=45$ で $0.1$ になり，安定上限 $63$ より小さいので条件範囲と整合する。

組合せ回路と順序回路

組合せ回路は現在の入力だけで出力が決まり，順序回路はフリップフロップなどの状態を持つ。 記憶素子がある時点で，クロックごとの状態遷移として読むのが基本である。

マルチプレクサ木

8 個から 1 個を選ぶ構成では，下位ビットが最初の 2 択，中位ビットが 4 個のまとまりの選択， 上位ビットが左右半分の選択を担当する。PC の各ビットをこの階層に対応させればよい。

データハザード

パイプラインでは，命令の結果が RF に書き戻される前に次の命令が読み出しを行うことがある。 このため，直前命令の生成値を直接後段へ送るフォワーディングが必要になる。 判定には「どのレジスタへ書くか」と「どのレジスタを読むか」の番号比較が本質である。

採点の置き所

回路の空欄は，選択肢番号だけでなく，対象が組合せ回路か順序回路かを説明するとよい。 パイプライン小問では，同じ時刻に各命令がどの段にいるかを表にしてから信号値を読む。 フォワーディングの説明は，比較するレジスタ番号と置き換えるデータ経路を両方書く。

典型ミス

RF への書き込み完了前に次命令が値を読む点を見落とすと，$T4$ の $xtv$ を 3 としてしまう。 マルチプレクサ木では，上位ビットと下位ビットの担当段を逆に読むと選択信号が全てずれる。