The Algorithm Magic of Polynomial
- Polynomials
- The Root of Polynomial
- A Delete Channel
- Polynomials for Finding Maximum Matchings
Polynomials 多项式
一个 d d d 次多项式可以用一个 d + 1 d+1 d+1 元组 c i {c_i} ci 表达。在这种情况下,两个多项式相加的时间复杂度是 O ( d ) O(d) O(d) ,而两个多项式相乘的实践复杂度是 O ( d log d ) O(d \log d) O(dlogd) 。
快速地估计一个多项式的值的方法:对应给定值b,循环执行将当前式子乘b,加下一项。这个方法叫做霍纳规则。流程如下:
c d c d × b + c d − 1 ( c d × b + c d − 1 ) × b + c d − 2 c_d c_d \times b + c_{d-1} (c_d \times b + c_{d-1}) \times b +c_{d-2} cdcd×b+cd−1(cd×b+cd−1)×b+cd−2
该算法的时间复杂度是 O ( d ) O(d) O(d)。
多项式的根
对于一个多项式 P ( x ) P(x) P(x),令 P ( x ) = 0 P(x)=0 P(x)=0 的值 x ′ x' x′ 被称作多项式的根。
根据代数基本定理,一个d次多项式一定有d个根。
Unique Reconstruction Theorem 唯一重构定理
唯一重构定理告诉我们,给定d个点 ( x 1 , y 1 ) , ( x 2 , y 2 ) ⋱ , ( x d , y d ) (x_1,y_1),(x_2,y_2) \ddots, (x_d,y_d) (x1,y1),(x2,y2)⋱,(xd,yd), 总有一个多项式 P ( x ) P(x) P(x) 使得这些点都在多项式上。
事实上,唯一重构定理告诉我们如何构造这样一个多项式满足条件。
首先我们构造这样一组多项式 R i ( x ) R_i(x) Ri(x) 满足:
R i ( x i ) = 1 R i ( x j ) = 0 , j ≠ i R_i(x_i) = 1 R_i(x_j) = 0, j \neq i Ri(xi)=1Ri(xj)=0,j=i
结果如下:
Π j ≠ i ( x − x j ) Π j ≠ i ( x i − x j ) \quad{\Pi _{j\neq i}(x-x_j)}\over{\Pi _{j\neq i}(x_i-x_j)} Πj=i(xi−xj)Πj=i(x−xj)
那么
P ( x ) = y 0 R 0 ( x ) + y 1 R 1 ( x ) + ⋯ + y d R d ( x ) P(x) = y_0 R_0(x) + y_1 R_1(x) + \cdots +y_d R_d(x) P(x)=y0R0(x)+y1R1(x)+⋯+ydRd(x)
举个例子:有三个点 ( 5 , 1 ) , ( 6 , 2 ) , ( 7 , 9 ) (5,1),(6,2),(7,9) (5,1),(6,2),(7,9),现在找出经过这三个点的多项式。
R 1 ( x ) = ( x − 6 ) ( x − 7 ) ( 5 − 6 ) ( 5 − 7 ) = 1 2 ( x 2 − 13 x + 42 ) R 2 ( x ) = ( x − 5 ) ( x − 7 ) ( 6 − 5 ) ( 6 − 7 ) = − 1 2 ( x 2 − 12 x + 35 ) R 3 ( x ) = ( x − 5 ) ( x − 6 ) ( 7 − 6 ) ( 7 − 5 ) = 1 2 ( x 2 − 11 x + 30 ) P ( x ) = R 1 ( x ) + 2 R 2 ( X ) + 9 R 3 ( x ) = 4 x 2 − 50 x + R_1(x) = \frac{(x-6)(x-7)}{(5-6)(5-7)} = \frac{1}{2} (x^2 -13x +42) R_2(x) = \frac{(x-5)(x-7)}{(6-5)(6-7)} = -\frac{1}{2} (x^2 -12x +35) R_3(x) = \frac{(x-5)(x-6)}{(7-6)(7-5)} = \frac{1}{2} (x^2 -11x +30) P(x) = R_1(x) + 2R_2(X) + 9R_3(x) = 4x^2-50x + R1(x)=(5−6)(5−7)(x−6)(x−7)=21(x2−13x+42)R2(x)=(6−5)(6−7)(x−5)(x−7)=−21(x2−12x+35)R3(x)=(7−6)(7−5)(x−5)(x−6)=21(x2−11x+30)P(x)=R1(x)+2R2(X)+9R3(x)=4x2−50x+
A Deletion Channel 丢失频道
下面是另一个问题,假设在上面构造多项式的情景中,Alice要向Bob传d+1个数,但是在传输的过程中总会有k个数丢失,那么怎么才能保证Bob一定收的到这d+1个数呢?
一种很笨的方法是,将每个数据发送k+1次就可以了。但是这需要发送 d × ( k + 1 ) d\times (k+1) d×(k+1) 个数据,有没有更好的方法呢?
一种好方法是构造一个多项式 P ( x ) = Σ c i x i P(x) =\Sigma c_i x_i P(x)=Σcixi,然后发送 P ( 0 ) , P ( 1 ) , ⋱ , P ( d + k ) P(0),P(1),\ddots,P(d+k) P(0),P(1),⋱,P(d+k),这样Bob至少可以收到d+1个多项式的值,根据唯一重构定理,Bob可以计算出这个多项式从而得出所有的c。
这种做法的时间复杂度是 O ( d + k + 1 ) O(d+k+1) O(d+k+1),比上面的做法少传输很多数据。(注意,不用担心乱序的问题,因为是一个一个传的,而如果出错会传乱码而不是什么也不做)。
General Error Correction 误码纠错
假设现在不是传输丢失,而是传输一个错误的数字,那么在同样的背景下,需要进行怎样的传输呢?
很明显,答案是需要传输 d + 2 k + 1 d+2k+1 d+2k+1个数字,其中 d + k + 1 d+k+1 d+k+1是正确的多项式的值。因为 k + 1 > k k+1>k k+1>k,所以我们从理论上确认了Bob可以通过这种方式找到正确的多项式。
那么实际上应该怎么找到那个正确的多项式呢?
假设Bob收到的数据是 r 0 , r 1 , ⋱ , r d + 2 k r_0,r_1,\ddots,r_{d+2k} r0,r1,⋱,rd+2k,Z是其中错误信息的集合,那么我们声明一个错误项多项式
E ( x ) = Π i ∈ Z ( x − i ) E(x) = \Pi_{i\in Z}(x-i) E(x)=Πi∈Z(x−i)
那么对于Bob收到的所有项都满足以下等式,因为要么 E ( x ) = 0 E(x)=0 E(x)=0,要么 P ( x ) = r x P(x) = r_x P(x)=rx
P ( x ) ⋅ E ( x ) = r x ⋅ E ( x ) P(x)\cdot E(x) = r_x \cdot E(x) P(x)⋅E(x)=rx⋅E(x)
Berlekamp-Welch Algorithm BW算法
BW算法是一种用于误码纠错的算法,其运行规律基于上文所述,我们假设
E ( x ) = x k + e k − 1 x k − 1 + ⋯ + e 0 ( i f d e g r e e ( E ( x ) ) i s k ) P ( x ) ⋅ E ( x ) = f d + k x d + k + f d + k − 1 x d + k − 1 + ⋯ + f 0 E(x) = x^k +e_{k-1}x^{k-1} + \cdots + e_0 (if degree(E(x)) is k) P(x) \cdot E(x) = f_{d+k}x^{d+k} + f_{d+k-1}x^{d+k-1} + \cdots + f_0 E(x)=xk+ek−1xk−1+⋯+e0(ifdegree(E(x))isk)P(x)⋅E(x)=fd+kxd+k+fd+k−1xd+k−1+⋯+f0
这种情况下,我们分别将 x = 0 , 1 , ⋯ , d + 2 k x = 0,1,\cdots, d+2k x=0,1,⋯,d+2k带入方程
P ( x ) ⋅ E ( x ) = r x ⋅ E ( x ) P(x) \cdot E(x) = r_x \cdot E(x) P(x)⋅E(x)=rx⋅E(x)
左边是一堆参数f相加,右边是一堆e相加,f和e未知数的总和是d+2k+1个,而带入d+2k+1个x的值对应d+2k+1个方程,而且方程必定有解,因此就可以解出所有的e和f。
已知 P ( x ) ⋅ E ( x ) P(x) \cdot E(x) P(x)⋅E(x) 和 E ( x ) E(x) E(x) ,相除就可以求出 P ( x ) P(x) P(x)。
Polynomials for Finding Maximum Matching 多项式在最大匹配中的应用
Schwarz-Zippel Lemma Schwarz-Zippel 引理
这个引理的内容是:假设 P P P是一个非零 m m m元 d d d次多项式,假设 S S S是有限域 F F F的一个子集。如果从 S S S中随机抽取 m m m个数 x 1 , x 2 , ⋯ , x m {x_1,x_2,\cdots,x_m} x1,x2,⋯,xm,那么
P r [ P ( x 1 , ⋯ , x m ) = 0 ] ≤ d ∣ S ∣ Pr[P(x_1,\cdots,x_m)=0] \leq \frac{d}{|S|} Pr[P(x1,⋯,xm)=0]≤∣S∣d
健全性检查:当 m = 1 m=1 m=1时,因为d次多项式最多有 d d d个根,因此概率很明显就是 d ∣ S ∣ \frac{d}{|S|} ∣S∣d。
这个引理可以用来解决下文提到的图的匹配问题。
Tutte Matrix
每个顶点数 v v v的简单无向图都对应一个Tutte Matrix M ( G ) M(G) M(G),简单来说如图所示:
Tutte Determinant Theorem Tutte行列式定理
一个图有完美匹配当且仅当 M ( G ) M(G) M(G)的行列式不是零多项式。
(注:匹配指的找到图中一组边集,其中任意两条边都没有公共点。如果这组边集包括了图中所有的顶点,那么就说该匹配是完美匹配。)
那么剩下的就是选取 F F F的大小了, F F F的基数越大,这张图有完美匹配的概率就越高。
Finding a Perfect Matching
上面我们知道了有完美匹配的概率,但是我们如何找到一个完美匹配呢?下面是一个方法:
对于每个边,将图中的该边删去,判断剩下的图中是否还存在完美匹配。如果没有完美匹配,那么将该边加回来;否则丢弃该边。
最后一定剩下 V 2 \frac{V}{2} 2V条边,这些边就是一个完美匹配。