Yuchen You

可数集合 我们一般用函数的映射关系来描述两个集合的大小关系，其中，由于函数本身的定义，映射总是从最小集合到最大集合

测量误差的定义 在测量的过程中，我们对于不同的解有不同的误差，这些误差可以分为两种：系统误差systematical error 和随机误差 random error。系统误差是由于实验设计和硬件问题导致的，它会导致多次测量的平均值相对于标准值发生了一定的偏差 bias，而随机误差是由于测量过程中的偶然因素引起的，测试数量越多，其平均值越接近于 0。 因此一个测量的值等于 true value=measured value+systematical error+random error\text{true value} = \text{measured value} + \text{systematical error} + \text{random error} true value=measured value+systematical error+random error 这里我们将 measured value + systematical error 表述为 μ\muμ, 即 Bias = μ−true value\mu - \text{true value}μ−true  ...

人和计算机的区别 据我们所知，人类的大脑是一个非常神奇的工具，它能理解很多各种各样的符号，而计算机很不幸只能理解 01 数据信号，那么，在算法中我们了解了计算机解决问题能力的强大之处，但是计算机少了很多符号的理解和处理能力，它在一般计算能力上是不是也会有一些缺点呢？ 在一百年前就有很多大师提出了这样的问题，这个问题的发展和人类对于算法的定义变化是非常契合的，在早期算法定义为 “对于每一个不同的输入样例，能解决问题，能输出正确答案的工具”，但是这个说法还是不够全面 首先我们要定义 problem: 是一个事实和相应解决办法的集合，我们有判断问题 (decision problem) 其答案是 yes/no, 这是一类答案可以用 01 进行直观编码的问题，因此我们先从讨论这一类问题开始。 字母表、字符串和语言 字母表 alphabet 一个非空且有限的符号集合 (symbol / character) 是一个字母表 Σ\SigmaΣ 如果在一个问题没有说明的时候， Σ={0,1}\Sigma = \{0,1\}Σ={0,1} 字符串 string 由0个或者多个字母表中的字符组成的有限序列 ...

## 对分查找 binary search 这个查找的前提是建立在数组有序的基础上，我们可以通过对分的位置判断分区，从而快速找到目标节点 一般只能返回是否找到目标节点，而不能返回其位置，我们应该使用 标准迭代器 lower_bound(), upper_bound() 进行坐标确定，其中 lower_bouund 能从右侧逼近最靠近目标元素的位置； upper_bound 能从最左侧逼近最靠近目标元素的位置 什么样的集合是方便查找的？ 从对分查找的经验里面我们可以知道，如果集合是有序的是很利于其查找的 但是很多时候我们会对一个集合进行操作，如何保持集合的有序性是一个很重要的问题 最直接的想法，是将两个数组用两个迭代器分别指向，然后比较将较小的值填充进新数组中。 但是，如果数组的同异集合性并不能通过数值来进行表示呢？ 例如，在生物图谱中，我们如何知道人类和鱼类是否有相近的基因？假设生物学已经构建了以人为中心和以鱼类为中心的两个集合图，然后假设某一天有科学家证明了这两个集合图中的某对元素(a∈a\ina∈ 人, b∈b\inb∈ 鱼) 存在近亲关系，那么我们就可以将这两个集合合并到一起 ...

单精度浮点数 float 浮点数在内存中的存储格式是 127 基偏差 方式 (base biased 127 encoding) 即将 -127 = 0x00000000 那么: 1 = 0x10000000 128 = 0x11111111 0 = 0x01111111 小数点的前后 对于十进制小数 10.625, 我们可以将整数部分分解为二进制: 1010 但是小数部分如何用二进制表示？ 类比十进制，小数点后一位是 10−110^{-1}10−1, 二进制小数点后一位是 2−12^{-1}2−1, 二进制小数点后二位是 2−22^{-2}2−2, 以此类推。 那么 .625 就可以理解为 0.5+0.125=2−1+2−3=0b0.1010.5 + 0.125 = 2^{-1} + 2^{-3} = 0b0.1010.5+0.125=2−1+2−3=0b0.101 因此整个小数就是 0b1010.1010b1010.1010b1010.101 = 10.625 正规化 normalization 为了方便浮点数的运算，我们需要将小数点的位置规整化，类似于科学计数法，我们只将位数 ...

字符串的自我处理

背景 在编译 C 或者 C++ 文件的时候，我们都会用到链接这一步骤，即 预处理 - 编译 - 汇编 - 链接 四个步骤 我们已经学过了汇编了，那么接下来就该了解一下什么是 linking 了 什么是链接 在汇编中，我们一般是每一个 c/cpp 文件生成一个 汇编代码文件 (obj file, 扩展名 .o)，那么，如果存在跨文件的变量，汇编怎么知道这个变量是来自哪里的呢？ 首先我们联想在编译的时候 (compile time) 我们会在项目编译的内存空间中创建一个格式为 text - data - heap - stack 的空间结构(这里说的不恰当，应该说 compile time 分配的 text - data 空间)，那么类似的，对于每个源文件生成的汇编码，我们都要用一个表来记录全局变量的引用 cross−refcross-refcross−ref 以及外来方法 (即函数) 的对应引用 obj 文件的内容 上述两个表格会在编译的过程中存储在 .o 文件中，因此 obj 文件的格式会表现为: Header - Text - Data - Symbol Table - Reloc ...

排课问题 假设开学季的某一个下午多个社团都想要占用霍体开设招新活动，每个活动的时间长度各不相同且开始和结束的时间都各不相同，那么，学校方希望能尽可能多的开设活动，而并不考虑总活动时长的影响因素 最早结束时间算法 Earliest Ending Time EET 将这些活动按照时间结束的早晚进行排序，然后选中最前面那个，然后去除所有重叠的活动，然后递归选取下一个 选择的可靠性 (safe) 我们需要证明我们选择的这个活动确实是能带来最多活动数量的，或者用数学术语来说，存在最优解集 IOPTI_{OPT}IOPT​, 我们要证明 我们选择的 first ends I∈IOPTI \in I_{OPT}I∈IOPT​ 由于根据定义，结束时间 end(I)≤end(IOPT)end(I) \le end(I_{OPT})end(I)≤end(IOPT​) 那么由于 IOPTI_{OPT}IOPT​ 的下一个元素开始时间一定晚于当前的结束时间，所以 end(I)<start(IOPT,next)end(I) < start(I_{OPT, next})end(I)<start( ...

二维连续变量条件空间理解 假设我们有两个变量 X,YX, YX,Y, 存在一定的概率密度函数 fXY(x,y)f_{XY}(x,y)fXY​(x,y) 来表示在 X=x,Y=yX = x, Y = yX=x,Y=y 情况的概率密度 这个图像在 xyfxyfxyf 三维坐标下表现为 一个 f∈(0,1)f\in(0,1)f∈(0,1) 的一个曲面 其和 f=0f = 0f=0 平面形成的体积为 1 有效坐标 support 我们称 坐标 (x,y)(x,y)(x,y) fXY(x,y)>0f_{XY}(x,y) > 0fXY​(x,y)>0 为有效坐标，也就是在这个坐标上有可能发生事件 边界概率 marginal probability 如果我们想知道某一个变量的概率密度分布，那么我们就需要将这个二维曲面压缩到一维曲线上 例如我们想知道 fXYf_{XY}fXY​ 转变成 fXf_XfX​ 的形状，那么我们就可以将 y 坐标压缩到 x 轴上，也就是将 所有 y 的可能性都累加起来保存到 x 上，公式表达为: fX(x)=∫−∞∞fXY(x,y)dyf_{X}(x) = ...

概率密度函数的变化 假设原函数为 fX(x)={2x,0<x<10,o.w.f_X(x) = \begin{cases}2x &, 0 < x < 1\\ 0 &, o.w.\end{cases}fX​(x)={2x0​,0<x<1,o.w.​ 那对于随机变量 U=3X+1U = 3X + 1U=3X+1 我们如何计算 UUU 的概率密度函数呢？ 首先我们可以尝试将 x 直接变成 uuu 得到 x=u−13x = \frac{u - 1}{3}x=3u−1​ 从而直接带入公式求分布 但是这样其实忽略了一个问题: x→ux \to ux→u 的变换发生了拉伸以及偏移，所以其概率曲线可能是微微变形的 原函数，但是其归一性可能已经不满足了 因此我们直接从 最满足归一性 的 c.d.f 入手 （因为非线性变换之后可能我们不能用除以全积分归一来简单求解）我们使用 fU=dduFU(u)f_U = \frac{d}{du}F_U(u)fU​=dud​FU​(u) 而这里c.d.f 用的是 FU(u)=P[U≤u]=P[3X+1≤u]=P[X≤u ...