算法导论30.3 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 3.5k 阅读时长 ≈ 3 分钟

30.3-1

经过蝴蝶变换，得到$A$的新序列为$A’=(0,4,3,7,2,5,-1,9)$。

以下是自底向上的DFT过程：

$\begin{array}{|l|l|}\hline
s&\\hline
0&[0],[4],[3],[7],[2],[5],[-1],[9]\\hline
1&[4,-4],[10,-4],[7,-3],[8,-10]\\hline
2&[14,-3-3i,-8,-3-3i],[15,3+4i,-13,3-4i]\\hline
3&\left[19,\left(-4+\dfrac{7\sqrt{2}}{2}\right)-\left(4+\dfrac{13\sqrt{2}}{2}\right)i,-6+i,-\left(4+\dfrac{7\sqrt{2}}{2}\right)+\left(4-\dfrac{13\sqrt{2}}{2}\right)i,-1,-\left(4+\dfrac{7\sqrt{2}}{2}\right)-\left(4-\dfrac{13\sqrt{2}}{2}\right)i,-6-i,\left(-4+\dfrac{7\sqrt{2}}{2}\right)+\left(4+\dfrac{13\sqrt{2}}{2}\right)i\right]\\hline
\end{array}$

30.3-2

考虑图30.6的FFT电路。在第$s$个阶段，有$\dfrac{n}{2^s}$个蝶形电路组，从上到下分别编号$0\sim \dfrac{n}{2^s}-1$，在每个蝶形电路组中，有$2^{s-1}$个蝶形电路组，假设从上到下编号为$0\sim 2^{s-1}-1$。

那么对于第$k$条导线，它在第$s$阶段是在蝶形电路组$\left\lfloor\dfrac{\text{rev}(k)}{2^s}\right\rfloor$，在这个组内的编号为$\text{rev}(k)\bmod {2^{s-1}}$。

也就是说，对于第$s$个阶段第$g$个蝶形电路组的的第$j$个蝶形电路，其输入和输出的两条引线的编号为$\text{rev}(g\cdot 2^s+j)$和$\text{rev}(g\cdot 2^s+j+2^{s-1})$。

30.3-3

假设$k$是一个01列向量$k=(b0,b_1,\dots,b{n-1})^T$。那么由于是对向量$k$进行逆序，即相当于将位置$i$上的比特转移到位置$n-1-j$。因此，$M$矩阵的构造如下：

考虑向量$z=Mk$，那么计算向量$zi$元素的值，有$\displaystyle{z_i=\sum{j=0}^{n-1}m{ij}k_j=k{n-1-j}}$。因此构造出的矩阵$M$为所求。事实上，$M$的形式如下：

30.3-4

蝴蝶变换的本质是将数组$a$中，对若干对数交换位置。因此可以通过BIT-REVERSE-OF计算出新位置后原地交换。由于$i = \text{rev}(\text{rev}(i))$，因此只有当$\text{rev}(i)< i$时才交换这两个数的位置。

1
2
3
4
5
6
BIT-REVERSE-PERMUTATION(a, n)
  b = lg(n)
  for k = 0 to n - 1
    i = BIT-REVERSE-OF(k, b)
    if k < i
      exchange a[i] with a[k]

$\star$ 30.3-5

对于$i\in[0,n)$，输入$ai=i+1$。那么电路相当于计算多项式$\displaystyle{A(x)=\sum{i=0}^{n-1}(i+1)\cdot x^i}$，当$x\neq 1$时，可以得到$A(x)=\dfrac{nx^{n+1}-(n+1)x^n+1}{(x-1)^2}$。（选择这种系数的原因是，确保了不会有任何一个中间电路的输出值是$0$）

对于$k\in[0,n)$，考虑计算$y_k=A(\omega_n^k)$的值，那么有

$y_k=
\left {\begin{aligned}
&\dfrac{n(n+1)}{2} & & \text{if}\quad k=0 \
&\dfrac{n}{1-\omega_n^k} & & \text{if}\quad k=1,2,\dots,n-1\
\end{aligned}\right.$

其中第二行式子容易得出，因为

$\begin{aligned}
y_k&=\dfrac{n\omega_n^{k(n+1)}-(n+1)\omega_n^n+1}{(\omega_n^k-1)^2}\
&=\dfrac{n\omega_n^k-(n+1)+1}{(\omega_n^k-1)^2}\
&=\dfrac{n(\omega_n^k-1)}{(\omega_n^k-1)^2}\
&=\dfrac{n}{\omega_n^k-1}\
\end{aligned}$

可见，$y_k$可以以$O(n)$的时间全部计算出来。

接下来，对题目中的故障电路输入上面所提供的输入，获得输出$y’$，并且记录集合$S={k:y_k\neq y_k’,k\in[0,n)}$。令$m=\lg n$，对于图中的FFT电路，可见一个错误的输入将会导致两个错误的输出，也就是说，如果第$i$个阶段的电路发生故障，那么最终将会导致$2^{m-i}$个输出错误。

因此，在这个电路中发生故障的蝶形电路是在阶段$s=m-\lg |S|$中。并且可见，对于$S$中的所有数，它们都是关于$2^{s}$同余的，因此故障蝶形电路所在蝶形电路组的编号为$\displaystyle{j=\dfrac{\min_{x\in S}x}{2}}$。接下来求故障蝶形电路所在的蝶形电路组$g$。

首先，如果蝶形电路的两个输入均为$0$，那么两个输出也是$0$。这启发我们首先定义多项式$\displaystyle{A{l,r}(x)=\sum{i=0}^{n-1} a_{l,r,i} x^i}$，其中系数如下：

$a_{l,r,i}=
\left {\begin{aligned}
&i+1 & & \text{if}\quad l\le i\le r \
&0 & & \text{otherwise}\
\end{aligned}\right.$

可以发现，$A{0,n-1}(x)=A(x)$。类似的，当$x\neq 1$时，可以得到$A{l,r}(x)=\dfrac{(l+1)x^l-lx^{l+1}-(r+2)x^{r+1}+(r+1)x^{r+2}}{(x-1)^2}$

对于$k\in[0,n)$，考虑计算$y{l,r,k}=A{l,r}(\omega_n^k)$的值，那么有

$y_{l,r,k}=
\left {\begin{aligned}
&\dfrac{(l+r + 2)(r-l+1)}{2} & & \text{if}\quad k=0 \
&\dfrac{(l+1)\omega_n^{kl}-l\omega_n^{k(l+1)}-(r+2)\omega_n^{k(r+1)}+(r+1)\omega_n^{k(r+2)}}{(\omega_n^k-1)^2} & & \text{if}\quad k=1,2,\dots,n-1\
\end{aligned}\right.$

同样可见，$y_{l,r,k}$可以以$O(n)$的时间全部计算出来。

那么我们考虑使用二分法来确定电路组$g$，每次给定对应的输入，判断一个连续的蝶形电路组$[l,r]$是否包含了一个故障蝶形电路（即输入多项式$A_{lr}(x)$并判断输出结果是否正确），如果输出不正确，那么故障的电路确实在这个电路组中。最终需要$\lg n-s$次判断即可。

因此，最终我们只需要恰好$\lg n-s+1$次（至多$\lg n$从）的判断。整个找出故障蝶形电路的位置$(s,g,j)$由程序FIND-FAILED-ADDER给出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
GEN-POLY(l, r, n)
  let A[0 : n - 1] be a new array
  for i = 0 to n - 1
    if l <= i and i <= r
      A[i] = A[i + 1]
    else
      A[i] = 0
  return A[i]

COMPUT-CORRECT-RESULT(l, r, n)
  let Y[0 : n - 1] be a new array
  ωn = exp(2 * π * i / n)
  ωnl = ωn ^ l
  ωnl1 = ωnl * ωn
  ωnr1 = ωn ^ (r + 1)
  ωrn2 = ωnr1 * ωn
  ω = 1
  ωl = 1
  ωl1 = 1
  ωr1 = 1
  ωr2 = 1
  Y[0] = (l + r + 2) * (r - l + 1) / 2
  for k = 1 to n - 1
    ω = ω * ωn
    ωl = ωl * ωnl
    ωl1 = ωl1 * ωnl1
    ωr1 = ωr1 * ωnr1
    ωr2 = ωr2 * ωnr2
    Y[k] = ((l + 1) * ωl - l * ωl1 - (r + 2) * ωr1 + (r + 1) * ωr2) / (ω - 1) ^ 2
  return Y

// D是题目所提供的带有故障的FFT电路
FIND-FAILED-ADDER(D, n)
  m = lg n
  y = COMPUT-CORRECT-RESULT(0, n - 1, n)
  input polynomial GEN-PLOY(0, n - 1, n), run FFT circuit D, and get output y'
  S = {k : y_k != y_k', 0 <= k < n}
  s = lg |S|
  j = min{x : x ∈ S} / 2
  l = 0
  r = n / 2 ^ s - 1 
  while l < r
    mid = ⌊(l + r) / 2⌋
    Alr = GEN-PLOY((2 ^ s) * l, 2 ^ s * (mid + 1) - 1, n)
    y = GEN-POLY((2 ^ s) * l, 2 ^ s * (mid + 1) - 1, n)
    input polynomial Alr, run FFT circuit D, and get output y'
    if y == y'
      // 说明带有故障电路组不在区间[l, mid]中
      l = mid + 1
    else
      r = mid
  return s, l, j