東北大 情報科学研究科 2群 情報・生命系 基礎・専門科目 2023年3月実施 院試 過去問 解答例・解説（全5問）

方針

クワイン・マクラスキー法は，(i) 最小項を1の個数で分類，(ii) 1ビット違いの併合を打ち止めまで繰り返して主項を得る，(iii) 主項表から必須主項を選ぶ，の3段からなる。「簡単化の過程も示すこと」と明示されているので併合表と主項表を必ず書く。本問は必須主項 $P_1,P_2,P_3,P_5$ だけで全最小項が覆われるため被覆問題に進む必要がない。冗長主項 $P_4=x_1x_2x_4$ を答えに入れると最簡形ではなくなる。

検算

得られた式の各項が覆う最小項を数え直す。$x_1x_3\to\{10,11,14,15\}$，$\overline{x_2}x_3\overline{x_4}\to\{2,10\}$，$x_1\overline{x_2}\,\overline{x_4}\to\{8,10\}$，$x_2\overline{x_3}x_4\to\{5,13\}$。和集合は元の最小項集合に一致し，余分な最小項も現れない。この「両側の一致」を見れば過剰簡単化と簡単化不足を同時に排除できる。併合に使った項に印を付け忘れると主項を取り違えるので，最後の被覆確認は省かない。

方針

完全系の証明は，よく知られた完全系（$\{\text{AND},\text{OR},\text{NOT}\}$ など）を作れることを示すのが最短である。$M(x,y,0)=x\cdot y$，$M(x,y,1)=x+y$ という2つの等式が本問の核心で，$M$ は第3引数を定数に固定すると AND と OR に化ける。あとは定数をどう用意するかだけが問題になる。

極小性の示し方

「取り除くと完全でなくなる」は，残った関数がすべて共有し合成で保たれる性質を1つ挙げれば示せる。使えるのは $0$ 保存・$1$ 保存・単調・自己双対・線形の5種類（Post の定理でいう5つの極大クラス）で，本問は自己双対・$0$ 保存・線形をちょうど1回ずつ使う。なお $M$ と $g$ の2つだけでは極小完全系にならない。$M$ は $0$ 保存・$1$ 保存・単調・自己双対をすべて満たすので $g$ はこの4つから外れねばならず，線形からも外れると $g$ 単独で完全になって「極小」に反する。ところが線形で $g(\boldsymbol{0})=1$，$g(\boldsymbol{1})=0$ を満たすものは変数の個数が奇数となり自己双対になって矛盾する。

失点しやすい点

$M$ と NOT だけで完全だと書く誤答が多い。$M$ も NOT も自己双対なので，どう組み合わせても自己双対関数しか作れず，AND も OR も定数も作れない。「例として NAND を加える」も誤りで，NAND 単独で完全だから極小性が壊れる。極小完全系は「完全」と「極小」の両方が主張であることを忘れないこと。

別解（場合分け）

変形が思いつかないときは $x_1$ で場合分けする。$x_1=1$ なら第3項が $1$。$x_1=0$ なら左辺は $x_3+\overline{x_2}\,\overline{x_3}+x_2$ で，$x_2=1$ なら $1$，$x_2=0$ なら $x_3+\overline{x_3}=1$。

$\ge$ の扱いと注意点

$f\ge g$ を「$f$ と $g$ が等しい」と読み違えると証明が成立しない。実際 $x_1=0,x_2=1,x_3=0$ では左辺 $=1$，右辺 $=0$ で等号は成り立たない。変形では $a+\overline{a}b=(a+\overline{a})(a+b)=a+b$ を使うが，$\overline{x_1}\,\overline{x_2}\,\overline{x_3}$ を $\overline{x_1x_2x_3}$ と書き違えるとド・モルガンの適用先が変わって破綻する。

方針と答案の書き方

「最小項の個数」は「関数が $1$ を返す入力の個数」と同じである。$2^{n}-1$ は「全入力から1つを除いた個数」で，入力を半分に分ける関数の値としては形が合わない。まず $n=2,3$ で数えて命題を疑うのが速い。真偽の判定だけでは点にならないので，正しい個数 $2^{n-1}$ とその導出を必ず書く。

この設問が試していること

$f_p$ は最小項が $2^{n-1}$ 個あって主加法標準形が指数的に長くなる一方，$x_1\oplus\cdots\oplus x_n$ なら $n-1$ 個の演算で済む。積和形の最簡化が万能でないことを意識させる設問である。

方針

(a) は定義どおりに書くだけだが，無向グラフなので行列の対称性と，隣接リストで各枝が2回現れることを外さない。(b) の $O(n+m)$ は「節点の配列 $+$ 枝の並び」という内訳を書くと，$O(m)$ とだけ書いた答案より確実である。(c) はクラスカル法でもプリム法でもよいが，採用・棄却の判断を表にして残す。

最小全域木の一意性

$G_1$ は7本の枝の重みがすべて異なる。重みがすべて異なる連結グラフの最小全域木は一意なので，得られた木は「一つの例」ではなく「唯一の答え」である。答案でこの一言を添えると，たまたま見つけた木を書いたのではないことが伝わる。

検算

全域木は $n-1=4$ 本の枝を持ち閉路を含まない。得られた4本 $\{c,d\},\{b,e\},\{b,d\},\{a,b\}$ で $a$–$b$–$d$–$c$ と $b$–$e$ がつながり，5節点がすべて到達可能で閉路がないことを図で確かめる。さらに，棄却した $\{d,e\}$ (4) を加えて閉路 $b$–$d$–$e$–$b$ の最大重み枝 $4$ を除くと元に戻る（閉路性質）ので，交換して重みが減る枝がないことも確認できる。

失点しやすい点

隣接行列の記憶量を「$m$ に比例」と書く誤りが多い。隣接行列は枝の有無によらず $n^2$ 要素を確保するので，疎なグラフでは隣接リストが有利である。逆に「2節点が隣接するか」の判定は隣接行列が $O(1)$，隣接リストが $O(\text{次数})$ で，用途によって優劣が入れ替わる。この対比を1行添えると (b) の理解が示せる。

なぜ右上から始めるのか

右上の要素は「その行で最大，その列で最小」という両極端の性質を同時に持つ。そのため大小どちらの比較結果でも，行または列のどちらか一方をまるごと捨てられる。左下から始めて右・上へ進んでも同じ理由で成立するが，左上や右下から始めると，比較結果から捨てられる範囲が定まらず破綻する。この「なぜ角のうち2つだけが使えるか」を書けると理解が伝わる。

別解との比較

各行に二分探索をかけると $O(n\log m)$ で，$m$ が大きいときは階段状探索より遅い。行列全体を1本の整列列とみなす二分探索は，行をまたぐと順序が保証されないため誤りになる（たとえば第1行の右端が第2行の左端より大きいことがある）。$O(n+m)$ という指定は，比較のたびに行または列を1本ずつ落とす形の解を要求している。

失点しやすい点

終了条件を書き忘れて「見つからない場合」に無限ループになる答案が多い。$i>n$ または $j<1$ で「No」を出す分岐を明示する。また，$x$ が複数個含まれる場合や $M$ に重複値がある場合でも，上の不変条件は「存在するならこの範囲」という形なので，最初に見つけた1個で「Yes」を返せばよく，正当性は変わらない。

この設問が試していること

設問1がデータ構造の記憶量，設問2が探索の時間計算量で，どちらも「$n$ と $m$ の両方が現れる $O$ 記法」を正しく扱えるかを見ている。$O(n+m)$ と $O(nm)$，$O(n\log m)$ の違いを，どの操作が何回起こるかまで戻って説明できるかが評価の分かれ目になる。

検算

$A(1,0,-2)^{\mathsf T}=(1,0,-2)^{\mathsf T}$，$A(1,1,-1)^{\mathsf T}=(3,3,-3)^{\mathsf T}$ で正しい。固有値の側はトレース $3+4+0=7$ が和 $1+3+3$ に，$\det A=9$ が積 $1\cdot3\cdot3$ に一致することで確かめられる。

対角化できないことの意味

$\lambda=3$ の代数的重複度は2，幾何的重複度は1で一致しない。したがって $A$ は対角化不可能で，相似変換で到達できるもっとも簡単な形が設問3の $B$，すなわちジョルダン標準形である。設問2で $B$ の右上に $1$ が置かれていること自体が「対角化できない」という予告になっている。重複度と解空間の次元を同一視して固有ベクトルを2本書く誤答が多い。

別の導き方と $0^{0}=1$ の断り

$B$ は $(a)$ と $J=\begin{pmatrix}b&1\\0&b\end{pmatrix}$ の直和である。$J=bI+N$，$N=\begin{pmatrix}0&1\\0&0\end{pmatrix}$ とおくと $N^{2}=O$ で $bI$ と $N$ は可換だから，二項定理により $J^{n}=b^{n}I+n\,b^{n-1}N$ となって $N^{2}$ 以降が消える。問題文が $0^{0}=1$ を置いているのは $b=0$ でも $n=1$ の式が破綻しないようにするためである。

方針

$P^{-1}AP=B$ を $AP=PB$ に直してから列ごとに読むのが定石である。逆行列を含む式のままでは条件が見えないが，$AP=PB$ にすれば「第1列は固有値 $1$，第2列は固有値 $3$ の固有ベクトル，第3列は $(A-3I)\boldsymbol{p}_3=\boldsymbol{p}_2$」と一つずつ確定する。

解が一意でないこと

$\boldsymbol{p}_3$ には $w$ の自由度，$\boldsymbol{p}_1,\boldsymbol{p}_2$ には定数倍の自由度があるので $P$ は一意でなく，条件を満たすものを一つ挙げれば十分である。ただし $\boldsymbol{p}_2$ の定数倍を変えると $(A-3I)\boldsymbol{p}_3=\boldsymbol{p}_2$ の右辺も変わるから，$\boldsymbol{p}_2$ と $\boldsymbol{p}_3$ は必ず組で決める。

検算

$n=1$ では $(1,1)$ 成分が $6-2-1=3$，$(2,2)$ 成分が $3+1=4$ などとなって $A$ に一致する。$n=2$ では第1行が $(5,6,2)$ となり $A^{2}$ の直接計算と合う。

$n$ の1次の項が現れる理由

$A^{n}$ が $1$ と $3^{n}$ の定数倍だけでなく $n\,3^{n-1}$ を含むのは，$B$ の右上の $1$（冪零成分）に由来する。対角化可能なら固有値の $n$ 乗の線形結合だけで書けるので，この項は対角化不可能性の現れである。

方針

$Z(t)$ は $F(t-1)$ に依存するので $t=1$ から順に埋めるしかない。表を $X\oplus Y$，$D(t)$，$F(t-1)$ の3列に分けて書くと，どこで間違えたかが後から追える。$F(0)=0$ という初期値を使うのは $t=1$ の1回だけである。

$F(t)$ の定義に注意

$F(t)$ は「$Z(t)$ の値の偶奇」ではなく「$Z(t)$ を2進表現したときのビットの和の偶奇」である。$Z=3=\texttt{011}$ は奇数だが $F=0$，$Z=4=\texttt{100}$ は偶数だが $F=1$ となり，値の偶奇とは一致しない。ここを読み違えると $\alpha_7$ と $\alpha_{10}$ が逆になる。$Z$ と $F$ の対応は $Z=0,3$ で $F=0$，$Z=1,2,4$ で $F=1$ の5通りしかないので，表を書き終えたらこの対応表で $F$ の列を独立に検算できる。

ゲート数を減らす工夫

$|x_i-y_i|$ を減算器と絶対値回路で作ると回路が大きくなる。1ビットどうしでは差の絶対値は不一致の判定と同じで，排他的論理和1個で済む。ここに気づけば残りは4つの1ビット値の総和で，全加算器の並べ方の問題に帰着する。なお FA3 は桁上げ入力を $0$ に固定しているので実体は半加算器であり，全加算器を減らしたいなら排他的論理和1個と論理積1個で置き換えられる。ただしその場合は追加ゲートが7個になるので，本文の構成の方が問題文の条件には合う。

$Z$ が3ビットに収まる根拠

$d_0+d_1+d_2\le 3$ と $F(t-1)\le 1$ より $Z(t)\le 4<8$ である。この上限を書いておかないと，桁あふれの処理が要るのかどうかが採点者に伝わらない。逆に $Z=4$ は実際に起こる（設問1の $t=5$）ので，$z_2$ を省くことはできない。

失点しやすい点

Dフリップフロップを $F(t)$ の生成より前に置いて $Z(t)$ を遅らせてしまう構成が目立つ。遅らせるのは $F$ だけで，$Z(t)$ は同じ時刻の入力から組合せ回路で決まる。また $F(0)=0$ に対応するリセット入力を図に描き添えると，初期状態の指定まで読めていることが示せる。

最簡であることの示し方

「最簡積和形で示せ」とあるので，主加法標準形を書くだけでは足りず，これ以上簡単にならない理由を添える。$s$ については「$1$ を出す4つの入力がカルノー図で市松模様に並び，隣接する組がない」の一言で足りる。$c_o$ については必須主項が3つそろって全体を覆うことを示す。

$s$ を排他的論理和で書く場合

$s=a\oplus b\oplus c_i$ は最短の表現だが積和形ではない。問題文が $\wedge,\vee,\overline{\phantom{x}}$ の3記号を指定しているので，展開した4項の形で答える。なお $c_o$ は3変数多数決関数そのもので，「入力の2つ以上が $1$ なら桁上げが出る」という算術的な意味と一致している。設問2で全加算器を計数器として使えたのもこの性質による。

方針

真偽を問う3命題は，偽なら反例1つ，真なら一般の証明が要る。反例の方が圧倒的に安いので，まず小さい語で成り立たない例を探す。ここでは3つとも偽で，(a) だけは「反例がない」ことの証明が必要になる。

曖昧性の判定で見るところ

曖昧性は「言語」ではなく「文法」の性質である。$G_1$ が非曖昧なのは，$S$ の4つの右辺のうち $aS$ だけが非終端記号を含み再帰が1本しかないため，導出の長さが語の長さから一意に定まるからである。(b) で挙げた $S::=aS\mid Sa\mid aba$ は逆に曖昧だが，主張は非終端記号の個数だけなので構わない。$L_2=a^{+}ba^{+}$ では $b$ が必ず1個だから，核 $aba$ を右辺に直接書き，左右への伸長を $aS$ と $Sa$ に任せる手が使える。

失点しやすい点

(c) で $L_1$ の第2の型 $a^{n}ba$ を $n=0$ の $ba$ だけと考えると，$ba$ は $L_2$ の条件 $i\ge1$ を満たさないので「共通部分は空」と誤答してしまう。3つの型を $L_2$ と1つずつ突き合わせるのが安全である。

方針

(b) は「スタックの出入りの収支」を式にするのが要点である。積む・取り出すの回数から $p-q_2-2q_3=1$ が出て，長さの定義と連立すれば $p$ の動ける範囲 $(\ast)$ が決まる。深さの最大は $p$ の最大に等しく，最小は3項演算子を使わずに済むかで決まる。

検算

$n=4$ では $(\ast)$ が $2.5\le p\le3$ で $p=3$，最大の深さは $\lfloor9/3\rfloor=3$ となり，問題文の例 $8\,2\,7\,\triangledown$（長さ4・深さ3）と一致する。$n=7$ では $p_{\max}=5$，$q_3=2$，$q_2=0$ で深さは $5\to3\to1$ と動く。

偶奇の場合分けを落とさない

(i) で「深さの最小は常に2」と答えるのが典型的な誤りである。$n$ が偶数だと2項演算子だけでは長さが合わず，3項演算子が必ず奇数個入るので深さ3が下限になる。