供南开大学计算机学院和网络空间安全学院期末复习使用

免责声明：本人水平有限，笔记难免有错误，请理性使用，切莫完全相信本笔记的所有内容。

分值分配：课上随堂测试考核(10%)、研讨内容(10%)、实验内容考核(40%)和期末考试(40%)

期末考试：30道选择题（每小题2分）4道简答题（每小题5分）2道解答题（每小题10分）

第八章 博弈

知识点

博弈相关概念

玩家 () ：参与博弈的决策主体 策略 () ：玩家可以采取的行动方案，是一整套在采取行动之前就已经准备好的完整方案。

• 某个玩家可采纳策略的全体组合形成了策略集 ()
• 所有玩家各自采取行动后形成的状态被称为局势 ()
• 混合策略 (): 玩家可通过一定概率来选择若干个不同的策略
• 纯策略 (): 玩家每次行动都选择某个确定的策略

收益 () ：各个玩家在不同局势下得到的利益

• 混合策略意义下的收益应为期望收益 ()

规则 () ：对玩家行动的先后顺序、玩家获得信息多少等内容的规定

囚徒困境：警方逮捕了共同犯罪的甲和乙，但没有掌握充分证据，将他们分开审讯，并告诉他们如下事实：

• 若一人认罪并指证对方，而另一方保持沉默，则此人会被当即释放，沉默者会被判监禁年
• 若两人都沉默，则根据已有的犯罪证据两人各判半年
• 若两人都认罪并相互指证，则两人各判年

在囚徒困境中，最有可能的判决就是两个人都指认对方，都获得五年的监禁

最优解为两人同时沉默；但是两人实际倾向于选择同时认罪 (均衡解)

博弈的分类：

• 合作博弈与非合作博弈
• 静态博弈和动态博弈
• 完全信息博弈与不完全信息博弈

博弈的稳定局势即为纳什均衡 ()

任何玩家单独改变策略都不会得到好处，也就是说当所有其他人都不改变策略时，没有人会改变自己的策略

定理：若玩家有限，每位玩家的策略集有限，收益函数为实值函数，则博弈必存在混合策略意义下的纳什均衡

纳什均衡的本质就是不后悔

遗憾最小化算法

若干定义

• 玩家所采用的策略为，一个策略组包含所有玩家的策略，
  • 玩家的策略空间用表示
  • 表示中除了之外的策略
• 玩家在给定策略下的期望收益为：

策略选择

根据过去博弈中的遗憾程度来决定动作选择的方法

玩家在过去T轮中采取策略的累加遗憾值为 在第轮次玩家选择策略的概率如下（悔值越大越选择）

遗憾最小化例子：见：石头剪刀布

供南开大学计算机学院和网络空间安全学院期末复习使用

免责声明：本人水平有限，笔记难免有错误，请理性使用，切莫完全相信本笔记的所有内容。

分值分配：课上随堂测试考核(10%)、研讨内容(10%)、实验内容考核(40%)和期末考试(40%)

期末考试：30道选择题（每小题2分）4道简答题（每小题5分）2道解答题（每小题10分）

第五章 无监督学习

知识点

无监督学习，就是不给​的值，只分类，但是我们不知道其具体的语意

监督学习的特征：

无监督学习的特征：

可以看出我们的监督学习是对我们的数据进行了分类，并且能够得知其类别；无监督学习只能起到分类的作用

我们的无监督学习有自己的相似度函数，比如说对上面的六个东西进行分类，我们根据颜色和形状，分类出来的结果是不一样的

K均值聚类(K-Means)

算法原理

输入：个数据，并且没有任何的标注

输出：个聚类结果

我们的目标是，将个维的数据分为个聚簇，使得簇内方差最小化

两个维数据之间的欧氏距离为 我们的欧氏距离越小，就说明我们类内越相似，反之欧氏距离越大就是类内越不相似

K-means聚类算法步骤

1. 初始化聚类质心
   • 初始化个聚类质心，
   • 每个聚类质心所在集合记为
2. 将每个待聚类数据放入唯一一个聚类集合中
   • 计算待聚类数据和质心之间的欧氏距离
   • 将每个放入与之距离最近聚类质心所在聚类集合中，即
3. 根据聚类结果，更新聚类质心
   • 根据每个聚类集合中所包含的数据，更新该聚类集合质心值，即：
4. 算法循环迭代，直到满足条件
   • 循环步骤
   • 终止条件：达到迭代次数上限，或者前后两次迭代中，聚类质心基本保持不变

聚类算法的缺点

• 需要事先确定聚类数目
• 需要初始化聚类中心，而且会对结果产生很大的影响
• 算法是迭代执行，时间开销非常大
• 欧式距离假设数据每个维度之间的重要性是一样的

K均值聚类算法的应用：图像压缩，文本分类等

主成分分析(PCA)

是一种特征降维的方法，我们在过程中会将其化繁为简，降低我们的特征维数

方差

方差等于各个数据与样本均值之差的平方之和之平均数

方差描述了样本数据的波动程度 其中是我们的样本均值

协方差

我们用协方差来衡量两个变量之间的关系

• 当协方差 时，称与正相关
• 当协方差时，称 与负相关
• 当协方差时，称与不相关（线性意义下）

为了归一化处理，我们采用了皮尔逊相关系数来对其进行约束 皮尔逊相关系数的性质如下：

• 越大，线性相关度越大
• 的充要条件是存在常数和，使得
• 表示两者不存在线性相关关系（可能存在其他非线性相关的关系）
• 正线性相关意味着变量增加的情况下，变量也随之增加；负线性相关意味着变量减少的情况下，变量随之增加。

相关性与独立性：

• 如果X和Y的线性不相关，则
• 如果X和Y的彼此独立，则一定，且X和Y不存在任何线性或非线性关系

在降维之中，需要尽可能将数据向方差最大方向进行投影，使得数据所蕴含信息没有丢失，彰显个性

我们需要保证我们投影后，得到的样本方差最大，这样就不会丢失其中的信息

假设我们有个维的样本数据，构成集合

所以我们的集合可以表示成一个的矩阵

我们使用一个映射矩阵

所以我们的给定的样本可以通过映射矩阵进行降维，从维降到了维

我们用拉格朗日来进行求解

目标函数： 约束条件： 拉格朗日函数： 得到结果：

算法描述：

• 输入： 个维样本数据所构成的矩阵，降维后的维数
• 输出：映射矩阵

步骤：

1. 对于每个样本数据进行中心化处理：
2. 计算原始样本数据的协方差矩阵:
3. 对协方差矩阵进行特征值分解，对所得特征根按其值大到小排序
4. 取前个最大特征根所对应特征向量组成映射矩阵
5. 将每个样本数据按照如下方法降维：

特征人脸方法

我们也是使用主成分分析的方法，来进行特征降维

算法步骤：

跟前面的主成分分析是一样的，降维就可以了

将每幅人脸图像转换成列向量，如将一幅的人脸图像转换成的列向量

我们输入的是的列向量构成的矩阵，和我们降维之后的维数

输出是我们中间的映射矩阵

使用个特征人脸的线性组合来表达原始人脸数据

期望最大化算法(EM)

分为两个步骤，第一个是求取期望，第二个是期望最大化

• 在算法的步骤时，先假设模型参数的初始值，估计隐变量取值；
• 在算法的步骤时，基于观测数据、模型参数和隐变量取值一起来最大化“拟合”数据，更新模型参数。
• 基于所更新的模型参数，得到新的隐变量取值（算法的步），然后继续极大化“拟合”数据，更新模型参数（算法的步)。以此类推迭代，直到算法收敛，得到合适的模型参数。

具体例子见：书本页：二硬币投掷例子

算是CTF密码学的入门部分了，各大赛事有时候会出一个当签到题，基本也都能用随波逐流工具一把梭，所以一些算法的脚本也就基本用不上了，但是还是记录一下。

凯撒密码

凯撒密码（Caesar）加密时会将明文中的 每个字母 都按照其在字母表中的顺序向后（或向前）移动固定数目（循环移动）作为密文

举个例子，如果偏移量为3的话，那就是将明文的每个字母都往后移动3位，如果超出z了就往前重复，相当于一个模26的域

1 2	明文：ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文：DEFGHIJKLMNOPQRSTUVWXYZABC

根据偏移量的不同，还存在若干特定的恺撒密码名称：

• 偏移量为 10： Avocat （A→K）
• 偏移量为 13： ROT13
• 偏移量为 -5： Cassis （K→6）
• 偏移量为 -6： Cassette （K→7）

一般用的比较多的就是ROT13加密了，就是移动13位，没啥好说的

加密脚本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

def encrypt_caesar_cipher(plaintext):
    def shift(text, n):
        result = ""
        for char in text:
            if char.isalpha():
                shift = ord(char) + n
                if char.islower():
                    if shift > ord("z"):
                        shift -= 26
                    elif shift < ord("a"):
                        shift += 26
                elif char.isupper():
                    if shift > ord("Z"):
                        shift -= 26
                    elif shift < ord("A"):
                        shift += 26
                result += chr(shift)
            else:
                result += char
        return result

    print("尝试所有可能的位移：")
    for i in range(1, 26):
        print(f"位移 {i}: {shift(plaintext, +i)}")


if __name__ == "__main__":
    plaintext = input("请输入凯撒密码的明文：")
    encrypt_caesar_cipher(plaintext)

解密脚本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

def decrypt_caesar_cipher(ciphertext):
    def shift(text, n):
        result = ""
        for char in text:
            if char.isalpha():
                shift = ord(char) + n
                if char.islower():
                    if shift > ord("z"):
                        shift -= 26
                    elif shift < ord("a"):
                        shift += 26
                elif char.isupper():
                    if shift > ord("Z"):
                        shift -= 26
                    elif shift < ord("A"):
                        shift += 26
                result += chr(shift)
            else:
                result += char
        return result

    print("尝试所有可能的位移：")
    for i in range(1, 26):
        print(f"位移 {i}: {shift(ciphertext, -i)}")


if __name__ == "__main__":
    ciphertext = input("请输入凯撒密码的密文：")
    decrypt_caesar_cipher(ciphertext)

Atbash Cipher

埃特巴什码(Atbash Cipher)，它使用字母表中的最后一个字母代表第一个字母，倒数第二个字母代表第二个字母。

1
2

明文：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
密文：Z Y X W V U T S R Q P O N M L K J I H G F E D C B A

加密例子：

1 2	明文：the quick brown fox jumps over the lazy dog 密文：gsv jfrxp yildm ulc qfnkh levi gsv ozab wlt

直接随波逐流一把梭就行，2024的国赛就考了这个加密

简单替换密码

加密时，每个明文都有自己对应的密文，而且不是简单的移位，是混乱的。

举个例子：

1 2 3 4

明文: abcdefghijklmnopqrstuvwxyz 密钥: phqgiumeaylnofdxjkrcvstzwb a对应p,b对应h

一般用词频分析破解：http://quipqiup.com/

或者还是随波逐流一把梭

仿射密码

加密函数： \[ E(x)=(ax+b)\;mod \; m \] 其中，\(x\)是我们的原文，\(E(x)\)是我们的密文。\(a\)和\(m\)必须满足： \[ gcd(a,m)=1 \]

\(m\)是我们整个仿射体系中的编码个数，为什么要互素呢？根据数论的知识不难得知，如果不互素的话，就找不到逆元了

那么，我们的解密函数也就很明显了： \[ D(x)=a^{-1}(x-b)\;mod \; m \] 其中，\(a^{-1}\)是\(a\)的逆元

Playfair密码

原理：

1. 选取一串英文字母，除去重复出现的字母，将剩下的字母逐个逐个加入 5 × 5 的矩阵内，剩下的空间由未加入的英文字母依 a-z 的顺序加入。注意，将 q 去除，或将 i 和 j 视作同一字。
2. 将要加密的明文分成两个一组。若组内的字母相同，将 X（或 Q）加到该组的第一个字母后，重新分组。若剩下一个字，也加入 X 。
3. 在每组中，找出两个字母在矩阵中的地方
   • 若两个字母不同行也不同列，在矩阵中找出另外两个字母（第一个字母对应行优先），使这四个字母成为一个长方形的四个角。
   • 若两个字母同行，取这两个字母右方的字母（若字母在最右方则取最左方的字母）
   • 若两个字母同列，取这两个字母下方的字母（若字母在最下方则取最上方的字母）

新找到的两个字母就是原本的两个字母加密的结果。

举个例子：

以 playfair example 为密匙，得

1 2 3 4 5

P L A Y F I R E X M B C D G H K N O Q S T U V W Z

要加密的讯息为 Hide the gold in the tree stump

1	HI DE TH EG OL DI NT HE TR EX ES TU MP

加密后密文：

1	BM OD ZB XD NA BE KU DM UI XM MO UV IF

加解密网站：http://www.metools.info/code/playfair_186.html

Polybius

ADFGX密码

Vigenere

Nihilist

Hill

Autokey Cipher

培根密码

栅栏密码

曲路密码

列位移密码

01248密码

JSFuck

BrainFuck

Ook

猪圈密码

舞动的小人密码

键盘密码

古埃及象形文字

宝可梦图腾

精灵语

古精灵语

夏多密码

圣堂武士密码

盲文

外星人密码

音乐密码

标准银河密码

天干地支表

摩斯密码

玛雅数字

原神密码