吴紫航

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ##3.2 ###(1) 大概说一下证明思路，用类似于数学归纳法的写法(基本情况+归纳推理)来证明循环不变量即可。

1. 对于内循环，循环不变量是：

在循环结束时，始终比中的元素大；

2. 对于外循环，循环不变量是：

在循环结束时，部分按从小到大排好序了。

匹配

• 匹配：M是G的匹配：G中两两不相邻边构成的集合
• 被饱和的顶点：M中边的端点被M饱和

完美匹配

• 所有顶点都被饱和的匹配
• 阶是偶数
• 包含阶数的一半的边数
• 包含 个不重的完美匹配

最大匹配

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ##2.2 证明：对于任意整数,都存在非负整数，使得。

则

又

故对于任意整数都有

##2.5 本题直接证明第二问即可 证明:利用数学归纳法，很容易证明二叉树的边数比点数少一个。

数学运算背后的算法操作

注： 本题解为个人完成，难免有疏漏，请勿抄袭，仅供参考，同时欢迎留言指正。 ##1.1 ###(1) 算法设计 ###(2) 本问针对个人设计的算法，假设所有输入等可能出现，则： + 有可能性, 序最大, 进行第2、5行比较; + 有可能性, 序不为最大, 进行第2、5、7行比较;

最坏情况 需要进行3次比较。 平均情况 需要进行次比较

###(3) 本问求最坏情况(面向所有输入)比较次数的下界(面向所有算法)。 即

易得结果为3次，下面给出严格证明，分为两个步骤： + 存在一个可行算法，使得最坏输入情况的比较次数等于3; + 不存在一个可行的算法，最坏输入情况的比较次数都小于3。

前者用举例证明：如第1小问设计的算法，最坏情况的比较次数就是3; 后者用反证法：假设某可行算法进行了不到3次比较，通过改变输入，可以使得3个整数中至少有1对整数之间的序关系是未知的，那么就需要进行3次比较，产生矛盾。因此后者得证。 综合上述，最坏情况比较次数的下界为3次。

2-连通图的性质

块

G是块：G是无割点的连通图 H是G的块：H是G中极大无割点连通子图

块的等价定义(G是的连通图)

• G是2-连通的(块)
• G的任二顶点共圈
• G的任一顶点与任一边共圈
• G的任二边共圈
• 对 及 存在 路含有边
• 对 ，存在 路含有顶点
• 对 ，存在 路不含有顶点

割点和割边

割点定义

割点的一个定理

如果点v是简单图G的一个割点，则边集可划分为两个非空子集和，使得边导出子图和恰好有一个公共顶点v。

Double Counting Principle

数学含义

###lemma定理：

lemma定理的证明:定义一个矩阵，行是顶点，列是边，当一个顶点是边的端点，则矩阵对应位置为1。使用double counting principle即可证得lemma定理。

基本概念

图

定义：一集元素和它们之间关系的二元组(V,E)，其中集合V称为顶点集，集合E是V中元素组成的某些无序对的集合，称为边集，顶点的数目称为图的阶，边的数目称为图的边数。

图示

定义：点表示顶点，线段表示边，绘制出平面表示图。

Abstract

本文考虑神经网络中图像的OoD的检测问题。作者提出了ODIN方法，这个方法的好处是不用对训练好的网络进行任何的更改。本文的理论基于两个手段————temperature scaling和input perturbation。这两个手段可以加大ID和OoD的softmax分布的差异，有助于检测。作者通过一系列的实验证明ODIN的方法对于各种网络结构和数据集都是兼容的，并且性能远好于baseline，可以称得上是一个state-of-the-art的方法。例如，设置网络架构为DenseNet，数据集为CIFAR-10和Tiny-ImageNet，ODIN相比于baseline把FPR at 95% TPR从34.7%降低到4.3%。

Introduction

现代神经网络在训练集和测试集样本来自同一个分布的时候效果很好。但现实世界部署的时候，往往测试集的分布是不受控制的。最近的工作表明，即使是输入不相关的数据，神经网络的预测结果也会偏高。对于分类器来说，遇到没见过的输入时给出一个不确定的反馈非常重要。因此，精确的检测OoD样本在视觉识别任务的实践中非常重要。

一个看上去比较直接的OoD检测方式就是扩大In-Distribution集合和Out-of-Distribution集合的规模。而OoD的数据往往是很有限的，这让再训练变得昂贵且难以处理。此外，为了确保神经网络在准确的给ID进行分类的同时，也能正确的检测出OoD,可能需要很大的神经网络架构，这使得训练过程更加复杂。