24-25-1-离散数学II-期末

根据费马小定理，$5^{10} mod 11 = 1$。因此 $5^{131} mod 11 = 5 mod 11$，结果即为 5。

使用扩展欧几里得算法：

$141 \div 19 = 7 ...... 8$

$19 \div 8 = 2 ...... 3$

$8 \div 3 = 2 ...... 2$

$3 \div 2 = 1 ...... 1$

反过来，既有：

$1 = 3 - 2 = 3 - (8 - 2 \cdot 3) = 3 \cdot 3 - 8$

$= 3 \cdot (19 - 2 \cdot 8) - 8 = 3 \cdot 19 - 7 \cdot 8$

$= 3 \cdot 19 - 7 \cdot (141 - 7 \cdot 19) = 52 \cdot 19 - 7 \cdot 141$

于是结果为 52。

由上一题得知了 19 mod 141 的逆元。

于是等式两边同乘 52，得：

$19 \cdot 52 x \equiv 4 \cdot 52 \mod 141$

$x \equiv 208 \mod 141$

于是 $x=141k+67$，$k$ 为整数。

根据排列数问题的定理：

对有重复字母的词，重排种数为：总字母数! / (每种字母的个数!)之积。

我们发现 NONSENSE 中有 3 个 N，2 个 S，2 个 E 和 1 个 O，

因此结果为 $8!/(3!\cdot3!\cdot2!\cdot1)=560$。

只有 1 个 O，故先计算其他字母的排列情况数，为 210 种（方法同上题）。

然后 O 在最前和最后，共两种情况，故结果为 420。

首先我们计算所有位各不相同的三位码的总数，应该有 $10\cdot9\cdot8=720$ 种。

根据抽屉原理，应生成（5·总数+1）个数，才能保证一定存在 6 个完全相同的。故结果为 3601。

（注：本题的“三位码”指首位可以为 0。如果为“三位数”，则应只有 648 种情况，答案则为 3241）

答案：是群。

证明为群的 4 个条件：

• 封闭性：发现对任意 $\in\{0,1,2\}$ 的元素 $x, y$，$(x+y) mod 3 \in \{0,1,2\}$，故封闭性得证；
• 结合律：对任意 $\in\{0,1,2\}$ 的元素 $x, y, z$，$((x+y) mod 3 + z) mod 3 = (x+y+z) mod 3 = ( z + (x+y) mod 3) mod 3$，结合律得证；
• 存在 单位元 (identity)：我们发现对任意 $\in\{0,1,2\}$ 的元素 $x$，$(0+x) mod 3 = (x+0) mod 3 = x$，所以 0 就是单位元；
• 每个元素存在 逆元：0 的逆元是 0，1 的逆元是 2，2 的逆元是 1，所以每个元素都有逆元，得证。

答案：是群。

证明为群的 4 个条件：

• 封闭性：发现对任意 $\in\mathbb Q$ 的元素 $x, y$，$x+y-2$ 仍然是有理数，所以满足封闭性；
• 结合律：对任意 $\in\mathbb Q$ 的元素 $x, y, z$，$((x+y-2)+z-2)= (x+y+z-4) =(x+(y+z-2)-2)$，结合律得证；
• 存在 单位元 (identity)：我们发现对任意 $x$，$(2+x-2)=(x+2-2)=x$，所以 2 就是单位元；
• 每个元素存在 逆元：$x+(y-2)=2$，所以 $y=4-x$ 就是 $x$ 的逆元。

本题没有指出 $\{0,1\}$ 上的运算。但我们不妨梳理相关知识点：

• 要判断这种映射是否为同态，我们只需判断映射是否具有保运算性：$\mathbb Z$ 中两个数 $a, b$ 的和在 B 中的像是否与 $a', b'$ 在 B 中运算的结果是否相等；
• 要求 $ker(f)$，我们需要求出所有满足 $f(a)=e'$ 的 $\mathbb Z$ 中元素 $a$；
• $\mathbb Z/\ker(f)$ 即 $\mathbb Z$ 关于 ker(f) 的商群，即 ker(f) 在 A 中所有左陪集构成的集合。设 $\mathbb Z$ 中的元素为 $x$，则商群中的每个元素即为 {x+y|y∈ker(f)}。商群中的元素可使用 [该元素中的某一元素] 表示。

构造群码的方法：

1. 找出所有的原码，此题中为 000、001、…111；
2. 将每个原码与一致性检验矩阵前 m 行（此题中为前 3 行）的每一列计算模 2 点积（即按位与后，计算各位和再模 2），得出的结果组成的向量就是码字的后 r 位；

（例如，在本题中，110 与矩阵前三行的第一列按位与，结果为 100，各位和模 2 的结果为 1；与第二列按位与，结果为 000，各位和模 2 的结果为 0；与第三列按位与，结果为 110，各位和模 2 的结果为 0；因此 e(100) 的后三位为 100）

3. 在每个原码的后面加上步骤 2 中的后 r 位，即为结果。

本题的答案应为：

$e(000)=000000$

$e(001)=001110$

$e(010)=010001$

$e(011)=011111$

$e(100)=100101$

$e(101)=101011$

$e(110)=110100$

$e(111)=111010$

此题应使用极大似然规则进行译码。

对于每一个接收到的序列，计算其到每个码字的汉明距离（不同位的个数），取汉明距离最小且原码值最小的码字作为实际收到的码字，并写出相应的原码。

计算步骤：

1. 让序列与所有码字进行按位运算，所得的结果的集合即为左陪集；
2. 找出左陪集中权值（weight）最小的元素，即为陪集头；
3. 陪集头与一致性检验矩阵做模 2 点积，所得结果即为特征值。

$S \rightarrow 1S0 \rightarrow 10A0 \rightarrow 1000$

我们发现，S 要么直接变为 1，要么变为 0…01，其中 0 的个数不限。

因此，直接写出语言：

$L(G)=\{0^n1 \mid n=0, 1, 2...\}$

首先我们发现句子可能为空。因此存在生成规则 $S \rightarrow \lambda$；

然后我们不妨从对称角度思考，将 $0^m 1^n 2^{m+n}$ 拆为 $0^m 1^n 2^n 2^m$；

为了生成左端的 $0^m$ 和右端的 $2^m$，需要存在产生规则 $S \rightarrow 0S2$；

同时为了在需要时能终止外侧的 0 和 2 延伸，需要存在切换到内侧的机制 $S \rightarrow A$；

为了生成内侧的 $1^n 2^n$，需要存在产生规则 $A \rightarrow 0A2$；

此外，由于 n 也可能为 0，所以加上规则 $A \rightarrow \lambda$。

综上，产生规则集合 P 为 $\{ S \rightarrow \lambda , S \rightarrow 0S2, S \rightarrow A, A \rightarrow 1A2, A \rightarrow \lambda \}$。

所有词语组成的集合 V 为 $\{ S, A, 0, 1, 2 \}$。

所有终结符组成的集合 T 为 $\{ 0, 1, 2 \}$。

所有起始符组成的集合 S 为 $\{ S \}$。

文法即为 $G=(V, T, S, P)$。

首先观察状态转移图，我们发现被这种状态机接收的语言须满足：含有且只含有 2 个“1”，此外可以含有任意多的“0”。

因此我们写出语言：$\{0^l 1 0^m 1 0^n \mid l \ge 0, m \ge 0, n \ge 0\}$。

文法的产生规则集合 P 为：$\{ S \rightarrow A1A1A, A \rightarrow 0A, A \rightarrow \lambda \}$；

所有词语组成的集合 V 为 $\{ S, A, 0, 1 \}$；

所有终结符组成的集合 T 为 $\{ 0, 1 \}$；

所有起始符组成的集合 S 为 $\{ S \}$；

文法即为 $G=(V, T, S, P)$；