東大 情報理工学系研究科 創造情報学専攻 創造情報学 専門科目 2025年度 院試 解答例・解説

方針

この問題は，ページ間の辺をそのまま行列にするだけではなく，列と行の向きをそろえることが 最初の関門である。ここでは $p^{(t+1)}=Ap^{(t)}$ と置いたので，列 $j$ がページ $j$ から 各ページへ移る確率を表す。

ジャンプ導入の意味

ジャンプがない場合はページ3が吸収状態になり，長期的には確率がすべてページ3に集まる。 一方，ジャンプを入れると全成分が正の遷移行列になり，どのページにも戻れる。この差が 定常分布の一意性と初期分布非依存の収束を生む。

採点上の注意

定常分布の存在だけなら列確率行列の性質でも説明できるが，一意性と収束まで述べるには 「正の行列」であることを使う必要がある。ペロン・フロベニウスの定理を使う設問では， 最大固有値が1であること，それ以外の固有値の絶対値が1未満であること，正規化により 確率分布になることを分けて書くと減点されにくい。

方針

ネットワーク計算では，伝送遅延と伝搬遅延を混ぜないことが最重要である。伝送遅延は 「ビット列を回線へ押し出す時間」，伝搬遅延は「最後のビットかどうかに関係なく信号が 空間を進む時間」であり，足し合わせる場面が異なる。

ウィンドウ幅の考え方

停止待ち方式では，ACKを待つ間に送信者が空く。連続送信方式では，その空き時間を $w$ 個のパケット送信で埋める。したがって $w$ の条件は「ACKが届く時刻」以下ではなく， 「$w$ 個を送り終えた時刻がACK到着時刻を超えること」として立てる。

キュー問題の注意

サーバの処理順は，クライアントが要求を送った時刻ではなく，要求がサーバに到着した時刻で 決まる。特に単一処理の設問では，クライアント3の要求がクライアント2より先に到着するため， 処理順が $1,3,2$ になる点が典型的な落とし穴である。

方針

用語説明問題では，定義だけでなく，何に使うか，何が利点か，どこに注意点があるかを入れると 答案の密度が上がる。4項目を選ぶ形式では，互いに分野が散る項目を選ぶと，同じ説明の 繰り返しになりにくい。

採点上の注意

「知っている単語を並べる」だけだと説明にならない。基数ソートなら安定ソートが必要な理由， モデル検査なら反例を返せる点，ハッシュ関数なら暗号化との違いまで書くと，短い行数でも 理解が伝わる。