静岡大 総合科学技術研究科 情報学専攻 情報科学 2020年度 院試 過去問 解答例・解説（全7問）

列ベクトルの読み方

線形写像の行列は「標準基底がどこへ写るか」を列に並べたものである。$e_1+e_2$ の像が与えられているときは、線形性から第2列を差で求めればよい。固有値の条件で $x\ne0,\ y\ne0$ が付いているため、固有ベクトルのどちらかの成分が $0$ になる固有値は除外されるが、今回はどちらも除外されない。

展開の確認

$1/(1-2x)$ は等比級数の標準形であり、微分計算の答えも $f(0)=1,\ f'(0)=2,\ f''(0)/2=4$ と係数が一致する。この照合を書くと計算ミスを検出しやすい。

リストの先頭が意味するもの

OL は「これから調べる候補」、CL は「すでに取り出して展開した候補」である。縦型探索と横型探索の違いは、展開後の状態を先頭側に置くか末尾側に置くかだけで決まる。ここを曖昧にすると、同じグラフでも探索順が変わる。

均一コスト探索とA*

均一コスト探索は、ヒューリスティックを $0$ とした A* と見なせる。A* で最適性を保証するには、推定値 $\hat h(s)$ が真の残り最短コスト $h^*(s)$ を超えない、すなわち $$\hat h(s)\le h^*(s)$$ を満たす必要がある。このとき $f(s)+\hat h(s)$ はゴールまでの真の最短コストの下界になり、最適解より高く評価された経路を先に確定してしまう危険がなくなる。

符号付き表現の検算

2の補数では、負数 $-a$ は $2^{16}-a$ としても求められる。例えば $-32765$ は $65536-32765=32771=0x8003$ で、$1000\,0000\,0000\,0011$ と一致する。

回路の読み替え

全加算器の入力に「$2X$ と $X$ のどちらを流すか」を選ぶ転送ゲートが入っている、と捉えると、複雑な配線図をそのまま追うより早い。真理値表を作った後に $Y=(2S_1+S_0)X$ と照合すると、ビットの左右を取り違えたミスに気づける。

有限体で見るべき量

有限体の問題では、元そのものを展開して計算するより、位数を調べる方が速い。$\alpha$ の位数が $15$ なら $\alpha^5$ の位数は $15/\gcd(15,5)=3$。位数3の元は $x^3-1$ の根だが $1$ ではないので、$x^2+x+1$ に落ちる。

補グラフの証明の型

補グラフの連結性は「同じ成分にいる2点」と「異なる成分にいる2点」を分けて示すと書きやすい。非連結性を仮定したとき、別成分の頂点 $w$ を経由点にできるのが核心である。

クロックを上げる限界

同期回路では、あるクロックエッジでレジスタから出た値が、次のクロックエッジまでに組合せ回路を通り、次段レジスタで安定していなければならない。したがって、単に周波数を上げ続けることはできず、もっとも遅い経路が全体の上限を決める。

番地指定方式の採点観点

「相対ジャンプは短く書ける」とだけ書くと、この設定では命令語長が同じであるため弱い。ここでは、バイナリ上の意味の違いと、配置場所を変えたときの振る舞いの違いを明記するのが重要である。

OS問題の書き分け

排他制御では、アルゴリズム名より「待ち方」が採点対象になりやすい。ビジーウェイトは CPU を消費して待つ方式、セマフォやモニタは待ちプロセスをブロックできる方式として対比するとよい。

PKIの鍵の向き

証明書の検証に使うのは CA の公開鍵であり、通信相手の公開鍵ではない。通信内容の暗号化や鍵共有で使うのが通信相手の公開鍵、復号で使うのが通信相手の秘密鍵である。この区別が曖昧だと失点しやすい。

知能システムとしての限界

CAPTCHA は「人間なら必ず解け、機械なら絶対解けない」ものではない。機械学習モデルが発展すると、従来の画像認識型テストは突破されやすくなる。答案では、実効性の条件と限界をセットで述べると、単なる用語説明より説得力が出る。

指数時間の感覚

$2^{100}$ は日常的な時間感覚をはるかに超える。秒を年へ換算して「現実的に不可能」と結論づけると、最少手数の式だけを書くより答案として明確である。