Author#

KardeniaPoyu

Description#

図に示す ANSI-C 準拠である C 言語のプログラム (program) は、配列 (array) values の要素 (element) に格納された非負整数 (non negative integer) のデータ (data) を、$r$ 進数 ($r$-base number) ($2 \le r \le 256$) とみなして整列 (sort) し、出力 (output) するプログラムである。以下の各問に答えよ。

(1) プログラムの 10～26 行目の for 文の処理において 1 巡目 ($d=1$ のとき) および 2 巡目 ($d=2$ のとき) の終了時における配列 buckets の内容を答えよ。なお、配列の各要素は 0 で初期化される。配列の各要素 buckets[x][y] において、$x$ は 3 以上の値、$y$ は 5 以上の値を取りうるが、これらの内容については答えなくてよい。

(2) プログラムで実現されている整列アルゴリズム (sorting algorithm) に関する以下の各小問に答えよ。

• (2-1) この整列アルゴリズムは、一般に何と呼ばれているか名称を答えよ。
• (2-2) 整列対象のすべてのデータを $r$ 進数で表現したときの最大の桁数を $k$ 、データの数を $n$ としたとき、時間計算量のオーダー表記を理由とともに答えよ。
• (2-3) このアルゴリズムでは、どのような工夫によってデータ同士の比較を伴わない整列を可能にしているか答えよ。
• (2-4) 比較を伴う整列アルゴリズムと比較して、本アルゴリズムの特徴を時間計算量および空間計算量の観点から答えよ。

(3) 配列 values の要素に格納されたデータを降順 (descending order) に整列するようにプログラムを変更したい。そのために下線（ア）および下線（イ）をどのように記述すればよいか、適切な式を答えよ。

1
#include <stdio.h>
2
#define MAXR 256
3
#define MAXN 1000
4

5
void sort(int values[], int numvalues, int r, int maxdigit){
6
    int rd, d, b, i, n, j;
7
    int buckets[MAXR][MAXN];
8
    int numbucket[MAXR];
9

10
    rd = 1;
11
    for (d = 1; d <= maxdigit; d++){
12
        for (b = 0; b < r; b++){
13
            numbucket[b] = 0;
14
        }
15
        for (i = 0; i < numvalues; i++){
16
            n = (values[i] / rd) % r;
17
            buckets[n][numbucket[n]++] = values[i];
18
        }
19

20
        i = 0;
21
        for (b = 0;
22
             /* 下線(ア) */
23
             b < r; b++){
24
            for (j = 0; j < numbucket[b]; j++){
25
                /* 下線(イ) */
26
                values[i++] = buckets[b][j];
27
            }
28
        }
29
        rd *= r;
30
    }
31
}
32

33
int main(){
34
    int i;
35
    int values[5] = {12, 21, 1, 11, 2};
36
    sort(values, 5, 10, 2);
37
    for(i = 0; i < 5; i++){
38
        printf("%d\n", values[i]);
39
    }
40
    return 0;
41
}

Kai#

Summary#

参考视频

Author#

KardeniaPoyu

Description#

(1) 計算機 (computer), 特に, 中央処理装置 (CPU: central processing unit) に関する以下の各小問に答えよ. 解答は全て解答用紙の太線内に書くこと.

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

計算機の構成方式のことを [ (a) ] と呼ぶ. 現在, 実用的に利用されている大部分の計算機は, 線形アドレス空間 (linear address space) を有するメインメモリ (main memory) 上にプログラム (program) 及びデータ (data) を置き, プログラムを逐次実行する, 等の [ (a) ] を採用している. このような計算機は, [ (b) ] 計算機と呼ばれる．

[ (b) ] 計算機では, [ (c) ] が示すメインメモリアドレスから, プログラムの構成要素である機械語命令を読み出し, これをデコード (decode) して実行する. 機械語命令は, その種類を示す [ (d) ] 部と, 演算対象のデータである [ (e) ] の格納場所を示すアドレス部から成る.

Kai#

Summary & Insights#

NOTE

为了彻底理清本题中流水线受阻（Stall）的深层原因，我们需要明确 5 个阶段（Stage）的职责以及指令间的依赖关系：

1. 流水线阶段职责定义

• IF (Instruction Fetch / 命令フェッチ)：从内存中读取指令。

资源占用：会占用 内存总线（Memory Bus）。如果架构是单总线（指令和数据共用），此时其他阶段绝对不能访问内存。

• D (Decode / 命令デコード)：解析指令，确定操作类型。

资源占用：纯 CPU 内部操作，占用 CPU 内部的 指令译码器（Decoder）。互不干扰。

• OF (Operand Fetch / オペランドフェッチ)：从寄存器或内存中获取执行所需的数据。

资源占用（分两种情况）：

如果是从内存取数（如 MOV R1, (A)），会占用内存总线，此时会和 IF 阶段抢资源。

如果是从寄存器取数（如 ADD R1, R2），只占用 CPU 内部的高速总线，不会占用外部的内存总线，因此不会和 IF 抢资源。

• EX (Execute / 実行)：执行算术或逻辑运算。资源占用：纯 CPU 内部操作，占用 CPU 内部的 算术逻辑单元（ALU）。互不干扰。

• S (Store / 格納)：将执行结果写回至寄存器或内存。

资源占用（同样分两种情况）：

如果写回内存（如 MOV (B), R1），会占用内存总线。

如果写回寄存器（如 INC R1），只占用内部资源，不占用内存总线。但在写完（S阶段结束）之前，硬件会物理锁死（Stall）后面所有想读取该寄存器的指令，这就是数据冒险的根源。

NOTE

2. 指令流依赖分析

• 命令1: MOV R1, (A) → 写 R1（加载数据）。它在 OF 阶段 是去内存地址 A 中把数据拿出来。拿出来之后，数据在这个周期并没有立刻进入 R1。数据还要穿过 CPU 的内部总线，直到最后一步的 S（Store / 格納）阶段，CPU 才真正发出写信号，将高低电平打入 R1 的物理电路中。也就是说，直到命令1的 S 阶段结束，R1 里面装的才是新数据。

• 命令2: INC R1 → 读 R1 + 写 R1（自增）它要在下一阶段（EX 阶段）对数据进行 +1 运算。因此，它必须在 OF 阶段 把 R1 里面的值准确无误地读入 ALU（算术逻辑单元）的输入寄存器中。假设命令2的 OF 不等待，硬是在时钟周期3去读 R1。此时，命令1才刚刚完成内存读取（刚好过了 OF 阶段），数据还在传输总线上，并没有写入 R1。结果就是：命令2在周期3读取到了 R1 里面以前的旧数据（脏数据），然后拿这个错误的数据去加 1。整个程序的计算结果就全盘崩溃了。

• 命令3: MOV (B), R1 → 读 R1（存入内存）

TIP

总之，记住：(A)、(B)、IF 抢的是内存总线；而 R1、R2 是 CPU 内部寄存器。

NOTE

核心结论：这三条指令构成了典型的 RAW (Read-After-Write) 数据依赖。在硬件没有实现 Data Forwarding（数据前推）的情况下，命令2 必须严格等待 命令1 完成 S (Store) 阶段后才能进行自己的 OF 阶段；同理 命令3 也要等待 命令2。这种连续的资源竞争正是导致流水线大幅停顿的原因。

在（1-3-1）中我们能看出，周期 4 时，命令1在 S（写回寄存器 R1），命令2在 EX（ALU运算）。此时，内存总线释放，命令3得以顺利执行 IF！

在（1-3-2）中我们能看出，CPU 内部有一个叫冒险检测单元（Hazard Detection Unit）的纯硬件模块。它在周期 2 发现：命令2下一秒就要读 R1，但是命令1还要等到周期 4 结束才能把新数据写进 R1！

于是，这个硬件单元强制切断了命令2向后推进的时钟信号，把命令2物理冻结在流水线上。这就是周期 3、4 里的 -。

周期 5，因为命令1在周期 4 结束时，终于完成了 S，把高低电平打入了 R1 的物理电路。警报解除，命令2解除冻结，在周期 5 执行 OF（此时是从 CPU 内部的 R1 读取，不占用外部内存）。

命令3同理，命令3也要用 R1，冒险检测单元再次介入，把它冻结在 D 阶段后面。直到命令2在周期 7 结束 S（把 INC 后的新值写回 R1），命令3才在 周期 8 顺利进入 OF 阶段。

Author#

KardeniaPoyu

Description#

(1) 有限オートマトン (finite automaton) $M$ は 5 項組 $M = (Q, \Sigma, \delta, q_0, F)$ で与えられる。ここで，$Q, \Sigma, \delta, q_0, F$ は，それぞれ，状態 (state) の有限集合，入力記号 (input symbol) の有限集合（アルファベット (alphabet)），状態遷移関数 (state transition function)，初期状態 (initial state) ($q_0 \in Q$)，受理状態 (accepting state) の集合 ($F \subseteq Q$) である。 また，$M$ が受理 (accept) する言語 (language)（認識する言語）を $L(M)$ と表す。下の状態遷移図 (state transition diagram) に示す非決定性 (non-deterministic) 有限オートマトン $M_1$ について，以下の各小問に答えよ。なお，$Q = \{a, b, c, d, e, f, g, h, i, j, k\}$，$\Sigma = \{0, 1\}$，$q_0 = a$，$F = \{k\}$ である。

• (1-1) $M_1$ が受理する言語 (language) を正規表現 (regular expression) で示せ。
• (1-2) $M_1$ が受理する語 (word) を，1 文字目を最上位ビット (most significant bit) とす符号なし 2 進数 (unsigned binary number) とみなす。$M_1$ が受理するすべての語の中で，7 番目に小さな数となる語を示せ。
• (1-3) $M_1$ の状態 $i$ の $\varepsilon$-閉包 ($\varepsilon$-closure) を示せ。
• (1-4) $L(M_1) = L(M_2)$ を満たす，決定性 (deterministic) 有限オートマトン $M_2$ をサブセット構成 (subset construction) 法を用いて求め，状態遷移図で示せ。同値 (equivalent) な状態があっても全て残すこと。状態名は $A, B, C, \dots$ とすること。導出過程と結果を示すこと。
• (1-5) $M_2$ の状態数を最小化した決定性有限オートマトン $M_3$ を求め，状態遷移図で示せ。状態名は $A', B', C', \dots$ とすること。

(2) 文脈自由文法 (context-free grammar) により生成される文脈自由言語 (context-free language) の閉包性 (closure property) を考える。文脈自由文法 $G$ は 4 項組 $G = (V, T, P, S)$ で表される。ただし，$V$ は変数 (variable，あるいは非終端記号 non-terminal symbol) の集合，$T$ は終端記号 (terminal symbol) の集合，$P$ は生成規則 (production rule) の集合，$S$ は開始記号 (start symbol) で $S \in V$ である。なお，生成規則の集合は $\varepsilon$-規則 ($\varepsilon$-rule) を含んでよいものとし，変数の集合と終端記号の集合は共通の記号を含まないものと仮定する。文法 $G$ が生成する言語を $L(G)$ と表記する。 任意の文脈自由文法 $G_1 = (V_1, T_1, P_1, S_1)$ と $G_2 = (V_2, T_2, P_2, S_2)$ が与えられる（ただし $V_1 \cap V_2 = \emptyset$ である）。 文脈自由言語は和 (union) 演算に関して閉じている。なぜなら，文脈自由文法 $G_3$ を以下の通りに構成すると，証明は省略するが，$L(G_1)$ と $L(G_2)$ の和の言語 $L_3 = L(G_1) \cup L(G_2)$ は $G_3$ によって生成される，すなわち $L_3$ は文脈自由言語だからである。

• $G_3 = (V_3, T_3, P_3, S_3)$
• $V_3 = V_1 \cup V_2 \cup \{S_3\}$，ただし $S_3 \notin (V_1 \cup V_2)$
• $T_3 = T_1 \cup T_2$
• $P_3 = \{S_3 \to S_1, S_3 \to S_2\} \cup P_1 \cup P_2$

文脈自由言語は連結 (concatenation) 演算に関して閉じていることを，文法の構成により示したい。以下の各小問に答えよ。

• (2-1) $L(G_1)$ と $L(G_2)$ を連結した言語 $L_4 = \{w_1w_2 \mid w_1 \in L(G_1), w_2 \in L(G_2)\}$ を生成する文脈自由文法 $G_4 = (V_4, T_4, P_4, S_4)$，すなわち $L_4 = L(G_4)$ である $G_4$ を構成せよ。
• (2-2) 上記 (2-1) で構成した $G_4$ によって生成される任意の語 $w$ は，上記 (2-1) で定義した $L_4$ に属することを証明せよ。
• (2-3) 上記 (2-1) で定義した $L_4$ に属する任意の語 $w$ は，上記 (2-1) で構成した $G_4$ により生成されることを証明せよ。

Kai#

Summary#

NOTE

(2-3)得分句：

• 1. $w = w_1 w_2$（$w_1 \in L(G_1), w_2 \in L(G_2)$）。
• 2. $S_1 \Rightarrow_{G_1}^* w_1$ 和 $S_2 \Rightarrow_{G_2}^* w_2$
• 3. $P_1 \subseteq P_4, P_2 \subseteq P_4$

🧱 前置准备：(2-1) 构造 $G_4$#

为了生成连接语言 $L_4 = L(G_1) L(G_2)$，我们构造的文法 $G_4$ 是这样的： $V_4 = V_1 \cup V_2 \cup \{S_4\}$ （把两边的变量倒进一个池子，并新增大 Boss $S_4$） $T_4 = T_1 \cup T_2$ （把两边的终结符倒进一个池子） $P_4 = P_1 \cup P_2 \cup \{S_4 \to S_1 S_2\}$ （规则池合并，并赋予大 Boss 分裂技能）

🛡️ (2-2) 证明 $L(G_4) \subseteq L_4$ (健全性 / Soundness)#

你的疑问： “从 $S_4$ 变出 $S_1 S_2$，不就是 $w_1 w_2$ 吗？” 考官的刁难： “你怎么知道在推导 $S_1$ 的时候，它不会不小心用到了 $P_2$ 里的规则，从而生成出乱七八糟的东西？”

【证明的核心逻辑：变量隔离】 这道题的“免死金牌”就藏在题干里的一句话：$V_1 \cap V_2 = \emptyset$（两个文法的变量集合互不相交）。这就是防止“交叉感染”的物理隔离墙！

【考场踩分推导步骤】

1. 起点：假设有一个字符串 $w$ 被 $G_4$ 生成，即 $w \in L(G_4)$。
2. 第一步推导：根据 $G_4$ 的规则，推导的第一步必须且只能是 $S_4 \Rightarrow S_1 S_2$。 所以，最终的字符串 $w$ 必然可以切分为两半：$w = w_1 w_2$，其中 $S_1 \Rightarrow^* w_1$ 且 $S_2 \Rightarrow^* w_2$。
3. 核心论证（踩分点！）： 由于题设中 $V_1 \cap V_2 = \emptyset$ ，这意味着 $P_1$ 中的规则左侧全都是 $V_1$ 中的变量，$P_2$ 中的规则左侧全都是 $V_2$ 中的变量。 因此，在把 $S_1$ 变成 $w_1$ 的整个推导过程中，绝对不可能触发任何属于 $P_2$ 的规则。同理，$S_2$ 变成 $w_2$ 时也绝不会触发 $P_1$。
4. 结论： 推导 $S_1 \Rightarrow^* w_1$ 完全只依赖于 $P_1$，因此 $w_1 \in L(G_1)$。 推导 $S_2 \Rightarrow^* w_2$ 完全只依赖于 $P_2$，因此 $w_2 \in L(G_2)$。 所以 $w = w_1 w_2 \in L_4$。证明完毕。

⚔️ (2-3) 证明 $L_4 \subseteq L(G_4)$ (完全性 / Completeness)#

你的疑问： “只要是 $w_1 w_2$，肯定能用 $G_4$ 生成啊，这还要证？” 考官的刁难： “请你用数学符号，把这个生成过程一步步‘走’一遍给我看，证明 $G_4$ 的规则池够用。”

这个证明比 (2-2) 简单得多，它就是一个“顺水推舟”的构造过程。

【考场踩分推导步骤】

1. 起点：假设有一个字符串 $w \in L_4$ 。根据定义，必然存在 $w_1 \in L(G_1)$ 和 $w_2 \in L(G_2)$，使得 $w = w_1 w_2$ 。
2. 翻译已知条件： 因为 $w_1 \in L(G_1)$，说明在 $G_1$ 中存在推导序列：$S_1 \Rightarrow^* w_1$（仅使用 $P_1$）。 因为 $w_2 \in L(G_2)$，说明在 $G_2$ 中存在推导序列：$S_2 \Rightarrow^* w_2$（仅使用 $P_2$）。
3. 在 $G_4$ 中模拟推导（踩分点）： 现在我们在 $G_4$ 中开始推导。
   • 首先使用新增的规则：$S_4 \Rightarrow S_1 S_2$。
   • 因为 $P_4$ 包含了 $P_1$ 和 $P_2$ 所有的规则（$P_1 \subseteq P_4, P_2 \subseteq P_4$），所以我们在 $G_1$ 和 $G_2$ 中能做的推导，在 $G_4$ 中原封不动全都能做。
   • 我们先对 $S_1$ 施加魔法，把它变成 $w_1$：$S_1 S_2 \Rightarrow^* w_1 S_2$。
   • 然后再对 $S_2$ 施加魔法，把它变成 $w_2$：$w_1 S_2 \Rightarrow^* w_1 w_2$。
4. 结论： 我们成功在 $G_4$ 中找到了一条合法路径：$S_4 \Rightarrow^* w_1 w_2 = w$。 因此 $w \in L(G_4)$。证明完毕。

总结：为什么需要这两步？#

在数学证明中，证明两个集合相等（$L(G_4) = L_4$），必须证明 相互包含（$\subseteq$ 和 $\supseteq$）。

• (2-2) 证明了“没有多造”：证明了 $G_4$ 绝不会因为规则混用，生出一个不属于 $L_4$ 的怪胎。（靠的是变量不相交的物理隔离）。
• (2-3) 证明了“没有少造”：证明了 $L_4$ 里的任何一个合法句子，$G_4$ 都有足够的规则（$P_4 \supset P_1, P_2$）去把它完美推导出来。

这就是计算理论中的**“形式化证明（Formal Proof）”**。

Author#

KardeniaPoyu

Description#

データリンク層 (data link layer) では、端末 (host) がフレーム (frame) を送信する際にプリアンブル (preamble) と呼ばれる特定のビット列を付与している。プリアンブルとフレームの構成は、図1 に示すものとする。以下の各問に答えよ。

(1) 伝送レート (transmission rate) $X$ [bps] の伝送媒体 (transmission medium) を用いた場合に、上位層に対して提供できる最大の転送レート (transfer rate) を、$X$ および図1 中の $Y$ を用いて示せ。なお、インターフレームギャップ (inter-frame gap) は考えなくて良い。

(2) プリアンブルに関する以下の各小問に答えよ。

• (2-1) プリアンブルをフレームに付与する目的を述べよ。
• (2-2) プリアンブルのビット列として最も適切なものを、以下の四つの選択肢から一つ選び、記号を答えよ。また、選んだビット列が、最も適切である理由を説明せよ。
  • 選択肢 A：00000111 00000110 00000101 00000100 00000011 00000010 00000001 00000000
  • 選択肢 B：10101010 10101010 10101010 10101010 10101010 10101010 10101010 10101011
  • 選択肢 C：11111111 11111111 11111111 11111111 00000000 00000000 00000000 00000000
  • 選択肢 D：11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
• (2-3) プリアンブルと同一のビット列がペイロード (payload) に含まれる場合に生じる問題を述べよ。また、その問題を回避するためにイーサネット (Ethernet) で行われる方策を説明せよ。

(3) 図1 で与えられるフレームには、伝送誤り (transmission error) 検出を行うための FCS (frame check sequence) が含まれている。生成多項式 $G(x)$ を用いた巡回冗長検査 (cyclic redundancy check) によりフレームの伝送誤りが検出される。すなわち、生成多項式 $G(x)$ で定義される擬巡回符号 (pseudo-cyclic code) の符号語の冗長記号部分が FCS となり、誤り検出が行われる。以下の各小問に答えよ。ただし、生成多項式 $G(x)$ は次の多項式とする。

$G(x) = x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1$

• (3-1) FCS のサイズ $Y$ [バイト] の値を答えよ。
• (3-2) 受信フレーム（誤り検出における受信語）の多項式表現を $R(x)$ とする。巡回冗長検査において誤り無しと判断する条件式を、$R(x)$ と $G(x)$ を用いて書け。
• (3-3) 生成多項式 $G(x)$ を用いて検出できないビット誤り (bit error) の最小個数 $r$ を考える。フレーム長が 1000 [バイト] である時の $r$ を求めよ。求めた過程も簡単に書け。必要に応じて、$G(x)$ を生成多項式とする巡回符号の次数最小の符号語を表す多項式（符号多項式） $c(x)$ をハミング重みごとにまとめた表1 を用いてよい。

表1 $G(x)$ を生成多項式とする巡回符号の次数最小の符号語を表す多項式 $c(x)$

• (3-4) 図1 のフレームの最大ペイロード長は 1500 [バイト] である。最大ペイロード長をその 10 倍の 15000 [バイト] に増やすことの利点と欠点を、巡回冗長検査の観点から簡潔に説明せよ。
• (3-5) 生成多項式 $G(x)$ を用いたバースト誤り (burst error) 検出に関する以下の文章中で、$b$ にあてはまる数値と空欄 [ ] にあてはまる多項式を書け。

フレーム内で、図2 に示すような 1 つのバースト誤りが発生したとする。その長さが $b$ [ビット] 以下であれば、確実にそのバースト誤りを検出できる。しかし、長さが $(b+1)$ [ビット] のときは、検出できない場合がある。例えば、送信フレーム（符号語）を表す多項式が 0 と等しく小問 (3-2) の多項式 $R(x)$ が [ ] と等しいときに、そのバースト誤りを検出できない。

Kai#

Summary & Insights#

NOTE

1. 传输速率 (Transfer Rate)#

• 核心公式：$\text{最大転送レート} = X \times \frac{\text{最大ペイロード}}{\text{最大ペイロード} + \text{固定オーバーヘッド}}$
• 物理意义：物理极速 $\times$ 纯货物的有效占比。
• MTU 扩大（巨型帧）的利弊：
  • 利：降低开销占比，提升吞吐量（スループット向上）。
  • 弊：长帧使得原本装不下的长跨度错误得以潜伏，误り検出能力（最小ハミング距離）低下。

2. 前导码 (Preamble)#

• 两大目的：
  1. 確立クロック同期（建立时钟/比特同步）。
  2. フレーム開始位置の特定（确定帧起始位置/字节边界）。
• 比特模式 (1010...11) 的理由：
  • 1010 交替提供高频电压跳变（エッジ），最适合 PLL 提取时钟。
  • 末尾 11 (SFD) 明确标识同步结束，数据本体开始。
• 误同步 (False Sync) 的回避：
  • 依靠物理层的インターフレームギャップ (IFG: 帧间隙)。仅在无信号状态（アイドル）后收到的首个有效跳变才被视为前导码。

3. CRC 校验与多项式 (Cyclic Redundancy Check)#

• FCS 长度法则：FCS 比特数 $\equiv$ 生成多项式 $G(x)$ 的最高次数 $r$。
• 无错判定条件：$R(x) \pmod{G(x)} = 0$ （接收多项式能被生成多项式完美整除）。
• 突发错误 (Burst Error) 的检错极限：
  • 绝对能检出：长度 $\le r$ 的所有突发错误。
  • 无法检出的特例（长度 $= r+1$ 时）：当且仅当错误多项式 $E(x)$ 与 $G(x)$ 完全相同时（即 $E(x) = G(x)$）。

🚨 盲区 1：死记数学公式，忽略了“物理空间限制”（最致命弱点）

• 症状： 看到表 1 的 $x^{91639}$ 觉得只是个数学符号，不知道怎么和“1000 字节帧长”联系起来。
• 纠正记忆： 多项式的次数 $\approx$ 电缆上的物理长度。 如果一个骗子多项式的跨度是 9万多位，而你的车厢（帧）只有 8000 位长，这个骗子就绝对塞不进你的车厢。想通“装不下就不会发生”，表 1 就变成了比大小的送分题。

🚨 盲区 2：在离散边界问题上掉入“植木算（Fencepost Error）”陷阱

• 症状： 疑惑“为什么物理长度 $L=4$，最高次幂却是 3？”
• 纠正记忆： 多项式的起点是 $x^0$，不是 $x^1$。 $x^0$ 作为一个合法的数字（1），强行占用了物理世界的一个比特位。因此，物理长度永远等于最高次幂 $+1$。遇到边界问题，立刻在脑子里画 1 _ _ 1 对应 $x^3 \dots x^0$。

🚨 盲区 3：把网络协议当成“规定”，而不是“权衡（Trade-off）”

• 症状： 需要专门解释为什么最大转发速率要用 1500 去除以 1522。
• 纠正记忆： 网络工程没有绝对的规定，全是对物理极限的妥协。想要速度快，就得加大 Payload；但 Payload 太大，CRC 检错能力就会退化（3 位的错误就能瞒天过海）。记住这组矛盾：帧越长 $\to$ 效率越高 $\to$ 检错越弱。

Author#

KardeniaPoyu

Description#

(1) 情報論理 (mathematical logic) に関する以下の各小問に答えよ. ただし, 論理式 (logic formula) の記述には以下の記号を用いる. $\to, \land, \lor, \neg$ はそれぞれ含意 (implication), 論理積 (conjunction, and), 論理和 (disjunction, or), 否定 (negation, not) を表す論理演算子とする. また, 必要に応じて $\bigwedge_{1 \le i \le n} T_i$ (あるいは $\bigvee_{1 \le i \le n} T_i$) の表記を用いる. これは論理式 $T_i$ の $i$ を 1 から $n$ ($n$ は正整数) まで順次変えながら論理積 (あるいは論理和) で結合した式を意味している. なお, $\bigwedge_{1 \le i < j \le n} T_{ij}$ は, $\bigwedge_{1 \le i \le n-1} \left(\bigwedge_{i+1 \le j \le n} T_{ij}\right)$ を意味する.

縦 $n^2$ マス $\times$ 横 $n^2$ マスで構成されるパズル (puzzle) を考える. 本パズルにおける規則は以下の通りである.

• 空いているマスに 1 から $n^2$ までの整数を入れる.
• 各列, 各行および, 太線で囲まれた $n \times n$ の各ブロック内に同じ整数を複数用いてはいけない.

図 1 は, $n = 3$ における本パズルの問題例である. 以降, このパズル問題を解くための制約式を和積形 (CNF: Conjunctive Normal Form) の命題論理式 (propositional formula) で与えることを考える. なお, 和積形とは, 一つ以上の和項の論理積で表される論理式である. また, 和項とは, 一つ以上のリテラル (literal) の論理和で表される論理式である. ここでリテラルとは, 命題変数 (propositional variable) または命題変数の否定を意味する. $i$ ($1 \le i \le n^2$) 行 $j$ ($1 \le j \le n^2$) 列のマスを $c(i, j)$ で表記する (行は上から順に $1, \dots, n^2$ 行目, 列は左から順に $1, \dots, n^2$ 列目である).

マス $c(i, j)$ に整数 $k$ ($1 \le k \le n^2$) が入っているとき, かつ, そのときのみ真となる命題変数 $x_{ijk}$ を導入する. 以下の各小問に答えよ.

• (1-1) 図 1 において命題変数 $x_{115}, x_{214}, x_{841}$ の真偽をそれぞれ答えよ.
• (1-2) 縦 $n^2$ マス $\times$ 横 $n^2$ マスで構成される本パズル問題における命題変数 $x_{ijk}$ の総数はいくつか. $n$ を用いて示せ.
• (1-3) 「1 行 1 列目のマスには, 1 以上 9 以下の整数が少なくとも一つ入る」ことを表す論理式を記述せよ.
• (1-4) CNF 式 $A(i, j)$ を「$i$ 行 $j$ 列目のマスには, 1 以上 $n^2$ 以下の整数が少なくとも一つ入る」ことを表す論理式とする. 論理式 $A(i, j)$ を記述せよ.
• (1-5) $A(i, j)$ を用いて, 「どのマスについても, 1 以上 $n^2$ 以下の整数が少なくとも一つ入る」ことを表す論理式 $A$ を示せ.
• (1-6) $\neg p \lor \neg q$ は, 「$p, q$ がともに真になるということはない」ことを表す論理式である. これを用いて「どの行についても各整数は高々1回しか現れない」ことを表す CNF 式 $B$ を作りたい. 以下の空欄を埋めることで $B$ を完成させよ.

$B = \bigwedge_{1 \le i \le n^2} \bigwedge_{1 \le j < l \le n^2} \bigwedge_{1 \le k \le n^2} (\Box)$

• (1-7) 「どの列についても各整数は高々1回しか現れない」ことを表す CNF 式 $C$ を示せ.

• (1-8) この小問では, $n = 2$ として, 図 2 の問題に着目する.

図 2 の問題では, 空いたマス (例えば 2 行 4 列目) にどのように整数を埋めても, パズルを解くことができない. ここでは, (命題 P) 「図 2 の問題では, 空いたマスにどのように整数を埋めても, パズルを解くことができない」ことを示したい. この命題 P を示すには, 「太線で囲まれた $n \times n$ のどのブロックについても各整数が高々1回現れる」ことを意味する CNF 式を $D$, 図 2 における整数の配置を表す論理式を $Assign$ としたときに, (方針) $A \land B \land C \land D \land Assign$ の CNF 式が充足不能 (unsatisfiable) であることを示せればよい。 このとき, 以下の (1-8-1)～(1-8-2) に答えよ.

• (1-8-1) 論理式 $Assign$ を示せ.
• (1-8-2) 上記の方針に沿って, 命題 P が成り立つことを導出原理 (resolution principle) 用いて具体的に示せ.

(2) 空でない有限集合 (finite set) $V$ 上の二項関係 (binary relation) $E$ について, 次のように二項関係 $R_i$ と $S_i$ ($i = 0, 1, 2, \dots$) を定義する. また, $V$ の各要素を頂点とし, $E$ の各要素を有向辺とする有向グラフ (directed graph) を $G$ とする. ただし $(u, v) \in E$ に対しては, $u$ を有向辺の始点とし, $v$ を有向辺の終点とする.

$R_0 = S_0 = \{(v, v) \mid v \in V\}$ $R_{i+1} = \{(u, v) \mid (\exists w \in V) [u R_i w \land w E v]\} \quad (i \ge 0)$ $S_{i+1} = S_i \cup R_{i+1} \quad (i \ge 0)$