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

直列負荷はインピーダンス，並列補償はアドミタンスで扱う

最初の回路は直列なのでインピーダンスを足せばよい。一方，コンデンサを並列に入れた後はアドミタンスを足すのが最も簡単である。この切り替えをすると，力率改善条件は虚部を消すだけになる。

有効電力と皮相電力を混同しない

有効電力 $P$ は抵抗で実際に消費される電力である。皮相電力 $S$ は電圧実効値と電流実効値の積で，配線や電源設備に必要な容量を表す。誘導性負荷では $S>P$ となり，その差が力率改善の対象になる。

力率90\%には2つの容量性リアクタンスがある

力率は位相角の余弦の絶対値で決まるため，アドミタンスの虚部 $B$ は正負どちらでも同じ $90\%$ を与える。したがって，誘導性を少し残す場合と容量性に少し過補償する場合の2解が出る。問題文が「全て」としているので，この2解を落とさないことが重要である。

余りを状態にする理由

2進数に1ビットを追加する操作は「現在値を2倍して入力ビットを足す」操作である。したがって，値そのものを保持する必要はなく，$6$ で割った余りだけを保持すれば十分である。この発想を最初に書くと，状態遷移表の根拠が明確になる。

状態簡単化の見方

$0$ と $3$ はどちらも入力 $0$ で $\{0,3\}$ に戻り，入力 $1$ で $\{1,4\}$ に移る。さらに出力も常に同じである。同様に $(1,4)$，$(2,5)$ も同値である。単に「同じ形に見える」ではなく，同じ入力列に対する将来の出力列が区別できないことを確認するのが簡単化の根拠である。

MIL図での実装

MIL記号では，$D_1,D_0,z$ を上の積和形でAND，OR，NOTに分解して描けばよい。試験答案では，状態符号化，状態遷移表，カルノー図による簡単化，Dフリップフロップへの接続，の順に示すと採点者が追いやすい。

配列更新の注意

この疑似コードでは経路圧縮をしていないため，`find(0)' を呼んでも `parent[0]' は直接根に書き換わらない。最後の配列で `parent[0]=5' としてしまう誤答が起きやすい。問題文の疑似コードが実際に何を代入しているかを追う必要がある。

サイズ併合の証明

小さい木を大きい木に付けると，深さが増えた頂点が属する集合のサイズは少なくとも2倍になる。サイズは最大でも $N$ なので，1つの頂点の深さは高々 $\log_2 N$ 回しか増えない。この一文が，$O(\log N)$ の理由として重要である。

時刻問い合わせの設計

通常のUnion-Findは「いま同じ集合か」を高速に答える構造であり，「いつ同じになったか」は情報を捨てている。したがって，時刻を答えるには併合時刻を別構造として残す必要がある。併合履歴木を作る方法は，最初に同じ集合になった瞬間をLCAで表現できるため，説明しやすく堅い。

ネットワーク層とリンク層を混同しない

ブリッジ，リピータ，ARP，MTUの設問は，どの層の情報を見て判断しているかを問うている。リピータは物理層なのでアドレスを見ない。ブリッジはリンク層なのでMACアドレスを見られる。ルータはネットワーク層なのでIPプレフィックスで転送先を選ぶ。

最長プレフィックス一致

経路表の問題では，一致する行のうちネットマスクが最も長いものを選ぶ。$192.168.10.12$ は /26 や /24 にも一致するが，/29 のほうが具体的なので /29 の次ホップを選ぶ。この規則を書かないと，表を上から読むだけの答案に見えてしまう。

TCPの信頼性の範囲

TCPはアプリケーションに「順序付きバイトストリーム」を見せるための仕組みであり，暗号化や認証のプロトコルではない。改ざん検出についてはTCPチェックサムがあるが，これは偶発的な誤り検出であって，攻撃者に対する完全性保証ではない。セキュリティを保証するにはTLSやIPsecなどが必要である。

奇成分のフーリエ変換

実奇関数 $x_o(t)$ に対して，余弦成分は奇関数との積になって積分が0になり，正弦成分だけが残る。そのためフーリエ変換は純虚数になり，実部は0である。これは直接積分するより短く，しかも誤差が出にくい。

畳込みの幾何的意味

矩形同士の畳込みは，2つの区間の重なり長を数えているだけである。中心が離れるほど重なりは線形に減るので三角波になる。$f_2$ の高さ $E^2\tau$ は，$t=0$ で長さ $\tau$ 全体が重なることから確認できる。

微分と端点

$f_2$ は連続な折れ線なので，通常の関数としての微分は区間ごとに定数になる。端点や $t=0$ での値はフーリエ積分には影響しない。分布の言葉を使う必要はないが，$g(t)=E\{f(t+\tau/2)-f(t-\tau/2)\}$ と書くと，左右の矩形の差として形を直感的に理解できる。