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

Description#

配点： (1) 12点, (2) 12点, (3) 14点, (4) 25点, (5-1) 20点, (5-2) 30点, (6) 12点

図1に示す ANSI-C 準拠である C 言語のプログラム (program) は、複数の整数 (integer) のデータ (data) を、二分木 (binary tree) を利用して昇順 (ascending order) に整列 (sort) して出力 (output) するプログラムである。図1のプログラムでは、配列 (array) の添え字 (index) が二分木の節点番号 (node number) に対応している。ただし、二分木の根 (root) の節点番号を 0 とし、節点番号が $i$ の節点に子 (child) がある場合、左の子の節点番号を $2i+1$、右の子の節点番号を $2i+2$ とする。また、配列に格納されたデータは、二分木の対応する節点のデータを示している。

整列するデータは図2に示すような形式 (format) のファイル data.txt で与えられ、1行目には整列するデータの個数 $n$ ($n \ge 1$)、2行目以降の $n$ 行には整列するデータの値 (value) が書かれている。図3は、図2の data.txt を与えて図1のプログラムを実行した場合の、28行目が実行される直前の配列 d に対応する二分木であり、丸が節点、丸の左側の数字が節点番号、丸の中の数字がデータの値、線分が枝 (edge) を示している。図1のプログラムに関する以下の各問に答えよ。

1
#include <stdio.h>
2
#include <stdlib.h>
3

4
void swap(int d[], int p, int q) {
5
    int tmp;
6
    tmp = d[p]; d[p] = d[q]; d[q] = tmp;
7
}
8

9
void downh(int d[], int n, int k) {
10
    int child, current = k;
11
    while (current < n / 2) {
12
        child = current * 2 + 1;
13
        if ((child + 1 < n) && (d[child] < d[child + 1])) // (ア) (イ)
14
            child++;
15
        if (d[current] < d[child]) // (ウ)
16
            swap(d, current, child);
17
        else
18
            break;
19
        current = child;
20
    }
21
}
22

23
void uph(int d[], int k) {
24
    int parent, current = k;
25
    while (0 < current) {
26
        parent = (current - 1) / 2;
27
        if (d[parent] < d[current]) // (エ)
28
            swap(d, parent, current);
29
        else
30
            break;
31
        current = parent;
32
    }
33
}
34

35
void sort(int d[], int n) {
36
    int i;
37
    for (i = 1; i < n; i++) // 28行目
38
        uph(d, i);
39
    for (i = n - 1; 0 < i; i--) { // 29行目
40
        swap(d, 0, i);
41
        downh(d, i, 0);
42
    }
43
}
44

45
int main() {
46
    int i, N, *D;
47
    FILE* fp;
48
    fp = fopen("data.txt", "r");
49
    fscanf(fp, "%d", &N);
50
    D = (int*) malloc(sizeof(int) * N);
51
    for (i = 0; i < N; i++)
52
        fscanf(fp, "%d", &D[i]);
53
    fclose(fp);
54

55
    sort(D, N);
56

57
    for (i = 0; i < N; i++)
58
        printf("%d ", D[i]);
59
    printf("\n");
60
    free(D);
61
    return 0;
62
}

(1) 40行目で呼び出されている関数 (function) sort で実現されている整列アルゴリズム (sorting algorithm) は、一般に何と呼ばれているか名称を答えよ。

(2) 図2の data.txt を与えてプログラムを実行した場合の、28行目が実行された直後の配列 d に対応する二分木を図示せよ。ただし、図3にならい、丸で節点、丸の左側の数字で節点番号、丸の中の数字でデータの値、線分で枝を示すこと。

(3) 11行目および12行目が実行されることにより、節点番号が current の節点のデータとその子データの間に成立する関係を説明せよ。

(4) 関数 sort で実現されている整列アルゴリズムの最悪時間計算量 (worst case time complexity) を、整列するデータの個数 $n$ を用いて理由と共にオーダ表記 (order notation) で示せ。

(5) 関数 sort において、28行目の実行時に関数 swap が呼び出される回数を $T(n)$ とする。$n$ は整列するデータの個数である。28行目を変更し、28行目の for ループの繰り返し回数と $T(n)$ の最大値をできる限り削減（28行目の実行に要する最悪時間計算量を削減）することを考える。以下の各小問に答えよ。

(5-1) 下記の (あ) 〜 (え) を埋めて変更後の 28 行目を完成させよ。 for (i = (あ); 0 <= i; i--) downh( (い), (う), (え) );

(5-2) 変更後のプログラムにおける $T(n)$ の $n$ に関するオーダ表記を理由と共に示せ。 $\sum_{j=0}^{h} \frac{j}{2^j} = 2 - \frac{2+h}{2^h}$ を用いてよい。

(6) 下線 (ア) 〜 (エ) で示す条件式を必要に応じて変更し、データを降順 (descending order) に整列して出力することを考える。変更後のプログラムにおける下線 (ア) 〜 (エ) の条件式をそれぞれ答えよ。

Kai#

(1)#

• 日本語 (Japanese): ヒープソート (Heap Sort)
• 英語 (English): Heap Sort
• 中文解析 (Chinese Analysis): 该程序实现的是堆排序（Heap Sort）。利用数组模拟完全二叉树，并通过向上调整（uph）和向下调整（downh）维护大顶堆（max-heap），每次将堆顶最大值放置到未排序部分的末尾以实现升序排列。

(2)#

• 日本語 (Japanese): 28行目のヒープ構築ループが終了した直後の二分木の状態は以下の通りである。
• 英語 (English): The state of the binary tree immediately after the heap construction loop (Line 28) completes is shown below.
• 中文解析 (Chinese Analysis): 初始数据为 [40, 30, 50, 10, 60, 20]，执行完28行的 uph 循环后，数组 d 被调整为满足大顶堆性质的 [60, 50, 40, 10, 30, 20]。对应的完全二叉树结构如下所示：

1
graph TD
2
    0((0: 60)) --- 1((1: 50))
3
    0 --- 2((2: 40))
4
    1 --- 3((3: 10))
5
    1 --- 4((4: 30))
6
    2 --- 5((5: 20))

(3)#

• 日本語 (Japanese): 節点番号 current の節点のデータは、その存在するすべての子のデータ以上であるという関係が成立する。
• 英語 (English): The relationship established is that the data of the node at index current is greater than or equal to the data of all its existing children.
• 中文解析 (Chinese Analysis): 建立的关系是：父节点 current 的数据大于或等于其所有子节点（左子节点，以及若存在则包含右子节点）的数据。 过程分析：第11行先判定右子节点是否存在，并选择左右子节点中数值较大的一个（将下标存入 child）。第12行将当前节点与这个较大的子节点进行比较，若当前节点较小，则与之交换，从而保证当前节点不小于它的任何子节点。

(4)#

• 日本語 (Japanese): 最悪時間計算量は $O(n \log n)$ である。 理由:
  1. ヒープ構築フェーズ: $n-1$ 回 uph を呼び出す。各ステップ $i$ での uph の最大実行時間は完全二分木の高さ $O(\log i)$ に比例するため、ヒープ構築の最悪計算量は $\sum_{i=1}^{n-1} O(\log i) = O(n \log n)$ となる。
  2. 整列フェーズ: $n-1$ 回 downh を呼び出す。サイズ $i$ のヒープに対する downh の最大実行時間は高さ $O(\log i)$ に比例するため、整列フェーズの最悪計算量は $\sum_{i=1}^{n-1} O(\log i) = O(n \log n)$ となる。 両フェーズを合わせた全体の最悪時間計算量は $O(n \log n) + O(n \log n) = O(n \log n)$ となる。
• 英語 (English): The worst-case time complexity is $O(n \log n)$. Reason:
  1. Heap construction phase: The loop calls uph $n-1$ times. For each index $i$, the worst-case time of uph is proportional to the tree height $O(\log i)$. The total time is $\sum_{i=1}^{n-1} O(\log i) = O(n \log n)$.
  2. Sorting phase: The algorithm extracts the maximum element and calls downh $n-1$ times. The worst-case time for downh on a heap of size $i$ is $O(\log i)$. The total time is $\sum_{i=1}^{n-1} O(\log i) = O(n \log n)$. Thus, the overall worst-case time complexity is $O(n \log n) + O(n \log n) = O(n \log n)$.
• 中文解析 (Chinese Analysis): 堆排序的整体最坏时间复杂度为 $O(n \log n)$。 具体原因：
  • 堆构建阶段：从二叉树的第2个节点（索引1）开始，依次向上调整（uph），由于完全二叉树的高度为 $\log n$，因此 $n$ 个节点逐步插入堆的耗时累计为 $\sum \log i = O(n \log n)$。
  • 排序调整阶段：依次将堆顶与未排序的最后一个元素交换，然后向下调整（downh）。每次向下调整的最大深度为当前二叉树的高度 $O(\log i)$，执行 $n-1$ 次，累加耗时同样为 $O(n \log n)$。
  • 两者相加，最坏时间复杂度为 $O(n \log n)$。

(5-1)#

• 日本語 (Japanese):
  • (あ): n / 2 - 1
  • (い): d
  • (う): n
  • (え): i 完成した28行目: for (i = n / 2 - 1; 0 <= i; i--) downh( d, n, i );
• 英語 (English):
  • (あ): n / 2 - 1
  • (い): d
  • (う): n
  • (え): i Completed line 28: for (i = n / 2 - 1; 0 <= i; i--) downh( d, n, i );
• 中文解析 (Chinese Analysis): 为了优化建堆效率，我们可以采用**自底向上（Bottom-up）**的建堆方法（即弗洛伊德建堆算法）。
  • 所有的叶子节点（下标为 $\lfloor n/2 \rfloor$ 到 $n-1$ 的节点）本身已经是可以看作合法的堆，因此不需要向下调整。
  • 我们只需要从最后一个非叶子节点（即下标为 $\lfloor n/2 \rfloor - 1$ 的节点）开始，自底向上对每个节点调用 downh 即可。
  • 结合 downh(int d[], int n, int k) 的参数定义：(い) 代表数组指针 d；(う) 代表堆大小 n；(え) 代表当前要调整的节点下标 i。

(5-2)#

• 日本語 (Japanese): 変更後の $T(n)$ の最悪計算量は $O(n)$ である。 理由: 要素数を $n$、二分木の高さを $h = \lfloor \log_2 n \rfloor$ とする。高さ $j$ にある節点の最大数は $\lceil n / 2^{j+1} \rceil$ 個であり、それらの節点に対して downh を適用する際の swap 回数（調整の深さ）は最大で $j$ 回である。 したがって、全 swap 回数 $T(n)$ は以下のように抑えられる： $T(n) \le \sum_{j=0}^{h} \frac{n}{2^{j+1}} \times j = \frac{n}{2} \sum_{j=0}^{h} \frac{j}{2^j}$ 与えられた和の公式 $\sum_{j=0}^{h} \frac{j}{2^j} = 2 - \frac{2+h}{2^h}$ を代入すると： $T(n) \le \frac{n}{2} \left( 2 - \frac{2+h}{2^h} \right) < \frac{n}{2} \times 2 = n$ これにより、$T(n) < n$ となり、その最悪時間計算量は $O(n)$ となる。
• 英語 (English): The worst-case time complexity of the modified $T(n)$ is $O(n)$. Reason: Let $n$ be the number of elements and $h = \lfloor \log_2 n \rfloor$ be the height of the tree. The maximum number of nodes at height $j$ (counting from the bottom leaves at height 0) is $\lceil n / 2^{j+1} \rceil$. For a node at height $j$, the maximum number of swaps during downh is $j$. Thus, the total number of swaps $T(n)$ is bounded by: $T(n) \le \sum_{j=0}^{h} \frac{n}{2^{j+1}} \times j = \frac{n}{2} \sum_{j=0}^{h} \frac{j}{2^j}$ Substituting the given summation formula $\sum_{j=0}^{h} \frac{j}{2^j} = 2 - \frac{2+h}{2^h}$, we get: $T(n) \le \frac{n}{2} \left( 2 - \frac{2+h}{2^h} \right) < n$ Therefore, $T(n) = O(n)$.
• 中文解析 (Chinese Analysis): 优化后的建堆过程，其最坏时间复杂度（即最大交换次数 $T(n)$）为 $O(n)$。 数学推导：
  • 设完全二叉树高度为 $h$。对于高度为 $j$（叶子节点高度为 0，根节点高度为 $h$）的节点，其向下调整所需要的最大交换次数为 $j$。
  • 在高度为 $j$ 的层，最多有 $\lceil n/2^{j+1} \rceil$ 个节点。
  • 累加每层节点向下调整的最大开销： $T(n) \le \sum_{j=0}^{h} \frac{n}{2^{j+1}} \cdot j = \frac{n}{2} \sum_{j=0}^{h} \frac{j}{2^j}$
  • 代入题目给定的求和公式 $\sum_{j=0}^{h} \frac{j}{2^j} = 2 - \frac{2+h}{2^h}$： $T(n) \le \frac{n}{2} \left( 2 - \frac{2+h}{2^h} \right) < \frac{n}{2} \cdot 2 = n$
  • 因为 $T(n)$ 被 $n$ 线性上界锁死，所以其时间复杂度为 $O(n)$。

(6)#

• 日本語 (Japanese):
  • (ア): child + 1 < n (変更なし)
  • (イ): d[child] > d[child + 1] (または d[child + 1] < d[child])
  • (ウ): d[current] > d[child]
  • (エ): d[parent] > d[current]
• 英語 (English):
  • (ア): child + 1 < n (Unchanged)
  • (イ): d[child] > d[child + 1] (or d[child + 1] < d[child])
  • (ウ): d[current] > d[child]
  • (エ): d[parent] > d[current]
• 中文解析 (Chinese Analysis): 要通过堆排序输出降序（Descending order）的序列，我们需要使用小顶堆（Min-heap）。 在小顶堆的维护过程中，父节点的值必须小于或等于左右子节点的值。因此：
  • (ア)：判定右子节点是否存在，这只与边界 $n$ 有关，故保持 child + 1 < n 变。
  • (イ)：在左右子节点中选择较小的那个，所以当右子节点的值比左子节点小时进行自增操作，条件改为 d[child] > d[child + 1]。
  • (ウ)：向下调整时，如果父节点的值大于较小儿子节点的值，则进行交换，条件改为 d[current] > d[child]。
  • (エ)：向上调整时，如果父节点的值大于当前子节点的值，则进行交换，条件改为 d[parent] > d[current]。

Description#

配点： (1-1) 10点, (1-2-1) 15点, (1-2-2) 15点, (1-2-3) 15点, (1-2-4) 10点, (2-1) 18点, (2-2) 20点, (2-3) 12点, (2-4) 10点

(1) 計算機 (computer) における数の表現に関する以下の各問に答えよ。#

(1-1) 以下の文章の空欄 (a) 〜 (e) に当てはまる最も適切な語句または数値を、下記の選択肢から選び、記号で答えよ。

数の表現形式として固定小数点 (fixed point number) 表現と浮動小数点 (floating point number) 表現がある。科学技術計算の分野では、 (a) 等の理由から (b) 表現多く用いられ、小型機器の制御等の分野では、 (c) 等の理由から (d) 表現が多く用いられる。いずれの表現形式においても、指数の底 (base of exponent) が 2 の場合、10 進数 (decimal number) の (e) を誤差 (error) 無く表現することはできない。 [選択肢] (ア) 固定小数点 (イ) 浮動小数点 (ウ) 演算回路 (arithmetic circuit) が簡素になる (エ) 表現できる数の範囲が広い (オ) 小数を誤差無く表現できる (カ) 0.5 (キ) 0.25 (ク) 0.1

(1-2) 以下の浮動小数点表現に関し、(1-2-1)〜(1-2-4) に答えよ。(1-2-1)〜(1-2-3) については導出過程も示すこと。

• 浮動小数点数 A を $A = (-1)^s \times 2^{e-7} \times (1 + m)$ と表し，符号部 $s$ (sign)，指数部 $e$ (exponent)，仮数部 $m$ (significand, mantissa) を最上位ビットから順にメモリに格納する．
• 符号部 $s$ は 1 ビットである．$s \in \{0,1\}$ をメモリに格納する．
• 指数部 $e$ は 4 ビットである．7 余り表現とし，$e$ を 4 ビットの符号無し 2 進整数 (unsigned binary integer) で表したビット列をメモリに格納する．$e = 0$ および $e = 15$ は $\pm\infty$ などの特殊な数を表現するのに用いる．
• 仮数部 $m$ は 9 ビットである．正規化 (normalization) し，整数部分の 1 は記録しない（隠しビット）．小数部分の $m$ を 2 進数の小数で表し，小数点以下の 9 ビットをメモリに格納する．丸め (rounding) 処理は切り捨て (rounding down) とする．非正規化 (denormalization) 表現は用いない．

(1-2-1) この表現形式で表すことのできる，正の最大値を 10 進数の小数で示せ．但し，無限大 (infinity) は除く．

(1-2-2) この表現形式で表すことのできる，正の最小値を 10 進数の小数で示せ．

(1-2-3) 10 進数 $-36.66$ をこの形式で表現し，そのビット列を示せ．

(1-2-4) 繰り返し計算を行う際，丸め処理として切り捨てを用いると，問題が生じる場合がある．どの様な問題か，理由も含めて示せ．

(2) 仮想記憶 (仮想メモリ; virtual memory) に関して以下の各小問に答えよ．#

(2-1) 次の説明文を読み，空欄 (a) 〜 (i) にあてはまる最も適切な語句を下の (ア) 〜 (ソ) の選択肢から選んで記号で答えよ．一つの選択肢を複数回用いてはならない． 仮想記憶は，主記憶 (primary storage, main memory) と補助記憶 (secondary storage, auxiliary memory) を用いて，主記憶の容量よりも大きい (a) を提供する．プロセスが指すアドレスは (b) と呼ばれる．プロセスの実行においてメモリアクセスのたびに，アドレス変換テーブル (mapping table) に基づいて (b) を (c) に変換する．一般的に，アドレス変換テーブルは (d) 上に構成する． アドレス変換を固定長 (fixed length) のブロック単位で行う方式を (e) と呼び，可変長 (variable length) のブロック単位で行う方式を (f) と呼ぶ．主記憶の利用効率 (memory efficiency) の観点からこれらの方式を比較すると， (e) 方式の利点は，主記憶領域の割り当てと解放を繰り返しても (g) がほとんど発生しない点である．一方，欠点は，固定長のページ単位で領域を割り付けるために (h) が発生しやすい点である． (h) は， (i) の大きさと比較して使用領域が小さいプロセスを実行する場合に顕著である． [選択肢] (ア) 主記憶 (イ) ページ (page) (ウ) 内部断片化 (internal fragmentation) (エ) スラッシング (thrashing) (オ) 実アドレス (real address) (カ) 仮想アドレス (virtual address) (キ) アドレス空間 (address space) (ク) 補助記憶 (ケ) メモリ階層 (memory hierarchy) (コ) ページング (paging) (サ) セグメント (segment) (シ) 外部断片化 (external fragmentation) (ス) ページフォールト (page fault) (セ) レジスタ (regsiter) (ソ) セグメンテーション (segmentation)

(2-2) プロセスが次に示すページ参照列 $S$ で処理を行う場合を想定する．ページ枠 (page frame) の数が 3 のページング方式を採用した場合に，ページフォールトが発生するページ参照に◯を記入せよ．ページ置換アルゴリズムに LRU (least recently used) および FIFO (first in first out) を用いる場合についてそれぞれ回答せよ．但し，初期状態では全てのページ枠は空である． ページ参照列 $S$: $0, 1, 2, 0, 3, 1, 4, 3, 2, 3, 1, 2, 4

(2-3) ページング方式を採用したシステムを想定する．このシステムでは，1回の主記憶へのアクセスに 2 [マイクロ秒] を要し，ページフォールトが発生するとそれに加えて 8 [ミリ秒] のオーバヘッド (overhead) が発生する．1命令あたり平均 2 回のメモリアクセスを行うとき，ページフォールトによる性能低下をページフォールトの無い状態と比較して平均 10% 以下に抑えるために，許容できるページフォールトの確率 $P$ の上限を求めよ．導出過程も示せ．なお，ページフォールトが発生しない場合のメモリアクセス時間は主記憶へのアクセス時間に等しく，演算時間および他のオーバヘッドは無視できるものとする．

(2-4) ページング方式を採用し，ページ置換アルゴリズムに LRU を用いたシステムにおいて，ページフォールトを削減する方法を具体的かつ簡潔に記述せよ．但し，実行する各プロセスのページ参照列は変更しないものとする．

Kai#

(1-1)#

• 解答: (a) エ, (b) イ, (c) ウ, (d) ア, (e) ク
• 中文解析:
  • 科学计算需要很大的数值表达范围，因此常用 (b) 浮动小数点（イ），对应原因是 (a) 表现范围广（エ）。
  • 嵌入式微型设备控制中，常用 (d) 固定小数点（ア），因为其不需要昂贵的浮点协处理器，对应原因 (c) 运算电路简单（ウ）。
  • 以 2 为底数的浮点数系统无法精确表示 (e) 0.1（ク），因为 0.1 在二进制中是一个无限循环小数 $0.0001100110011..._2$，在有限位宽存储时必然产生截断误差。

(1-2-1)#

• 解答: $255.75$
• 導出過程: 正の数であるため，符号部 $s = 0$ である． 無限大を除く正の最大値を得るためには，指数部 $e$ と仮数部 $m$ を最大にすればよい． $e = 0$ および $e = 15$ は特殊な数の表現として除外されるため，正規化数における $e$ の最大値は $14$ である． 仮数部 $m$ は 9 ビットであり，その最大値はすべてのビットが $1$ のときである： $m = \sum_{i=1}^{9} 2^{-i} = 1 - 2^{-9} = 1 - \frac{1}{512} = \frac{511}{512}$ したがって，正の最大値 $A_{\max}$ は： $A_{\max} = (-1)^0 \times 2^{14-7} \times \left(1 + \frac{511}{512}\right) = 2^7 \times \left(2 - 2^{-9}\right) = 256 - 2^{-2} = 256 - 0.25 = 255.75$
• 中文解析: 符号位 $s=0$。指数部除去保留值 0 和 15，最大正规化指数 $e=14$。 尾数部 $m$ 在 9 位全 1 时取得最大值 $1 - 2^{-9} = \frac{511}{512}$。 代入公式：$A_{\max} = 2^{14-7} \times (1 + \frac{511}{512}) = 128 \times \frac{1023}{512} = \frac{1023}{4} = 255.75$。

(1-2-2)#

• 解答: $0.015625$
• 導出過程: 正の数であるため，符号部 $s = 0$ である． 正の最小値（正規化数）を得るためには，指数部 $e$ と仮数部 $m$ を最小にすればよい． 非正規化数（denormalization）は用いないため，最小の指数部 $e = 1$ である． 仮数部 $m$ の最小値はすべてのビットが $0$ のときであり，$m = 0$ である． したがって，正の最小の正規化数 $A_{\min}$ は： $A_{\min} = (-1)^0 \times 2^{1-7} \times (1 + 0) = 2^{-6} = \frac{1}{64} = 0.015625$
• 中文解析: 正的最小正规化数在 $e=1$ 且 $m=0$ 时取得。 代入公式：$A_{\min} = 2^{1-7} \times (1 + 0) = 2^{-6} = \frac{1}{64} = 0.015625$。

(1-2-3)#

• 解答: 11100001001010 (または 1 1100 001001010)
• 導出過程: 値が負数であるため，符号部 $s = 1$ である． 次に，絶対値 $36.66$ の指数部 $e$ を求める． $32 \le 36.66 < 64$ であるため，$2^5 \le 36.66 < 2^6$ となり，指数部分は $2^5$ すなわち $e - 7 = 5$ となる． よって，$e = 12$ であり，これを 4 ビットの 2 進数で表すと 1100 となる． 仮数部 $m$ は次のように求められる： $1 + m = \frac{36.66}{2^5} = \frac{36.66}{32} = 1.145625 \implies m = 0.145625$ $m = 0.145625$ を 2 進数の小数に展開し，切り捨てを適用して小数点以下 9 ビットを抽出する：
  • $0.145625 \times 2 = 0.29125 \to 0$
  • $0.29125 \times 2 = 0.5825 \to 0$
  • $0.5825 \times 2 = 1.165 \to 1$
  • $0.165 \times 2 = 0.33 \to 0$
  • $0.33 \times 2 = 0.66 \to 0$
  • $0.66 \times 2 = 1.32 \to 1$
  • $0.32 \times 2 = 0.64 \to 0$
  • $0.64 \times 2 = 1.28 \to 1$
  • $0.28 \times 2 = 0.56 \to 0$
  • (以降は切り捨て) これより，仮数部 $m$ の 9 ビット列は 001001010 となる． 以上を統合すると，ビット列は 1 (符号部) + 1100 (指数部) + 001001010 (仮数部) = 11100001001010 となる．
• 中文解析:
  • 负数，所以符号位 $s=1$。
  • $36.66$ 处于区间 $[32, 64)$，因此对应阶数为 $2^5$。由 $e - 7 = 5$ 得到 $e = 12$，二进制位为 1100。
  • 尾数部分 $1 + m = 36.66 / 32 = 1.145625 \implies m = 0.145625$。
  • 通过乘2取整法将 $0.145625$ 转换为9位二进制小数。由于舍入规则是“切り捨て”（截断/向下舍入），直接取前 9 位得 001001010。
  • 最终拼接得：11100001001010。

(1-2-4)#

• 日本語 (Japanese): 丸め処理に切り捨てを使用すると、発生する誤差が常に同一方向（絶対値を減少させる方向）に蓄積するため、繰り返し計算によって「累積誤差」が一方通行に増大し、最終的な計算精度が著しく低下する。また、大小の差が極端に大きい数値同士の加算において、小さい方の有効桁数が全て切り捨てられて加算結果に反映されない「情報落ち」が発生する。
• 英語 (English): When truncation (rounding down) is used, the rounding errors occur consistently in the same direction (underestimating the absolute values). During iterative calculations, these errors accumulate unidirectionally, leading to significant cumulative errors. Additionally, when adding values of vastly different magnitudes, the significant bits of the smaller value may be shifted out completely and discarded, resulting in a “loss of significance” where the addition of the smaller value has no effect.
• 中文解析 (Chinese Analysis): 主要存在两个问题：
  1. 累计误差（Error Accumulation）：截断舍入每次都向绝对值缩小的方向舍入，舍入误差是同向的。在成千上万次迭代后，误差单向累加，导致严重的数值漂移。
  2. 信息流失（Loss of Significance / Absorption）：在大小悬殊的数相加时，较小数对齐阶数后其有效位全部溢出假数部被截断，使得加法等于没加，数值信息丢失。

(2-1)#

• 解答: (a) キ, (b) カ, (c) オ, (d) ア, (e) コ, (f) ソ, (g) シ, (h) ウ, (i) イ
• 中文解析:
  • 虚拟内存提供比物理主存空间更大的 (a) アドレス空間（キ）。
  • 进程产生的是 (b) 仮想アドレス（カ），每次访问都要转换成 (c) 実アドレス（オ）。
  • 页表一般配置在 (d) 主記憶（ア）上。
  • 固定长度划分为 (e) ページング（コ），可变长度为 (f) セグメンテーション（ソ）。
  • 页面分配机制的优点是没有 (g) 外部断片化（シ），但是有 (h) 内部断片化（ウ）。
  • 当分配的 (i) ページ（イ）尺寸远大于进程需要的实际空间时，内部碎片化最明显。

(2-2)#

• 解答:
  • LRU:

    参照	0	1	2	0	3	1	4	3	2	3	1	2	4
    LRU	◯	◯	◯		◯	◯	◯		◯		◯		◯

  • FIFO:

    参照	0	1	2	0	3	1	4	3	2	3	1	2	4
    FIFO	◯	◯	◯		◯		◯				◯	◯

• 中文解析:
  • 缺页标记为 ◯。
  • LRU 缺页 9 次，第4项、第8项、第10项、第12项命中了缓冲，其余换入。
  • FIFO 缺页 7 次，在命中后队列顺序不发生更新。

(2-3)#

• 解答: $P \le 2.5 \times 10^{-5}$ (または $2.5 \times 10^{-3} \%$ 以下)
• 導出過程: 主記憶への 1 回のアクセス時間を $T_m = 2 \ \mu\text{s}$ とする． ページフォールトのオーバヘッドを $T_{pf} = 8 \ \text{ms} = 8000 \ \mu\text{s}$ とする． ページフォールトの発生確率を $P$ としたとき，実効メモリアクセス時間 $T_{eff}$ は以下のように表される： $T_{eff} = (1 - P) T_m + P (T_m + T_{pf}) = T_m + P \cdot T_{pf}$ 1命令あたり平均 2 回のメモリアクセスを行うため，1命令の実効アクセス時間は $2 T_{eff}$，ページフォールトが無い状態のアクセス時間は $2 T_m$ である． 性能低下を 10% 以下に抑える条件は： $\frac{2 T_{eff} - 2 T_m}{2 T_m} \le 0.1 \implies \frac{T_{eff} - T_m}{T_m} \le 0.1$ $\frac{P \cdot T_{pf}}{T_m} \le 0.1 \implies P \le 0.1 \times \frac{T_m}{T_{pf}}$ 数値を代入すると： $P \le 0.1 \times \frac{2 \ \mu\text{s}}{8000 \ \mu\text{s}} = \frac{0.2}{8000} = 0.000025 = 2.5 \times 10^{-5}$ したがって，許容できるページフォールトの確率 $P$ の上限は $2.5 \times 10^{-5}$ である． (注: もし確率 $P$ が「1命令あたり」に発生する確率と解釈される場合，上限は $P_{inst} = 2 P = 5.0 \times 10^{-5}$ となる)
• 中文解析:
  • 正常主存访问时间 $T_m = 2\ \mu\text{s}$。缺页开销为 $T_{pf} = 8000\ \mu\text{s}$。
  • 包含缺页概率 $P$ 的等效单次访存时间为 $T_{eff} = T_m + P \times T_{pf}$。
  • 性能下降率可以通过单次访存时间的相对增加值来计算（因为每条指令的平均访存次数 2 可以约掉）： $\text{性能降低} = \frac{P \times T_{pf}}{T_m} \le 10\%$
  • 代入数字：$P \times 8000 / 2 \le 0.1 \implies P \le 2.5 \times 10^{-5}$。
  • 这意味着缺页率必须控制在 $0.0025\%$ 以内。

(2-4)#

• 日本語 (Japanese):
  1. プロセスに割り当てるページ枠数を増やす。LRU はスタックアルゴリズムの特性（包含特性）を満たすため、ページ枠数を増やすことで缺页率を確実に低減（または維持）できる。
  2. ページサイズを拡張する。空間的局所性を生かして、参照ページ数を減少させることができる。
  3. ページバッファリング（Page Buffering）を導入し、置換対象となったページを即時に破棄せずフリーリストに保持しておくことで、再参照時の物理ディスクアクセスを回避する。
• 英語 (English):
  1. Increase the number of page frames allocated to the process. Since LRU is a stack algorithm, increasing the number of allocated frames is mathematically guaranteed to decrease (or keep constant) the page fault frequency.
  2. Increase the page size to leverage spatial locality, which reduces the total number of unique page faults during execution.
  3. Employ page buffering, keeping replaced pages in a pool of free frames temporarily so they can be immediately reclaimed without disk I/O if accessed again shortly.
• 中文解析 (Chinese Analysis): 在页面访问序列不变的前提下，降低 LRU 缺页中断的方法有：
  1. 增加分配给进程的物理页框数：LRU 属于栈式算法（满足包含性质，不发生贝雷迪异常），因此多给页框一定会减少或维持缺页数。
  2. 增大页面尺寸：利用空间局部性（Spatial Locality），单次换入载入更多邻近数据，减少页面总数。
  3. 页面缓冲机制（Page Buffering）：被淘汰的页面不立即清空，而是挂在空闲页面链表尾部，若短期内再次被访问则可以直接回收，免去昂贵的磁盘I/O。

Description#

配点： (1-1) 15点, (1-2-1) 10点, (1-2-2) 25点, (1-3) 10点, (2-1) 40点, (2-2) 25点

(1) アルファベット (alphabet) $\Sigma_{ab} = \{a, b\}$ で構成される言語 $L_{ab} = \{a^n b^n \mid n \text{ is a positive integer} \}$ を考える．なお，$a^n$ は $a$ が $n$ 個連結した文字列 (string) を表す．例えば，$a^3 = aaa$ である．また，$\varepsilon$ は空文字列 (empty string) を表す．言語 $L_{ab}$ を認識（受理）するオートマトン (automaton) に関する以下の各問に答えよ．#

(1-1) プッシュダウンオートマトン (pushdown automaton) は $(Q, \Sigma, \Gamma, \delta, q_0, Z, F)$ で表される．$Q$ は状態 (state) の有限集合，$\Sigma$ は入力アルファベット (input alphabet)，$\Gamma$ はスタックアルファベット (stack alphabet)，$\delta$ は遷移関数 (transition function)，$q_0$ は開始状態 (start state)，$Z$ はスタックの開始記号，$F$ は最終状態 (final state) の集合である．最終状態による受理 (acceptance by final state) を行うプッシュダウンオートマトンを利用して，言語 $L_{ab}$ を認識することを考える．

下図は言語 $L_{ab}$ を認識する非決定性 (non-deterministic) プッシュダウンオートマトンの状態遷移図 (state transition diagram) であり，開始状態は $q_0$，最終状態は $q_2$ である．状態遷移図の空欄 [(A)], [(B)], [(C)] に必要な動作を，$(r, s) / t$ の形式で答えよ．ただし，$(r, s) / t$ ($r \in \Sigma \cup \{\varepsilon\}, s \in \Gamma, t \in \Gamma^*$) は，入力から読み出す記号が $r$ でスタックから取り出す記号が $s$ のときに，スタックからその $s$ を取り去り，$t$ をスタックに押し込むことを意味する．$t$ が複数の記号の場合は右側の記号から順にスタックに押し込む．$(a, Z) / 0Z$ は，$a$ を読み出すときにスタックから $Z$ を取り去り，スタックに $Z$ と $0$ をこの順で押し込むことを意味する．$t$ が $\varepsilon$ の場合は，スタックに記号を押し込まない．$r$ が $\varepsilon$ の場合は，入力から記号を読み出さないで遷移を行う．入力アルファベットは $\Sigma = \Sigma_{ab}$，スタックアルファベットは $\Gamma = \{Z, 0\}$ とする．

1
           (a, Z) / 0Z
2
            +-----+
3
            | (A) |
4
            |     v
5
        +---- q0 ----+     (e, Z) / e
6
--->    |            | --------------> (( q2 ))
7
        +------------+
8
           |     ^
9
           | (B) |
10
           |     |
11
           v     |
12
        +---- q1 ----+
13
        |            |
14
        +------------+
15
            | (C) |
16
            +-----+

(1-2) 決定性有限オートマトン (deterministic finite automaton) は $(Q, \Sigma, \delta, q_0, F)$ で表される．$Q$ は状態の有限集合，$\Sigma$ は入力アルファベット，$\delta$ は遷移関数，$q_0$ は開始状態，$F$ は最終状態の集合である．入力アルファベットは $\Sigma = \Sigma_{ab}$ とする．このとき，(1-2-1) および (1-2-2) に答えよ．

(1-2-1) 言語 $L_2 = \{ a^n b^n \mid n = 2 \}$ を認識する決定性有限オートマトン，および，言語 $L_3 = \{ a^n b^n \mid n = 3 \}$ を認識する決定性有限オートマトンの状態遷移図をそれぞれ書け．なお，上図に示すように開始状態には太い矢印 (thick arrow) を付与し，最終状態は二重丸 (double circle) で表現すること．また，全ての状態において，全ての入力記号に対する遷移を表記すること．

(1-2-2) 言語 $L_{ab}$ を認識する決定性有限オートマトンは存在しないことを背理法 (proof by contradiction) により証明したい．以下の空欄 (D) に適切な文章を記述し，証明を完成させよ．

証明: 言語 $L_{ab}$ を認識する決定性有限オートマトンが存在すると仮定し，そのオートマトンの状態数を $k$ とする．文字列 $a^k b^k$ が与えられたとき，$a$ を $i$ 個 ($0 \le i \le k$) 読み終えた時点での状態を $p_i$ とすると，

1
                            (D)

よって仮定と矛盾するため，言語 $L_{ab}$ を認識する決定性有限オートマトンは存在しない． (証明終)

(1-3) 言語 $L_{ab}$ を認識する決定性有限オートマトンは存在しないが，言語 $L'_{ab} = \{ a^n b^m \mid n \text{ and } m \text{ are positive integers} \}$ を認識する決定性有限オートマトンは存在する．言語 $L'_{ab}$ を認識する決定性有限オートマトンの状態遷移図を書け．なお，上図に示すように開始状態には太い矢印を付与し，最終状態は二重丸で表現すること．また，すべての状態において，すべての入力記号に対する遷移を表記すること．

(2) 文脈自由文法 (context-free grammar) は，変数 (variable) の有限集合 $V$，終端記号 (terminal symbol) の有限集合 $T$，生成規則 (production rule) の有限集合 $P$，および開始記号 (start symbol) $S$ の組により定められる．変数は非終端記号 (nonterminal symbol) と呼ぶこともある．Chomsky 標準形 (Chomsky normal form) とは，文脈自由文法のうち，生成規則が，(i) $X \to YZ$, (ii) $X \to a$ のいずれかの形をしたものである．ただし，$X, Y, Z$ は変数，$a$ は終端記号である．#

ここで，Chomsky 標準形で与えられる文脈自由文法 $G = (V, T, P, S)$ および文字列 $w = a_1 a_2 \dots a_n$ （ただし，各 $a_i$ は $T$ に属する）に対し，$w$ が $G$ によって生成されるか否かを，動的計画法 (dynamic programming) によって効率的に判定するアルゴリズムを考える．まず，整数 $i, j$ のうち $1 \le i \le j \le n$ であるものに対し，集合 $M[i, j] = \{ X \in V \mid \text{文法 } G \text{ において，} w \text{ の連続した部分文字列 } a_i a_{i+1} \dots a_j \text{ を変数 } X \text{ から導出できる} \}$ を定める．以下に擬似コードで示したアルゴリズムでは各 $M[i, j]$ を $M[1, 1], M[2, 2], \dots, M[n, n], M[1, 2], M[2, 3], \dots, M[n-1, n], M[1, 3], \dots$ の順に $M[1, n]$ まで計算している．最後の判定では，$w$ が $G$ によって生成されるとき，かつそのときに限り $S \in M[1, n]$ という性質を利用している．

1
入力 w = a_1 a_2 ... a_n に対し，集合 M[i, j] (1 <= i <= j <= n) の初期値をすべて空集合 Ø とする．
2
for i = 1 to n do             // 部分文字列の長さが 1 の場合の計算
3
    (X -> a_i) in P であるすべての X in V を M[i, i] に追加．
4
end for
5
for l = 2 to n do             // 他のすべての M[i, j] の計算．l は部分文字列の長さを表す．
6
    for i = 1 to n - l + 1 do // i は部分文字列の先頭位置を表す．
7
        j = i + l - 1 とする． // j は部分文字列の終了位置を表す．
8
        for k = i to j - 1 do // k は部分文字列の分割位置の一つ前を表す．
9
            ある Y in M[i, k], Z in M[k+1, j] に対し，(X -> YZ) in P であるすべての X in V を M[i, j] に追加．
10
        end for
11
    end for
12
end for
13
S in M[1, n] であれば Yes を，そうでなければ No を出力して終了． // 判定

文脈自由文法 $G_1 = (V_1, T_1, P_1, S_1)$ を，$V_1 = \{A, B, C, D, S\}, T_1 = \{a, b\}, S_1 = S,$ $P_1 = \{ S \to AB, A \to CA, A \to AA, A \to a, B \to DB, B \to b, C \to a, D \to b \}$ と定める．例えば，文法 $G_1$ と文字列 $bab$ に対し，上記のアルゴリズム実行した場合の計算は以下のように行われる．

• まず，$M[1, 1], M[2, 2], M[3, 3]$ が決まる．
• 次に，部分文字列の長さが $l = 2$ の場合，先頭位置は $i = 1, 2$ の二つの場合があり，
  • $i = 1$ ならば $j = 2$ であり，$k = 1$ として，$Y \in M[1, 1], Z \in M[2, 2]$ を調べることで $M[1, 2]$ が決まる．
  • $i = 2$ ならば $j = 3$ であり，$k = 2$ として，$Y \in M[2, 2], Z \in M[3, 3]$ を調べることで $M[2, 3]$ が決まる．
• 最後に，部分文字列の長さが $l = 3$ の場合，先頭位置は $i = 1$ の場合だけであり，
  • $i = 1$ ならば $j = 3$ である．このとき，$k = 1$ として，$Y \in M[1, 1], Z \in M[2, 3]$ を調べ， $k = 2$ として，$Y \in M[1, 2], Z \in M[3, 3]$ を調べることで，$M[1, 3]$ が決まる．

終了時における $M[i, j]$ の内容は以下の表のとおりである．この場合，$S \notin M[1, 3]$ であるため No が出力される．

以下の各小問に答えよ．

(2-1) 文法 $G_1$ および文字列 $w_1 = aaab$ に対し，上記のアルゴリズムを実行した場合，終了時における $M[i, j]$ の内容を，上記の例のように，表として示せ．

(2-2) 文脈自由文法 $G_2 = (V_2, T_2, P_2, S_2), V_2 = \{A, B, S\}, T_2 = \{a, b\}, S_2 = S,$ $P_2 = \{ S \to AB, S \to SA, S \to BS, S \to \varepsilon, A \to a, B \to b \}$ を考える．ここで，$\varepsilon$ は空文字列 (empty string) である．文法 $G_2$ は，上で説明した Chomsky 標準形の制約を満たしていないため，上記のアルゴリズムに対して正しく動作しない場合がある．つまり，ある入力文字列に対しては間違った判定をする．その様な入力文字列として長さ 2 以上のものを具体的に示し，正しく動作しないことを説明せよ．

Kai#

(1-1)#

• 解答:
  • [(A)]: (a, 0) / 00
  • [(B)]: (b, 0) / \varepsilon
  • [(C)]: (b, 0) / \varepsilon
• 中文解析: 这是一个利用栈匹配 $a^n b^n$ 的下推自动机（PDA）。
  • 状态 $q_0$ 负责读取字符 $a$。若栈顶为底座 $Z$，读入第一个 $a$ 后将 0 压入，变为 $0Z$。如果是后续的 $a$，此时栈顶为 $0$，应继续向栈中压入一个 $0$。因此 $q_0$ 的自环 [(A)] 应为 (a, 0) / 00。
  • 读到第一个 $b$ 时，跳转到状态 $q_1$，同时必须消耗一个栈中的 $0$（代表一次匹配）。因此 [(B)] 应为 (b, 0) / \varepsilon。
  • 状态 $q_1$ 负责读取后续的 $b$，每读入一个 $b$ 必须消耗栈顶的一个 $0$。因此 $q_1$ 的自环 [(C)] 也是 (b, 0) / \varepsilon。
  • 最终栈为空（只剩底座 $Z$）且输入读取完毕时，通过 (\varepsilon, Z) / \varepsilon 迁移至接受状态 $q_2$。

(1-2-1)#

• 解答:
  • DFA for $L_2 = \{aabb\}$: 状态集合 $Q = \{q_0, q_1, q_2, q_3, q_4, q_{dead}\}$，其中 $q_0$ 为开始状态，$q_4$ 为最终（接受）状态，$q_{dead}$ 为死状态。

1
stateDiagram-v2
2
    [*] --> q0
3
    q0 --> q1 : a
4
    q0 --> q_dead : b
5
    q1 --> q2 : a
6
    q1 --> q_dead : b
7
    q2 --> q3 : b
8
    q2 --> q_dead : a
9
    q3 --> q4 : b
10
    q3 --> q_dead : a
11
    q4 --> q_dead : a, b
12
    q_dead --> q_dead : a, b
13
    classDef accept fill:#f9f,stroke:#333,stroke-width:2px;
14
    class q4 accept;

1
- **DFA for $L_3 = \{aaabbb\}$**:
2
  状态集合 $Q = \{q_0, q_1, q_2, q_3, q_4, q_5, q_6, q_{dead}\}$，其中 $q_0$ 为开始状态，$q_6$ 为最终状态。

1
stateDiagram-v2
2
    [*] --> q0
3
    q0 --> q1 : a
4
    q0 --> q_dead : b
5
    q1 --> q2 : a
6
    q1 --> q_dead : b
7
    q2 --> q3 : a
8
    q2 --> q_dead : b
9
    q3 --> q4 : b
10
    q3 --> q_dead : a
11
    q4 --> q5 : b
12
    q4 --> q_dead : a
13
    q5 --> q6 : b
14
    q5 --> q_dead : a
15
    q6 --> q_dead : a, b
16
    q_dead --> q_dead : a, b
17
    classDef accept fill:#f9f,stroke:#333,stroke-width:2px;
18
    class q6 accept;

• 中文解析: 由于 $L_2$ 和 $L_3$ 是有限语言，DFA 只需要依次严格匹配特定长度的 $a$ 和 $b$。因为题目要求**“在所有状态中，必须标明对所有输入符号的迁移”**，所以必须显式引入死状态 $q_{dead}$。任何不合规的输入都会直接掉入死状态，且无法逃离。

(1-2-2)#

• 解答 (Dに入力する文章):
  • 日本語 (Japanese): 鳩の巣原理（Pigeonhole Principle）より，$p_g = p_h$ となるような異なる二つの整数 $g, h$ ($0 \le g < h \le k$) が存在する． ここで，文字列 $a^g b^g$ と $a^h b^g$ に対するオートマトンの遷移を考える． $a^g b^g \in L_{ab}$ であるため，初期状態から $a^g b^g$ を読み終えた時点での状態は最終状態（受け入れ状態）である． 一方，初期状態から $a^h$ を読み終えた状態は $p_h = p_g$ となる．ここからさらに残り部分の $b^g$ を読み終えたときの状態は，$a^g$ の後に $b^g$ を読み終えたときの状態と同一になり，これも最終状態となる． これは，このオートマトンが $a^h b^g$ を受け入れることを意味するが，$g \neq h$ より $a^h b^g \notin L_{ab}$ であるため，このオートマトンが $L_{ab}$ を認識するという仮定に矛盾する．
• 英語 (English): By the Pigeonhole Principle, since there are $k+1$ states in the sequence $p_0, p_1, \dots, p_k$ and the DFA has only $k$ states, there must exist two distinct integers $g$ and $h$ ($0 \le g < h \le k$) such that $p_g = p_h$. Now, consider the transitions of the automaton for the strings $a^g b^g$ and $a^h b^g$. Since $a^g b^g \in L_{ab}$, the state reached after reading $a^g b^g$ from the initial state must be an accepting state. On the other hand, the state reached after reading $a^h$ from the initial state is $p_h = p_g$. Thus, starting from $p_h$ and reading the remaining $b^g$ must lead to the exact same accepting state. This implies that the automaton accepts $a^h b^g$. However, since $g \neq h$, $a^h b^g \notin L_{ab}$, which contradicts the assumption that the automaton recognizes $L_{ab}$.
• 中文解析: 本题是正则语言不可判定性的经典证明（利用鸽巢原理证明，本质上也是泵引理的内核）。
  • 输入 $a^k$ 在读入每个字符时会经历 $k+1$ 个状态。而有限自动机状态数仅为 $k$，所以在前 $k$ 步中必定有两个不同的步数 $g, h$ 停留在了相同的状态 $p_g = p_h$。
  • 一旦在此处发生状态重合，由于自动机是决定性的（DFA），当后面拼上相同的后缀 $b^g$ 时，它们所抵达的最终状态也必定完全相同。
  • 由于 $a^g b^g \in L_{ab}$ 是合法串，最终状态必为接受状态，这导致 $a^h b^g$ 也会被误接受，然而 $h \neq g$，该串在数量上并不相等，不属于语言，因而产生矛盾。

(1-3)#

• 解答: 言語 $L'_{ab} = \{a^n b^m \mid n, m \ge 1\}$ は正規表現 $a a^* b b^*$ で表される正規言語である．これを認識する DFA は以下のようになる．

1
stateDiagram-v2
2
    [*] --> q0
3
    q0 --> q1 : a
4
    q0 --> q_dead : b
5
    q1 --> q1 : a
6
    q1 --> q2 : b
7
    q2 --> q2 : b
8
    q2 --> q_dead : a
9
    q_dead --> q_dead : a, b
10
    classDef accept fill:#f9f,stroke:#333,stroke-width:2px;
11
    class q2 accept;

• 中文解析: 与 $L_{ab}$ 不同，$L'_{ab}$ 只要求 $a$ 和 $b$ 至少各出现一次且 $a$ 必须在 $b$ 之前，并不要求两者的数量相等。因此它不需要无限的记忆能力，是正则语言。可以使用 4 个状态的 DFA（包含死状态）来表示。

(2-1)#

• 解答: 終了時における $M[i, j]$ の内容は以下の表の通りである．$S \in M[1, 4]$ であるため，判定結果は Yes となる．

• 中文解析:
  • $\ell=1$ 时，$w_1 = aaab$ 对应的单个字符分别为 $a, a, a, b$。由于 $A \to a, C \to a$，故 $M[1, 1] = M[2, 2] = M[3, 3] = \{A, C\}$。同理 $B \to b, D \to b$，故 $M[4, 4] = \{B, D\}$。
  • $\ell=2$ 时，计算相邻两两组合。例如对于 $aa$，利用 $M[i, i]$ 和 $M[i+1, i+1]$ 交叉组合，规则 $A \to AA, A \to CA$ 将其规约为 $A$。故 $M[1, 2] = M[2, 3] = \{A\}$。而对于末尾的 $ab$，通过 $M[3, 3] = \{A, C\}$ 和 $M[4, 4] = \{B, D\}$ 交叉，由于 $S \to AB$，规约为 $S$。故 $M[3, 4] = \{S\}$。
  • 依次类推完成动态规划填表，最后右上角的 $M[1, 4]$ 包含开始符号 $S$，表明该字符串可以被文法生成。

(2-2)#

• 日本語 (Japanese): 正しく動作しない長さ 2 以上の入力文字列の具体例として $aa$ （または $bb$, $ba$）が挙げられる． 文法 $G_2$ において，これらの文字列は $S \Rightarrow SA \Rightarrow SAA \Rightarrow \varepsilon AA \Rightarrow aa$ という導出が可能であるため，言語 $L(G_2)$ に属する．したがって，正しい判定結果は Yes である． しかし，提示されたアルゴリズムを実行した場合： 初期化フェーズで $M[1, 1] = \{A\}$，$M[2, 2] = \{A\}$ となる． 長さ 2 の計算において，アルゴリズムは $Y \in M[1, 1]$, $Z \in M[2, 2]$ から $X \to YZ$（すなわち $X \to AA$）の形式の生成規則を探索する．しかし，文法 $G_2$ の生成規則には右辺が $AA$ である規則が存在しないため，$M[1, 2] = \emptyset$ のままとなる． 最終的に $S \notin M[1, 2]$ となり，アルゴリズムは誤って No を出力する． この問題が発生する理由は，提示されたアルゴリズムが $\varepsilon$（空列）を生成する規則（$\varepsilon$-プロダクション）を考慮しておらず，導出の過程で変数が消去される（空列になる）ケースを追跡できないためである．
• 英語 (English): A concrete example of a string of length 2 or more for which the algorithm fails is $aa$ (or $bb$, $ba$). In the grammar $G_2$, this string can be derived as $S \Rightarrow SA \Rightarrow SAA \Rightarrow \varepsilon AA \Rightarrow aa$, meaning it belongs to the language $L(G_2)$, and the correct output should be Yes. However, running the specified algorithm: In the initialization phase, we get $M[1, 1] = \{A\}$ and $M[2, 2] = \{A\}$. During the computation for length 2, the algorithm searches for production rules of the form $X \to YZ$ where $Y \in M[1, 1]$ and $Z \in M[2, 2]$ (i.e., $X \to AA$). Since there are no production rules in $G_2$ with $AA$ on the right-hand side, $M[1, 2]$ remains $\emptyset$. Consequently, $S \notin M[1, 2]$, and the algorithm incorrectly outputs No. The reason for this failure is that the algorithm does not account for $\varepsilon$-productions (rules deriving the empty string). Thus, it cannot trace derivations where a variable is erased (becomes $\varepsilon$) during the derivation process.
• 中文解析 (Chinese Analysis):
  • 反例：字符串 $aa$（或者 $bb$, $ba$ 等）。
  • 逻辑漏洞说明：在文法 $G_2$ 中，由于含有 $S \to \varepsilon$ 规则，我们可以通过消去 $S$ 来实现 $S \Rightarrow SA \Rightarrow SAA \Rightarrow \varepsilon AA \Rightarrow aa$，因此 $aa$ 是一个合法句子。
  • 然而，CYK 算法要求文法严格处于乔姆斯基范式中（即右侧只能是两个非终结符 $YZ$ 或一个终结符 $a$）。在计算 $M[1, 2]$ 时，算法只寻找形如 $X \to AA$ 的产生式。由于 $P_2$ 中没有右侧为 $AA$ 的规则，计算出的 $M[1, 2]$ 为空集，最终输出 No，发生了误判。
  • 其本质原因在于：CYK 算法的动态规划分治策略强行假定每次切分成的两部分都至少产生长度为1的字串，它无法追踪和处理推导中途某一部分坍缩为 $\varepsilon$（空串）的消去路径。