電子情報学専攻 専門
令和 2 年 8 月 17 日(月) 10 時 00 分～12 時 00 分実施
問題数 5 題 (このうち 3 題を選択して解答すること)注意
1. この問題冊子の本文は表紙を除き全部で 6 頁ある。
2. 3 題を選択して解答せよ。5 題中どの 3 題を選択してもよい。1 つの問題の解答は複数枚の解答用紙に渡ってよい。ただし、1 枚の解答用紙に 2 題以上の解答を記してはならない。
3. 全ての答案用紙上部に解答した問題の番号と受験番号を必ず記入すること。
4. 答案は必ず 3 題分を提出すること。解答した問題が 3 題未満であっても 3 題のそれぞれについて問題番号と受験番号を記入した答案用紙を提出のこと。
5. 解答は日本語または英語で記述すること。
6. この問題冊子は，ダウンロードしたり保存したりしてはならない。

第２問
クロックに同期して１ビットずつ入力されるデータ系列 (X0 X1 X2 X3 · · ·, Xk は 0 または 1) に関して，X(i) ＝i∑(Xk × 2i−k )(X0 X1 X2 · · · Xi を 2 進数とみなした値)

k=0が 6 で割って 3 余る数のときだけ１を返し（出力 Z ＝ 1），それ以外のときは 0 を返す（出力 Z ＝ 0）
同期式順序回路を作りたい．以下の問いに答えよ．

(1) 順序回路とは何か．50 字以内で説明せよ．
(2) この回路の状態遷移図をミーリーグラフの形式で作成せよ．
(3) 状態遷移図をできるだけ簡単化せよ．(2) が理論的に簡単化できないときは，本問は解答不要である．
(4) 状態遷移表を作成せよ．
(5) (4) からカルノー図を作成せよ．
(6) この同期式順序回路を設計し，MIL 記号（図）を用いて図示せよ．その際，（5）のカルノー図を使って論理をできるだけ簡単化すること．

第３問
N 個の物体があるフィールド上を移動している．時刻 t において 2 つの物体 a, b が接触すると，(t, a, b) の三つ組みが記録されるものとする．2 つの物体は一度接触すると同値関係となり，同じ同値類に所属する．各同値類は最初に単独の物体を含んでいるものとする．同値類に含まれる物
体が他の同値類に含まれる物体と接触すると，それらの同値類は 1 つの同値類に合併する．
以下の問いに答えよ．
(1) 次ページの疑似コードは，各物体の同値類を記録する union-ﬁnd アルゴリズムを示している．init 関数は，同値類を記録する配列 parent の初期化を行う（配列 sizes はこの問いでは無視せよ）．上記の三つ組みが記録される度に union 関数が実行され parent を更新する．N が 6 であるとき，以下の三つ組みが記録された後の配列 parent の内容を示せ．
(1, 0, 3), (2, 4, 2), (3, 1, 5), (4, 0, 1)(2) find 関数および union 関数について最悪時間計算量のオーダを理由と共に示せ．
(3) 配列 sizes を用いて，各同値類に含まれる物体の数を記録することを考える．疑似コード
中の (X) と (Y) を埋めて，関数 size が指定された物体 a を含む同値類中の物体の数を返すようにせよ．(X), (Y) には複数行を記入してもよい．
(4) 配列 sizes を用いて union 関数を変更することで，union および find 関数の時間計算量を改善することが可能になる．疑似コード中の (X) を変更して示せ．また，改善された
union 関数の最悪時間計算量のオーダを理由と共に示せ．
(5) 指定された物体 a と b が同値となった時刻を求めることを考える．アルゴリズムの変更の方法を述べ，この時刻を求める関数の手続きを説明せよ．また，この関数の最悪時間計算量のオーダを理由と共に示せ．

Union-find algorithm:
int parent[N];int sizes[N];void init() {for (int i = 0; i < N; ++i) {parent[i] = i;sizes[i] = 1;}}
int find(int i) {while (parent[i] != i) {i = parent[i];}return i;}void union(int a, int b) {int i = find(a);int j = find(b);parent[i] = j;(X)}
int size(int a) {(Y)}第４問
TCP/IP に関して，以下の問いに答えよ．
(1) データリンク層において，ブリッジにはできてリピータにはできないことの具体例を述べよ．
(2) ネットワークセグメント内で対象ホストの MAC アドレスを IP アドレスから取得するプロトコルの名前を述べよ．
(3) ネットワークセグメント 192.168.10.16/28 では，何個の IP アドレスを割り当て可能か答
えよ．
(4) DHCP がホストに割り当てる IP アドレスと共に配布しうる情報を 3 種類答えよ．
(5) IP パケットヘッダに含まれる TTL フィールドの役割を述べよ．
(6) ICMP がもたらす代表的な機能を 3 つ答えよ．
(7) パケット A（宛先: 192.168.10.5）とパケット B（宛先: 192.168.10.12）が，下記経路表に従うルータで転送される．パケット A とパケット B はそれぞれどの IP アドレスに転送されるかを示せ．
Destination
Gateway
192.168.10.8/29 192.168.11.249
192.168.10.0/26 192.168.11.246
192.168.10.0/24 192.168.11.244
192.168.11.1
0.0.0.0/0(8) 転送する IPv4 パケットの大きさがデータリンク層の Maximum Transmission Unit (MTU)を超えるときの処理を述べよ．
(9) TCP において，Source-to-Destination 経路上の MTU が下記であった場合に Source の最良の Maximum Segment Size (MSS) を求めよ．MSS は TCP セグメントの最大ペイロード長である．IP ヘッダ長は 20 オクテットであり，TCP ヘッダ長は 20 オクテットである．

(10) traceroute がどのように経路を探索するかを述べよ．
(11) TCP は，信頼性のあるデータ配送サービスを提供するとされている．しかし，TCP を使えば必ず相手ホストと通信できるようになるとは限らない．また，配送途中でデータが改ざんされてしまう可能性もある．ここで言う TCP の信頼性について述べよ．
(12) IPv6 のアドレス長を述べよ．
(13) IPv6 のアドレスの例を一つ示せ．
(14) DNS がどのように名前を解決するかを述べよ．

第５問
フーリエ変換に関する以下の問いに答えよ．


1 (−1 ≤ t < 0)x(t) =−2 (0 ≤ t < 2)
0 (otherwise){f (t) =E (|t| ≤ τ /2)
0 (|t| > τ /2)とする．ただし，τ > 0，E > 0 である．a(t) ∗ b(t) は，2 つの信号 a(t) と b(t) の畳込み積分を意味する．

(1) x(t) = xo (t) + xe (t) を満たす xo (t) と xe (t) のグラフを図示せよ．ただし，xo (−t) = −xo (t)，xe (−t) = xe (t) である．
(2) xo (t) のフーリエ変換を Xo (ω) とする．Xo (ω) の実部 Re(Xo (ω)) を求めよ．
(3) f (t) のフーリエ変換 F (ω) を求めよ．さらに，F (ω) = 0 となるすべての ω を求めよ．
(4) f2 (t) = f (t) ∗ f (t) とする．f2 (t) のグラフを図示せよ．
(5) f3 (t) = f2 (t) ∗ f (t) とする．(3) で求めた F (ω) を用いて，f2 (t), f3 (t) にそれぞれ対応する
フーリエ変換 F2 (ω), F3 (ω) を求めよ．
df2 (t) とする．g(t) のグラフを図示し，f (t) を用いて数式で表わせ．
(6) g(t) = dt

(7) g(t) のフーリエ変換 G(ω) を求めよ．