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

削除操作の見方

$\odot$ は連続部分文字列の削除ではなく，部分列の削除である。 したがって $ababa\odot ab$ では，1文字目の $a$ と4文字目の $b$ を 削除する場合も考える必要がある。この点を落とすと(1)の列挙で漏れが出る。

正規表現の作り方

$(ab)^*$ では $a$ は各ブロックの先頭に1つずつ現れる。 2つの $a$ を消すと，それぞれのブロックは $b$ だけになる。 その前，間，後ろには通常の $ab$ ブロックが任意個残るため， $(ab)^*b(ab)^*b(ab)^*$ という形が自然に出る。

オートマトン構成の核心

残す文字は入力として読む。削除する文字は入力には現れないので $\varepsilon$ 遷移で処理する。この2種類の遷移を同じ $A_1$ 上で動かすことで， 「残した語」と「削除した語」を合わせたものが $L_1$ に属するかを確認できる。 文脈自由の場合も同じ発想で，削除列を有限オートマトンではなく プッシュダウンオートマトンに読ませればよい。

ページテーブルサイズの基本

仮想ページ番号はページ内オフセットを除いた上位ビットで決まる。 そのため，総ページ数は $2^v/2^p=2^{v-p}$ である。 単一レベルページテーブルでは，全仮想ページにPTEを1つずつ持つため， ページテーブルサイズは「総ページ数 $\times$ PTEサイズ」で決まる。

FIFOの落とし穴

FIFOは最も古く入ったページを追い出すだけで，最近使われたかどうかを見ない。 そのため，フレーム数を3から4に増やしてもフォールト数が12から13に増える。 これはアルゴリズムの性質によるもので，計算ミスではない。

TLBとページフォールトの時間

TLB missでページフォールトがない場合は，TLB参照，ページテーブル参照， データ参照の3段階になる。ページフォールトがある場合は， ページテーブル参照でフォールトを検出してから処理を行い，その後にアクセスを再開する。 「処理後はTLB参照から再開する」と明記されているので，再開後のTLB参照と ページテーブル参照も時間に含める。

パイプライン時間の分解

実行時間は「クロック周期 $\times$ サイクル数」である。 クロック周期はステージ遅延の最大値で決まる。サイクル数は理想的には $N+4$ だが，ロード直後利用の回数だけ1サイクルずつ増える。 この問題ではストール理由がそれだけに限定されているため，分岐や構造ハザードを 追加で考える必要はない。

ゲート数制限への対応

デコーダでは3入力ANDをそのまま作るとゲート数が増える。 $e\bar{x}_1\bar{x}_0=\overline{\bar{e}\lor(x_1\lor x_0)}$ のように， NANDでOR項を作り最後をNORで受ける形にすると，4出力を条件内で作れる。

ロードユースハザード

フォワーディングは「計算済みだがまだレジスタに書かれていない値」を早く渡す仕組みである。 しかしロード値はMAステージでメモリから戻るまで計算済みにならない。 この時刻の違いが，ロード命令だけ特別に1サイクル止まる理由である。

有限差分の係数

$D^{(k)}$ は離散版の $k$ 階微分に対応する。 係数は二項係数で現れ，符号は $$(-1)^k,\ (-1)^{k-1},\ldots,1$$ と交互になる。したがって5階差分では $$-1,\ 5,\ -10,\ 10,\ -5,\ 1$$ が並び，$a_{i+3}$ の係数は $10$ である。

最大値探索の見方

列そのものを見るより，隣接差分 $$a_{i+1}-a_i$$ を見る方がよい。差分が正なら上り坂，負なら下り坂である。 2階差分が負という条件は，この傾きが単調に下がることを意味するので， 山は高々1つになり，二分探索が使える。

一般の固定次数の場合

$c$ が入力サイズに依存しないことが重要である。 山や谷の個数は $c$ によってのみ抑えられるため，候補点の数は定数個で済む。 もし $c$ が $n$ とともに増えるなら，同じ議論では $O(\log n)$ は保証できない。