吴紫航

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ## 15.1 ### (1) 基于矩阵的算法实现： + 矩阵每个位置存放着两个元素的等价关系 + 初始化矩阵的时候考虑自反性 + 判断两个元素是不是在一个并查集中，开销 + 两个元素并操作，，先遍历的第行，对于满足的，把第行加到第行；再遍历的第行，对于满足的，把第行加到第行；

正确性证明：主要考虑，是不是同一个等价类中任意一对元素，在矩阵中都是，那么用数学归纳法证明，因为查不会改变矩阵，那么对并操作进行归纳推理。 + 初始情况，满足 + 假设进行了次并操作，命题成立，则再进行一次并，两个元素各自所在的等价类的内部自然已经满足命题，那么再考虑从两个等价类中分别取一个元素，在算法完成后矩阵对应位置改成了

时间复杂性：每次最多是线性遍历2次，算法复杂度，开销主要是矩阵的行运算

(2)

基于数组的算法实现： + 数组每个位置存放对应代表元的下标 + 查操作，即反复查找其代表元，直到到达根为止，单次查最坏情况是线性的 + 并操作，即找到的根下标，然后把p挂到q上，即令，单次操作复杂度最坏情况也是线性的 + 总的复杂度是

支配集

支配集(控制集)

• 是支配集：
• 极小支配集：任何真子集都不是支配集
• 最小支配集：顶点数最小
• 支配数：最小支配集的势

支配集与匹配

• 从完美匹配中的每条边任取一个端点构成一个支配集
• 从最大匹配中的每条边中存在一个端点的取法构成支配集

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ## 6.2 二分查找的区间范围设为，并假定每轮开始时都已经知道以下四个变量的值： + + + +

则比较和的大小以后，可以以的代价更新上面的变量，以进入左半边子区间为例 + + + +

这样把单次的开销降到常数，总的开销就是

6.3

思路是对递归定义使用数学归纳法，以证明始终符合直接定义。

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ## 5.2 假设5个数分别为。找中位数就是找第3小的数。

• ，若则，使得

• ，若则，使得

• ，若则，使得，且不影响，此时比至少3个数小，故不可能是第3小的数，于是接下来考虑中第2小的数

• ，若则，使得

• ，若则，使得，且不影响。故此时是四个数中的最小值，不可能是第2小；又比都大，故也不可能是第2小。故接下来考虑中较小的那个即可

• ，较小的那个是中位数

如果用决策树表示这个算法，每个非叶节点给出哪两个数之间比较，两个不同的比较结果分别导向左右子树。

最后一层比较得到的较小者就是中位数，由于画的太密集，叶子节点没有画出来。

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ## 14.1 + 是第h个节点的父节点 + 是第h个节点的层数 + 是第h个节点的父节点的层数 + ，因为的层数比父节点的层数多一层

14.2

取堆的前层即可，找第大的数，复杂度，和无关

14.3

D-ARY-PARENT

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ## 7.1 用朴素的两层遍历当然可以，也可以基于归并排序或堆排序进行改进。

7.4

(1)

一般不作说明的要求分析复杂度，考虑最坏情况即可：

(2)

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ## 4.1 利用数学归纳法即可，本题的归纳推理除了个人推荐的自顶向下的方式，也可以自底向上。 + 的情况，只有一个根节点， + 假设的情况，k是非负整数，有命题成立，则对于任意的情况，可以把这个树分解为根节点和左右子树，这里有左右子树的树高不超过k显然成立 ，则叶子总数量。 + 故命题成立

4.4

注意体会这两道题的区别，和解答思路的区别 1）只需要给出一个满足条件的算法，最坏情况用5次比较对4个元素排序，我们知道可以花3次比较来确定其中三个数的序关系，即。记排序后的三个数为，则对于最后一个数的序，我们第4次比较把它和中位数进行比较，无论比较结果如何，至少能确定和其中的2个的序关系，然后第5次比较留给最后一个不确定的序关系即可。

具体算法的规范书写从略。

2. 本题不光要找到一个算法，对5个元素进行排序，并且要证明在最坏情况下这个方法是最优的。那么理论上就需要穷尽所有的比较方法，然后找到其中最优的方法。个人尝试了一下决策树和穷举的思路，过于复杂，这里推荐另一种思路：先放缩得到算法比较次数的下界，再给出最坏情况下能取到下界比较次数的算法。

中国邮递员问题

最优邮路

求赋权连通图中含有所有边且权和最小的闭途径

Euler图

• Euler迹：经过每条边恰好一次的迹
• Euler闭迹：经过每条边恰好一次的闭迹
• Euler图：有Euler闭迹的图
• Euler图的最优邮路：即Euler闭迹

Abstract

对于和训练集同分布的数据，深度神经网络已经获得了惊人的性能，但对于其他数据集性能会明显变差。因此，检测一个样本是不是OoD对于能拒绝或警示这种样本的系统是重要的。包含 一些小数据集的OoD benchmarks下的工作在近期已经取得了巨大的进展。然而，这些方法很多都需要神经网络训练、调参的时候同时有in-distribution和out-of-distribution的数据。后者是难以先验定义的，不同的OoD数据会产生不同的学习效果。本文的工作基于一个流行的方法：ODIN。这个方法提出两个重要的策略，不需要OoD的数据，同时改进了OoD的检测性能。本文具体的提出了分解置信度的方法以及改进input preprocessing的方法。本文展示了这两者都得能显著提高检测OoD的性能。并且，作者在更大规模的图像数据集上进行了分析，表明数据的分布迁移有两种：语义迁移和非语义迁移。这两者会让问题的难度变得非常不同，这提供了一个关于ODIN-like的策略何时能有效的分析。

Introduction

先进的机器学习模型，具体来说是深度神经网络，通常在静态封闭世界假设下设计的。这些模型需要引入测试集和训练集独立同分布的假设。在真实世界，数据分布会以复杂和动态的方式进行迁移。更坏的是，新概念（如新的分类对象）可能在任何时刻输入到模型中。这样的类内的迁移或者是新概念的数据都会导致灾难性的失败，因为模型依然是基于封闭世界假设来预测的。这些失效经常是无声的，模型不会输出明显的错误。

以上的问题已经被规范为一个检测问题，即判断一个输入数据是不是in-distribution的数据，或者是out-of-distribution。这个问题已经被研究了很多年，也以各种观点被讨论了，例如rejection, anomaly detection, open set recognition, uncertainty estimation。最近几年，一个流行的基于神经网络检测的baseline使用了类别的后验概率（即softmax）的最大值，这个方法可以在有些情况是一个良好的区分in-distribution和out-of-distribution的指示器。

面向二部图的增广路算法

算法思路

• 搜索一条增广路
• 如果找到了：替换得到更大的匹配，返回1
• 否则结束

算法细节

1. 每轮从二部图的任意一侧的不饱和顶点开始，搜索增广路，以左侧为例。
2. 左侧到右侧，找不在匹配中的边；右侧到左侧，找在匹配中的边。
3. 如果找到一个不是起点的未饱和顶点 则找到增广路 替换得到更大的匹配 转到5。
4. 或深度优先搜索完所有的点和边，仍未找到增广路 本轮没找到增广路 转到5。
5. 如果左侧还有不饱和的顶点没有搜索过，则转到1进入下一轮搜索。