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

NFAとDFAの差

NFAでは「この位置が後ろから $k$ 番目だ」と非決定的に推測できるため， $k+1$ 個程度の状態で足りる。一方，DFAでは最後の $k$ 文字を区別できなければならない。 そのため全ての長さ $k$ の接尾辞に対応する $2^k$ 通りの情報が必要になる。

平方数位置の非正規性

正規言語は，十分後ろでは周期的な判定しかできない。平方数の間隔は $2k+1$ ずつ広がるので，固定周期では表せない。この性質を $ab^*$ との共通部分に落とすと，非正規性が見えやすくなる。

競合ミスが支配的になる理由

配列 $A$ と $B$ の開始アドレスは $0x1000$ だけ離れている。 これはキャッシュ容量256バイトの整数倍なので，ダイレクトマップでは同じインデックスに 対応する。したがって，$A$ を読んだ直後に $B$ へ書くと，同じ場所を取り合う。

IPC計算の注意点

IPCは命令数をサイクル数で割る。キャッシュヒット率だけからIPCは直接出ない。 `div' の4サイクル，メモリアクセスのヒット・ミス時のサイクル，ループ回数をすべて足し合わせる。

全域木の基本

探索で初めて頂点を発見した辺だけを集めると，すべての頂点に到達し，かつ各頂点は一度だけ 親を持つ。したがって閉路は生じず，全域木になる。

辺交換の考え方

木から1辺を抜くと必ず2成分に分かれる。そこに別の横断辺を1本戻すと，再び連結になり， 辺数も $n-1$ のままなので木である。全域木の交換性を使う典型的な議論である。

値呼びと名前呼びの違い

値呼びでは関数に入る前に引数を一度だけ評価する。名前呼びでは，引数式を本体に そのまま代入し，必要になった時点で評価する。そのため，同じ式が複数回現れると， 同じ計算が繰り返される。

呼び出し回数が増える理由

この関数では条件判定で $x$ を使い，さらに返り値側でも $x$ を含む式が現れる。 名前呼びではそれぞれの出現箇所で引数式が再評価されるため，呼び出し回数が指数的に増える。