Yuchen You

定义 A language LLL is NP-complete if L∈L\inL∈ NP LLL is NP-hard 证明方法: polynomial-time mapping reduction 定义归纳关系 A≤pBA\le_p BA≤p​B 表示 ∃f s.t. x∈A⇔f(x)∈B\exists f \text{ s.t. } x \in A\Leftrightarrow f(x) \in B∃f s.t. x∈A⇔f(x)∈B 引理 lemma B∈P⇒A∈PB\in P \Rightarrow A \in PB∈P⇒A∈P AAA NP-hard ⇒\Rightarrow⇒ B NP-hard 用法 选取一个已知的 NP-hard 问题 A 来归纳关系 A≤pBA\le_p BA≤p​B 定义问题转变映射: 如何将问题集合 A 的某个确定 instance 转变为 B 的对应的 instance 证明这个转变 f 的时间复杂度是 polynomial 证明 correctness: 证明一个能解决 A 的 answer 同样在转变的问题中可以以同样的答案 ...

树的定义 没有 cycle 的无向图 rooted tree 存在某个 node 作为根节点 每个节点事实上都可以作为 root 二叉树的操作复杂度 二叉树的方法时间复杂度看的主要是二叉树自身的结构形状，如果是 complete 树是最好情况; 如果是 每个节点都只有一个子枝，其复杂度最大，是 worst case 数组法 insert 最好 O(1) 最差 O(n) 和树的排布方式有关，如果树的根节点的某个字节点为空那么直接插入，复杂度 O(1); 如果全部排满我们需要遍历找到空节点位置那么时间复杂度 O(n) remove 最差 O(n) parent O(1) child O(1) space 最好 O(n) 最差 O(2^n) 这里取决于数据的排布方式, 如果是完全二叉树，那只需要 O(n) 空间; 如果是完全一叉树 (每个node最多只有一个节点) 就需要 O(2^n) 空间 指针法 insert 好 O(1) 坏 O(n) remove 坏 O(n) parent O(n) 因为没有爹指针 child O(1) space 好 O(n) 坏 ...

SRAM, DRAM, SSD SRAM 静态随机访问内存 由六个三极管组成 脆弱volatile：需要常量的电压来保存数据 快速: 1ns 左右的数据访问时间 空间占用率低: 只能在芯片上存储 MB 大小的数据 DRAM 动态随机访问内存 每一个 bit 用一个 三极管和一个电容组成 需要常量的电压来保存数据 缓慢: 大约 50 ns 的访问时间 便宜，可以提供 GB 单位的内存空间 现代硬件结构中这个往往被用作是主要内存硬盘 Disk 光盘 硬件将数据存储在 磁电,通过光盘的旋转来进行数据获取 数据获取非常缓慢，约 3ms 的访问时间 不脆弱：即使没有电压也可以保存数据 固态硬盘 solid-state disk, SSD 相比光盘，访问时间快很多，大约 0.1 ms 的时间 十分便宜 总结 reg, cache, memory 的速度和内存大小的关系如下图: 缓存 Caches 功能 缓存存储了我们认为最有可能会被使用的数据, 从时间和空间维度，共有两种可能： 空间(spatial locality)：最近被调用的数据的附近更有可能会被调用 时间(temp ...

NP-hard 定义 一个语言 LLL 是 NP-hard 若对任意 NP 中的语言 X 存在关系 X≤pLX\le_p LX≤p​L 定义这个关系为：at least as hard as 并不要求 NP-hard 问题属于 NP NP-complete 定义语言 LLL 是 NP-complete 的如果 1. L∈L\inL∈ NP 且 2. L∈L\inL∈ NP-hard 从简单上来认识这个 class，可以理解为这是最难解决的 NP 问题 NP-hard 的复杂度性质 如果对于任何一个 NP-hard 的问题，存在一个 多项式复杂度的解 那么任何 NP 问题都可以在 P 时间内解决 因此有两种可能性: NP-complete 问题全部都属于 P NP-complete 问题全部需要超过 多项式时间复杂度的求解难度 NP-hard reduction 定义符号 ≤p\le_p≤p​ 使得 A≤pB⇔A\le_p B \LeftrightarrowA≤p​B⇔ ∃f\exists f∃f 多项式函数 s.t. x∈A⇔f(x)∈Bx\in A \Leftrightarrow ...

P 类 多项式可解类 定义 P class:= 所有的 decidable 的 problem 中可以在多项式中决定的集合 即若有 L∈PL\in PL∈P, 那么就会存在图灵机 MMM decides LLL, 且 MMM 的时间复杂度是 O(nk)O(n^k)O(nk) 难以解决的问题-例: traveling salesperson problem (TSP) 旅行商问题 在一个图中，是否存在一条路径经过每个点一次且路径权值和小于常数 b ? 这个问题的求解步骤或许非常麻烦，但是当我们提出一种解之后，我们很容易就可以根据定义来进行验证其真伪，我们称这类容易验证的问题为 efficiently verifiable 其他难解决易证明问题 走迷宫问题、数独求解问题 证明属于 P 类 证明属于 decidable 问题 (用伪代码定义图灵机的存在, 需要证明 correctness) 证明过程可以在 O(nk)O(n^k)O(nk) 时间内停止，这里 nnn 表示 input size NP 类 多项式可验证类 定义 NP class := 所有的能在多项式时间内验证一个问题的真 ...

point estimator 和 point estimate estimator 一个从样本数据计算实验参数的过程，本质上是一个随机变量, 或者说是一个随机变量的函数 (简单理解为随机变量的函数还是随机变量); 其作为函数而言，输入量是 多个随机变量 (注意表达式这里不能用数值，应该用随机变量)，但不能包括实验的参数 θ\thetaθ 其观测值为 estimate estimate 是一个数值 目的 通过样本的数据来估算 population 具有的特征 两个研究角度 对于给定的 point estimate 如何评价估计效果？ 如何计算 point estimate? MSE 最小平方误差 bias B[θ^]=E[θ^−θ]=E[θ^]−θB[\hat \theta ] = E[\hat \theta - \theta] = E[\hat\theta] - \thetaB[θ^]=E[θ^−θ]=E[θ^]−θ unbiased: B[θ^]=0B[\hat\theta] = 0B[θ^]=0 MSE MSE[\hat \theta] = (E[\hat \theta - ...

定义 总体分布函数完全未知或只知形式不知参数情况下，推断总体某些特性，提出某些关于整体的假设，根据样本对所提出的假设作出接受或是拒绝的决策 假设思路 有两种假设: 零假设和备择假设, 证明思路是将目标论点作为备择假设，定义补集为零假设，通过积分证明零假设不成立，从而证明备择假设(证明目的)成立 两类决策错误 第一类决策错误 弃真错误: H0H_0H0​ 为真的时候拒绝 H0H_0H0​ 第二类决策错误 取伪错误: H0H_0H0​ 不为真的时候接受 H0H_0H0​ 零假设的错误可能 如果用假设检验的思路，只会说明 reject H0H_0H0​ 或者 not reject H0H_0H0​, 那么我们只有可能会犯弃真错误而不会犯第二类错误，而第一类错误我们可以用一个变量来进行描述 显著性水平 α\alphaα significance level 当原假设实际上正确时, 检验统计量落在拒绝域的概率, 就是犯弃真错误的概率 在正态分布的cdf积分表中属于是积分结果一类 P-value 描述了当前样本在零假设前提下更加极端的概率和，也就是不符合零假设的概率大小 如果 p-val 越大 ...

目的 可以压缩执行时间，从单循环的长周期短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