東大 情報理工学系研究科 コンピュータ科学専攻 専門科目（コンピュータ科学） 2025年度 院試 解答例・解説

平方根言語の見方

$H(L)$ は「同じ語を2回続けたものが $L$ に入るか」を見る操作である。 したがって，単に正規表現を半分に切るのではなく，$ww$ の前半と後半に同じ構造が 現れることを使う。(1)では2個の $c$ の位置が強い制約になっている。

正規言語で閉じる理由

正規言語では，語そのものを覚える必要はない。語 $w$ がDFAの状態集合上に作る 有限個の状態変換だけを覚えればよい。有限集合 $Q$ に対する写像は高々 $|Q|^{|Q|}$ 個なので，これを状態にしたDFAが作れる。

文脈自由言語で同じ議論が使えない理由

プッシュダウンオートマトンでは，$w$ を1回読んだあとに同じ $w$ をもう一度 同じ順序で読むことを有限制御だけでは表せない。スタックに $w$ を積むと取り出しは 逆順になるため，正規言語のように「変換だけを持つ」という処理ができない。 このため，文脈自由言語では反例が存在する。

CPIの分解

この問題では，総サイクル数を $$\text{命令実行の基本サイクル} +\text{ロードユースストール} +\text{キャッシュミスストール} +\text{分岐ミスペナルティ}$$ に分けると見通しがよい。パイプラインの立ち上がり・終了コストは問題文で無視してよい 扱いなので，基本サイクルは命令数そのものとして数える。

ラインサイズの決まり方

配列を4バイト刻みで順に読む場合，キャッシュラインサイズが $B$ バイトなら， 1本のラインに $B/4$ 個のアクセスが入る。初期状態が空なので，各ラインの最初の ロードだけがミスになる。ここでは合計1024バイトを走査してミスが32回なので， 1ラインは $1024/32=32$ バイトである。

命令フォーマットの比較

レジスタ番号の位置をそろえる設計は，レジスタファイルの読み出しポートに渡す信号を 単純にできる。一方で，即値を分割すると，命令種別に応じた連結・並べ替え・符号拡張の 回路が必要になる。実際の命令セットでも，この2つはしばしばトレードオフになる。

待ち時間の数え方

待ち時間には実行可能キューで待つ時間だけでなく，セマフォの待ちキューで待つ時間も 含まれる。全プロセスが終了する場合は $$\text{待ち時間}=\text{終了時刻}-\text{到着時刻}-\text{実行時間}$$ でまとめて計算できるので，途中でどのキューにいたかを細かく足し上げるより安全である。

SRTFとセマフォの相互作用

セマフォがないSRTFでは，時刻20に到着した短い $P_5$ が $P_1$ を中断する。 しかし(3)では $P_5$ は $S_1$ を取得できないため待ちに入り，$P_1$ がそのまま 終了まで進む。このように，優先度が高いプロセスでも資源を取れなければ実行できない。

デッドロックの確認

(4)のRRでは，$P_2$ と $P_3$ が逆順に $S_1,S_2$ を要求する。 片方が $S_1$ を持って $S_2$ を待ち，もう片方が $S_2$ を持って $S_1$ を待つと， どちらも進めない。時刻80でこの循環待ちが完成する。

サイクルと2本のパス

2点 $a,b$ を含むサイクルは，サイクル上で $a$ から $b$ へ進む2通りの向きの パスに分解できる。この2本は端点以外の頂点を共有しない。逆に，内点素な2本の $a$-$b$ パスを合わせればサイクルになる。この対応が(1)の中心である。

新しい頂点を足す補題

(2)は，あとで「指定された点集合」を「新しい1点の近傍」として扱うための準備である。 $u$ を消さない場合でも，$A$ には $k$ 点あり，削除できるのは高々 $k-1$ 点なので， $u$ とつながる頂点が必ず1つ残る。この数え上げが証明の要点である。

一般化の構造

高連結性は，ある頂点から既存のサイクルへ多数の互いに独立な接続路を保証する。 接続点が指定点の数より1つ多くあるため，指定点を含まない弧を避けてサイクルを 作り直せる。これが「$k$ 連結なら任意の $k$ 点が同一サイクルに乗る」理由である。