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

Rotate の添字

操作 $p_i$ は、1 始まりで左から $i$ 番目の要素を先頭に移す操作である。 C の配列は 0 始まりなので、まず A[i-1] を退避する。 コード片では A[--i] として先に $i$ を 1 減らしているため、 退避後の $i$ は配列添字そのものになる。以後は $$\texttt{A[i]=A[i-1]}$$ で先頭側を右に詰め、最後に A[0]=temp とすればよい。

最小操作回数の見方

この操作で動かさなかった要素どうしの相対順序は変わらない。 最終形を昇順にしたいので、動かさずに残す要素は、ある $k$ について $$k+1,k+2,\ldots,N$$ がもとの順列の中でこの順に並んでいる部分に限られる。 残せる末尾部分が長いほど操作回数は少なくなり、 最小操作回数は「先頭に移す必要がある $1,\ldots,k$ の個数」になる。

Sort の前半ループ

temp=N,N-1,... と下げながら、それらの値の位置が右向きに保たれているかを調べている。 直前に見た位置を i に保存するので、次の値の位置 j が i より右に出た時点で、残せる末尾部分が途切れる。 したがって更新は i=j である。

Sort の後半ループ

途切れた値から 1 までを大きい順に先頭へ移すと、最終的には小さい値ほど前に来る。 i は 0 始まりの添字であり、問題の操作番号は 1 始まりなので、 出力も Rotate への引数も i+1 になる。

重複禁止と重複許可を分ける

問い [1] は同じ文字を使えないので、位置選択と順列の積で数える。 一方、問い [2] は同じ文字を使ってよいので、全体 $n^5$ から 「指定文字を含まない」場合を包除原理で差し引くのが最短である。

部分文字列の重なり

指定部分文字列に同じ文字が繰り返されていないため、長さ 7 の中で 2 回同時に現れることはない。 例えば開始位置が 1 と 2 の両方だと、2 文字目が同時に別の指定文字でなければならず矛盾する。 したがって、開始位置ごとの $n^2$ 通りを単純に足してよい。

ハミング距離 1 の数え方

集合 $X$ に入らないという条件が重要である。 $X$ の文字列の外側 2 文字だけを変えると、指定部分文字列がそのまま残るので、依然として $X$ に入る。 逆に指定部分文字列の内部 1 文字を別の文字に変えれば、その開始位置での出現は壊れる。 長さ 7 では別開始位置の出現も同時には作れないため、重複なく $15n^2(n-1)$ と数えられる。

直列部分と並列部分を分ける

図の回路は、$R$ と、$L$ と $C$ の並列回路が直列になっている。 したがって全体のインピーダンスは、抵抗 $R$ と並列合成インピーダンスの和である。 並列部は $$\frac{1}{j\omega L} + j\omega C = j\left(\omega C-\frac{1}{\omega L}\right)$$ の逆数を取ればよい。

電流の極値

電源電圧の大きさが一定なら、電流は $|Z|$ が小さいほど大きい。 この回路では $R$ は一定で、周波数依存するのはリアクタンスだけである。 リアクタンスが 0 になる低周波極限で最大、並列共振でリアクタンスが発散するため最小になる。

テブナン等価

右側の枝には $Z_1,Z_2$ があるが、開放端子電圧を求めるときには電流源が注入する電流が 最終的に $Z_3$ を通って戻る。したがって上側端子の電位は、電圧源分 $E$ と $Z_3$ の電圧上昇 $IZ_3$ の和になる。 等価インピーダンスでは独立源を殺すので、電圧源は短絡、電流源は開放として扱う。

電荷を固定する場合

電源を外した後は、極板に蓄えられた電荷 $Q$ が固定される。 このとき電界は電圧ではなく面電荷密度から求めるのが速い。 端効果を無視すれば面電荷密度は $Q/A$ であり、真空中の関係 $D=\varepsilon_0 E$ を使う。

誘電体の直列合成

電界方向に複数の層が並ぶときは、各層が直列コンデンサになる。 同じ面積 $A$ なら、容量計算では各層の厚さを $$\frac{\text{厚さ}}{\varepsilon_r}$$ に換算して足せばよい。今回は真空 $d/4$、誘電体 $d/2$、真空 $d/4$ なので、 有効厚さは $3d/4$ になる。

変位電流

コンデンサ電流は、極板電荷 $Q(t)=CV(t)$ の時間微分である。 電圧が正弦波なら電流はその時間微分になり、電圧より位相が $\pi/2$ 進んだ余弦波になる。

集合演算の簡約

(1) では $A\cap C$ が $A\cap(B\cup C)$ に含まれるため、全体は $A\cap(B\cup C)$ だけでよい。 (2) は、排他的論理和が $\overline{A\cap B}$ の一部に含まれるため、 和を取ると $\overline{A\cap B}$ になる。 (3) は $A\cap\overline{B}$ が $\overline{A\cap B}$ に含まれるため、 積を取ると $A\cap\overline{B}$ が残る。

IEEE754 の手順

単精度では、符号 1 bit、指数 8 bit、仮数 23 bit に分ける。 正規化した形 $1.x\times2^e$ を作り、指数部には $e+127$ を入れる。 仮数部には先頭の暗黙の 1 を除いた小数部分だけを左から詰める。

数値誤差の典型例

丸め誤差は各演算で少しずつ混入する。 桁落ちは近い数の引き算で相対誤差が大きくなるのが危険である。 情報落ちは、仮数部の桁合わせによって小さい項が丸ごと捨てられる点に注意する。

偶関数の密度

$|x|$ は $[-1,1]$ 上で偶関数であり、$x|x|$ は奇関数である。 したがって平均の積分は左右で打ち消し合い、0 になる。 分散では $x^2$ が掛かるため偶関数となり、正の側を 2 倍すればよい。

差の分布

$X=X_1-X_2$ は、$X_1$ と $X_2$ の差なので、密度は $$h(x)=\int f_{X_1}(u) f_{X_2}(u-x)\,du$$ で求める。指数分布は $u\ge0$ のときだけ値を持つため、積分範囲は $x\ge0$ と $x<0$ で分ける。 結果は 0 を中心とするラプラス分布になる。

分散の別解

独立性を使うと $$\mathrm{Var}(X_1-X_2)=\mathrm{Var}(X_1)+\mathrm{Var}(X_2) =\frac{1}{\lambda^2}+\frac{1}{\lambda^2} =\frac{2}{\lambda^2}$$ とすぐに確認できる。