Blogs

次水平集和超水平集次水平集定义对于 的次水平集是 性质 是凸的 是凸的 但是反过来不成立 超水平集定义对于 的超水平集是 性质 是 concave 是 convex DefinitionDefine the epigraph of function as Property is convex is convex is convex is concave

Sublevel setsDefinitionif is convex is convex Superlevel setsDefinitionif is concave is convex

什么是Block Cipher依赖工作流（Mode of operation），加密定长明文的算法 常见的工作模式ECB 模式按照可加密的长度切分明文之后，直接进行加密因为该模式可能泄露明文之间的关系，可被选择明文攻击不应该使用 CBC 模式每次先把明文和一个随机生成的 做异或，然后放到函数 里面做加密，得到结果 使用 再输入 做加密得到下一段密文 优点 加密是基于概率的 如果函数 满足PRF 安全，那么CBC模式满足CPA安全，即豁免选择明文攻击 缺点 整个加密流程是串行（sequential）的，并且无法进行并行化 OFB 模式首先生成随机的串，经过 加密之后作为输入传给下一个 同时用作密钥给明文做异或操作。 优点 密钥生成的部分是可以预处理的，所以理论上可以更快 函数 不要求是可逆的（因为此时其实只需要正向运用 得到每一次的密文就可以了） 如果函数 是满足 PRF 的，那么加密算法满足 PCA 安全 CTR 模式首先生成一个串 ctr 然后依次使用 作为输入给 获得密钥对对应的明文进行加密 优点 如果函数 是满足 PRF 的，那么加密算法满足 PC ...

m路搜索树定义一般定义：一棵 m 路搜索树, 它或者是一棵空树, 或者是满足如下性质的树： 根最多有 m 棵子树, 并具有如下的结构： 其中， 是指向子树的指针，； 是关键码，。 在子树 中所有的关键码都小于 ，且大于 ，。 在子树 中所有的关键码都大于 在子树 中的所有关键码都小于 子树 也是 路搜索树，

DefinitionA set is convex if for any , any , we have How to judge whether a set is convexWay 1The first way is to use the Definition![[Convexity#Definition]] Way 2The second way is that a set is convex if and only if the intersection intersection with an arbitrary line is convex. That is to say, if we let and let we would have which becomes a one-variable function. We could only consider the convexity of . Note: The here represents the starting point of a line and the vector represents ...

Proper cone真锥是满足以下定义的锥 K is convex K is closed K is solid, which means it has nonempty interior K is not pointed, which means that it contains no line ()We will used the Proper cone to define the generalized inequality. Generalized inequalityDefine the generalized inequality with a proper cone is belowand define a strict partial order by

Dual coneDefinitionDual cone of a given cone K is Property is convex even if is not. if and only if is the normal of a hyperplane that support at the origin换句话说，只有当向量 是锥 的在顶点处的一个支撑超平面的法向量的时候，才会属于它的对偶锥，如图形象一些理解的话，就是想象一个原来的锥  ，然后对偶锥就是对两条边界射线做垂线，这两条垂线内部就是对偶锥。 implies if has nonempty interior, then is pointed Dual Generalized Inequalities![[Cone#Generalized inequality]] if and only if for all Proof Dual Characterization of Minimum Elementx is the minimum element of , with respect t ...

定义 if convex if 定义域是凸的 满足 感性理解：任意的直线在函数上方 if strictly convex if 定义域是凸的 满足 和上面那个只差一个负号 特殊性质仿射函数既是凸函数，又是凹函数 基于导数的其它定义方式First-order condition如果函数 是可微的，那么函数 是凸的当且仅当 is convex For all Second-order condition如果 是二阶可微的，那么 是凸的当且仅当 的定义域是凸的 For all 这里的 是Hesson矩阵，考虑是不是正定的 判定方法0阶条件定义法：利用定义域中所有的直线和它相交![[image/Pasted image 20231109200631.png]]注意，这里的 中的 是任意一个 1阶条件![[image/Pasted image 20231109200748.png]] 2阶条件![[image/Pasted image 20231109200833.png]]

B树的的相关知识依赖m路搜索树：[[m路搜索树]] 定义一棵 m 阶B_树是一棵 m 路搜索树，它或者是空树，或者是满足下列性质的树： 根结点至少有 2 个子女 除根结点以外的所有结点 (不包括失败结点)至少有 个子女 所有的失败结点都位于同一层。Note: 失败结点：是当搜索值x不在树中时才能到达的结点注意：事实上，在B树的每个结点中还包含有一组指针D[m]，指向实际对象的存放地址。K[i]与D[i] 形成一个索引项(K[i], D[i])，通过K[i]可找到某个对象的存储地址D[i]。 搜索时间分析B树的搜索时间分为两种情况考虑 搜索成功所需的时间：取决于关键码所在的层次 搜索不成功所需的时间：取决于树的高度。 插入节点的方法 B树是从空树起，逐个插入关键码而生成的 在B树，每个非失败结点的关键码个数都在之间。 插入在最底层的非失败结点开始。如果在关键码插入后结点中的关键码个数超出了上界 m-1，则结点需要“分裂”，否则可以直接插入 插入时节点分裂的方法设结点 p 中已经有 m-1 个关键码当再插入一个关键码后结点中的状态为  其中 , 这时必须把结点 p 分裂成两个结 ...

Definition 节点是红色或者黑色 根节点是红色 叶子节点是黑色 红色节点不能有红色子节点 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（简称黑高） ARB and RBARB(Almost red-black tree) 和红黑树的区别就是根节点是红色 Black heightThe black height of any or is well defined. which is the number of black nodes. 和B树的关系可以把同一层（两个红色节点链接在一个黑色节点后面记为一层）的红色节点和黑色节点放到一起，相当于就是一个2-4 B树 修复的基本操作红黑树的修复是通过变色、左旋和右旋三种操作组合而成的，关于旋转的操作详见[[AVL#AVL树基本结构]] 插入流程插入的概略过程： 先插入一个结点 将插入的结点标记为红色（Black height constraint仍然成立） 在保证Black height constraint的情况下，调整颜色和结构，使得Color constraint成立在插入节点之后，可能RBT的性质被破坏了 ...