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

方針

この問題は，DFAを「何を記憶する機械か」として設計すると見通しがよい。必要なのは過去の 入力列そのものではなく，長さの偶奇や $3$ で割った余りだけである。余りは3通り，偶奇は2通り なので，その直積を取れば6状態になる。

逆順入力の扱い

$w^R$ を読むと元の下位桁から処理することになるため，桁の偶奇を明示的に持つ方法が自然である。 一方，3で割り切れるかだけなら，二進数を反転しても「0である余り」は保存される。これは $2^{m-1}$ を掛けるだけの違いになり，$3$ では $1$ または $2$ を掛けることに相当するからである。

採点上の注意

状態図を描く問題では，開始状態，受理状態，各状態から各入力記号に対する出辺の3点を落とすと 大きく減点される。遷移表で確認してから図に直すと，出辺の欠落や重複を避けやすい。

方針

前半はアドレス空間の個数とCIDRの最小ブロックを数える問題である。特にサブネット分割では， 必要台数だけでなく，ネットワークIDとブロードキャスト相当の予約IDを除いた有効数で判断する。 必要有効数が2なら，最小ブロックは4アドレスの $/30$ になる。

割り当て不能を答案にする場面

問題文が「割り当てよ」と書いていても，制約を満たす割り当てが存在しない場合は， 無理な範囲を列挙するよりも不可能性を示す方が正しい。今回は最小消費数が524で， 元の範囲512を上回るため，どのように並べ替えても実現できない。

通信性能の見方

音声ではペイロードがたまるまでの待ち時間が効くので，ペイロードを小さくする必要がある。 一方，大きなファイル転送ではヘッダ比率を下げるためにペイロードを大きくした方が有利である。 同じパケットサイズでも，目的が遅延最小化かスループット最大化かで望ましい設定は変わる。

方針

用語説明では，定義，仕組み，利点，注意点の順に書くと密度の高い答案になる。単語を知っている だけでなく，どの入力をどのように処理し，どの条件で性能や正しさが変わるかまで述べるとよい。

選択の理由

この4項目は，データ構造，OS，機械学習，ロボティクスに分散しており，それぞれ具体例と 注意点を書きやすい。特にハッシュテーブルでは平均と最悪，スレッドでは共有と同期， ランダムフォレストでは過学習低減，SLAMでは位置推定と地図作成の相互依存を書くと採点されやすい。

典型ミス

ハッシュテーブルを常に $O(1)$ と断定する，スレッドをプロセスと同じものとして扱う， ランダムフォレストを単なる大きな一本の木と説明する，SLAMを位置推定だけと説明する，といった 答案は不十分である。各用語の「何を共有し，何をランダム化し，何を同時に推定するか」を 一つずつ明確にする。