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

Description#

配点： (1) 20点, (2) 35点, (3) 15点, (4-1) 15点, (4-2) 15点, (5) 25点

図1に示す ANSI-C 準拠である C 言語のプログラム (program) は、所有している複数のくじ (lottery) のそれぞれが当選 (win) しているかを調べて、当選しているくじ番号 (lottery number) と等級 (grade) をもれなく出力 (output) するものである。くじ番号は 10000 未満の自然数 (natural number) で定められており、いずれのくじ番号のくじもただか一つしか存在しない。所有しているくじ番号が、当選番号 (winning number) と一致した場合に、その当選番号に対応する等級に当選したとする。当選番号は 10000 未満の自然数から重複なく選ばれた $N$ 個 ($N$ は $3 \le N \le 100$ の自然数) の数字で、等級は 1等から 3等まであり、1等が1本、2等が1本、3等が $N-2$ 本である。

当選番号と等級は図2に示すような形式 (format) のファイル win.txt で与えられ、1行目には当選番号の総数 $N$、2行目以降の $N$ 行は全ての当選番号とその等級 $r$ ($r$ は $1 \le r \le 3$ の自然数) が書かれている。また、所有しているくじ番号は図3に示すような形式のファイル lots.txt で与えられ、所有しているくじ番号が 1行目から各行に一つずつ書かれている。以下の各問に答えよ。

1
void functionA(int a[], int b[], int t, int w){
2
    if(t<w){
3
        int i, j, x, tmp;
4
        i=t; j=w;
5
        x=a[t];
6

7
        while(1){
8
            while(a[i]<x) i++;
9
            while(a[j]>x) j--;
10
            if(i>=j) break;
11
            tmp=a[i]; a[i]=a[j]; a[j]=tmp;
12
            tmp=b[i]; b[i]=b[j]; b[j]=tmp;
13
            i++; j--;
14
        }
15
        functionA(a, b, [ (あ) ], [ (い) ]);
16
        functionA(a, b, [ (う) ], [ (え) ]);
17
    }
18
}

Kai#

(1)#

• 日本語 (Japanese): a[j] > a[j+1]
• 英語 (English): a[j] > a[j+1]
• 中文解析 (Chinese Analysis): 该程序通过 functionA 实现冒泡排序，对中奖号码数组 a 进行升序排列。在每一轮的相邻元素比较中，若前一个元素 a[j] 大于后一个元素 a[j+1]，则需要将它们交换。因此，空栏 (A) 应填入 a[j] > a[j+1]。 从表格中可以看出，在 $i=1$ 结束后，数组中的最大元素 9003 已经冒泡到了末尾的 a[9]；在 $i=3$ 结束后，最大三个元素 7888, 8698, 9003 均已在数组的最右端排好序，这符合冒泡排序的执行结果。

(2)#

• 日本語 (Japanese): 配列 win の要素は昇順（小さい順）に整列され、配列 grade の要素は win の並び替えと同期して入れ替えられる。 平均時間計算量は $O(n^2)$ である。 理由: 外側のループは $n-1$ 回実行され、各ステップ $i$ において内側のループは $t$ から $w-i$ まで実行される。したがって、比較の総数は $\sum_{i=1}^{n-1} (n - i) = \frac{n(n-1)}{2}$ 回となる。平均してこの比較の半数でスワップ（入れ替え）が発生するため、比較回数・スワップ回数ともに平均時間計算量は $O(n^2)$ となる。
• 英語 (English): The elements of the array win are sorted in ascending order, while the elements of the array grade are swapped in tandem to remain synchronized with their corresponding elements in win. The average-case time complexity is $O(n^2)$. Reason: The outer loop runs $n-1$ times, and for each iteration $i$, the inner loop runs from $t$ to $w-i$. Thus, the total number of comparisons is $\sum_{i=1}^{n-1} (n - i) = \frac{n(n-1)}{2}$. In the average case, swaps occur for approximately half of these comparisons. Since both the comparisons and swaps scale with $n^2$, the complexity is $O(n^2)$.
• 中文解析 (Chinese Analysis):
  • 数组变化：数组 win 的元素会被按升序（从小到大）进行排列。与此同时，数组 grade 中的等级元素会与 win 数组同步进行位置交换，以维持原有的“中奖号码-中奖等级”的一一对应关系。
  • 时间复杂度：平均时间复杂度为 $O(n^2)$。
  • 原因：这是因为外层循环共执行 $n-1$ 次，而在第 $i$ 次循环中，内层循环会执行相邻元素比较共 $n-i$ 次。因此，总的比较次数为定值 $\sum_{i=1}^{n-1} (n-i) = \frac{n(n-1)}{2}$。在输入乱序的平均情况下，大约有半数比较会伴随元素交换，因此总操作次数与 $n^2$ 成正比，即为 $O(n^2)$。

(3)#

• 日本語 (Japanese): 整列済みの配列 win から二分探索 (Binary Search) を用いて、値が lot に一致する要素を検索する。 戻り値は、lot が win 内に存在する場合はそのインデックス (位置) を返し、存在しない場合は -1 を返す。
• 英語 (English): It searches for the value lot in the sorted array win using binary search, where n is the size of the array. The return value is the index of lot in the array win if found, and -1 if not found.
• 中文解析 (Chinese Analysis): functionB 实现了二分查找（Binary Search）算法。它在大小为 n 且已按升序排列的数组 win 中检索值等于 lot 的元素。由于本题中中奖号码各不相同，若找到匹配项，函数将返回该中奖号码在数组 win 中的对应下标（$0$ 至 $n-1$ 之间的整数）；若未能检索到，则返回 -1。

(4-1)#

• 日本語 (Japanese): (iii)
• 英語 (English): (iii)
• 中文解析 (Chinese Analysis): 此段代码实现的是快速排序的 Hoare 分区方案。双指针 i 和 j 分别自左右两端起向中间逼近，在相遇或交叉（i >= j）时结束。 当循环退出时，数组已被分成两个区间：
  • 左半部分：下标从 t 到 i-1，其中所有的元素值均小于或等于枢轴量 $x$。
  • 右半部分：下标从 j+1 到 w，其中所有的元素值均大于或等于枢轴量 $x$。 因此，下一步递归调用的两个子区间分别为 [t, i-1] 和 [j+1, w]。空栏的正确填写方式为：(あ) = t, (い) = i-1, (う) = j+1, (え) = w。这与选项 (iii) 完全相符。

(4-2)#

• 日本語 (Japanese): $O(n \log n)$
• 英語 (English): $O(n \log n)$
• 中文解析 (Chinese Analysis): 修改后的 functionA 采用了快速排序。在平均情况下，每次划分均能将数组大致等分为两部分，使得递归树的深度为 $O(\log n)$。在每一层递归中，分区的线性扫描操作总计花费 $O(n)$ 时间。根据主定理，总的平均时间复杂度为 $O(n \log n)$。

(5)#

• 日本語 (Japanese):
  • 下線 (ア): grade, win, 0, n-1
  • 下線 (イ): (k = (lot == win[0] ? 0 : -1)) != -1
• 英語 (English):
  • Underline (ア): grade, win, 0, n-1
  • Underline (イ): (k = (lot == win[0] ? 0 : -1)) != -1
• 中文解析 (Chinese Analysis):
  • 逻辑分析： 题目限定只能修改 main 函数中 functionA 的参数 (ア) 和 if 条件式 (イ)，并要求以平均 $O(1)$ 的时间复杂度判断所持号码 lot 是否中了 1 等奖。 等级有 1 等、2 等、3 等（对应的等级数值为 1, 2, 3）。由于 $N$ 个奖项中，1 等奖刚好只有 1 本，2 等奖 1 本，3 等奖 $N-2$ 本。 如果我们改变排序时的键值，将等级数组 grade 传作主数组 a，将中奖号码数组 win 传作辅数组 b，即执行： functionA(grade, win, 0, n-1); (ア) 那么，程序会对等级值进行升序排序。排序后，grade 数组中的元素会被整理为： grade[0] = 1（1等）, grade[1] = 2（2等）, 其余为 3。 相应的，win 数组也作了同步交换，此时 win[0] 中存储的必定是唯一的 1 等奖中奖号码，win[1] 存放的是 2 等奖号码。 因此，我们不再需要进行全局的二分查找，只需在 $O(1)$ 时间内比对所持号码 lot 与 win[0] 即可判断是否中了 1 等奖。 为适配后续代码的输出 grade[k]（需要打印出中奖等级 1，即 grade[0]），我们需要在比对成功时令 k = 0，失败时令 k = -1。 因此，条件式 (イ) 应写为包含赋值的表达式：(k = (lot == win[0] ? 0 : -1)) != -1。

Description#

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

1
while (true) {
2
    m = m + 1;
3
}
4
/* プロセス3 */
5

6
while (true) {
7
    print(m);
8
}
9
/* プロセス4 */

Kai#

(1-1)#

• 日本語 (Japanese):
  • 符号絶対値表現: 10001111
  • 1の補数表現: 11110000
• 英語 (English):
  • Signed magnitude representation: 10001111
  • One’s complement representation: 11110000
• 中文解析 (Chinese Analysis): 对于数值 $-15$：
  1. 符号绝对值表示法：最高位（MSB，第7位）表示正负符号，0表示正数，1表示负数。其余 7 位存储绝对值 $15 = (0001111)_2$。结合后即为 10001111。
  2. 1的补码表示法：负数的1的补码为对应正数各位按位取反。正数 $+15$ 二进制为 00001111，取反后即为 11110000。

(1-2)#

• 日本語 (Japanese):
  • 正の最大値: ビット列 01111111 (10進数: $127$)
  • 負の最小値: ビット列 10000000 (10進数: $-128$)
• 英語 (English):
  • Maximum positive value: 01111111 (Decimal: $127$)
  • Minimum negative value: 10000000 (Decimal: $-128$)
• 中文解析 (Chinese Analysis): 在 8 位二进制的 2的补码（Two’s Complement）表示法下：
  • 正的绝对值最大时，最高位（符号位）为 0，数值位全为 1，即 01111111。十进制值为 $2^7 - 1 = 127$。
  • 负的绝对值最大时（即数值最小），最高位为 1，数值位全为 0，即 10000000。十进制值为 $-2^7 = -128$。

(1-3-1)#

• 日本語 (Japanese): $+43$ の 2の補数表現: 00101011 $-5$ の 2の補数表現: 11111011

  加算過程は以下の通り：

  1
    00101011  (43)
  2
  + 11111011  (-5)
  3
  -----------
  4
   100100110  (38)
  

  最上位ビットからの桁上げ出力 (carry-out) は 1 であるが、8ビットの加算処理においてこの桁上げは無視（破棄）される。最終的な 8ビットの計算結果は 00100110 となり、これは10進数で $38$ に相当し、計算が正しく行われる。

• 英語 (English): The 2’s complement representation of $+43$: 00101011 The 2’s complement representation of $-5$: 11111011

  The addition process:

  1
    00101011  (43)
  2
  + 11111011  (-5)
  3
  -----------
  4
   100100110  (38)
  

  The carry-out from the MSB is 1. In 8-bit arithmetic, this carry-out is ignored (discarded). The final 8-bit result is 00100110, which corresponds to $38$ in decimal.

• 中文解析 (Chinese Analysis): 计算 $43 + (-5)$ 的过程：

  • 将 $+43$ 转换为 8 位二进制补码：$43 = 32 + 8 + 2 + 1 \to$ 00101011。
  • 将 $-5$ 转换为 8 位二进制补码：$+5$ 的二进制为 00000101，按位取反为 11111010，再加 1 得到 11111011。
  • 将两个补码按位相加：

    1
      00101011
    2
    + 11111011
    3
    ----------
    4
     100100110
    

    相加结果得 9 位二进制数 100100110。在 8 位加算器运算中，最左边的溢出进位（carry-out = 1）被直接忽略丢弃。最后保留的 8 位结果为 00100110，转换为十进制是 $32 + 4 + 2 = 38$，数值正确。

(1-3-2)#

• 日本語 (Japanese): 符号の正負に関わらず、減算（引き算）を加算（足し算）と同じ加算器回路（ハードウェア）を用いて同一に処理できること。
• 英語 (English): Subtractions can be performed using the same adder hardware circuit as additions, avoiding the need for a separate subtractor circuit.
• 中文解析 (Chinese Analysis): 利于硬件实现。引入 2的补码后，减法运算可以转换为加法来处理，这样计算机在进行符号数加减时，都可以统一使用同一套加法器电路（Adder），无需再单独设计减法器，大大节省了硬件设计成本和电路复杂度。

(1-4-1)#

• 日本語 (Japanese): c = 1
• 英語 (English): c = 1
• 中文解析 (Chinese Analysis): 对于无符号整数相加，只有在最高有效位（MSB）产生向外的进位时，才会发生溢出。因此判断条件为 $c = 1$。

(1-4-2)#

• 日本語 (Japanese): (a ∧ b ∧ ¬s) ∨ (¬a ∧ ¬b ∧ s) (あるいは、最高位ビットへの桁上げ入力 $c_{in}$ と最高位ビットからの桁上げ出力 $c$ を用いて $c_{in} \neq c$ とする)
• 英語 (English): (a ∧ b ∧ ¬s) ∨ (¬a ∧ ¬b ∧ s) (Alternatively, using the carry-in to the MSB $c_{in}$ and the carry-out $c$, the condition is $c_{in} \neq c$)
• 中文解析 (Chinese Analysis): 有符号补码加法溢出发生在两个同号数相加却得出异号数结果的时刻：
  • 两个负数相加，结果为正数：符号位 $a=1, b=1$ 而 $s=0$，对应 $(a \land b \land \neg s)$；
  • 两个正数相加，结果为负数：符号位 $a=0, b=0$ 而 $s=1$，对应 $(\neg a \land \neg b \land s)$。 因此，判断公式为 $(a \land b \land \neg s) \lor (\neg a \land \neg b \land s)$。此外，也可以通过判断最高位的进位输入 $c_{in}$ 与进位输出 $c$ 是否不相等（即 $c_{in} \oplus c = 1$）来判定。

(2-1)#

• 日本語 (Japanese):
  • デッドロック (Deadlock): 2つ以上のプロセスが、互いに相手が占有しているリソースの解放を待ち続けることで、すべてのプロセスが永久にブロックされて実行が進まなくなる状態。
  • 飢餓状態 (Starvation): システム全体は動作しており他のプロセスは実行できているが、特定のプロセスが競合やスケジューリングの都合により、必要なリソースを永久に割り当てられず、実行を再開できない状態。
• 英語 (English):
  • Deadlock: A state in which two or more processes are permanently blocked because each process is holding a resource and waiting for another resource held by another process in a circular chain.
  • Starvation: A state where a specific process is perpetually denied necessary resources to make progress, even though the system as a whole is running successfully and other processes are active.
• 中文解析 (Chinese Analysis):
  • 死锁（Deadlock）：指系统中两个或多个进程因循环等待对方所持有的独占资源而全部陷入无限期挂起、永远无法继续执行的僵死状态。
  • 饥饿（Starvation）：指在多任务调度中，某个特定进程由于资源分配优先级或调度算法设计缺陷，导致长时期甚至永久性地无法获得执行所需的资源，从而无法推进。此时系统整体依然在正常轮转并处理其他进程（没有陷入死锁）。

(2-2)#

• 日本語 (Japanese): 実行順序: (ア) $\to$ (ウ) $\to$ (イ) $\to$ (エ) 理由: top = x の状態からプロセス1が (ア) top = top - 1 を実行すると、top は x - 1 になる。この段階でプロセス切り替えが起き、プロセス2が (ウ) pop_item = stack(top) を実行すると、まだデータが書き込まれていない stack(x-1) の未定義の値を読み込んでポップしてしまう。その後、(イ) と (エ) が順に実行されると、top は最終的に x に戻るが、プッシュしたはずの push_item は stack(x-1) に放置され、アクセス不可能（消失）になる。
• 英語 (English): Execution order: (ア) $\to$ (ウ) $\to$ (イ) $\to$ (エ) Reason: Initially top = x. Process 1 executes (ア) top = top - 1, setting top to x - 1. If a context switch occurs here and Process 2 runs (ウ) pop_item = stack(top), Process 2 pops uninitialized, invalid data from stack(x-1) instead of popping the valid item d1 from stack(x). Subsequently, (イ) and (エ) execute, resetting top to x. The pushed item is left at stack(x-1) and becomes inaccessible, resulting in data loss.
• 中文解析 (Chinese Analysis): 产生异常的执行顺序为：(ア) $\to$ (ウ) $\to$ (イ) $\to$ (エ)。
  • 过程追踪：
    1. 初始状态下 top = x。
    2. 进程1执行 (ア) top = top - 1，将 top 变更为 x - 1。随后时钟中断触发进程切换。
    3. 进程2执行 (ウ) pop_item = stack(top)，即执行 pop_item = stack(x-1)。由于此时新元素还没有被压入，进程2实际上弹出了越界的、未定义的内存垃圾数据。
    4. 进程1重新调度执行 (イ) stack(top) = push_item，把元素写入到 stack(x-1)。
    5. 进程2执行 (エ) top = top + 1，将 top 恢复为 x。
  • 异常结果：进程2弹出了错误的数据；新压入的数据留在了 stack(x-1) 处，但由于栈顶指针恢复为了 x，这个新数据再也无法被读取，等同于数据被遗弃丢失。

(2-3-1)#

• 日本語 (Japanese):
  • プロセス1 (Push):

    1
    P(a);
    2
    top = top - 1;
    3
    stack(top) = push_item;
    4
    V(a);
    

  • プロセス2 (Pop):

    1
    P(a);
    2
    pop_item = stack(top);
    3
    top = top + 1;
    4
    V(a);
    

  • 初期値: a = 1
• 英語 (English):
  • Process 1 (Push): [Code above]
  • Process 2 (Pop): [Code above]
  • Initial Value: a = 1
• 中文解析 (Chinese Analysis): 使用一个互斥二值信号量 a。通过在进/出栈的临界区代码段前后分别插入 $P(a)$ 与 $V(a)$ 命令，实现同一时间只允许一个进程对栈结构（top 指针和 stack 数组）进行操作。信号量 a 的初值应设为 1。

(2-3-2)#

• 日本語 (Japanese):
  • プロセス3:

    1
    while (true) {
    2
        P(b);
    3
        m = m + 1;
    4
        V(c);
    5
    }
    

  • プロセス4:

    1
    while (true) {
    2
        P(c);
    3
        print(m);
    4
        V(b);
    5
    }
    

  • 初期値: b = 0, c = 1
• 英語 (English):
  • Process 3: [Code above]
  • Process 4: [Code above]
  • Initial Values: b = 0, c = 1
• 中文解析 (Chinese Analysis): 为满足输出序列为 1, 2, 3, ... 的同步要求，两进程必须紧密交替执行：进程4先打印当前的 m 值（第一轮为初值1），打印完毕后放行进程3；进程3把 m 增加1（第二轮变为2），然后放行进程4。 我们引入两个控制同步的信号量：
  • b：控制进程3是否被允许进行自增。初值为 0。
  • c：控制进程4是否被允许执行打印。因为一开始必须首先打印初值 1，所以初值设为 1，使得第一步 P(c) 可以顺利通过。
  • 工作序列：
    1. 进程4运行，P(c) 成功减为 0，打印 m（即 1），随后 V(b) 释放 b（b 变为 1）。
    2. 进程3运行，P(b) 成功减为 0，执行 m = m + 1（m 变 2），随后 V(c) 释放 c（c 变 1）。
    3. 进程4再次被唤醒运行，完成下一轮迭代。

Description#

配点： (1-1) 5点, (1-2) 5点, (1-3) 35点, (1-4) 20点, (2-1) 35点, (2-2) 25点

1
                    ┌──────┐
2
      (a, Z)/0Z     │      │
3
      (a, 0)/00     │      │
4
      (a, 1)/01     │      │
5
      (b, Z)/1Z     │ (あ) │     (a, 0)/ε
6
      (b, 0)/10     │      │     (b, 1)/ε
7
      (b, 1)/11     │      │
8
       ┌───┐        │      │      ┌───┐    (ε, Z)/Z     ┌───┐
9
──===> │q0 │ ───────┼──────┼====> │q1 │ ──────────────> │q2 │
10
       └───┘        │      │      └───┘                 └───┘
11
        ↺           │      │       ↺
12
                    └──────┘

Kai#

(1-1)#

• 日本語 (Japanese):

  1
  stateDiagram-v2
  2
      [*] --> q0: 開始
  3
      q0 --> qa: a
  4
      q0 --> qb: b
  5
      qa --> q2: a
  6
      qa --> qd: b
  7
      qb --> qd: a
  8
      qb --> q2: b
  9
      q2 --> qd: a, b
  10
      qd --> qd: a, b
  

  状態定義：
  • $q_0$: 開始状態（長さ0）
  • $q_a$: 文字 a を1つ読んだ状態（長さ1）
  • $q_b$: 文字 b を1つ読んだ状態（長さ1）
  • $q_2$: aa または bb を読んだ状態（受理状態、長さ2）
  • $q_d$: 回文にならない、もしくは長さが3以上の文字列（デッド状態）
• 英語 (English): [State transition diagram above] State definitions:
  • $q_0$: Start state (length 0)
  • $q_a$: Read single a (length 1)
  • $q_b$: Read single b (length 1)
  • $q_2$: Read aa or bb (accepting state, length 2)
  • $q_d$: Dead state for invalid or longer strings
• 中文解析 (Chinese Analysis): 长度为 2 的回文串只有 aa 和 bb。DFA 从初始状态 $q_0$ 开始，分别读取第一个字符 a 或 b 转向状态 $q_a$ 或 $q_b$；在第二个字符与第一个字符相同时，转移至唯一接收状态 $q_2$。若第二字符不匹配或长度超过 2，则统一进入陷阱死状态 $q_d$。

(1-2)#

• 日本語 (Japanese):

  1
  stateDiagram-v2
  2
      [*] --> q0: 開始
  3
      q0 --> qa: a
  4
      q0 --> qb: b
  5
      qa --> qaa: a
  6
      qa --> qab: b
  7
      qb --> qba: a
  8
      qb --> qbb: b
  9
      qaa --> q3: a
  10
      qaa --> qd: b
  11
      qab --> q3: a
  12
      qab --> qd: b
  13
      qba --> qd: a
  14
      qba --> q3: b
  15
      qbb --> qd: a
  16
      qbb --> q3: b
  17
      q3 --> qd: a, b
  18
      qd --> qd: a, b
  

  状態定義：
  • $q_0$: 開始状態
  • $q_a, q_b$: 長さ1の文字列を読んだ状態
  • $q_{aa}, q_{ab}, q_{ba}, q_{bb}$: 長さ2の各文字列を読んだ状態
  • $q_3$: 受理状態（aaa, aba, bab, bbb のいずれかを読んだ状態）
  • $q_d$: 受理条件を満たさない文字列用のデッド状態
• 英語 (English): [State transition diagram above] State definitions:
  • $q_0$: Start state
  • $q_a, q_b$: States after reading length 1 string
  • $q_{aa}, q_{ab}, q_{ba}, q_{bb}$: States after reading length 2 strings
  • $q_3$: Accepting state (after reading aaa, aba, bab, or bbb)
  • $q_d$: Dead state
• 中文解析 (Chinese Analysis): 长度为 3 的回文串只有 aaa, aba, bab, bbb。我们建立状态记录前两位的不同路径组合（$q_{aa}, q_{ab}, q_{ba}, q_{bb}$）。第三位读入时只有当首尾字符相同时才进入接收状态 $q_3$，其它多余或不相等的字符输入全部导向死状态 $q_d$。

(1-3)#

• 日本語 (Japanese): 言語 $L = \{ p \in \Sigma_{ab}^* \mid p \text{ is a palindrome} \}$ が正則言語であると仮定し、反復補題の定数を $n$ とする。 文字列 $s = a^n b a^n$ を考えると、明らかに $s \in L$ であり、かつ長さは $|s| = 2n + 1 \ge n$ である。 反復補題の定義より、文字列 $s$ は以下の3つの条件を満たす $s = xyz$ に分割できる：

  1. $|xy| \le n$
  2. $|y| \ge 1$
  3. 任意の $k \ge 0$ に対して $x y^k z \in L$

  条件1より、$xy$ は $s$ の先頭の $n$ 個の終端記号（すべて a）の領域に含まれる。したがって、$y = a^m$ ($m \ge 1$) と表すことができる。 ここで $k = 0$ の場合を考えると、得られる文字列は $xz = a^{n-m} b a^n$ となる。 条件2より $m \ge 1$ であるため、この文字列中の左側の a の個数 $n-m$ は、右側の a の個数 $n$ と一致しない。したがって、$xz$ は回文ではなくなり、$xz \notin L$ となる。 これは条件3の $x y^0 z \in L$ に矛盾する。 したがって、仮定は誤りであり、言語 $L$ は正則言語ではない。

• 英語 (English): Assume $L = \{ p \in \Sigma_{ab}^* \mid p \text{ is a palindrome} \}$ is a regular language, and let $n$ be the pumping lemma constant. Consider the string $s = a^n b a^n$. Clearly, $s \in L$ and $|s| = 2n + 1 \ge n$. According to the pumping lemma, $s$ can be partitioned into $s = xyz$ satisfying:

  1. $|xy| \le n$
  2. $|y| \ge 1$
  3. $x y^k z \in L$ for all $k \ge 0$.

  By condition 1, $xy$ must lie entirely within the first $n$ characters of $s$ (which are all $a$‘s). Thus, we can write $y = a^m$ for some $m \ge 1$. Let $k = 0$. The pumped string is $xz = a^{n-m} b a^n$. Since $m \ge 1$, we have $n-m < n$. The number of $a$‘s on the left ($n-m$) is less than the number of $a$‘s on the right ($n$), meaning that $xz$ is not a palindrome ($xz \notin L$). This contradicts condition 3. Therefore, the initial assumption is false, and $L$ is not a regular language.

• 中文解析 (Chinese Analysis): 采用反证法：

  • 假设回文语言 $L$ 是正则的，由泵引理知存在一个泵常数 $n$。
  • 构造字符串 $s = a^n b a^n$。容易验证 $s$ 是回文串，所以 $s \in L$，且长度为 $2n+1 \ge n$。
  • 根据泵引理，字符串 $s$ 应可以拆分为 $xyz$，且满足 $|xy| \le n$ 且 $|y| \ge 1$。
  • 由于 $|xy| \le n$，$xy$ 部分只能完全位于字符串最左端的 $a^n$ 内部。所以子串 $y$ 必定是一段纯 $a$ 串，可表示为 $y = a^m$ 且 $m \ge 1$。
  • 当我们将 $y$ 泵出（即令 $k = 0$）时，生成新串 $xz = a^{n-m} b a^n$。
  • 由于 $m \ge 1$，导致新串左侧的 $a$ 的数量 $n-m$ 小于右侧 $a$ 的数量 $n$，新字符串失去了回文性质（$xz \notin L$）。这与泵引理中要求 $xz \in L$ 的断言相矛盾。
  • 故原假设不成立，回文串语言 $L$ 并非正则语言。

(1-4)#

• 日本語 (Japanese):
  • $(\varepsilon, Z) / Z$
  • $(\varepsilon, 0) / 0$
  • $(\varepsilon, 1) / 1$
  • $(a, Z) / Z$
  • $(a, 0) / 0$
  • $(a, 1) / 1$
  • $(b, Z) / Z$
  • $(b, 0) / 0$
  • $(b, 1) / 1$
• 英語 (English): The transitions in the box (あ) are: [List of 9 transitions above]
• 中文解析 (Chinese Analysis): 下推自动机需要非确定性地猜测回文串的中心线。从 $q_0$ 到 $q_1$ 的状态转移即表示“跨越对称中点”：
  • 对于偶数长度回文串，中点不包含任何独立字符。自动机执行空转移 $\varepsilon$，且不修改栈状态：即 $(\varepsilon, Z)/Z, (\varepsilon, 0)/0, (\varepsilon, 1)/1$。
  • 对于奇数长度回文串，中点包含一个多余的中心字符（a 或 b）。自动机在跳转时读入该字符，但不改变栈：即 $(a, Z)/Z, (a, 0)/0, (a, 1)/1$ 和 $(b, Z)/Z, (b, 0)/0, (b, 1)/1$。 因此，框 (あ) 中共有 9 条转移关系。

(2-1)#

• 日本語 (Japanese): $k > 1$ の場合、導出の最初のステップは $A \Rightarrow aAbA$ または $A \Rightarrow bAaA$ である。 $A \Rightarrow aAbA$ の場合、この2つの変数 $A$ はそれぞれ $k-1$ 回以下の生成規則の適用により、終端記号列 $v_1, v_2 \in T_1^*$ を導出する（$w = a v_1 b v_2$）。 帰納法の仮定より、$|v_1|_a = |v_1|_b$ および $|v_2|_a = |v_2|_b$ が成立する。 したがって、 $|w|_a = |a v_1 b v_2|_a = 1 + |v_1|_a + |v_2|_a = 1 + |v_1|_b + |v_2|_b = |a v_1 b v_2|_b = |w|_b$ となり、$|w|_a = |w|_b$ が成立する。 $A \Rightarrow bAaA$ の場合も同様に（$w = b v_1 a v_2$）、 $|w|_a = |b v_1 a v_2|_a = 1 + |v_1|_a + |v_2|_a = 1 + |v_1|_b + |v_2|_b = |b v_1 a v_2|_b = |w|_b$ となり、$|w|_a = |w|_b$ が成立する。
• 英語 (English): For $k > 1$, the first step of the derivation is either $A \Rightarrow aAbA$ or $A \Rightarrow bAaA$. In the case of $A \Rightarrow aAbA$, the two variables $A$ derive terminal strings $v_1, v_2 \in T_1^*$ respectively using $k-1$ or fewer steps (giving $w = a v_1 b v_2$). By the induction hypothesis, we have $|v_1|_a = |v_1|_b$ and $|v_2|_a = |v_2|_b$. Therefore, $|w|_a = 1 + |v_1|_a + |v_2|_a = 1 + |v_1|_b + |v_2|_b = |w|_b$, and the statement holds. In the case of $A \Rightarrow bAaA$, the two variables $A$ derive terminal strings $v_1, v_2 \in T_1^*$ with $w = b v_1 a v_2$. Similarly, $|w|_a = 1 + |v_1|_a + |v_2|_a = 1 + |v_1|_b + |v_2|_b = |w|_b$ holds.
• 中文解析 (Chinese Analysis): 当归纳步骤 $k > 1$ 时，推导的第一步要么是 $A \Rightarrow aAbA$，要么是 $A \Rightarrow bAaA$。
  • 在第一步为 $A \Rightarrow aAbA$ 时，推导出的字符串格式为 $w = a v_1 b v_2$，其中子串 $v_1$ 和 $v_2$ 分别由生成式中的两个 $A$ 经不超过 $k-1$ 步规则生成。根据数学归纳法假设，此时 $v_1$ 和 $v_2$ 必定含有相同数量的 a 和 b，即满足 $|v_1|_a = |v_1|_b$ 和 $|v_2|_a = |v_2|_b$。因此整个串满足：$|w|_a = 1 + |v_1|_a + |v_2|_a = 1 + |v_1|_b + |v_2|_b = |w|_b$。
  • 类似地，当第一步为 $A \Rightarrow bAaA$ 时，可写成 $w = b v_1 a v_2$，同样有：$|w|_a = 1 + |v_1|_a + |v_2|_a = 1 + |v_1|_b + |v_2|_b = |w|_b$。归纳成立。

(2-2)#

• 日本語 (Japanese):
  • (イ): 生成規則の中に $A \to \varepsilon$ が存在するため、$A \Rightarrow \varepsilon = w$ となり、$w \in L_1$ が成立する。
  • (ウ): aAbA
  • (エ): bAaA
• 英語 (English):
  • (イ): Since $A \to \varepsilon \in P_1$, we have $A \Rightarrow \varepsilon = w$, hence $w \in L_1$ holds.
  • (ウ): aAbA
  • (エ): bAaA
• 中文解析 (Chinese Analysis):
  • (イ)：当字符串长度 $|w|=0$ 即 $w=\varepsilon$ 时，由于文法规则集合中包含 $A \to \varepsilon$，推导 $A \Rightarrow \varepsilon = w$ 成立，因此 $w \in L_1$。
  • (ウ)：首字母为 a，表示为 $w = a v_1 b v_2$。我们使用产生式 $A \to aAbA$ 来匹配首尾的 a 和 b，然后分别由两个 $A$ 递归生成 $v_1$ 和 $v_2$，故此处需填入 aAbA。
  • (エ)：首字母为 b，表示为 $w = b v_1 a v_2$。我们使用产生式 $A \to bAaA$ 来匹配首尾的 b 和 a，故此处需填入 bAaA。

Description#

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

1
記号
2
    N     全ノードの集合.
3
    c(i,j)  ノード i からノード j へのリンクのコスト. c(i,j) ≧ 0, c(i,i) = 0 とする. また,
4
          ノード i からノード j へリンクがない場合は c(i,j) = ∞ とする.
5
    di(j)  ノード i において, その時点でノード i が知るノード i からノード j までの最小
6
          コスト経路のコストを保持する変数.
7
    Di    ノード i の持つディスタンスベクトル. N = {x,y,z} の場合, Di は以下の通り
8
          とする.
9
          Di = [di(x) の値, di(y) の値, di(z) の値]
10
初期状態
11
    * 各ノード i において c(i,j) は既知である (∀j ∈ N).
12
    * 各ノード i において di(j) = c(i,j) である (∀j ∈ N).
13
動作
14
    全ノードは, 各ステップで以下の動作I, 動作IIのそれぞれを同期的に (synchronously) に
15
    実行し, そのステップを繰り返し実行する.
16
    動作 I.   各ノード i は, 隣接 (adjacent) ノードにディスタンスベクトル Di を送信し,
17
             自身に送信されたディスタンスベクトルを受信する.
18
    動作 II.  各ノード i は, 受信したすべてのディスタンスベクトルにもとづいて, 自身の
19
             ディスタンスベクトル Di を更新する.
20
経路の収束 (convergence)
21
    前ステップと現ステップの間で Di (∀i ∈ N) の値に変化がなくなることを経路が収束す
22
    ると定義する. 最小コスト経路は, 収束したときの各ノードが持つ情報から導出できる.