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

極限の典型処理

対数の差は必ず商の対数にまとめる。三つ目の極限は分子・分母がともに 0 に近づくため， ロピタルの定理または Taylor 展開を使えばよい。

行列式は積を展開しない

行列積を実際に計算すると式が大きくなるが，$\det(AB)=\det A\det B$ を使えば一瞬で終わる。 第1の行列は第1行で展開でき，第2の行列は第1列で展開できる形である。

密度関数の積分

$\int_0^1 x^m\log x\,dx=-1/(m+1)^2$ を使うと期待値計算が短い。 累積分布関数では，端点で $F_X(0)=0,\ F_X(1)=1$ になることを確認しておくと符号ミスに気づける。

検定の書き方

対立仮説が「A に入りやすい」なので片側検定である。 帰無仮説・対立仮説・検定統計量の分布・棄却判断をそろえて書くと，答案として減点されにくい。

採点の置き所

この大問は小問ごとの独立性が高いため，途中計算を短くしても結論だけを並べないことが重要である。 行列式では $\det(AB)=\det A\det B$，確率密度では正規化済み密度の積分範囲， 検定では片側の $p$ 値までを書けていれば，部分点を取りやすい。

典型ミス

累積分布関数で $0<x<1$ の式だけを書き，$x\le0$ と $x\ge1$ の場合を落とす誤答が多い。 また Bayes の公式では，検査陽性の全確率に偽陽性項を入れ忘れると桁が大きくずれる。 検定では $\Pr(X\ge4)$ ではなく $\Pr(X=4)$ だけを使わないようにする。

含意の真理値

$A\to B$ が偽になるのは $A$ が真で $B$ が偽のときだけである。 この規則を機械的に適用すれば，真理値表は安定して埋められる。

自然演繹の読み方

連言除去は左成分か右成分を取り出すだけである。 含意除去では，$p_1$ と $p_1\to(p_2\to p_3)$ から $p_2\to p_3$ が得られ， さらに $p_2$ と合わせて $p_3$ が得られる。

量化記号の順序

$\forall x\exists y$ と $\exists x\forall y$ は意味が大きく異なる。 前者は $x$ ごとに $y$ を選べるが，後者はすべての $y$ に同時に通用する $x$ を 1 つ要求する。 反例を作るときは，等号関係のような小さい 2 元モデルを使うと見通しがよい。

採点の置き所

命題論理では真理値表，恒真性，充足可能性を別々に結論づけると採点しやすい答案になる。 自然演繹は空欄だけでなく，どの規則でその式が出てくるかを一言添えるとよい。 述語論理の反例では，ユニバース，関係の定義，前件が真で後件が偽になる確認までを書く。

典型ミス

含意を「前件が偽なら偽」と誤解すると真理値表全体が崩れる。 また，$\forall x\exists y$ の $y$ を $x$ に依存して選べる点を忘れて， $\exists x\forall y$ と同じ意味にしてしまうのが典型的な失点である。

整列プログラムの見分け方

隣接交換を繰り返すものはバブルソート，手元の既整列列に要素を差し込むものは挿入ソートである。 ループ変数名よりも，交換・シフトのされ方を見ると判定しやすい。

反転数と隣接交換

隣接する大小逆転した 2 要素を交換すると，その 1 組の反転だけが消える。 バブルソートはこの操作を繰り返して反転数を 0 にするため，交換回数が初期反転数に一致する。

マージの添字

左半分が尽きたら右半分から，右半分が尽きたら左半分から作業配列へ移す。 比較回数を返す変更では，局所変数 $c$ に左右の再帰呼び出しの戻り値を加算し，最後に $c$ を返す必要がある。

採点の置き所

整列名の選択では，交換対象やシフト方向を根拠として書くと選択肢問題でも答案の説得力が出る。 反転数では実際の反転対を列挙し，最大反転数では降順配列と $\binom n2$ を結びつける。 コード変更は変更行だけでなく，左右再帰の戻り値を足す理由を書けると部分点を落としにくい。

検算

反転数 $4$ は，降順部分 $(4,3,2)$ の反転 3 個に $(1,0)$ を足すと確認できる。 マージソートの出力順は，再帰木を左部分木から深さ優先にたどると再現できる。 比較回数の戻り値は，最下層の呼び出しが 0 を返し，上位で加算される形になっているかを確認する。

指数因子と $s$ のシフト

ラプラス変換で $e^{-\alpha t}$ が掛かると，積分核が $e^{-(s+\alpha)t}$ になる。 このため，既知の変換式の $s$ を $s+\alpha$ に置き換えればよい。

初期値の入れ忘れに注意

$\mathcal{L}[f']$ と $\mathcal{L}[f'']$ には初期値が入る。 ここでは $f(0)=1,\ f'(0)=1$ なので，分子の $s^2+(1+\eta)s+2$ が得られる。

共振条件

ゲイン最大化は分母の二乗を最小化する問題である。 $\omega=0$ 以外の極値が正の周波数に存在するには $1-2\gamma^2>0$ が必要で， これが減衰比の上限を与える。

採点の置き所

ラプラス変換では標準公式，初期値を含む微分公式，部分分数分解の三段階を明示する。 2 次系では伝達関数の分母を正しく作ったうえで，ゲイン最大化を分母最小化へ移すのが主な採点箇所である。 グラフは厳密な描画よりも，初期値，収束値，減衰振動の有無が読み取れることが重要である。

検算

$F(s)$ の最終値は最終値定理で $\lim_{t\to\infty}f(t)=\lim_{s\to0}sF(s)=1$ と確認できる。 共振周波数は $\gamma\to0$ で $\omega_0$ に近づき， $\gamma\ge1/\sqrt2$ で正の極値が消えるため，条件の向きも確認しやすい。

D フリップフロップの役割

D フリップフロップは，クロック立ち上がり時の入力を次の状態として保持する。 したがって順序回路全体は「現在状態を組み合わせ回路に入れ，その出力を次状態として記憶する」構造になる。

2進カウンタの次状態

3 ビット 2 進カウンタでは最下位ビットは毎回反転し，中央ビットは下位ビットからの桁上がりで反転し， 最上位ビットは下位 2 ビットがともに 1 のときに反転する。 この見方をすると $y_1=x_1\oplus x_0$，$y_2=x_2\oplus(x_1x_0)$ が自然に得られる。

Gray 符号の利点

Gray 符号では連続する状態のハミング距離が 1 である。 複数ビットが同時に変わらないため，後段の組み合わせ回路で遅延差による一時的な不一致が生じにくい。 この性質がグリッチの有無の判定に直接効く。

採点の置き所

順序回路では現在状態，次状態，出力のどれを答えているかを明確に分ける。 2 進カウンタは全 8 状態の遷移表，Gray 符号カウンタは状態列を書けば，多くの空欄を一貫して埋められる。 グリッチの説明では「1 ビットだけが変化する」という性質とゲート遅延の関係を言葉で補う。

典型ミス

D フリップフロップの出力を同じ時刻の組み合わせ回路出力と混同すると，$n-1$ の空欄や時刻指定の出力がずれる。 Gray 符号から 2 進数へ戻す式では XOR の累積を使うため，OR と取り違えないようにする。