Yuchen You

Socket 定义 socket 即套接字，是一个双向通信通道，两端为两个process或者两个机器 socket是对网络通信的一种抽象 提供了数据交换的 api 去处了一些网卡交互的细节 服务器工作流 server flow 用户工作流 client flow 工作流解读 SC 交互 socket() 构造 参数为 socket(int domain, int type, int protocol, 都使用宏定义进行输入的 domain 表示交流的范围，对于 IPv4 使用宏 AF_NET type 定义了交流的semantics, 对于双向交流的 socket，使用宏 SOCK_STREAM protocol 定义了协议，使用宏 IPPROTO_tCP 即可 整个函数定义在 <sys/socket.h> bind() 绑定 参数为 bind(int sockfd, const struct sockaddr_in * addr, socklen_t addrlen); sockfd: 上文构造的 socket 对象 addr 定义了一些参数包括 port ...

Message Integrity 信息完整性 定义 ensures that attackers cannot modify a message w/o being detected. MITM 模型 传输部分 并不完全相信网络的信息的真实性 希望 Bob 接收到的完全就是 Alice 发出的信息 威胁模型 threat model Mallory 可以 see/modify/forge(伪造) message Mallory 的目的是让 Bob 相信一个不是由 Alice 发出的信息 防御威胁的方法论 verifier 验证器 如图所示，在发送的时候额外传送一个验证码，即要求验证码 v=f(m)v = f(m)v=f(m) random function 完全随机函数 被 A/B 容易计算，但是不容易被 M 计算 (即不被知道) 如果被找到 x≠mx\neq mx​=m 且 f(m)=f(x)f(m) = f(x)f(m)=f(x) 的 collision 就失败了 表示方法：用一个很大的表格记录映射关系，需要内存非常大 优点: 完全安全，即 M 除了瞎猜没有更好的 ...

概述 网络信息传播需要遵循 应用(Application) -> 封装送货信息+路由选择(Transport) -> 国际地址封装(Network) -> 地区地址封装(Data Link) -> 物理层发送(Physical) 的五层收发结构 低层级 (后面的不需要知道前面发生了什么) 每一层只负责该层任务以及与相邻层的 api 交互 同层之间遵循同样的协议，可以互相交流 分层的优缺点 优点 reduce complexity improve flexibility better manageability increase redundancy (冗余多): 每一层都有自己的恢复措施，因此可靠性更强 缺点 high overhead cross layer information is often useful speed decreased 封装形式 Header: 每一层协议，除了物理层都会给数据包在前面 append 一个表头表示 instructions on how to process payload. Payload: 表示有效 ...

定义 一个图 G=(V,E)G = (V,E)G=(V,E) 由点的集合 VVV 和边的集合 EEE 组成 平行边 两个节点之间存在多条边界 self-loop 自循环 没有自循环的图称为 simple graph，两端不同的边称为 simple path connect path: 一个 simple path 存在于任意一对 vertices 之间 (节点间均间接/直接相连) cycle: 简单路径除了首尾 vertex 相同 稠密度 complete graph 任意两个 vertex 直接相连 dense graph 稠密图表示图内的 edge 数量很多 E∼V2E\sim V^2E∼V2 sparse graph 稀疏图 E∼VE\sim VE∼V 相邻关系表示 邻接矩阵 adjacency matrix 一个 0-1 矩阵，坐标 i,j 表示边 (i,j) 是否存在于图中 常用于无权图 距离矩阵 distance matrix 在这个距离矩阵中，对应坐标的值表示对应 edge 的距离 一般用 ∞\infty∞ 表示不存在通路 邻接表 adjacency list 点均边 ...

定理内容 SAT 问题是 NP-complete 问题 由于 SAT 问题在给定 certificate 的情况下只需要逐个检验是否符合, 复杂度是 polynomial -> NP, 因此这里只需要证明其是 NP-hard 即可 证明 NP-Hard 利用 NP-hard 的定义, 这里需要证明对所有的 language L∈NPL\in NPL∈NP 都有 L≤pSATL\le_p SATL≤p​SAT (因为 SAT 问题往往会作为 NP-hard origin 来归纳其他的问题是否 NP-hard, 这里不能用其他 NP-hard 来归纳之) 因此假设我们有一个任意 np 问题的 instance x 和一个输入语言 L ∈\in∈ NP, 即存在 Verify−LVerify-LVerify−L 可以在多项式时间内决定 L; 证明目的是是否存在一个 SAT instance ϕ\phiϕ satisfiable iff 存在 c 使得 Verify-L(x,c) accept 定义 VL 算法为一个 TM, 并将其编码为一个 ∣x∣k×∣x∣k|x|^k\times | ...

定义 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 := 所有的能在多项式时间内验证一个问题的真 ...