降维Dimension Reduction1 Metric Embedding失真distortion: 对于$\alpha \ge 1$, 对于任意$x,y\in X$, 有 \frac{1}{\alpha}\cdot d(x,y)\le d(\phi(x),\phi(y))\le \alpha ...

Pólya计数理论1 群群$(G, \cdot)$: 闭合, 结合律, 幺元, 逆 1.1 置换群置换为双射$\pi:[n]\to [n]$, 置换之间的操作符 $\cdot$ 定义为函数的复合, 即$(\pi \cdot \sigma)(i)=\pi(\sigma(i))$ 对称群$S_n$$S ...

Concentration of measure1 Chernoff Bound矩生成函数: 随机变量$X$的矩生成函数为 \mathbb E[e^{\lambda X}]=\mathbb E [\sum_{k=0}^{\infty}\frac{\lambda^k}{k!}X^k] =\sum_{ ...

6 链路层和局域网 两种截然不同的链路层信道: 广播信道, 点对点通信链路 6.1 链路层概述 直连网络—链路层—网卡 在通过特定的链路时, 传输节点将数据报封装在链路层帧中, 并将该帧传送到链路中 (首部 + data(IP包) + 尾部) 6.1.1 链路层提供的服务 成帧: 把数据报封 ...

Balls into Bins 背景: 将$m$个球独立均匀随机地扔进$n$个盒子, 等价于随机映射$f:[m]\to[n]$. 1 生日问题 问题: $m$个学生生日独立随机均匀分布于一年365天. 求没有两人同一天生日的概率 等价于: 将$m$个不同的球扔进365个盒子. 更一般的, 盒子数为 ...

容斥原理1 容斥原理对于$n$个有限集合$A_1,A_2,\cdots, A_n$, |\cup_{i=1}^nA_i|=\sum_{I\subseteq\{1,\cdots, n\}}(-1)^{|I|-1}|\cap_{i\in I}A_i|补集形式: 全集$U$ |\bar A_1\ca ...

Hashing and Sketching1 不同元素的个数问题: 输入一系列(未必不同)的元素$x_1,x_2\cdots,x_n\in \Omega$, 输出不同元素的个数$z=|\{x_1,x_2,\cdots,x_n\}|$ 通常算法需要维护字典结构, 需要至少$O(n)$空间, 现在想要 ...

1 生成函数 $a_n$的ordinary generating function(ODF): G(x)=\sum_{n\ge 0}a_nx^n 1.1 组合 例1: $(x_0+x_1)^3$的展开式表示了3元集的所有子集, $(1+x)^3$的展开式的$x_k$系数表示了$k-$子集的数量 ...

Fingerprinting1. Polynomial Identity Testing (PIT) Polynomial Identity Testing (PIT): 给定两个多项式, 确定他们是否相同 单变量情形 问题 输入: 两个多项式$f$, $g\in \mathbb F [x]$(单 ...

1 计算机网络和因特网1.1 什么是因特网1.1.1 具体构成描述组成组成: 端系统, 通信链路, 分组交换机 连入因特网的设备: 主机(host) 或 端系统 端系统通过通信链路 和 分组交换机连接到一起 通信链路: 由不同类型的物理媒体构成: 同轴电缆, 铜线, 光纤, 无线电频谱 传输速度 ...