Yuchen You

分治算法 divide and conquer 正确性证明 Correctness 使用 数学归纳法 (尤其是 强归纳法进行证明) base case 证明: 用一个 trivial 的方法证明 base case 是正确的 recursive step: 首先假设前几步返回的都是真的 (也就是在 分治算法里面本层的返回值有效) 然后利用 conquer 步骤的特性证明最终输出是正确的 搜索类算法的正确性分析 如果要用分治算法进行搜索，我们很难直接用归纳法证明递推性质 (因为其他都不符合，并不能说该算法很好的证明了前面的部分) 所以用 invariant 来进行说明 某一部分查找的特性已经被前几层 递归保存了 (即为什么会到这一层递归？一定是前几层没有满足某一个原因，但是由于递归是具有方向选择性的，因此我们会确保某一个部分的 inveriant 能被保证成立) 那么只要证明 本层筛选针对其他没有 被保证的角度也会通过筛选证明即可 时间分析 Runtime Analysis 一般要用到一个递归表达式以及一个时间表达式，然后利用 master theorem 进行证明 2D 平面最近的 ...

目的 可以压缩执行时间，从单循环的长周期短cpi和多循环的短周期长cpi结合得到 短周期 + 短 cpi (等于 多循环的cpi) 特点 在 multi-cycle 的电路基础上，添加一个 对应每个 stage 的寄存器, 一共四个 最大同时执行指令的次数: 5 (即 if, id, ex, mem, wb 各一个同时进行) 总 cycle 数 instr 数 + pipeline_stage 数 - 1 pipeline 问题 data hazard data dependency: 指令依赖于前面某个指令的结果 data hazard: 一个指令如果不进行额外处理就会遇到错误情况 解决方案 代码主动避免 avoid 检测与贮存 (处理器主动等待) detect and stall 自动修复为标准值 detect and forward 1. 代码主动避免 加入 noop 轮空 cycle 问题 硬件版本不同需要的 noop 数量不同 (新的硬件可能 pipeline 更长，需要的noop会变) 程序体变大很多 执行速度变慢 2. 检测与贮存 Detect and Sta ...

选择器 mux 在逻辑电路中，我们经常会需要选择使用哪个数据源(这里其实是比较 compare 逻辑)，所以我们会用到 mux 来完成, 其符号如下: 原理 这个逻辑可以用 与门 来完成 加法器 adder 已经在基本逻辑电路中解释过了，大致原理就是接收 进位位 Carrier, 输入位 a,b 通过逻辑演算得到 本位值以及进位位值 解码器 decoder 简单理解，就是将每一个输入根据其digit转为第n根线出high

切比雪夫不等式 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 对于一个正在构建的数组(数据流)，每到来一个元素我们都会需要将新变量插入到本来已经有 ...

eecs 281 复习 Container and ADT Stack 标准的 FIFO 结构 常用的 method 函数 push() pop() top() size() empty() array 型 stack 的时间复杂度分析 push O(1)O(1)O(1) 对于一般情况; O(n)O(n)O(n) 对于内存满了需要额外申请的情况 注意申请空间的时间复杂度是 O(1)O(1)O(1)，而复制内容到新的数组的时间复杂度是 O(n)O(n)O(n) pop, top, size, top 的时间复杂度都是 O(1)O(1)O(1) 摊还分析 amortized analysis 对于一个不一定要进行内存申请空间的vector，平均的push花费的时间复杂度是: 从 size = n 到 size = 2n 一共要 push n 次, 每次 O(1) 在 size = 2n 的时候要进行空间申请和复制，时间开销是 O(2n) 总花销 O(1)⋅n+O(2n)O(1) \cdot n + O(2n)O(1)⋅n+O(2n), 总步长 nnn 那么平均复杂度是 O( ...

从二项分布到柏松分布 在二项分布中我们只讨论一个事件的发生次数，而其载体是离散的“机会”，但是如果这个机会是一个连续的区间，例如一个面积或者一个时间，就是一个柏松分布 伯努利分布的 概率质量函数 首先我们将一个连续的一维空间（这里用时间举例）分割成 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 的概率