算法导论30.3 Exercises 答案

发表于 分类于 阅读次数： 本文字数： 3.8k 阅读时长 ≈ 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=(b_0,b_1,\dots,b_{n-1})^T\)。那么由于是对向量\(k\)进行逆序，即相当于将位置\(i\)上的比特转移到位置\(n-1-j\)。因此，\(M\)矩阵的构造如下：

\[ m_{ij}= \left \{\begin{aligned} &1 & & \text{if}\quad i+j=n-1 \\ &0 & & \text{if}\quad i+j\neq n-1 \\ \end{aligned}\right. \]

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

\[ \begin{bmatrix} 0 & 0 & 0 & \cdots & 0 & 1\\ 0 & 0 & 0 & \cdots & 1 & 0\\ 0 & 0 & 0 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 1 & 0 &\cdots & 0 & 0\\ 1 & 0 & 0 &\cdots & 0 & 0 \end{bmatrix} \]

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)\)，输入\(a_i=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