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

階数の見方

行列の階数は、非零行の数まで簡約しなくても、各行に独立なピボットを確保できるかで判断できる。今回は第1列、第2列、第3列、第5列にピボットを置けるため4である。

指数関数の極限

$a^x=e^{x\log a}$ と書くと、$a^x-1\sim x\log a$ がすぐ出る。最後の極限は「$1^\infty$ 型」なので対数を取るのが定石である。

DP表の検算

編集距離表では、左上から右下へ進む対角移動が置換または一致、下移動が削除、右移動が挿入に対応する。最終値が2であることだけでなく、実際の編集操作を一つ示せると答案の信頼性が上がる。

選択肢問題の注意

比較回数と交換回数は別物である。選択ソートは比較回数は多いままだが交換が少ない。挿入ソートは平均比較回数が半分程度になり、整列済みに近い入力では線形時間に近づく。

論理式の見通し

$A$ と $\overline A$ が対になって消える構造に気づくと、カルノー図を書かなくても $B$ と $C$ の排他的論理和だと分かる。指定ゲートに XOR がないため、最終的には AND, OR, NOT の形に展開して答える。

don't care の使い方

BCD表示では 1010 から 1111 は使わない入力であり、出力を自由に選んでよい。この自由度を使うと $a$ のように $W$ を含む簡単な式にまとめられる。

符号語の一意性

ハフマン符号は左右の 0/1 の割当を入れ替えても同じ平均符号長になる。重要なのは、頻度の高い $S_1,S_2,S_3$ が短い符号語を持ち、$S_4,S_5$ が長い符号語を持つ木構造である。

正則でない理由

有限オートマトンには、前半の $0$ の個数を無制限に記憶する能力がない。ポンピング補題はこの直感を、十分長い $0$ の並びの一部を増減しても認識されるはずだ、という形で矛盾にする道具である。

具体例で書く

状態フラグは抽象的に説明するだけでなく、「比較後の条件分岐」「ゼロ判定」「負数判定」のような使い道を添えるとよい。PCとSPも、単なる名前ではなく、サブルーチンコールでどの順に更新されるかを書くと答案として強くなる。

状態遷移の原則

待ち状態のプロセスは、待っていた事象が完了してもすぐCPUを得るわけではなく、いったん実行可能状態に戻る。実際に実行中へ移るのは、スケジューラに選ばれてからである。

ネットワーク計算

/22 のマスクは $255.255.252.0$ なので、第3オクテットは $0,4,8,\ldots,164,168,\ldots$ の境界を持つ。167は164から始まるブロックに入る。この境界計算を明記すると、単なる暗算より減点されにくい。

アブダクションの慎重さ

「$q$ だから $p$」は形式論理では妥当ではない。アブダクションは、複数の候補の中からもっとも説明力の高い仮説を選ぶ過程であり、後続の観察で修正され得る。この点を述べると、演繹との違いが明確になる。

フレームと意味ネットワーク

フレームは属性値制約、意味ネットワークは部品間の関係を表すのに向いている。図形認識では、単に丸い座面と脚があるだけでなく、「人が座れる高さ」「脚が座面を支持する」「地面と接触する」といった関係知識が必要になる。