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

前半だけを見る操作

$\Gamma(L)$ は，$L$ の語を同じ長さの前半・後半に分けたときの前半集合である。 接頭辞全体ではなく「ちょうど半分」である点が重要である。

DFAでの構成

後半 $w$ は存在すればよく，具体的に入力として読む必要はない。 残り長さが $t$ のときに受理状態へ到達できる状態集合を逆向きに更新すれば， 有限個の状態で管理できる。

平均下界と最大要素下界を組み合わせる

この問題の近似比の証明では，最適値 $\mathrm{OPT}$ に対する基本的な下界を2つ使う。 1つは総和を $m$ 個に分ける以上，最大和は平均値 $\|P\|/m$ 以上であるという下界である。 もう1つは，どの要素もどこかの集合に入るため，最大要素そのものも $\mathrm{OPT}$ 以下である という下界である。終了条件は $\|S_j\|\le \mathrm{top}(S_j)+\|S_k\|$ と読み替えられるので， この2つを足すだけで2近似が出る。

ループ回数の証明で見るべき不変量

一見すると，移動した要素が別のスタックからまた戻ってくる可能性がありそうに見える。 ここで効く不変量は「全体の最小和は減少しない」という性質である。 ある要素 $x$ が移動した時点の移動先の既存部分の和を $a$ とすると， その後に $x$ を再び動かすには，現在の最小和が $a$ より小さくなっている必要がある。 しかし最小和は減少しないため，これは起こらない。 したがって，各要素は高々1回しか移動せず，反復回数は $n$ で抑えられる。

データ構造の選び方

このアルゴリズムで毎回必要なのは「最大和のスタック」と「最小和のスタック」である。 全スタックを毎回走査すると1回 $O(m)$ かかり，全体で $O(nm)$ になってしまう。 和をキーにしたヒープを使えば，最大・最小の取得と更新を対数時間にできる。 スタック本体とスタック和を分けて管理するのが，実装上の要点である。

LRUと最適置換の違い

LRUは過去を見て「最も長く使われていないページ」を捨てる。最適置換は未来を見て 「次に使うのが最も遅いページ」を捨てる。試験では，この2つを混同せず，表を作って 1参照ずつ追うことが重要である。

リトルエンディアン

リトルエンディアンでは，数値の低位バイトが小さいアドレスに置かれる。 整数値をそのまま16進で左から読むのではなく，バイト単位に分解してアドレス順を考える。

CPI式の作り方

キャッシュミスペナルティは「1命令あたり何回そのミス機会があるか」にミス率とペナルティを 掛ける。命令キャッシュは全命令，データキャッシュはロード・ストア命令だけが対象である。