Blogs

Introduction强化学习的基本思想是从与环境的互动中学习，与其他学习方式最大的两个区别就是： trial-and-error search delayed reward 基本元素 policy reward signal value function a model of environment policy指agent每次在特定的时间下选择action的策略 reward signal指的是整个强化学习的目标，每一次做出决策之后，环境都会给予一个反馈，这里的reward signal是及时反馈 value function这里的value function是长期的反馈，是用于衡量一个决策的长期收益的。 value的定义是指未来获得的奖励(reward)的总和的期望。value是基于reward的，只有有reward才能衡量value Modelmodel是用来模拟环境变化的，是用来做计划的，强化学习算法可以分为model-based和model-free的

SOCP问题![[image/Pasted image 20231116141755.png]] Robust Linear Programming![[image/Pasted image 20231116141315.png]]问题： 这里有无穷个约束，并且不可明确写出到底是哪些约束 所以这个就不是一个线性规划问题了解决方法： 取出上确界即可![[image/Pasted image 20231116141551.png]]后面那个是由于同方向的时候整个内积取最大值最后可以化成一个SOCP问题![[image/Pasted image 20231116141659.png]] Geometric ProgrammingMonomial Function（单项式）![[image/Pasted image 20231116141938.png]] Posynomial Function（正项式）![[image/Pasted image 20231116142008.png]] GP问题（几何优化问题）![[image/Pasted image...

和与差的分布和的分布函数公式被称之为卷积公式： 设 为二维随机变量，其联合密度为 求 的密度函数 ： 有按照 形区域积分，有做变量替换，令 有所以有 商与积的分布设 则设 则下面给出一个乘法的证明求导得 min 和 max 的分布令 ， 那么他们的分布函数为注意，这里只能用分布函数来做运算，不能直接通过密度函数得出对应点的密度 同理

带函数的期望一维形式设 是随机变量 的韩云 ，（ 连续） 若 是离散型，分布律为 那么若 收敛那么变量 的数学期望为 若 是连续行随机变量，其密度函数为 若对应的级数是绝对收敛的，那么有 二维形式设随机变量 的函数 是一个随机变量，那么 若 是离散型随机变量，那么有 若 为连续性随机变量，那么有 做题技巧如何处理带最小值的期望例如习题4.9 带最小值的期望不好用每一个部分的贡献加起来求，因为每一个部分的贡献是不确定的，最好的方式是求出最小值 的变量 的概率，然后直接用 求 而这道题里面最重要的就是 的密度函数怎么求，应该先求分布函数。而 有变量小于 这里的 的变量 的分布函数 求出之后再求导即可得到密度函数 如何处理多个事件共同决定的变量的期望拆分成多个事件，直接求各个事件的期望的和

离散型二维联合分布三项分布若二维离散型随机变量 的分布律是其中 且 记为 三项分布是二项分布的拓展形式:![[Common probability distributions in one dimension#二项分布]] 二维超几何分布若二维变量 的分布律满足其中 而 则称其符合二维超几何分布 二维超几何分布是一维的拓展 ![[Common probability distributions in one dimension#超几何分布]] 连续性随机变量二维联合分布二维均匀分布设 为平面有界区域，其面积是 则二维变量 满足其他可以看做是一维的均匀分布变成了平面![[Common probability distributions in one dimension#均匀分布]] 二维正态分布若二维变量 的联合密度满足则称其满足二维正态分布 如何记忆:考虑一维的形式，二维相当于是带上了相关系数之后的两个一维乘到一起，再加上交叉项 ![[Common probability distributions in one dimension#正态分布]]

泊松定理设 是正整数， 是常数，则对于任意的正整数 有 对于公式的理解:这里的 可以理解为期望，即整个事件发生的平均值泊松定理表明了，在重复次数足够多的情况下，二项分布的分布率趋向泊松分布 离散型随机变量0-1 分布若随机变量 的可能取值只有 ，且那么就称其为 0-1 分布 二项分布若随机变量 的分布律满足且其中的 那么称 满足服从参数 的二项分布，记为 容易发现，在 的时候退化为 0-1 分布二项分布的概率意义是在n次独立实验（放回）中，事件出现k次的概率 泊松分布若随机变量 满足其中的 为常数，则称变量 服从泊松分布，记为 注意，这里的 k 的可能取值是从0开始的泊松分布的 可以认为是事件的期望，即平均值泊松分布刻画的是在平均值为 的情况下，变量出现小概率事件 的概率 几何分布如果随机变量 的分布律满足其中 那么称变量 服从参数为 的几何分布，记作 几何分布描述的是单次实验概率为 的事件在前 次不发生，在第 次发生的概率 几何分布的无记忆性无记忆性的概率表达式是 超几何分布假定在 N...

函数调用完成控制转移之后的栈形态从图中可以看到，在完成了控制转移等一系列操作之后，函数的第一个实参的地址在 的位置上，这是由于前面依次是 EBP旧值 和 返回地址 两个指针，各占据了4个字节 注意，在函数压栈的时候，入口参数是返序压栈的，即先压入栈中的是最后一个参数，而在C语言中写在最前面的参数最靠近 ebp 注意事项： 做题的时候注意题目给出的立即数是小端还是大端方式存放的 看汇编写C语言的时候，除了要注意数据的大小，还要通过指令的类型来区分是有符号数还是无符号数 函数调用的几条指令分别的作用： leave 的作用只是先把当前的 esp 设置为当前 ebp 的值，然后把 ebp 恢复成 ebp 旧值 ret 指令的作用是通过上一步恢复的 esp 取出返回地址，把 eip 的值指向返回地址，移交控制权限 call 的作用是保存返回地址，然后移动 eip 到指定位置，移交控制权限

What is it 流密码是一种确定性的算法，通过输入一个随机的种子，输出一串看起来像是随机的比特串 用处是替代PRG，更快地加密 缺点是并没有严格的安全性证明 Definition一个 stream cipher 包括两个部分: Init: GetBits: 此处的 表示状态信息 Init 算法通过输入种子 和一个随机的向量 来输出一个初始状态 GetBits 操作通过获取当前状态输出一个看起来随机的bit 并更新状态为

Background在堆的合并中，仅仅只是拷贝都需要 的时间复杂度，所以希望提出一种更好的数据结构，让堆的合并的效率更高 Definition外节点只有一个儿子或没有儿子的节点，即左右儿子至少有一个为空节点的节点。 距离/零路长距离/零路径长 null path length ： 定义为 X 结点到它的后代中离它最近的外结点的最短路径长度，即两结点之间路径的权值和。特别的，外结点的距离为 0 ，空结点的距离为 。 左式堆左偏树/左式堆：一种满足左偏性质的堆有序的二叉树，其左偏性质体现在左儿子的距离大于等于右儿子的距离。即对于任意一个节点， 左式堆的距离左偏树/左式堆的距离：我们将一棵左偏树根结点的距离作为该树的距离。 合并操作 如果两个堆中有一个堆为空，就直接返回另一个堆。 否则为了合并两个堆，需要比较它们的根。 将具有大的根值的堆H2与具有小的根值的堆H1的右子堆H3合并得到一个新的左式堆，其中H2和H3的合并也采用同样的逻辑。 合并代码示例12345678910111213141516171819202122232425void...

Definition of MAC一个消息认证码(Message authentication code or MAC) 算法包括三个部分，即 Gen: 通过输入安全参数，输出一个 key，长度是 Mac: 生成认证码的算法，输入一个 key 和一个消息 然后输出一个tag: Vrfy: 通过输入k,m,t，判断消息是不是有效的(Valid) 如果是，输出1否则输出0 Secure MAC消息认证实验 通过 生成一个key 记为k，k对于攻击者是保密的 攻击者对于标签生成器 MAC 有神谕机的访问权限，可以获取多项式对 记所有的攻击者访问的明文的集合为 攻击者获胜当且仅当 如果攻击者获胜输出1，否则输出0整个实验记作 Plain secure如果一个标签算法是在选择明文攻击下不可伪造的(unforgeable) 当且仅当对于任意PPT的敌手，有 定义的缺陷攻击者可能可以给出以前已经认证过的消息一个新的标签，所以需要定义一个更强的安全性 Strong MACStrong unforgeable 实验 通过 生成一个key...