Yuchen You

切比雪夫不等式 Chebyshev’s Inequality 马尔可夫不等式 Markov’s Inequality 公式: P[X≥t]≤E[X]tP[X \ge t] \le \frac{E[X]}{t} P[X≥t]≤tE[X]​ 这个公式限制了限制了随机变量的累积分布函数存在一个下界限制，可以用来推导切比雪夫不等式 证明 E[X]=∫−∞∞xf(x)dx=∫0xxf(x)dx≥∫a∞xf(x)dx≥∫a∞af(x)dx=aP(x≥a)E[X] = \int_{-\infty}^\infty xf(x)dx = \int_0^x xf(x)dx \ge \int_a ^\infty xf(x)dx \ge \int_a^\infty af(x)dx = aP(x\ge a) E[X]=∫−∞∞​xf(x)dx=∫0x​xf(x)dx≥∫a∞​xf(x)dx≥∫a∞​af(x)dx=aP(x≥a) 切比雪夫不等式公式 切比雪夫不等式会使用方差来作为一随机变量超过平均值概率的上限: P[∣X−μ∣≥t]≤Var[X]t2P[|X - \mu| \ge t] \le \frac{Var ...

常用的不可定中间语言 BARBER LBARBER={⟨M⟩:Mdoes not accept ⟨M⟩}L_{BARBER} = \{ \langle M \rangle : M \text{does not accept } \langle M \rangle \}LBARBER​={⟨M⟩:Mdoes not accept ⟨M⟩} HALT LHALT={(⟨M⟩,x):M halts on w}L_{HALT} = \{ (\langle M\rangle, x) : M \text{ halts on } w \}LHALT​={(⟨M⟩,x):M halts on w} ACC LACC={⟨M⟩:M accepts L(M)}L_{ACC} = \{ \langle M \rangle : M \text{ accepts } L(M) \}LACC​={⟨M⟩:M accepts L(M)} 单string停机问题 虽然不能解决通用停机问题，但是我们是否可以解决单string停机问题？即对于给定的一个string，判断一个特定的图灵机是否能停机。从简单的角度考虑，我 ...

罗素悖论 - 理发师悖论 Barber Paradox 一个小镇上的理发师，只给那些不给自己理头发的人理发 那么就会出现一个问题，如果这个理发师给自己理发（假设物理上做得到）那么他就违反了他的 slogan，因为他自己是理头发的人，他不能给理头发的人理头发 如果这个理发师不给自己理头发，那么他也违反了自己的slogan，他不给自己理头发但是他理应给自己理头发 图灵机的循环 由于我们知道图灵机能表述为一个 string (即用其的7元组进行各部分编码得)，那么我们是不是可以用另一个图灵机来处理这个图灵机？ 再根据理发师悖论，我们就有了一个很叛逆的图灵机： 图灵机 TM 只接受任意不接受任意自己描述的字符串的 TM1TM_1TM1​ 那么，这个特殊的 TM 可以接受其自身的描述字符串吗？ 很遗憾根据悖论，这里是不行的 可决定集合 假设我们有一个语言 LAccL_{Acc}LAcc​ 包含了所有的 tuple (⟨M⟩,x)(\langle M\rangle, x)(⟨M⟩,x), 其中 MMM 是一个 TM, xxx 是一个 string, 且 MMM 接受 xxx 这在生活中很常见：我们 ...

排序的分类 一般我们将排序能不能根据输入数组后能否优化处理的特性将排序算法分为两类 Non-Adaptive Sort: 不会根据输入数据的特性进行优化处理 Adaptive Sort: 会根据输入数据的特性进行优化处理 冒泡排序 bubble sort 用两个指针，逐个将相邻的两个节点大小进行比较，每次把最极端的值放到数组的某一边，然后下一层循环减小空间 时间复杂度 O(n2)O(n^2)O(n2) 空间复杂度 O(1)O(1)O(1) Adaptive 策略 如果在一次遍历中没有发生任何元素的交换，说明数组已经有序，可以提前结束排序 选择排序 selection Sort 每次遍历一个数组，找到最极端的值然后和边界值进行互换，再在剩下的空间完成剩余的排序 时间复杂度 O(n2)O(n^2)O(n2) 空间复杂度 O(1)O(1)O(1) Adaptive 策略 在极端值的时候，如果index和交换目标相同，那么就不交换 (这里其实基本上没有优化) 插入排序 insertion sort 对于一个正在构建的数组(数据流)，每到来一个元素我们都会需要将新变量插入到本来已经有 ...

从二项分布到柏松分布 在二项分布中我们只讨论一个事件的发生次数，而其载体是离散的“机会”，但是如果这个机会是一个连续的区间，例如一个面积或者一个时间，就是一个柏松分布 伯努利分布的 概率质量函数 首先我们将一个连续的一维空间（这里用时间举例）分割成 n 个小块，确保每个小块内至多有一次事件发生，那么这小块内就是一个简单的伯努利分布，发生 1 次的概率为 ppp, 而不发生的概率就是 1−p1 - p1−p, 发生 2 次及以上的概率为 0 那么我们需要找到 n 和 p 的关系 期望中间值 我们定义 E[X]=np:=λtE[X] = np := \lambda_tE[X]=np:=λt​ 为一个时间段内发生的次数的期望值，那么我们可以转写二项分布中的概率质量函数为： lim⁡n→∞(nk)(λtn)k(1−λtn)n−k=λke−λk!\lim_{n\to\infty} \binom{n}{k} (\frac{\lambda_t}{n})^k (1-\frac{\lambda_t}{n})^{n-k} = \frac{\lambda^k e^{-\lambda}}{k!} n→∞li ...

伯努利分布 一个随机变量 XXX 可以被赋值为 0 或者 1 就是一个 伯努利随机变量 这里我们用 ppp 来表述 X=1X = 1X=1 的概率

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

测量误差的定义 在测量的过程中，我们对于不同的解有不同的误差，这些误差可以分为两种：系统误差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  ...

## 对分查找 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 为了方便浮点数的运算，我们需要将小数点的位置规整化，类似于科学计数法，我们只将位数 ...