大阪大学 情報科学研究科 情報工学 2018年度 必須問題＆選択問題#

Description#

配点： (1-1) 15点, (1-2) 10点, (1-3) 30点, (2-1) 20点, (2-2-1) 30点, (2-2-2) 20点

図1に示すANSI-C準拠であるC言語のプログラム（program）は任意の2人が同じ組織（organization）に所属するか判定し、その結果を出力（output）するものである。人（構成員（member）と呼ぶ）は $N$ 人（$N$ は正の整数（positive integer））存在し、各構成員には直属の上司（direct supervisor）である構成員が1人以下（1 or less）存在する。組織は一つ以上存在し、各組織は、各構成員を節点（ノード（node））、その直属の上司を親（parent）とする木（tree）で表される。同じ組織に所属する構成員は、その組織の最上位の上司を根（root）とする一つの木を構成する。

各構成員にはそれぞれ $0 \sim N-1$ の整数（integer）が構成員番号として重複なく付与されている。配列（array）p は構成員番号 i である構成員の直属の上司の構成員番号を要素（element）として p[i] に格納し、直属の上司が存在しない場合は自身の構成員番号を格納する。このデータ構造を用い、関数 same は2人の構成員番号を引数とし、同じ組織に所属するかどうかを標準出力に出力する。input.txt，pair.txt という図2および図3にそれぞれ示すようなフォーマットのファイルが存在するものとし、図1のプログラムでそれらを読み込み実行する。input.txt の1行目には構成員の総数 $N$（$N$ は N_MAX 以下の正の整数）、2行目以降の各行には、構成員とその直属の上司の構成員番号のペア（pair）がこの順で書かれている。pair.txt の各行には、同じ組織に所属するか判定したい構成員のペアの構成員番号が書かれている。以下の各問に答えよ。

Kai#

(1-1)#

• 日本語 (Japanese):

  1
    (0)            (1)           (5)
  2
     |            /   \
  3
    (2)         (3)   (7)
  4
               /   \
  5
             (4)   (6)
  6
              |
  7
             (8)
  8
              |
  9
             (9)
  

• 英語 (English): [The three trees illustrated in the ASCII diagram above]
• 中文解析 (Chinese Analysis): 根据 input.txt 的输入：
  • $N = 10$，初始化时每个节点 $i$ 的父节点为自身，即 p[i] = i。
  • 之后依次读入 i 与 sv，执行 p[i] = sv。这表示 sv 是 i 的直属上司（父节点）。
  • 读入的边为：$2 \to 0$, $3 \to 1$, $4 \to 3$, $6 \to 3$, $7 \to 1$, $8 \to 4$, $9 \to 8$。
  • 其余节点如 $0, 1, 5$ 的 p 值保持不变，仍为自身，即它们是各自树的根节点。 因此得到三个不同的树结构如上所示。

(1-2)#

• 日本語 (Japanese): 構成員 x が属する組織の最上位の上司（木の根の構成員番号）を返す。
• 英語 (English): It returns the top supervisor (the root of the tree) of the organization to which member x belongs.
• 中文解析 (Chinese Analysis): find(x) 沿着父指针 p[x] 递归向上查找，直到找到 p[root] == root 的根节点并将其返回。在题目背景中，这意味着寻找成员 x 所属组织的最上位上司（即代表者）。

(1-3)#

• 日本語 (Japanese):
  • A: find(y)
  • B: n == m
• 英語 (English):
  • A: find(y)
  • B: n == m
• 中文解析 (Chinese Analysis): 在 same(x, y) 中，要判断 x 和 y 是否在同一组织中。
  • 13行已有 n = find(x);。
  • 14行需要求出 y 的代表者并赋给 m，因此空栏 A 填 find(y)。
  • 15行若二者在同一组织中，则根节点应该相同，因此空栏 B 填 n == m。

(2-1)#

• 日本語 (Japanese): $O(h)$ 理由: 関数 same は内部で関数 find(x) と find(y) を呼び出す。find 処理は引数で指定されたノードから根に向かって親への参照をたどるため、その計算量は探索するパスの長さに比例する。ノードの平均の深さが $h$ であるため、find の1回当たりの平均時間計算量は $O(h)$ となる。よって、same の平均時間計算量も $O(h)$ である。
• 英語 (English): $O(h)$ Reason: The function same calls find(x) and find(y) internally. The helper function find traverses the path from the target node up to the root. Since the average depth of nodes in the trees is $h$, the average number of steps required to reach the root is proportional to $h$. Thus, the average time complexity of find and consequently same is $O(h)$.
• 中文解析 (Chinese Analysis):
  • 平均时间复杂度：$O(h)$
  • 原因：函数 same 执行了两次对 find 的调用。在未进行路径压缩的情况下，find 必须逐级向上访问父节点直到根节点。由于节点的平均深度为 $h$，路径的平均长度即为 $h$。因此，find 和 same 的平均时间复杂度均为 $O(h)$。

(2-2-1)#

• 日本語 (Japanese): return p[x] = find(p[x]);
• 英語 (English): return p[x] = find(p[x]);
• 中文解析 (Chinese Analysis): 将第9行修改为带有赋值的递归调用 return p[x] = find(p[x]); 可以实现路径压缩（Path Compression）。它在查找到根节点后，顺便将路径上所有经过的节点直接连接到根节点下。

(2-2-2)#

• 日本語 (Japanese): $O(1)$ （または $O(\alpha(N))$） 理由: パス圧縮（path compression）を行う場合、一度 find が実行されると、その探索経路上にあるすべてのノードが根に直接接続される。そのため、以降の探索ではほぼ定数ステップで根に到達できるようになる。same を十分に多い回数実行した場合、アモルタライズされた（ならし）1回当たりの時間計算量は、実質的に定数時間 $O(1)$（厳密には逆アッカーマン関数 $\alpha(N)$）に漸近する。
• 英語 (English): $O(1)$ (or $O(\alpha(N))$) Reason: When path compression is applied, each call to find updates the parent pointers of all traversed nodes to point directly to the root. As a result, subsequent lookups for these nodes take constant time. When the operation is repeated a large number of times, the amortized cost per operation asymptotically approaches $O(1)$ (or more formally, the inverse Ackermann function $O(\alpha(N))$, which is practically constant for any physical input size).
• 中文解析 (Chinese Analysis):
  • 渐近平均时间复杂度：$O(1)$（或 $O(\alpha(N))$）
  • 原因：当应用路径压缩后，每次查询根节点时，该路径上的所有节点都会被直接挂接到根节点上。随着 same 操作次数的不断增加，树的高度会被极大地压扁。在进行了足够多次操作后，绝大多数节点都直接指向根节点，因而单次操作的平均（摊还）时间复杂度趋向于常数级别 $O(1)$。若从并查集（Disjoint Set Union）的严格摊还分析来看，其复杂度为 $O(\alpha(N))$，其中 $\alpha$ 是增长极其缓慢的反阿克曼函数，实际中可视为 $O(1)$。

Description#

配点： (1-1) 8点, (1-2) 10点, (1-3-1) 18点, (1-3-2) 29点, (2-1) 18点, (2-2-1) 27点, (2-2-2) 10点, (2-2-3) 5点

Kai#

(1-1)#

• 日本語 (Japanese):
  • (a) 時間局所性 (Temporal Locality)
  • (b) 空間局所性 (Spatial Locality)
• 英語 (English):
  • (a) Temporal locality
  • (b) Spatial locality
• 中文解析 (Chinese Analysis): 局部性原理（Principle of Locality）包括：
  • 时间局部性（a）：若一个内存位置被访问，则它在不久的将来很可能会再次被访问（例如循环中的变量）。
  • 空间局部性（b）：若一个内存位置被访问，则其附近的内存位置在不久的将来很可能会被访问（例如数组的连续访问）。

(1-2)#

• 日本語 (Japanese):
  • (a) メモリアクセスの高速化（CPUの平均データアクセス待ち時間を短縮し、実行効率を向上させる）。
  • (b) メモリ空間の拡大と保護（物理主記憶の容量制限を超えたプログラムの実行を可能にし、プロセス間の独立したアドレス空間を確保する）。
• 英語 (English):
  • (a) Speed up memory access (reduce the average CPU wait time for data access and improve execution efficiency).
  • (b) Expand and protect memory space (allow execution of programs larger than the physical main memory and isolate address spaces between processes).
• 中文解析 (Chinese Analysis):
  • 引入高速缓存（a）的作用在于缓解CPU与主存之间的速度鸿沟，利用局部性原理将常用数据缓存在极高速的 SRAM 中，提高平均访存速度。
  • 引入虚拟内存（b）的作用在于：1. 扩充地址空间（使大程序能在小内存机器上运行）；2. 内存隔离与保护（各进程拥有独立的虚拟地址空间，互不干扰）。

(1-3-1)#

• 日本語 (Japanese):
  • (a) 8
  • (b) 4
  • (c) 32
  • (d) 2
  • (e) 2
  • (f) 5
• 英語 (English):
  • (a) 8 bits
  • (b) 4 blocks
  • (c) 32 entries
  • (d) 2 bits
  • (e) 2 bits
  • (f) 5 bits
• 中文解析 (Chinese Analysis):
  • (a) 虚拟内存容量为 $256$ 字节，按字节寻址。因此逻辑地址长度为 $\log_2(256) = 8$ 位。
  • (b) 高速缓存容量为 $8$ 字节，块大小为 $2$ 字节。因此缓存块数为 $8 / 2 = 4$ 块。
  • (c) 页面大小为 $8$ 字节，虚拟内存为 $256$ 字节。页面数为 $256 / 8 = 32$，因此页表项数为 $32$。
  • (d) 主存容量为 $32$ 字节，页面大小为 $8$ 字节。物理页框数为 $32 / 8 = 4$。物理页框号所需比特数为 $\log_2(4) = 2$ 位。
  • (e) 在物理地址缓存（Physical Address Cache）中，缓存使用物理地址进行访问。主存 $32$ 字节对应物理地址长度为 $\log_2(32) = 5$ 位。这 5 位物理地址被划分为：
    • 块内偏移量：$\log_2(\text{块大小}) = \log_2(2) = 1$ 位。
    • 缓存索引（Index）：$\log_2(\text{缓存块数}) = \log_2(4) = 2$ 位。
    • 标记（Tag）：物理地址长度 - 索引 - 偏移 = $5 - 2 - 1 = 2$ 位。
  • (f) 在逻辑地址缓存（Logical Address Cache）中，缓存使用逻辑地址进行访问。逻辑地址长度为 8 位。划分如下：
    • 块内偏移量：$\log_2(2) = 1$ 位。
    • 缓存索引：$\log_2(4) = 2$ 位。
    • 标记（Tag）：逻辑地址长度 - 索引 - 偏移 = $8 - 2 - 1 = 5$ 位。

(1-3-2)#

• 日本語 (Japanese):
  • 各サイクルの値:
    • サイクル 0: (a) 0, (b) 0, (c) 0
    • サイクル 1: (a) 0, (b) 0, (c) 0
    • サイクル 2: (a) 1, (b) 1, (c) 0
    • サイクル 3: (a) 1, (b) 1, (c) 0
    • サイクル 4: (a) 2, (b) 2, (c) 0
    • サイクル 5: (a) 4, (b) 0, (c) 1
    • サイクル 6: (a) 10, (b) 2, (c) 2
    • サイクル 7: (a) 15, (b) 3, (c) 3
  • (d) キャッシュヒット率: $25\%$ （または $2/8$）
• 英語 (English):
  • Values for each cycle:
    • Cycle 0: (a) 0, (b) 0, (c) 0
    • Cycle 1: (a) 0, (b) 0, (c) 0
    • Cycle 2: (a) 1, (b) 1, (c) 0
    • Cycle 3: (a) 1, (b) 1, (c) 0
    • Cycle 4: (a) 2, (b) 2, (c) 0
    • Cycle 5: (a) 4, (b) 0, (c) 1
    • Cycle 6: (a) 10, (b) 2, (c) 2
    • Cycle 7: (a) 15, (b) 3, (c) 3
  • (d) Cache hit rate: $25\%$ (or $2/8$)
• 中文解析 (Chinese Analysis):
  • 页面大小为 $8$ 字节。物理页框 0, 1, 2, 3 分别映射虚拟页面 0, 1, 2, 31。
    • 虚拟页面 0（LA 0-7）$\to$ 物理页框 0（PA 0-7）。
    • 虚拟页面 1（LA 8-15）$\to$ 物理页框 1（PA 8-15）。
    • 虚拟页面 2（LA 16-23）$\to$ 物理页框 2（PA 16-23）。
    • 虚拟页面 31（LA 248-255）$\to$ 物理页框 3（PA 24-31）。
  • 物理地址缓存使用物理地址访问，块大小为 2 字节。
    • 主存块号：$\lfloor PA / 2 \rfloor$。
    • 缓存块号：主存块号 $\pmod 4$。
    • 标记（Tag）：$\lfloor PA / 8 \rfloor$（即物理页框号 PFN）。
  • 逐步追踪过程：
    • C0: LA=0 $\to$ Page 0 $\to$ PFN 0 $\to$ PA=0 $\to$ 主存块=0 $\to$ 缓存块=0 $\to$ Tag=0。（Miss，填入缓存块 0，Tag=0）
    • C1: LA=1 $\to$ Page 0 $\to$ PFN 0 $\to$ PA=1 $\to$ 主存块=0 $\to$ 缓存块=0 $\to$ Tag=0。（Hit！）
    • C2: LA=2 $\to$ Page 0 $\to$ PFN 0 $\to$ PA=2 $\to$ 主存块=1 $\to$ 缓存块=1 $\to$ Tag=0。（Miss，填入缓存块 1，Tag=0）
    • C3: LA=3 $\to$ Page 0 $\to$ PFN 0 $\to$ PA=3 $\to$ 主存块=1 $\to$ 缓存块=1 $\to$ Tag=0。（Hit！）
    • C4: LA=4 $\to$ Page 0 $\to$ PFN 0 $\to$ PA=4 $\to$ 主存块=2 $\to$ 缓存块=2 $\to$ Tag=0。（Miss，填入缓存块 2，Tag=0）
    • C5: LA=8 $\to$ Page 1 $\to$ PFN 1 $\to$ PA=8 $\to$ 主存块=4 $\to$ 缓存块=0 $\to$ Tag=1。（Miss，缓存块 0 原本为 Tag 0 $\neq 1$，替换为 Tag 1）
    • C6: LA=21 $\to$ Page 2 $\to$ PFN 2 $\to$ PA=16+5=21 $\to$ 主存块=10 $\to$ 缓存块=2 $\to$ Tag=2。（Miss，缓存块 2 原本为 Tag 0 $\neq 2$，替换为 Tag 2）
    • C7: LA=255 $\to$ Page 31 $\to$ PFN 3 $\to$ PA=24+7=31 $\to$ 主存块=15 $\to$ 缓存块=3 $\to$ Tag=3。（Miss，填入缓存块 3，Tag=3）
  • 8次访问中命中2次，因此命中率为 $2 / 8 = 25\%$。

(2-1)#

• 日本語 (Japanese):
  • (ア): (F) 順アクセス
  • (イ): (B) 直接アクセス
  • (ウ): (E) 最大ファイルサイズ
  • (エ): (G) 断片化
  • (オ): (A) インデックスファイル割り付け
  • (カ): (I) リンクファイル割り付け
• 英語 (English):
  • (ア): (F) sequential access
  • (イ): (B) direct access
  • (ウ): (E) maximum file size
  • (エ): (G) fragmentation
  • (オ): (A) indexed file allocation
  • (カ): (I) linked file allocation
• 中文解析 (Chinese Analysis):
  • 文件的访问方式分为顺序访问（(F)）和直接/随机访问（(B)）。
  • 连续文件分配因为是连续分配的，需要在一开始就确定分配的最大块数，故需要预估最大文件大小（(E)）。其带来的另一个问题是磁盘上的外部碎片问题（即断片化 (G)）。
  • 为了解决这些问题，可以使用索引文件分配（(A)）——将指针存储在专门的索引块中；或者使用链接文件分配（(I)）——在每个数据块中存储指向下一个块的指针。

(2-2-1)#

• 日本語 (Japanese):
  • (a) 順アクセス時のアクセスブロック数:
    • 方式 (i): $\text{ceil}(n / b)$
    • 方式 (ii): $\text{ceil}(n / (b - a))$
    • 方式 (iii): $1 + \text{ceil}(n / b)$
  • (b) 特定バイトのみアクセス時のアクセスブロック数:
    • 方式 (i): $1$
    • 方式 (ii): $\text{ceil}(n / (b - a))$
    • 方式 (iii): $2$
  • (c) 最小サイズ $p$:
    • 方式 (i): $\text{ceil}(s / b) \times b$
    • 方式 (ii): $\text{ceil}(s / (b - a)) \times b$
    • 方式 (iii): $(1 + \text{ceil}(s / b)) \times b$
• 英語 (English):
  • (a) Number of accessed blocks for sequential access:
    • Method (i): $\text{ceil}(n / b)$
    • Method (ii): $\text{ceil}(n / (b - a))$
    • Method (iii): $1 + \text{ceil}(n / b)$
  • (b) Number of accessed blocks for accessing only the $n$-th byte:
    • Method (i): $1$
    • Method (ii): $\text{ceil}(n / (b - a))$
    • Method (iii): $2$
  • (c) Minimum size $p$:
    • Method (i): $\text{ceil}(s / b) \times b$
    • Method (ii): $\text{ceil}(s / (b - a)) \times b$
    • Method (iii): $(1 + \text{ceil}(s / b)) \times b$
• 中文解析 (Chinese Analysis):
  • (a) 顺序读取前 $n$ 字节：
    • 方式 (i) 连续分配：只需要按序读取包含前 $n$ 字节的数据块即可，数据块数为 $\lceil n/b \rceil$。
    • 方式 (ii) 链接分配：每个物理块中有 $a$ 字节存储下一个块的地址，可用数据容量为 $b-a$ 字节。为了得到前 $n$ 字节，需要顺序读取并沿着指针遍历，读取的块数为 $\lceil n/(b-a) \rceil$。
    • 方式 (iii) 索引分配：首先需要读取一次索引块（计作1次访问），然后再读取包含前 $n$ 字节的数据块（数量为 $\lceil n/b \rceil$）。因此总共访问 $1 + \lceil n/b \rceil$ 个块。
  • (b) 仅访问第 $n$ 字节：
    • 方式 (i) 连续分配：因为地址是连续的，可以通过简单的数学计算 $\lfloor (n-1)/b \rfloor$ 得到目标物理块号，直接一步读取该块。因此只需访问 $1$ 个块。
    • 方式 (ii) 链接分配：无法直接定位，必须从文件的第一个块开始通过指针逐个向后查找，直到第 $\lceil n/(b-a) \rceil$ 个块。总访问块数为 $\lceil n/(b-a) \rceil$。
    • 方式 (iii) 索引分配：首先读取索引块获取对应的块指针，然后读取该特定数据块。总共访问 $2$ 个块（索引块 + 数据块）。
  • (c) 存储大小 $p$：
    • 方式 (i) 连续分配：文件占用 $\lceil s/b \rceil$ 个块，占用字节数为 $\lceil s/b \rceil \times b$。
    • 方式 (ii) 链接分配：每个块有效容量为 $b-a$，共需 $\lceil s/(b-a) \rceil$ 个块，占用字节数为 $\lceil s/(b-a) \rceil \times b$。
    • 方式 (iii) 索引分配：需要 $\lceil s/b \rceil$ 个数据块以及 $1$ 个索引块，总共 $\lceil s/b \rceil + 1$ 个块。总字节数为 $(1 + \lceil s/b \rceil) \times b$。

(2-2-2)#

• 日本語 (Japanese):
  • 方式 (i): $e = \frac{r}{\text{ceil}(r)}$。 $0 < r \le 3$ において鋸歯状（のこぎり刃状）のグラフとなる。
    • $0 < r \le 1$: $e = r$。 $r \to 0$ で $e \to 0$， $r = 1$ で $e = 1$。
    • $1 < r \le 2$: $e = r / 2$。 $r \to 1^+$ で $e \to 1/2$， $r = 2$ で $e = 1$。
    • $2 < r \le 3$: $e = r / 3$。 $r \to 2^+$ で $e \to 2/3$， $r = 3$ で $e = 1$。
  • 方式 (iii): $e = \frac{r}{1 + \text{ceil}(r)}$。 各区間で右上がりの一次関数となり、境界で不連続に下降する。
    • $0 < r \le 1$: $e = r / 2$。 $r \to 0$ で $e \to 0$， $r = 1$ で $e = 1/2$。
    • $1 < r \le 2$: $e = r / 3$。 $r \to 1^+$ で $e \to 1/3$， $r = 2$ で $e = 2/3$。
    • $2 < r \le 3$: $e = r / 4$。 $r \to 2^+$ で $e \to 1/2$， $r = 3$ で $e = 3/4$。
• 英語 (English):
  • Method (i): $e = r / \text{ceil}(r)$. The graph forms a sawtooth shape in the range $0 < r \le 3$:
    • For $0 < r \le 1$: $e = r$, scaling linearly from 0 to 1 (at $r=1$).
    • For $1 < r \le 2$: $e = r/2$, scaling linearly from $1/2$ (just above $r=1$) to 1 (at $r=2$).
    • For $2 < r \le 3$: $e = r/3$, scaling linearly from $2/3$ (just above $r=2$) to 1 (at $r=3$).
  • Method (iii): $e = r / (1 + \text{ceil}(r))$. The graph increases linearly within each interval, dropping discontinuously at the boundaries:
    • For $0 < r \le 1$: $e = r/2$, scaling from 0 to $1/2$ (at $r=1$).
    • For $1 < r \le 2$: $e = r/3$, scaling from $1/3$ to $2/3$ (at $r=2$).
    • For $2 < r \le 3$: $e = r/4$, scaling from $1/2$ to $3/4$ (at $r=3$).
• 中文解析 (Chinese Analysis):
  • 方式 (i) 的利用率 $e_i = s/p = s / (\lceil s/b \rceil b) = r / \lceil r \rceil$。其曲线呈锯齿状：
    • 在每个区间 $(k-1, k]$ 上，$\lceil r \rceil = k$ 恒定，利用率 $e_i = r/k$ 是斜率为 $1/k$ 的一次函数。
    • 在 $r=1, 2, 3$ 点处利用率均达到最大值 $1.0$。
  • 方式 (iii) 的利用率 $e_{iii} = s/p = s / ((1 + \lceil s/b \rceil) b) = r / (1 + \lceil r \rceil)$。其曲线也呈锯齿状，但由于索引块的额外开销，数值明显偏低：
    • 在每个区间 $(k-1, k]$ 上，$\lceil r \rceil = k$，利用率 $e_{iii} = r/(k+1)$。
    • 当 $r=1$ 时，$e = 1/2 = 0.5$；当 $r=2$ 时，$e = 2/3 \approx 0.67$；当 $r=3$ 时，$e = 3/4 = 0.75$。

(2-2-3)#

• 日本語 (Japanese): 比は増加し、1 に近づく。
• 英語 (English): The ratio of the utilization efficiency of method (iii) to method (i) increases and asymptotically approaches 1.
• 中文解析 (Chinese Analysis): 两者的利用率比值为 $\frac{e_{iii}}{e_i} = \frac{r / (1 + \lceil r \rceil)}{r / \lceil r \rceil} = \frac{\lceil r \rceil}{1 + \lceil r \rceil} = 1 - \frac{1}{1 + \lceil r \rceil}$。 当 $r$ 增大时，$\lceil r \rceil$ 随之增大，使得额外的 $1$ 个索引块占总块数的比例下降。因此，比值 $\frac{\lceil r \rceil}{1 + \lceil r \rceil}$ 会不断上升并渐近趋近于 $1$。

Description#

配点： (1-1) 16点, (1-2-1) 14点, (1-2-2) 15点, (2-1) 15点, (2-2) 15点, (2-3) 10点, (2-4) 10点, (2-5) 15点

1
[開始] ──> q0 ── (1, Z)/1Z ──> q1 ── (ε, Z)/Z ──> ((q2))
2
                  (2, Z)/2Z             |
3
                                        | (あ)
4
                                        v
5
                                     [loop]

Kai#

(1-1)#

• 日本語 (Japanese):
  • (i) 7 (正規表現: $b^*ab*ab^*$)
  • (ii) 8 (正規表現: $((a+b)(a+b)(a+b))^*(a+b)$)
  • (iii) 6 (正規表現: $b^*a*b(a+b)^*$)
  • (iv) 3 (正規表現: $(a + bb)^*(aa + b)^*$)
• 英語 (English):
  • (i) 7 (Regular expression: $b^*ab*ab^*$)
  • (ii) 8 (Regular expression: $((a+b)(a+b)(a+b))^*(a+b)$)
  • (iii) 6 (Regular expression: $b^*a*b(a+b)^*$)
  • (iv) 3 (Regular expression: $(a + bb)^*(aa + b)^*$)
• 中文解析 (Chinese Analysis):
  • (i) 该 NFA 包含三个状态。唯一的接受路径需要经过两次标签为 $a$ 的转移。其余在状态上环绕的转移为 $b$。所以该机接受包含恰好两个 $a$ 的字符串，对应的正规表达式为 $b^* a b^* a b^*$。这与选项 7 匹配。
  • (ii) 该 NFA 是一个有向环结构，包含三个状态。每个转移都接受 $a$ 或 $b$。要从起点到达接受状态，必须经过 $1, 4, 7, \dots$ 次转移。因此，可接受串的长度必须模 3 余 1（即 $3m+1$ 长度的串）。其表示为 $3m$ 长度的任意串接上一个任意字符，对应的正规表达式为 $((a+b)(a+b)(a+b))^*(a+b)$。这与选项 8 匹配。
  • (iii) 通过 NFA 状态转移搜索和化简，该状态机识别的语言是包含至少一个 $b$ 且在第一个 $b$ 之前只有 $b$ 和 $a$ 的某种组合，本质上等价于 $b^* a^* b (a+b)^*$。这与选项 6 匹配。
  • (iv) 起始状态具有自环 $a$ 和 $bb$。接受状态具有自环 $aa$ 和 $b$。二者之间由 $a$ 和 $b$ 的转换连接。对应的语言描述为：前半部分由 $a$ 和 $bb$ 构成，后半部分由 $aa$ 和 $b$ 构成。即 $(a + bb)^*(aa + b)^*$。这与选项 3 匹配。

(1-2-1)#

• 日本語 (Japanese):

  1
    =======> ((p0)) <─── 2 ─── p1
  2
              |  ^             ^ |
  3
              |  └──── 1 ──────┘ |
  4
              1                  2
  5
              |                  |
  6
              v                  v
  7
              p1 ──── 1 ───> p2 ──> p0 (on 1)
  8
                             p2 ─── 2 ───> p1
  

  状態遷移表 (State Transition Table):

  状態	入力 1	入力 2
  p0 (開始・最終)	p1	p2
  p1	p2	p0
  p2	p0	p1

• 英語 (English): The state transition diagram of the DFA $A_D$:
  • States: $Q = \{p_0, p_1, p_2\}$.
  • Start & Final state: $p_0$ (represented with a double circle and a thick incoming arrow).
  • Transitions:
    • $\delta(p_0, 1) = p_1$, $\delta(p_0, 2) = p_2$.
    • $\delta(p_1, 1) = p_2$, $\delta(p_1, 2) = p_0$.
    • $\delta(p_2, 1) = p_0$, $\delta(p_2, 2) = p_1$.
• 中文解析 (Chinese Analysis):
  • 状态代表当前数字累加和模 3 的余数。起始终止状态均为 $p_0$（余数为 0）。
  • 转移逻辑：
    • $p_0$ 状态（余数为 0）：输入 1 转移到 $p_1$（余数 1），输入 2 转移到 $p_2$（余数 2）。
    • $p_1$ 状态（余数为 1）：输入 1 转移到 $p_2$（余数 2），输入 2 转移到 $p_0$（余数 0）。
    • $p_2$ 状态（余数为 2）：输入 1 转移到 $p_0$（余数 0），输入 2 转移到 $p_1$（余数 1）。

(1-2-2)#

• 日本語 (Japanese):
  • (1, 1) / 2
  • (2, 2) / 1
  • (1, Z) / 1Z
  • (2, Z) / 2Z
• 英語 (English):
  • (1, 1) / 2
  • (2, 2) / 1
  • (1, Z) / 1Z
  • (2, Z) / 2Z
• 中文解析 (Chinese Analysis): 通过 PDA 的栈模拟累加和模 3 的状态。 栈顶为 $Z$ 代表当前余数为 0，为 $1$ 代表当前余数为 1，为 $2$ 代表当前余数为 2。
  • 若输入与栈顶代表值相加等于 3（即 1 与 2 组合），则发生抵消，直接弹出栈顶。题目中已有 (2,1)/ε 和 (1,2)/ε 表示此类情况。
  • 若栈顶为 $Z$：
    • 输入 1：入栈 1，即 (1, Z) / 1Z。
    • 输入 2：入栈 2，即 (2, Z) / 2Z。
  • 若相同元素相加：
    • 栈顶为 1，输入 1：余数变为 2，应将栈顶 1 替换为 2，即 (1, 1) / 2。
    • 栈顶为 2，输入 2：余数变为 $2+2 \equiv 1 \pmod 3$，应将栈顶 2 替换为 1，即 (2, 2) / 1。

(2-1)#

• 日本語 (Japanese): ()、 ()()、 (())、 ()()()、 ()(())、 (())()、 (()())、 ((()))
• 英語 (English): (), ()(), (()), ()()(), ()(()), (())(), (()()), ((())
• 中文解析 (Chinese Analysis): 文法中没有 $A \to \varepsilon$ 这一项，因此最短生成的串为 ()，长度只能为偶数。
  • 长度 2: ()
  • 长度 4: ()(), (())
  • 长度 6: ()()(), ()(()), (())(), (()()), ((()))

(2-2)#

• 日本語 (Japanese):

  1
      Tree 1:                  Tree 2:
  2
         A                        A
  3
       /   \                    /   \
  4
      A     A                  A     A
  5
     / \    |                  |    / \
  6
    A   A   ()                ()   A   A
  7
    |   |                          |   |
  8
   ()  ()                         ()  ()
  

• 英語 (English): [The two parse trees illustrated in the ASCII diagram above]
• 中文解析 (Chinese Analysis): 对于串 ()()()，仅能通过 $A \to AA$ 和 $A \to ()$ 这两组规则生成。 因为该串包含三个 ()，所以树的派生在第一步 $A \to AA$ 后，要么左边的 $A$ 进一步分裂为 $AA$（对应 (()())() 结构），要么右边的 $A$ 进一步分裂为 $AA$（对应 ()(()()) 结构）。故仅有上述两棵不同的构型树。

(2-3)#

• 日本語 (Japanese): 5
• 英語 (English): 5
• 中文解析 (Chinese Analysis): 对于仅包含 $n$ 个独立小括号对 () 组成的字符串 ()()...()，因为不能使用 $A \to (A)$ 的规则（否则会出现嵌套），所以构建不同构型语法树的方法数等价于对 $n$ 个元素进行完全二叉树划分（加括号）的方法数。 根据组合数学，这符合卡特兰数（Catalan Number） $C_{n-1}$。 对于 ()()()()， $n=4$，因此不同语法树的数目为 $C_3 = 5$。

(2-4)#

• 日本語 (Japanese): 14
• 英語 (English): 14
• 中文解析 (Chinese Analysis): 同理，对于 5 个独立括号对，其语法树数量对应第 4 个卡特兰数： $C_4 = 14$。

(2-5)#

• 日本語 (Japanese):
  • (ア): ()
  • (イ): AA
  • (ウ): (y)
  • (エ): (A)
• 英語 (English):
  • (ア): ()
  • (イ): AA
  • (ウ): (y)
  • (エ): (A)
• 中文解析 (Chinese Analysis):
  • (ア)：当长度为 2 时，直接应用规则 $A \to ()$，因此填 ()。
  • (イ)：当 $x$ 可以拆分为两个平衡括号串 $v, w$ 时，在归纳法中通过 $A \to AA \Rightarrow^* vw = x$ 进行推导，因此填 AA。
  • (ウ)：当 $x$ 不能拆分为两个非空的平衡括号串时，说明 $x$ 的首尾是一对相匹配的括号。因此它必须以 ( 开始，以 ) 结束，即 $x = (y)$，其中 $y$ 也是一个平衡括号串且长度为 $k$。因此填 (y)。
  • (エ)：对应上述情况，使用文法规则 $A \to (A)$ 并结合归纳假设 $A \Rightarrow^* y$ 导出 $x = (y)$。因此填 (A)。

Description#

配点： (1-1) (あ)〜(う) 各2点, (え)〜(け) 各4点, (1-2) 10点, (1-3) 10点 (2-1) (a)〜(c) 各6点, (d) 12点, (2-2) 25点, (2-3) 20点

Kai#

(1-1)#

• 日本語 (Japanese):
  • (あ): 7
  • (い): 4
  • (う): 4/7
  • (え): $\begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}$
  • (お): 3
  • (か): $2^m - 1$
  • (き): 1
  • (く): 検査
  • (け): シンドローム
• 英語 (English):
  • (あ): 7
  • (い): 4
  • (う): 4/7
  • (え): $\begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}$
  • (お): 3
  • (か): $2^m - 1$
  • (き): 1
  • (く): parity check (matrix)
  • (け): syndrome
• 中文解析 (Chinese Analysis):
  • (あ) 校验矩阵 $H$ 的大小为 $3 \times 7$，列数即为码长，故码长为 7。
  • (い) $H$ 的行数表示校验位数 $n - k = 3$，因此信息位数 $k = 7 - 3 = 4$。
  • (う) 编码率 $R = k / n = 4 / 7$。
  • (え) $H$ 可以写为 $[P^T \mid I_3]$。生成矩阵 $G$ 在系统码形式下写为 $[I_4 \mid P]$。 转置 $P^T$ 的前 4 列为： $P^T = \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \end{pmatrix}$ 对 $P^T$ 转置得到矩阵 $P$： $P = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}$
  • (お) 二元哈明码的最小码距 $d$ 恒等于 3。
  • (か) 具有 $m$ 个校验位的哈明码，其码长公式为 $2^m - 1$。
  • (き) 该码能纠正的错误比特数为 $\lfloor (d-1)/2 \rfloor = \lfloor (3-1)/2 \rfloor = 1$ 比特。
  • (く), (け) 限界距离译码通常通过接收字与校验矩阵相乘计算伴随式（Syndrome，又称信噪）来进行错误定位。

(1-2)#

• 日本語 (Japanese): 同じ冗長記号数 $m$ を持つ場合、検査行列 $H$ の行数は $m$ であり、 $H$ の列ベクトル（列要素）として取り得るすべての非零の列ベクトルの種類数は $2^m - 1$ 個である。ハミング符号の符号長はちょうど $2^m - 1$ であり、検査行列のすべての列が非零で互いに異なっている。ハミング符号より符号化率が高いブロック符号は、同じ $m$ のもとで符号長 $n$ が $2^m - 1$ より大きくなる。鳩の巣原理により、この検査行列には必ず零ベクトルである列が存在するか、あるいは少なくとも2つの同一の列ベクトルが存在する。列ベクトルに零ベクトルが存在すれば最小距離は1となり、2つの同一の列ベクトルが存在すれば（その和が零ベクトルになるため）最小距離は2以下となる。したがって、最小距離はハミング符号の最小距離 3 より必ず小さくなる。
• 英語 (English): If a block code has the same number of redundancy symbols $m$, its parity check matrix $H$ has $m$ rows, and the maximum number of distinct non-zero column vectors of length $m$ is $2^m - 1$. The binary Hamming code achieves the maximum possible code length $n = 2^m - 1$ with all columns being distinct and non-zero. A block code with a higher code rate under the same $m$ must have a code length $n > 2^m - 1$. By the Pigeonhole Principle, its parity check matrix $H$ must contain either a zero column vector or at least two identical column vectors. A zero column implies a minimum distance of 1, and two identical columns imply a minimum distance of at most 2. Thus, the minimum distance must be strictly less than 3.
• 中文解析 (Chinese Analysis): 校验位为 $m$ 时，校验矩阵 $H$ 的行数为 $m$。长为 $m$ 的非零二元列向量共有 $2^m - 1$ 种。 哈明码达到了该最大容量限制，其码长为 $2^m - 1$，矩阵 $H$ 中包含了所有可能的非零列向量且互不相同。 若某纠错码在相同冗余位 $m$ 下具有更高的编码率，其码长 $n$ 必须大于 $2^m - 1$。 根据鸽巢原理，其校验矩阵的 $n$ 列中必然会出现：
  1. 包含零列向量，此时最小码距为 1。
  2. 包含至少两列完全相同的列向量，其异或和为零向量，此时最小码距为 2。 在这两种情况下，最小码距都将小于哈明码的最小码距 3。

(1-3)#

• 日本語 (Japanese): 受信語を $r = c + e$ （ $c$ は送信符号語， $e$ は誤りパターン）とすると，シンドロームは $S = H e^T$ となる。誤りが1ビット（位置 $i$ ）の場合， $e$ は重み1のベクトルになり，シンドローム $S$ は検査行列 $H$ の第 $i$ 列ベクトル $h_i$ に一致する。 $H$ のすべての列ベクトルが非零かつ相異なるため，1ビット誤りのパターンと非零シンドロームは1対1に対応し，正しく訂正できる。しかし，誤りが2ビット（位置 $i$ と $j$ ）の場合，シンドロームは $S = h_i + h_j$ となる。 $h_i \ne h_j$ であるため，その和 $h_i + h_j$ は非零ベクトルとなり， $H$ のある第 $k$ 列ベクトル $h_k$ （ $k \ne i, j$ ）に一致する。このとき，限界距離復号法は $S = h_k$ に基づいて第 $k$ ビットに1ビットの誤りが発生したと判断し，第 $k$ ビットを反転するため，誤った符号語に復号される。よって，1個より多い誤りがある場合は必ず誤って復号される。
• 英語 (English): The syndrome of a received word $r = c + e$ is given by $S = H e^T = H e^T$. When there is exactly 1 bit error at position $i$, the error vector $e$ has weight 1, and the syndrome $S$ is equal to the $i$-th column $h_i$ of $H$. Since all columns of $H$ are distinct and non-zero, there is a unique one-to-one mapping between any single-bit error and the syndrome, guaranteeing correct decoding. However, if there are 2 bit errors at positions $i$ and $j$, the syndrome is $S = h_i + h_j$. Since $h_i \ne h_j$, their sum $h_i + h_j$ is a non-zero vector that must match some column $h_k$ of $H$ (where $k \ne i, j$). Bounded distance decoding will incorrectly assume a single-bit error occurred at position $k$ and flip bit $k$, leading to an incorrect codeword. Hence, any error count greater than 1 results in incorrect decoding.
• 中文解析 (Chinese Analysis): 伴随式为 $S = H e^T$。
  • 当发生 1 位错误（在第 $i$ 位）时，错误向量 $e$ 仅在第 $i$ 位为 1，此时计算得到的 $S$ 正好是校验矩阵的第 $i$ 列 $h_i$。由于 $H$ 的所有列向量均非零且互不相同，每一个单比特错误都有唯一对应的非零伴随式，因此能被无误纠正。
  • 当发生 2 位错误（在第 $i$ 和第 $j$ 位）时，伴随式 $S = h_i + h_j$。由于 $h_i \neq h_j$，它们的和也是一个非零向量。因为 $H$ 包含了所有可能的非零向量，所以 $h_i + h_j$ 必然等于 $H$ 中的某另一列 $h_k$（$k \neq i, j$）。此时限界距离译码器会判定在第 $k$ 位发生了单比特错误并对其进行纠正，从而导致译码错误，恢复出错误的码字。

(2-1)#

• 日本語 (Japanese):
  • (a): ランダム
  • (b): 二進指数（または 指数）
  • (c): $rD$
  • 下線部 (d) の処理を行う理由: 連続して衝突が発生することは、ネットワークの混雑度（負荷）が高いことを示している。再送待ち時間の選択範囲（ウィンドウサイズ $X$）を指数関数的に拡大し、平均待ち時間を大きくすることで、各ホストが再送するタイミングを時間的により広く分散させ、再衝突の確率を下げるため。
• 英語 (English):
  • (a): randomly
  • (b): binary exponential (or exponential)
  • (c): $rD$
  • Reason for performing the process in underline (d): Consecutive collisions indicate a high traffic load and congestion on the network. By expanding the backoff window size $X$ exponentially and increasing the average waiting time, the retransmission timings of the conflicting hosts are spread wider in time, thereby lowering the probability of subsequent collisions and alleviating network congestion.
• 中文解析 (Chinese Analysis):
  • (a) 整数 $r$ 是在区间 $[0, X]$ 中随机（randomly）选取的。
  • (b) 该算法为二进指数退避算法（binary exponential backoff）。
  • (c) 延迟时间为随机数 $r$ 乘以时隙时间 $D$，即 $t = rD$。
  • 折返等待时间增加的原因 (d)： 连续发生冲突说明当前网络负载极高，处于拥堵状态。通过指数级扩大退避窗口范围 $X$，使冲突节点选择的随机等待时间在时间轴上更广泛地分散开来，从而显著降低再次发生碰撞的概率，避免拥堵持续加剧。