(1)#

• 28 の格納：
  • ハッシュ値：$28 \bmod 10 = 8$。インデックス 8 のセルは空（EMPTY）であるため、28 はインデックス 8 のセルに格納される。
• 35 の格納：
  • ハッシュ値：$35 \bmod 10 = 5$。インデックス 5 のセルはすでに 15 によって占有されているため衝突が発生する。
  • 次のセルの探索：$(5 + k) \bmod 10 = (5 + 1) \bmod 10 = 6$。インデックス 6 のセルは空であるため、35 はインデックス 6 のセルに格納される。

解答：28：8，35：6

(2-1)#

プログラムの設定より、MAX = 20，SKIP = 3，EMPTY = -1 である。ハッシュ関数は $x \bmod 20$、衝突解決法は線形探索法（増分は 3）である。 data[] の 10 個の要素を順に格納するプロセスは以下の通りである：

1. 31: $31 \bmod 20 = 11 \implies$ 空のため、table[11] = 31
2. 45: $45 \bmod 20 = 5 \implies$ 空のため、table[5] = 45
3. 59: $59 \bmod 20 = 19 \implies$ 空のため、table[19] = 59
4. 25: $25 \bmod 20 = 5 \implies$ 衝突。$(5+3)\%20 = 8$ は空のため、table[8] = 25
5. 95: $95 \bmod 20 = 15 \implies$ 空のため、table[15] = 95
6. 39: $39 \bmod 20 = 19 \implies$ 衝突。$(19+3)\%20 = 2$ は空のため、table[2] = 39
7. 76: $76 \bmod 20 = 16 \implies$ 空のため、table[16] = 76
8. 27: $27 \bmod 20 = 7 \implies$ 空のため、table[7] = 27
9. 65: $65 \bmod 20 = 5 \implies$ 衝突 $\to 8$ (衝突) $\to (8+3)\%20 = 11$ (衝突) $\to (11+3)\%20 = 14$ は空のため、table[14] = 65
10. 43: $43 \bmod 20 = 3 \implies$ 空のため、table[3] = 43

最終的な table の状態：

• table[0] = -1
• table[1] = -1
• table[2] = 39
• table[3] = 43
• table[4] = -1
• table[5] = 45
• table[6] = -1
• table[7] = 27
• table[8] = 25
• table[9] = -1
• table[10] = -1
• table[11] = 31
• table[12] = -1
• table[13] = -1
• table[14] = 65
• table[15] = 95
• table[16] = 76
• table[17] = -1
• table[18] = -1
• table[19] = 59

(2-2)#

• (ア): hash(d)
• (イ): h
• (ウ): next(h)
• (エ): -1 (または EMPTY)

(2-3)#

SKIP を 4 に変更した場合、$\gcd(\text{MAX}, \text{SKIP}) = \gcd(20, 4) = 4 \ne 1$ となり、互いに素ではなくなる。 このとき、10番目の要素 43 の格納（store の呼び出し）において：

• $43 \bmod 20 = 3$（衝突：すでに 39 が格納されている）。
• 次に探索されるインデックスのシーケンスは：$3 \to 7 \to 11 \to 15 \to 19 \to 3 \to \dots$ となり、長さ 5 の巡回サイクルを形成する。
• このサイクルに含まれるセル（table[3]=39, table[7]=27, table[11]=31, table[15]=95, table[19]=59）はすべて EMPTY（-1）ではない。
• そのため、store 内の while (table[h] != EMPTY) ループから抜けることができず、無限ループに陥る。
• 結果として、43行目の store が終了せず、プログラムは45行目の printf 以降を実行できない。

(2-4)#

一般に、MAX 与 SKIP が**互いに素（coprime、すなわち最大公約数 $\gcd(\text{MAX}, \text{SKIP}) = 1$）**でなければならない。 二つの値が互いに素である場合のみ、任意の開始位置からハッシュ表のすべてのセル（MAX 個）を重複なく探索でき、空きセルが存在する限り必ずそこに到達できるため、無限ループを避けることができる。

(1-1)#

• (a): ウ（時間的局所性）
• (b): ア（空間的局所性）
• (c): カ（完全連想マッピング）
• (d): オ（直接マッピング）
• (e): コ（低）
• (f): カ（完全連想マッピング）
• (g): イ（セット連想マッピング）

(1-2)#

• 実装の容易さ (Ease of Implementation):
  • FIFO: 実装が非常に容易である。各ブロックがキャッシュに入った順番（キューや循環バッファ、単純なカウンタによる）のみを管理すればよく、ヒット（キャッシュヒット）時に情報の更新を行う必要がない。
  • LRU: 実装が比較的複雑である。キャッシュへのアクセス（ヒット・ミス問わず）が発生するたびに、アクセスされたブロックの「最近の参照履歴（タイムスタンプやスタック位置など）」を更新する必要があり、より多くのハードウェア（比較器や状態レジスタ）と消費電力を要する。
• ブロック枠の数とヒット率の関係 (Number of Blocks vs. Hit Ratio):
  • FIFO: スタックアルゴリズムの性質を満たさないため、ブロック枠（キャッシュ容量）を増やした際、特定のアクセスパターンでヒット率が逆に低下する現象（Beladyの偏執現象 / Belady’s Anomaly）が発生することがある。
  • LRU: スタックアルゴリズムの性質を満たすため、ブロック枠を増やすことでヒット率が低下することは決してなく、常に向上または維持されることが保証される。

(1-3-1)#

• キャッシュのブロック枠の総数は 4。2ウェイセット連想方式（セット数 2）なので、セットの数（Set count）は $4 / 2 = 2$ である。
• セットを識別するためのインデックス（Index）のビット幅：$\log_2(2) = 1$ ビット。
• 1ブロックの大きさは 4 語（ワード）であるため、ブロック内オフセット（Offset）のビット幅：$\log_2(4) = 2$ ビット。
• 主記憶のアドレスは 8 ビットであるため、タグ（Tag）のビット幅は以下の通りとなる： $\text{Tag bits} = 8 - \text{Index bits} (1) - \text{Offset bits} (2) = 5\ \text{bits}$

解答：5 ビット

(1-3-2)#

各アドレスに対応するブロック番号 $B = \text{Address} / 4$、およびマップされるセット番号 $S = B \bmod 2$ は以下の通りである。 LRU置換ポリシーにおける各セットの状態遷移（左側が MRU（最も新しく参照）、右側が LRU（最も古く参照））：

全 10 回のアクセスのうち、ヒットは 4 回（第 5, 6, 8, 10 回目）。 平均ヒット率：$4 / 10 = 40\%$

(2-1)#

• (a): カ（実行可能状態）
• (b): キ（ディスパッチ）
• (c): シ（実行状態）
• (d): ウ（待ち状態）
• (e): ソ（プリエンプション）
• (f): イ（コンテクストスイッチ）

(2-2)#

1
T =  0    1    2    3    4    5    6    7    8    9    10   11   12   13   14   15   16
2
     [------ プロセス A ------] (切) [B] (切) [------ プロセス C ------] (切) [--- プロセス D ---]

$M_1$#

1
stateDiagram-v2
2
    direction LR
3
    state "a (Initial)" as a
4
    state "c (Accepting)" as c
5
    [*] --> a
6
    a --> d : 0
7
    a --> b : 1
8
    d --> a : 0
9
    d --> g : 1
10
    b --> c : 0
11
    b --> e : 1
12
    c --> g : 0
13
    c --> e : 1
14
    e --> g : 0
15
    e --> b : 1
16
    g --> e : 0
17
    g --> f : 1
18
    f --> c : 0
19
    f --> g : 1

$M_2$#

1
stateDiagram-v2
2
    direction LR
3
    state "h (Initial)" as h
4
    state "k (Accepting)" as k
5
    [*] --> h
6
    h --> i : ε
7
    h --> k : ε
8
    i --> j : 1
9
    i --> k : 0
10
    j --> i : ε
11
    k --> i : 0
12
    k --> k : 1

$M_3$#

1
stateDiagram-v2
2
    direction LR
3
    state "l (Initial)" as l
4
    state "m (Accepting)" as m
5
    state "n (Accepting)" as n
6
    [*] --> l
7
    l --> l : 0
8
    l --> m : 0, 1
9
    m --> l : 0
10
    m --> n : 1
11
    n --> m : 0
12
    n --> n : 1

(1-1) 有限オートマトン $M_1$ が受理 (accept) する語 (word) の内，長さ 4 以下のもの全てを示せ．

(1-2) 有限オートマトン $M_2$ は $\varepsilon$-動作 ($\varepsilon$-move) を有する．最初に，$M_2$ の各状態に対する $\varepsilon$-閉包 ($\varepsilon$-closure) を示せ．次に，求めた $\varepsilon$-閉包から $\varepsilon$-動作のない非決定性 (non-deterministic) 有限オートマトン $M_2'$ を構成し，状態遷移図で示せ．ただし $M_2'$ は $M_2$ と同じ状態集合を有するものとし，状態遷移図には状態名も記入せよ．なお，ある状態 $x$ に対する $\varepsilon$-閉包とは，$x$ そのものと $x$ から $\varepsilon$-動作のみで到達できる状態全ての集合をいう．

(1-3) 有限オートマトン $M_3$ と同じ言語 (language) を受理する状態数が最小 (minimum) の決定性有限オートマトン $M_3'$ を求めて，状態遷移図で示せ．なお $M_3'$ を求める過程は示さずに，結果のみを示せ．

(2) 文脈自由文法 (context-free grammar) に関して以下の各小問に答えよ．なお文法 $G_1, G_2$ それぞれを以下の通り定める．

文法 $G_1(V_1, T_1, P_1, S_1)$

• 非終端記号の集合 $V_1 = \{A\}$
• 終端記号の集合 $T_1 = \{\text{if}, \text{then}, \text{else}, \text{e}, \text{s}\}$
• 開始記号 $S_1 = A$
• 生成規則の集合 $P_1 = \{ A \to \text{if e then } A, \quad A \to \text{if e then } A \text{ else } A, \quad A \to \text{s} \}$

文法 $G_2(V_2, T_2, P_2, S_2)$

• 非終端記号の集合 $V_2 = \{B, C, D\}$
• 終端記号の集合 $T_2 = \{\text{if}, \text{then}, \text{else}, \text{e}, \text{s}\}$
• 開始記号 $S_2 = B$
• 生成規則の集合 $P_2 = \{ B \to C, \quad B \to D, \quad C \to \text{if e then } B, \quad D \to \text{if e then } D \text{ else } B, \quad D \to \text{s} \}$

(2-1) 文法 $G_1$ における文 “$\text{if e then s else if e then s}$” に対する最左導出 (leftmost derivation) および最右導出 (rightmost derivation) における導出の過程をそれぞれ示せ．

(2-2) 文法 $G_1$ における文 “$\text{if e then if e then s else s}$” に対する異なる 2 通りの導出木 (derivation tree) を示せ．

(2-3) 文法 $G_2$ は曖昧である．具体的な根拠を示せ．

(1-1)#

状態遷移および受理状態 $c$ に至る長さ 4 以下の経路の解析：

• 受理状態は $c$ のみである。
• 長さ 2 の受理語：
  • $a \xrightarrow{1} b \xrightarrow{0} c \implies$ 10
• 長さ 4 の受理語：
  • $a \xrightarrow{0} d \xrightarrow{0} a \xrightarrow{1} b \xrightarrow{0} c \implies$ 0010
  • $a \xrightarrow{0} d \xrightarrow{1} e \xrightarrow{1} b \xrightarrow{0} c \implies$ 0110
  • $a \xrightarrow{1} b \xrightarrow{1} e \xrightarrow{1} b \xrightarrow{0} c \implies$ 1110

解答：10, 0010, 0110, 1110

(1-2)#

1
stateDiagram-v2
2
    [*] --> h
3
    h --> k : 0
4
    h --> i : 1
5
    h --> j : 1
6
    h --> k : 1
7
    i --> k : 0
8
    i --> i : 1
9
    i --> j : 1
10
    j --> k : 0
11
    j --> i : 1
12
    j --> j : 1
13
    k --> k : 1
14

15
    state h %% accepting
16
    state k %% accepting

(1-3)#

部分集合構成法（Subset Construction）を用いて NFA $M_3$ を DFA に変換し、等価な状態を併合して最小化（Minimization）を行う。 最小化された決定性有限オートマトン（DFA）$M_3'$ の状態集合は 5 つとなる：

• $S_0 = \{l\}$ （初期状態、非受理）
• $S_1 = \{l, m\}$ （受理状態）
• $S_2 = \{m\}$ （受理状態）
• $S_3 = \{m, n\}$ （受理状態）
• $S_4 = \{n\}$ （受理状態）

DFA $M_3'$ の状態遷移図：

1
stateDiagram-v2
2
    [*] --> S0
3
    S0 --> S1 : 0
4
    S0 --> S2 : 1
5
    S1 --> S1 : 0
6
    S1 --> S3 : 1
7
    S2 --> S0 : 0
8
    S2 --> S4 : 1
9
    S3 --> S1 : 0
10
    S3 --> S4 : 1
11
    S4 --> S2 : 0
12
    S4 --> S4 : 1
13

14
    state S1 %% accepting
15
    state S2 %% accepting
16
    state S3 %% accepting
17
    state S4 %% accepting

(2-1)#

対象の文は “$\text{if e then s else if e then s}$”：

• 最左導出 (Leftmost Derivation): $A \Rightarrow \text{if e then } A \text{ else } A \Rightarrow \text{if e then s else } A \Rightarrow \text{if e then s else if e then } A \Rightarrow \text{if e then s else if e then s}$
• 最右導出 (Rightmost Derivation): $A \Rightarrow \text{if e then } A \text{ else } A \Rightarrow \text{if e then } A \text{ else if e then } A \Rightarrow \text{if e then } A \text{ else if e then s} \Rightarrow \text{if e then s else if e then s}$

(2-2)#

対象 of 文は “$\text{if e then if e then s else s}$”。この文法には「懸念される else（dangling-else）」の曖昧性が存在する：

導出木 1 (else が内側の if と結合する場合):

1
graph TD
2
    A1[A] --> if1[if]
3
    A1 --> e1[e]
4
    A1 --> then1[then]
5
    A1 --> A2[A]
6
    A2 --> if2[if]
7
    A2 --> e2[e]
8
    A2 --> then2[then]
9
    A2 --> A3[A]
10
    A3 --> s1[s]
11
    A2 --> else2[else]
12
    A2 --> A4[A]
13
    A4 --> s2[s]

導出木 2 (else が外側の if と結合する場合):

1
graph TD
2
    A1[A] --> if1[if]
3
    A1 --> e1[e]
4
    A1 --> then1[then]
5
    A1 --> A2[A]
6
    A2 --> if2[if]
7
    A2 --> e2[e]
8
    A2 --> then2[then]
9
    A2 --> A3[A]
10
    A3 --> s1[s]
11
    A1 --> else1[else]
12
    A1 --> A4[A]
13
    A4 --> s2[s]

(2-3)#

文法 $G_2$ は曖昧（二義的）である。なぜなら、語 $w = \text{if e then if e then s else if e then s else s}$ に対して、異なる 2 通りの構文解析木（すなわち、2通りの異なる最左導出）を構築できるからである。

• 導出 1（外側の if が非終端記号 $C$、すなわち else を持たない構造に対応）： $B \Rightarrow C \Rightarrow \text{if e then } B$ ここで、内側の $B$ が if-else 構造を推出する： $B \Rightarrow D \Rightarrow \text{if e then } D \text{ else } B$ ここで最初の $D \Rightarrow \text{s}$ であり、二番目の $B \Rightarrow D \Rightarrow \text{if e then } D \text{ else } B \Rightarrow \dots \Rightarrow \text{if e then s else s}$ となる。

• 導出 2（外側の if が非終端記号 $D$、すなわち else を持つ構造に対応）： $B \Rightarrow D \Rightarrow \text{if e then } D \text{ else } B$ ここで最初の $D \Rightarrow \text{if e then } D \text{ else } B \Rightarrow \text{if e then s else } C \Rightarrow \text{if e then s else if e then s}$ であり、二番目の $B \Rightarrow D \Rightarrow \text{s}$ となる。

このように、同じ文に対して 2 つの異なる解釈（構文木）が存在するため、文法 $G_2$ は曖昧である。

Stop-and-Wait ARQ 方式#

1
sequenceDiagram
2
    autonumber
3
    Note over 送信側, 受信側: Stop-and-Wait ARQ
4
    送信側 ->> 受信側: フレーム 1
5
    受信側 -->> 送信側: ACK
6
    送信側 ->> 受信側: フレーム 2 (ビット誤り)
7
    受信側 -->> 送信侧: NACK
8
    送信側 ->> 受信側: フレーム 2 (再送)
9
    受信側 -->> 送信側: ACK
10
    送信側 ->x 受信側: フレーム 3 (消失)
11
    Note over 送信側: タイムアウト
12
    送信側 ->> 受信側: フレーム 3 (再送)
13
    受信側 -->> 送信側: ACK

Go-back-N ARQ 方式 (N = 5)#

1
sequenceDiagram
2
    autonumber
3
    Note over 送信側, 受信側: Go-back-N ARQ (N = 5)
4
    送信側 ->> 受信側: フレーム 1
5
    送信側 ->> 受信側: フレーム 2
6
    送信側 ->> 受信側: フレーム 3
7
    受信側 -->> 送信側: ACK 1
8
    受信側 -->> 送信側: ACK 2
9
    送信側 ->> 受信側: フレーム 4 (ビット誤り)
10
    送信側 ->> 受信側: フレーム 5
11
    受信側 -->> 送信側: ACK 3
12
    Note over 受信側: 4の誤り検出 -> NACK 4 送信
13
    受信側 -->> 送信側: NACK 4
14
    Note over 受信側: フレーム 5 棄却 (順序不正)
15
    Note over 送信側: NACK 4 受信により 4 以降を再送
16
    送信側 ->> 受信側: フレーム 4 (再送)
17
    送信側 ->> 受信側: フレーム 5 (再送)
18
    送信側 ->> 受信側: フレーム 6
19
    送信側 ->> 受信側: フレーム 7
20
    受信側 -->> 送信側: ACK 4
21
    受信側 -->> 送信側: ACK 5
22
    受信側 -->> 送信側: ACK 6
23
    受信側 -->> 送信側: ACK 7

Selective Repeat ARQ 方式 (N = 5)#

1
sequenceDiagram
2
    autonumber
3
    Note over 送信側, 受信側: Selective Repeat ARQ (N = 5)
4
    送信側 ->> 受信侧: フレーム 1
5
    送信側 ->> 受信側: フレーム 2
6
    送信側 ->> 受信側: フレーム 3
7
    受信側 -->> 送信側: ACK 1
8
    受信側 -->> 送信側: ACK 2
9
    送信側 ->> 受信側: フレーム 4 (ビット誤り)
10
    送信側 ->> 受信側: フレーム 5
11
    受信側 -->> 送信側: ACK 3
12
    Note over 受信側: 4の誤り検出 -> NACK 4 送信
13
    受信側 -->> 送信側: NACK 4
14
    Note over 受信側: 正常な 5 をバッファに保持
15
    受信側 -->> 送信側: ACK 5
16
    Note over 送信側: NACK 4 受信により 4 のみ再送
17
    送信側 ->> 受信側: フレーム 4 (再送)
18
    Note over 受信側: 4受信後、5 と共に順序通り引き渡し
19
    受信側 -->> 送信側: ACK 4 & 5
20
    送信側 ->> 受信側: フレーム 6
21
    送信側 ->> 受信側: フレーム 7
22
    受信側 -->> 送信側: ACK 6
23
    受信側 -->> 送信側: ACK 7

(1) 送受信ノードにおいて， I) Stop-and-Wait ARQ 方式には必要なく，Go-back-N ARQ 方式には必要な機能， II) Go-back-N ARQ 方式には必要なく，Selective Repeat ARQ 方式には必要な機能 を，それぞれ 2 つずつ以下から選んで記号を書き，それぞれについて簡潔に理由を述べよ．3つ以上の選択肢が該当する場合には，そのうちの2つについて解答すればよい． (a) データフレーム番号によるデータフレーム識別 (b) 受信側ノードでの受信データフレームの並べ替え (c) 受信側ノードでの受信済みデータフレーム番号の管理 (d) 送信側ノードでの送信データフレーム数の管理 (e) 送信側ノードでの最大 N 個分のデータフレームバッファの管理 (f) 受信側ノードでの最大 N 個分のデータフレームバッファの管理

(2) 片方向伝搬遅延 (one-way propagation delay) 40 ms, 通信速度 1000 bps の，フレーム誤りもフレームロスも発生しない伝送媒体において，長さ 100 bit のデータフレームを 99 個送信した際の，Stop-and-Wait ARQ 方式と Go-back-N ARQ 方式それぞれの平均スループットを求めよ．計算過程も示せ．なお，ACK フレームと NACK フレームの長さを 20 bit とし，Go-back-N ARQ 方式における N を 3 とする．平均スループットは，送信側ノードにおける一つ目のデータフレーム送信開始から最後のデータフレームに対する ACK フレーム受信完了までの単位時間あたりの送信データ量であり，単位は bps である．なお，問 (2) ～ 問 (4) においては，ACK フレーム，NACK フレームともに誤り，損失は発生しないものとする．

(3) 問 (2) において，片方向伝搬遅延を 200 ms とし，それ以外の条件を同じとした場合の，Stop-and-Wait ARQ 方式と Go-back-N ARQ 方式それぞれの平均スループットを求めよ．計算過程も示せ．

(4) 問 (2) において，伝送媒体でのフレームロスは発生しないが，確率 0.1 でフレーム誤りが発生するものとし，それ以外の条件を同じとした場合の，Stop-and-Wait ARQ 方式と Go-back-N ARQ 方式それぞれの平均スループットを求めよ．計算過程も示せ．

(5) 下図は，片方向伝搬遅延 40 ms, 通信速度 1000 bps の伝送媒体において，長さ 100 bit のデータフレームを順次送信し続けた際の，Stop-and-Wait ARQ 方式，Go-back-N ARQ 方式，Selective Repeat ARQ 方式の平均スループットを示したものである．なお，ACK フレームと NACK フレームの長さを 20 bit とし，Go-back-N ARQ 方式及び Selective Repeat ARQ 方式における N を十分大きいものとする．横軸が表す指標を答えよ．また，グラフ内の各線が上から順にそれぞれどの方式を表しているか答え，その理由を簡潔に述べよ．

(1)#

(2)#

给定参数：

• 单向传播延迟 $\tau = 40\text{ ms} = 0.04\text{ s}$
• 信道速率 $R = 1000\text{ bps}$
• 数据帧大小 $L_d = 100\text{ bit}$
• ACK 帧大小 $L_a = 20\text{ bit}$
• 数据帧总数 $M = 99$ 个
• 传输延迟：数据帧 $t_d = L_d / R = 0.1\text{ s}$；ACK 帧 $t_a = L_a / R = 0.02\text{ s}$。
• 每个帧的完整传输周期（RTT时间）：$T_{\text{cycle}} = t_d + \tau + t_a + \tau = 0.1 + 0.04 + 0.02 + 0.04 = 0.2\text{ s}$。

(3)#

参数变化：单向传播延迟 $\tau = 200\text{ ms} = 0.2\text{ s}$。

• 每个帧的完整传输周期变为：$T_{\text{cycle}} = t_d + 2\tau + t_a = 0.1 + 0.4 + 0.02 = 0.52\text{ s}$。

(4)#

参数同问 (2)，但有数据帧出错概率 $p = 0.1$。

(5)#

• 横轴所表示的指标：数据帧出错概率 $P_f$（或 フレーム誤り率，取值范围为 $0 \sim 1$）。
• 三条曲线从上至下的对应关系及理由：
  1. 最上方的实线：Selective Repeat ARQ 方式
     • 理由：因为 $N$ 足够大，当发生帧错误时，Selective Repeat 仅重传错误的那些帧。其吞吐量基本正比于 $(1 - P_f)$，下降最平缓，所以在任何错误率下其吞吐量都是三者中最高的。
  2. 中间的虚线：Go-back-N ARQ 方式
     • 理由：由于 $N$ 较大，一旦某个帧出错，整个发送窗口中的所有帧都要被迫回退并全部重传，重传开销大。其吞吐量随 $P_f$ 的增加比 Selective Repeat 下降得更快。但在错误率较低时，得益于流水线设计，它的吞吐量依然显著高于 Stop-and-Wait。
  3. 最下方の点線：Stop-and-Wait ARQ 方式
     • 理由：该方式不采用流水线，即便在完全无错（$P_f = 0$）的情况下，其吞吐量也被限制在 $500\text{ bps}$ 的低水平。随着错误率增加，由于重传的存在，其吞吐量也进一步下降，但始终在最底层。