農工大 工学府 知能情報システム工学専攻 専門科目 2025年度 院試 解答例・解説

3 文字表で十分な理由

与えられた制約は、いずれも「長さ 3 の連続部分列」を見れば違反を検出できる形である。 同じ文字が 3 個並ぶ違反、0 が途中で 2 個続く違反、同じ文字が 1 文字だけ挟まって現れる違反、 および 1 または 2 の直後 2 文字に関する制約は、すべて $w[k],w[k+1],w[k+2]$ の組で判定できる。 したがって、長さ 2 以下は常に通し、長さ 3 以上では全ての 3 文字窓を調べればよい。

表の作り方

たとえば $a_1=1$ では、$100$ は直後 2 文字の条件に合わず不適合、 $101$ は同じ 1 の間に 1 文字しかないため不適合、$102$ は適合である。 同様に $122$ は直後 2 文字が指定された組でないため不適合になる。 $a_1=2$ では $200,211$ が許され、$201,210$ は直後 2 文字の条件で落ちる。 このように各行を制約ごとに消していくと、解答の 0--1 表が得られる。

再帰生成の順序

生成関数は、現在の語を出力してから末尾に $0,1,2$ を順に試す。 したがって出力順は、短い接頭辞を先に出す深さ優先の辞書式順序である。 0110 の後は、同じ接頭辞を保ったまま最小の追加文字を試し、 3 文字表で通る最初の候補が 01102 になる。 末尾側は $2$ から始まる枝をできるだけ進み、最後の有効な接頭辞が 2211200 で止まる。

配列引数の扱い

C 言語では関数引数の int w[] は配列全体のコピーではなく先頭要素へのポインタとして扱われる。 そのため、再帰呼び出しごとに配列本体の領域が新しく確保されるわけではない。 局所変数として確保されているのは main 内の配列であり、各深さで同じ領域の末尾側を書き換えている。

実効アクセス時間の式

キャッシュヒット時は 1 ns、ミス時だけ追加で 100 ns かかる。 したがって平均時間は「ヒット時間 $+$ ミス率 $\times$ ミスペナルティ」である。 5 ns 以下という条件から $100\,\mathrm{NFP}\le 4$ として一発で求まる。

タグとインデックスの分解

ダイレクトマップでは、アドレスは $$\text{タグ}\ |\ \text{インデックス}\ |\ \text{ブロック内オフセット}$$ に分かれる。 4 KB のキャッシュに 128 B ブロックを入れるので、行数は 32 行でありインデックスは 5 bit。 128 B ブロックの中の位置指定に 7 bit 使うため、残り 20 bit がタグになる。

パイプラインの数え方

5 ステージのパイプラインで停止がなければ、最初の命令が出てくるまで 5 サイクルかかり、 以後は各サイクルで 1 命令ずつ完了する。 「命令数 $\times$ ステージ数」としてしまうと、パイプラインありの場合まで逐次実行として数えてしまう点に注意する。

ハザードとアウトオブオーダー

アウトオブオーダー実行は真の依存関係を消すわけではない。 ただし、ある命令がデータ待ちで止まる間に、依存しない別命令を先に実行できるため、 データハザードによる空き時間を減らせる。 制御ハザードそのものには分岐予測、構造ハザードには資源の複製やスケジューリングが主な対策になる。

直列 RLC の見方

有効電力は抵抗で消費される平均電力であり、 $P=V_{\mathrm{rms}}^2R/|Z|^2$ と書ける。 $R$ と入力電圧が固定されているため、$|Z|$ が最小になる共振条件で有効電力が最大になる。 本問では $\omega L=1/(\omega C)$、すなわち $L=1\ \mathrm{H}$ である。

1 W となる値が二つある理由

共振点からのずれは $(100L-100)^2$ で効く。 したがって、同じ有効電力を与える $L$ は共振点の左右に対称に現れる。 $L=0.8$ と $1.2$ は、どちらもリアクタンスの大きさが $20\ \Omega$ で等しい。

オペアンプ回路の符号

1 段目は非反転なので符号は反転しない。 2 段目は反転積分器なので、出力は入力の積分に負号を付けた形になる。 ここで $R_3C_1=5$ と大きいため、2 段目の振幅は $30/(100\cdot 5)=0.06$ まで小さくなる。 初期条件を入れると積分定数は 0 であり、直流オフセットは残らない。

準位とキャリアの対応

ドナーは伝導帯に近い浅い準位を作るので、室温で電子を伝導帯へ出しやすい。 この電子が n 型の多数キャリアであり、電離後のドナーは動けない正電荷として結晶中に残る。 アクセプタは価電子帯近くの電子を受け取るため、価電子帯には正孔が残る。 この正孔が p 型の多数キャリアであり、電離後のアクセプタは負電荷になる。

平衡バンド図の要点

平衡状態のバンド図で最も重要なのは、フェルミ準位が水平であることと、接合部に空乏層があることの二点である。 バンド端が曲がるのは、固定イオンによる内蔵電位が生じるためである。 p 側から n 側へ見ると、$E_C$ と $E_V$ は低くなる形で接続される。

I--V 特性の物理

順方向電圧は内蔵障壁を下げるため、電子と正孔が接合を越えて注入されやすくなる。 そのため電流は指数関数的に増える。 逆方向電圧は障壁を高くするので多数キャリアの流れを止め、熱生成された少数キャリアによる小さな電流だけが残る。 グラフでは、順方向の立ち上がりと逆方向のほぼ飽和した小電流を必ず示す。

三角波の変換

本問の三角波は幅 1 の矩形波を自己畳み込みした形でもあるため、 フーリエ変換が $\mathrm{sinc}^2$ 型になる。 直接積分する場合も、偶関数性を使って余弦積分にすると計算が短い。 $\omega=0$ で式をそのまま代入すると $0/0$ になるので、必ず極限値を書く。

シフトと干渉

$f(t+2)$ は左へ 2、$f(t-2)$ は右へ 2 だけ移動した波形である。 周波数領域ではそれぞれ $e^{j2\omega}$、$e^{-j2\omega}$ が掛かり、 和を取ると $2\cos(2\omega)$ が現れる。 これは左右対称な二つの同じ波形による周波数領域の干渉項と見られる。

エネルギー積分の近道

$|G(\omega)|^2$ を直接積分するのは重い。 この規約では、時間領域のエネルギーに $2\pi$ を掛けたものが周波数領域のエネルギーである。 二つの三角波は重ならないので、エネルギーは単純に 2 倍すればよい。

一次系の応答

$H(s)=1/(s+2)$ は安定な一次遅れ系である。 入力 $\sin t$ に対する応答は、最終的には同じ角周波数の正弦波になるが、 零初期条件では過渡項 $e^{-2t}/5$ が加わる。 定常応答だけを書いてしまうと、ラプラス変換で求める零状態応答としては不足する。

袋の事前確率

さいころの各目は等確率で、各袋は 2 個の目に対応している。 したがって、袋 A, B, C の事前確率はすべて $1/3$ でそろう。 このため赤玉全体の確率は、各袋で赤玉が出る確率の単純平均になる。

ベイズの定理の分母

赤玉が出たという条件の下で袋を推定するので、分母は $P(Y_1)$ で共通である。 分子は「その袋が選ばれる確率」と「その袋から赤玉が出る確率」の積になる。 袋 C は赤玉の割合だけなら高いが、袋 B の赤玉割合 $3/4$ がさらに高いため、事後確率は袋 B が最大になる。

期待点の比較

さいころの目が決まると袋も決まるため、期待点は $$\text{目の値}\times \text{その袋での色倍率の期待値}$$ で計算できる。 袋 A は黄玉が多く倍率期待値が高いので、同じ袋 A の中では 4 の目が 3 の目より大きい。 袋 C の 6 の目も高いが、色倍率の期待値が袋 A より低いため、最終的には 4 の目が最大になる。