千葉大 融合理工学府 情報科学コース 情報科学コース 専門科目 2026年度 院試 過去問 解答例・解説（全3問）

問1の基本方針

巡回シフトでできる同値類は，群作用の言葉では「軌道」である。ただし本問では群作用という用語を使う必要はなく，$\rho^n=\mathrm{id}$ と「同値類の大きさは最大でも $n$」の 2 点を書ければ十分である。特に (5) はバーンサイドの補題を使わなくても解ける。

問1の導出の見方

$N(4)$ では，4 文字の全 16 個を全部書き出すより，代表元で分類するほうが速い。例えば $\mathtt{aaab}$ 型は $\mathtt{aaab},\mathtt{aaba},\mathtt{abaa},\mathtt{baaa}$ の 4 個を含む。一方，$\mathtt{abab}$ は 1 回ずらすと $\mathtt{baba}$，さらに 1 回ずらすと元に戻るので，同値類の大きさは 2 である。このように周期が短い文字列があるため，常に同値類の大きさが $n$ になるわけではない。

問1の採点上の注意

同値関係の証明では，反射律・対称律・推移律を名前だけ挙げるのではなく，それぞれを巡回シフトの回数で説明する必要がある。対称律では「逆に回す」とだけ書くより，$\rho^n=\mathrm{id}$ なので $\rho^{n-r}$ 回のシフトで戻る，と書くと減点されにくい。

問1の典型ミス

$N(4)$ を $16/4=4$ としてしまう誤りが多い。これは全ての同値類の大きさが 4 であると仮定している点が誤りである。実際には $\mathtt{aaaa}$ や $\mathtt{bbbb}$ の同値類は 1 個，$\mathtt{abab}$ 型の同値類は 2 個しかない。

問1の検算

$n=4$ の分類表では，同値類の大きさの合計が $$1+4+4+2+4+1=16$$ となり，長さ 4 の 2 値文字列の総数 $2^4$ と一致する。列挙問題では，この合計チェックを入れると重複や漏れを発見しやすい。

問2の基本方針

問2は確率法の最小構成である。無作為に塗ると単色集合の個数 $X$ は確率変数になる。もし $\mathbb{E}[X]<1$ なら，非負整数値である $X$ が 0 になる場合が必ずある。したがって「望ましい彩色を具体的に作る」必要はなく，「望ましい彩色が少なくとも存在する」と示せばよい。

問2の導出の要点

4-一様の場合，固定した集合が全て赤になる確率は $2^{-4}$ である。単色は「全て赤」または「全て青」の 2 通りなので $2\cdot 2^{-4}=2^{-3}=1/8$ になる。$k$-一様では同じ計算が $2\cdot 2^{-k}=2^{1-k}$ へ一般化される。

問2の採点上の注意

(2) では集合 $S_1,\ldots,S_n$ が互いに独立である必要はない。集合どうしが要素を共有していると，「$S_i$ が単色である」という事象どうしは一般に独立ではない。しかし期待値の線形性は独立性を仮定しないため，$\mathbb{E}[X_1+\cdots+X_n]=\mathbb{E}[X_1]+\cdots+\mathbb{E}[X_n]$ としてよい。

問2の典型ミス

(3) で $n/8<1$ から「確率が 1 未満だから存在する」と書くのは不十分である。必要なのは，単色集合数 $X$ が非負整数であり，もし $X=0$ が一度も起こらないなら常に $X\ge 1$，したがって平均も 1 以上になる，という背理法の一文である。

問2の検算

$k=4$ を一般化した (4) の式に代入すると，単色確率は $2^{1-4}=1/8$ となり，(1) と一致する。また条件 $m<2^{k-1}$ に $k=4$ を入れると $m<8$，すなわち $m\le 7$ であり，(3) と同じ閾値になる。

状態の意味を先に決める

ミーリー・マシンでは出力が「現在状態」と「今入ったビット」の組で決まる。したがって，入力後に $101$ が完成する瞬間を，状態 $S_2$ にいて $x=1$ が来た場合として表せばよい。4 状態指定なので，検出直後の状態を $S_3$ として残しておくと，問題で指定された状態数に合う。

出力系列の X の扱い

開始状態が任意なので，最初の数ビットは一意に決まらないことがある。例えば $1010101$ の先頭の $1$ は，開始状態が $S_2$ ならただちに検出出力 $1$，開始状態が $S_0$ なら出力 $0$ になる。したがって先頭だけが $\mathrm{X}$ になる。一方，$001011$ は先頭の $0,0$ によってどの開始状態からも同じ状態系列に吸収されるため，$\mathrm{X}$ は出ない。

JK 励起表の作り方

JK フリップフロップでは，現在値が 0 のときは $K$ が次状態に影響しないため $K=\mathrm{X}$，現在値が 1 のときは $J$ が次状態に影響しないため $J=\mathrm{X}$ になる。この「使わない入力」を 0 や 1 に固定してしまうと，後のカルノー図で簡単化できる余地を失う。

カルノー図の検算

$J_1=1$ が必要なのは，$m_1m_0=01$ かつ $x=0$ のときだけである。行 $11$ の $x=0$ はドントケアなので，この 1 とまとめて $m_0=1,\ x=0$ の領域を作れる。よって $m_1$ が消え，$J_1=m_0\overline{x}$ となる。ここで出力 $y=m_1\overline{m_0}x$ と混同しないことが重要である。

CSMA/CD の採点ポイント

必要なのは片道伝播時間ではなく往復伝播時間である。片道だけで計算すると $25\,\mathrm{bit}$ になり半分ずれる。また，通信速度 $10\,\mathrm{Mbps}$ は $10^7\,\mathrm{bit/s}$ として扱う。

スイッチの典型ミス

端末 B が実際にはポート 2 に接続されていても，スイッチが MAC アドレス B を未学習ならポート 2 だけを選んで送ることはできない。未知ユニキャストなので，受信ポート 1 以外の全ポートにフレームを送信する。

サブネット計算の確認

/27 では各サブネットの総アドレス数が $2^5=32$，利用可能ホスト数がネットワークアドレスとブロードキャストアドレスを除いた $30$ 台で，条件の 20 台以上を満たす。/28 では $2^4-2=14$ 台なので条件を満たさない。したがって /27 がサブネット数を最大にする最も細かい分割である。

選択ソートと挿入ソートの見分け方

sortA は，内側ループで現在の最小位置 $k$ を保持し，最後に1回だけ交換する。 これは選択ソートの典型形であり，途中の比較結果によって交換回数は変わらない。 sortB は，隣り合う2要素を比べて必要なら交換し，注目要素を左へ押し込む。 これは挿入ソートを隣接交換で実装した形である。

採点上落としやすい点

sortA の swap 回数は $n-1$ ではなく $n$ である。 外側ループが $i=0,\ldots,n-1$ まで回り，最後の回でも swap(in,i,k) が呼ばれるためである。 また，sortB の問1(4)では，設問が「降順かつ重複なし」の場合を指定しているので，各挿入で先頭まで移動する。 失敗して止まる比較を余分に足すのではなく，隣接交換を起こす比較を合計して $\frac{n(n-1)}{2}$ とするのが本問の意図である。

配列計算の検算

問1(2)では，どちらも $i=3$ の処理が終わった直後を答える。 sortA の先頭4要素は $1,2,4,5$ と，入力全体の小さい4個が確定している。 sortB の先頭5要素は $1,2,4,7,8$ と，元の先頭5要素 $\{4,8,7,2,1\}$ を昇順にしたものになっている。 この違いを確認すると，両者の途中配列を取り違えにくい。

StringMatch1 の sum の数え方

$\texttt{sum}$ は，文字が一致したときだけでなく，不一致になった比較でも増える。 たとえば $i=0$ では $\texttt{a}$ と $\texttt{a}$ の一致で1回，次の $\texttt{c}$ と $\texttt{b}$ の不一致でもう1回，合計2回である。 完全一致した $i=7$ では4文字すべてを比べるので，ここだけで4回増える。

最大比較回数の理由

StringMatch1 では開始位置を1つずつずらすため，候補位置は $N-M+1$ 個ある。 各候補で最後の文字まで比較してから不一致になるような入力を考えると，各候補で $M$ 回比較できる。 したがって最大は $(N-M+1)M$ であり，これは単に $NM$ と書くより正確である。

シフト表の典型ミス

StringMatch2 のシフト表では，パターンの最後の文字 $P[m-1]$ は更新に使わない。 最後の文字も含めて更新すると，末尾文字のシフト量が0になり，照合位置が進まない場合が出る。 また，同じ文字が複数回現れる場合は，末尾に最も近い出現位置を使うため，後で現れた位置の値で上書きする。 このため $P=\texttt{abcdeiabfe}$ では $\texttt{a}$ は $9$ ではなく $3$，$\texttt{b}$ は $8$ ではなく $2$ になる。

StringMatch2 の検算

$P=\texttt{abga}$ では，末尾を除く $\texttt{a},\texttt{b},\texttt{g}$ のシフト量がそれぞれ $3,2,1$ になる。 最初の位置 $i=0$ では末尾から2回比較して不一致となり，末尾文字 $\texttt{a}$ により3だけ進む。 次の $i=3$ では1回で不一致となり，末尾文字 $\texttt{d}$ はパターンの末尾以外にないので4だけ進む。 最後に $i=7$ で4文字一致するから，合計 $2+1+4=7$ 回である。