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

構造を見抜く

同じ対角成分と同じ非対角成分を持つ行列は，$I$ と全成分 1 の行列 $J$ で表すと計算が大幅に短くなる。 $J$ は $\mathbf{1}$ 方向では固有値 $3$，その直交補空間では固有値 $0$ を持つため，3 次行列の行列式展開をする必要がない。

ユニタリ性とエルミート性

実行列でもユニタリの定義は共役転置で書く。今回のように実対称かつ固有値が $\pm1$ の行列では， $A^\ast A=I$ と $A^\ast=A$ の両方が成り立つ。直交行列とエルミート行列の性質を混同しないように， それぞれ定義から一行ずつ確認するのが安全である。

採点の置き所

$J$ を使って固有空間を分ける発想が最短経路である。 ただし答案では，$\mathbf{1}$ 方向と成分和 0 の平面で固有値がどう変わるかを明記する必要がある。 対角化では，固有値だけでなく正規直交化した固有ベクトルを列に置いた $B$ を示すと完答になる。

検算

$\det A=-1$ は固有値の積からも，$A^2=I$ と反射の固有値構造からも確認できる。 また $E_1$ は 2 次元でなければならないので，$x+y+z=0$ という条件式で次元を確認しておくとよい。

文法の分担

$S\to aSa$ と $S\to aTa$ は，少なくとも一対の $a$ を左右に作る役割を持つ。 残りの非終端記号 $T$ は中央部分だけを担当すればよく，$b$ を左右同数に増やして最後に $c$ で止める。

走査順序

前順序は「根，左，右」，後順序は「左，右，根」である。 算術式の木では，前順序は前置記法，後順序は逆ポーランド記法に対応する。

冠頭標準形

否定を量化記号の内側へ押し込むときは $\neg\forall=\exists\neg$ を使う。含意 $P\Rightarrow Q$ の否定は $P\wedge\neg Q$ であり，ここでは $P=\neg(x<y)$，$Q=(y<x)$ である。

採点の置き所

形式言語の小問では，生成規則を答えるだけでなく，その規則がどの部分列を担当するかを書けると強い。 木の走査は，訪問順を一度ノード列として書いてから記号列に直すと減点されにくい。 論理式変形は同値変形を 1 行ずつ置き，最後に自然数上の反例 $x=y$ を添える。

典型ミス

前順序と後順序を，中順序と混同しないことが重要である。 冠頭標準形では，含意を消す前に否定を押し込むと符号が崩れやすいので， $\neg(P\Rightarrow Q)\equiv P\wedge\neg Q$ を先に使うのが安全である。

配列添字の基本

0 始まりのヒープ配列では，親 $s$ の子が $2s+1,2s+2$ になる。 1 始まりの公式 $2s,2s+1$ と混同すると，コードの空欄がすべて一つずつずれる。

下方調整の不変条件

`func1` は，注目節点以外ではヒープ条件が保たれていることを前提に，注目値を下へ移動させる。 二つの子がある場合に大きい子と交換するのは，交換後に親が両方の子以上になる可能性を保つためである。

昇順になる理由

最大ヒープでは根が最大値である。根と未整列部分の末尾を交換すると，最大値が配列の右端に確定する。 未整列部分を一つ短くして同じ操作を繰り返すため，配列全体は左から右へ昇順になる。

採点の置き所

添字問題では 0 始まりであることを最初に宣言し，左子，右子，親の式を一貫して使う。 最小値の位置は「どの葉でもあり得る」と答える必要があり，単一の添字に決めつけない。 ヒープソートの空欄は，最大ヒープ構築，根と末尾の交換，未整列部分への下方調整の順で説明する。

検算

子の添字 $2s+1,2s+2$ は，根 $s=0$ に対して子が $1,2$ になることで確認できる。 ヒープソート後に昇順になるかは，最大値が右端から順に確定していくことを小さい配列で追うと検算できる。

閉ループの分母

負帰還であるため，閉ループの分母は $1+P(s)$ から出る。 分数をそろえると，開ループの分母 $s^2(s^2+2s+4)$ に開ループの分子 $K_P(K_Ds^2+s+K_I)$ が足される。

ラウス判別

3 次式 $s^3+2s^2+4s+K_P$ では，ラウス表の第1列が $$1,\quad 2,\quad \frac{8-K_P}{2},\quad K_P$$ になる。安定性では「正である」ことが必要なので，$K_P=0$ や $K_P=8$ は境界であり安定範囲に含めない。

定常偏差と積分器

ランプ入力に対する偏差は，低周波での開ループの原点極の数に強く依存する。 PI 制御では積分器が一つ増え，この系ではランプ入力に対しても定常偏差がゼロになる。

採点の置き所

閉ループ伝達関数，偏差伝達関数，安定判別，定常偏差を混ぜずに順番に書く。 ラウス表では第1列の符号条件を明示し，境界値を安定範囲に含めない理由まで書くとよい。 制御器比較では，PI は定常偏差，PID は過渡応答に効くという役割分担を具体的に述べる。

検算

$K_P\to0$ では制御入力が消えるため安定範囲の端点に来るのは自然である。 ランプ偏差 $4/K_P$ は $K_P$ を大きくすると小さくなるため，ゲイン増加の直感とも一致する。

出力のタイミング

`OUT` 命令を実行したクロックの立ち上がりで出力レジスタが更新されるため，表の `LOUT` は一つ前までに確定した出力を表す。 このため，`OUT` の次のクロックで LED パターンが指定値として観測される。

プログラムの読み方

前半のプログラムは $R10$ を左シフト相当で倍々にし，$11,22,44,88$ を作る。 後半のロード命令付きプログラムでは，$R11$ がデータメモリのオフセットとして 2 ずつ増え， $R10$ がループ回数として 1 ずつ減る。分岐先を $R14=0c$ に入れておくことで， ロードから分岐までのループを繰り返している。

アーキテクチャ拡張

ロード命令は「アドレス計算」と「メモリ値の書き戻し」を追加する命令である。 既存の ALU はアドレス計算に再利用できるため，新たに必要なのはデータメモリと， 書き込みデータをメモリ出力にも切り替えられる経路である。

採点の置き所

命令トレースでは，PC，レジスタ値，出力レジスタを同時に追う表を作ると途中点を取りやすい。 ロード命令追加の設計問題では，アドレス入力，メモリ出力，書き込みデータ選択の三つを必ず言及する。 LED 表示は 16 進値と点灯ビットの対応を両方書くと誤解が少ない。

典型ミス

`OUT` の瞬間と LED が保持している値を同じクロック内で混同すると，出力列が 1 回分ずれる。 ロード命令では，メモリから読んだ値をどのレジスタへ書き戻すかを忘れる答案が多い。