0%

注: 本题解为个人完成,难免有疏漏,请勿抄袭,仅供参考,同时欢迎留言指正。 ## 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次比较留给最后一个不确定的序关系即可。

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

  1. 本题不光要找到一个算法,对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进入下一轮搜索。
阅读全文 »