基础概念

1. 问题 $\pi$，最大化或最小化问题
2. 实例(instance) $I$
3. $I$ 的可行解集合 $S(I)$，需满足
   • 可行解 $s$ 大小为 $|I|$ 的多项式($|s|\in poly(|I|)$)
   • 多项式时间能判断解 $s$ 是否可行($s\in S(I)$)
4. 目标函数(objective function) $obj(I, s)$，需满足
   • $obj(I, s) \geq 0$
   • 给定 $I,s$ 时，目标函数能在多项式时间内算出
5. 最优解 $OPT(I)$, 算法所得解 $ALG(I)$
6. $\alpha$ 近似(factor-$\alpha$-approximation)：最小化问题为例，对于任意一个实例 $I$，算法给出的解 $s$ 都满足 $\frac{obj(I,s)}{OPT(I)} \leq \alpha$

组合数学

组合数

广义组合数

${n \choose m} = \frac{n^{\underline{m}}}{m!}$ $n$ 为实数，$m$ 为自然数

广义二项式定理

$(x+1)^\alpha = \sum\limits_{i\geq0} {\alpha \choose i}x^i$ $\alpha$ 为实数

单位根反演：

$[n \mid k]=\frac{1}{n}\sum {i=0}^{n-1} \omega {n}^{ik}$

$[k \mod n \equiv j ]=\frac{1}{n}\sum {i=0}^{n-1} \omega {n}^{i(k-j)}$

例：求 $\sum {n \choose 3i}$

范德蒙恒等式

${n+m\choose j} = \sum\limits_{0\leq i\leq j}{n\choose i} {m\choose j-i}$