文章来源: http://thunderfyc.wodpress.com.cn/

VII Selected Topics
  27 Sorting Networks
    总共N条数据线 要排序数据沿着线传递 某些两根线之间有比较交换器 可以在逆序时交换两线数据

    
    The zero-one principle
      如果排序网络满足所有可能的由01组成的数据 就能满足任意数据

    A bitonic sorting network
      Bitonic Sequence 先增后减或先减后增再减的序列
      Half-Cleaner 将第i个 和第i+n个比较 在上下中至少有一半会全0或全1
      Bitonic Sorter 继续在上下两个分区中做Half-Cleaner

    A merging network
      XY两个有序序列 将Y反序和X合并就是Bitonic序列 然后排序即可

    A sorting network
      先将相邻两个都排序 然后做Merging Network

  28 Matrix Operations
    Transpose 转置矩阵 行列颠倒

    乘法计算 cik = sigma(aij*bjk)
    A(BC) = (AB)C A0 = 0 IA != AI A(B+C) = AB+AC

    x是向量 (x1, x2, x3,…,xn)是Linearly Dependent 当存在系数使得 c1×1+c2×2+…+cnxn = 0
    列Rank是Linearly Independent的最大列数 行Rank同 当n*n时 为矩阵rank

    Positive-definite Matrices
      n*n的矩阵A 如果是正定矩阵 那么x’Ax>0 对于所有n非零向量x x’为转置矩阵
      任意均线形独立的A  A’A是正定矩阵

    Strassen’s Algorithm for matrix Multiplication
      左上右上左下右下 X abcd Y efgh  Z rstu  Z = XY
      A1 = a      B1 = f-h      P1 = A1B1
      A2 = a+b    B2 = h        P2 = A2B2
      A3 = c+d    B3 = e        P3 = A3B3
      A4 = d      B4 = g-e      P4 = A4B4
      A5 = a+d    B5 = e+h      P5 = A5B5
      A6 = b-d    B6 = g+h      P6 = A6B6
      A7 = a-c    B7 = e+f      P7 = A7B7
      r = P5+P4-P2+P6
      s = P1+P2
      t = P3+P4
      u = P5+P1-P3-P7
      巨型稠密图时采用

    Solving systems of linear equations
      a11×1 + a12×2 + … + a1nxn = b1
      a21×1 + a22×2 + … + a2nxn = b2
      …………………………..
      an1×1 + an2×2 + … + annxn = bn

      a形成矩阵A x形成列向量X b形成列向量B
      AX = B
      X = A’B (A’A = E)
      如果A的rank比n小 无法确定

      LUP方法
      求LUP使得 PA = LU
      L是单位左下三角矩阵 U是右上三角矩阵 P是排列矩阵（每个1不同行不同列 其余为0）
      AX = B PAX = PB LUX = PB Y = UX Forward substitution 得到Y back substitution得到X
     
      Forward Substitution LY = PB = B’
         y1                 = b1′
      l21y1 + y2            = b2′
      l31y1 + l32y2 + y3    = b3′
      ………………………
      ln1y1+… + yn        = bn’

      直接求y1 yi = bi’ - sigma(lij yj)

      Back Substitution
      u11×1 + u12×2 + … + u1nxn = y1
      …………………………..
              un-1n-1 xn-1+unn xn = yn-1
                           unn xn = yn
      直接求xn xi = (yi - sigma(uijxj))/uii

      LU
      A = ((a11 wT)(v A’)) = ((1 0)(v/a11 In-1))*((a11 wT)(0 A’-vwT/a11))
        = ((1 0)(v/a11 In-1))((a11 wT)(0 L’U'))
        = ((1 0)(v/a11 L’))((a11 wT)(0 U’))
        = LU
      a11为0 或者A’-vwT/a11为0时 用P来轮换避免 正定矩阵不需要轮换
      LU 枚举K 1->n 得到ukk = akk 然后做i k+1->n lik = aik/ukk uki = aki 调整a 做i k+1->n j k+1->n aij = aij - lik*ukj 返回L U

      LUP
      交换第1行和第k行 有矩阵Q
      QA = ((ak1 wT) (v A’)) = ((1 0)(v/ak1 In-1)) * ((ak1 wT)(0 A’-vwT/ak1))
      P’(A’-vwT/ak1) = L’U’
      P = ((1 0)(0 P’)) Q

    Inverting matrices
      AX = En
      D = ((En A 0) (0 En B) (0 0 En)) D’ = ((En -A AB) (0 En -B) (0 0 En))
      A = (B CT C D) A’ = (B’+B’CTS’CB’ -B’CTS’ -S’CB’ S’)

    Symmetric positive-definite matrices and least-squares approximation
      任何正定矩阵是满rank的(nonsingular)
      对称正定矩阵的左上角矩阵 都是对称正定矩阵

      Least-squares approximation
      已知m个点 (x1 y1)… (xm ym) 求函数使得yi = F(xi) + η(i) 假定F(x) = c1+c2x +….+cnx^n-1
      设fi(x) = x^i-1
      A ((f1(x1) … fn(x1) … (f1(xm) … fn(xm))) * c (c1..cn) = Ac(F(x1) .. F(xm))

      ||η|| = sqrt(sigma(ηi)^2) = ||Ac-y||^2 = sigma(sigma(aijcj)-yi)^2
      (d||η||^2)/(dck) = sigma(2(sigma(aijcj) - yi))aik = 0
      (Ac - y)^T * A = 0 => AT(Ac-y) = 0 => ATAc = ATy
      c = ((ATA)^-1 AT)y = A’y  A’ = (ATA)^-1 * AT

  29 Linear Programming
    在等式或者不等式的约束下 找最大或最小对象

    General Linear Programs
      线性函数 f(x1, x2,.., xn) = sigma(aj*xj)
      线性不等式 f() <= b / f() >= b
      求解对象 f() 的最值

    An overview of linear programming
      以两个变元为例 我们在笛卡尔坐标系上 可以看到满足约束的变元形成一个多边形区域feasible solution 然后通过做平行线族可以得到解
      对于n变元 每个约束是一个叫做simplex的半空间
      Simplex Algorithm 通过访问每个Simplex的顶点 查找其对象值 其中最优的一个必然是解

      Algorithms for linear programming
        椭圆算法 Ellipsoid Algorithm 内点算法 Interior-point Methods
        对于整数规划 Integer Linear Program 为NP难问题

    Standard and slack forms
      Standard form
        求 sigma(cj*xj)的最大值
        约束条件 sigma(aij*xj) <= bi  xj >= 0

      Slack form
        si = bi - sigma(aij*xj) si >= 0
        xn+i = si
        最后得到若干等式 和均大于等于0的约束

    Formulating problems as linear programs
      Shortest Paths
        求d[t]最小值
        约束条件 d[v] <= d[u] + g[u][v] d[s] = 0

      Maximum flow
        求sigma f(s,v)最大值
        约束条件 f(u,v) <= c(u,v) f(u,v) = -f(v,u) sigma(f(u,v)) = 0

      Minimum-cost flow
        求sigma(a(uv)*f(uv))最小值
        约束条件 f(uv) <= c(uv) f(uv) = -f(vu) sigma(f(uv)) = 0 sigma(f(su)) = targetflow

      Multicommodity flow
        约束条件 sigma(fi(uv)) <= c(uv) fi(uv) = -fi(vu) sigma(fi(uv)) = 0 sigma(fi(su)) = targetflow i

文章来源: http://thunderfyc.wodpress.com.cn/

    The simplex Algorithm
      写成slack form 后 通过pivot操作 将目标函数的系数均为负 所有选0 即为最大
      Pivot操作即将原来在目标函数中的e 转入到约束条件 将约束中的l 放入目标函数
      每次选取一个系数正的e 然后在约束中找到l 满足其等式中 e系数为正 可以找一个常数/系数最小的 如果找不到 就是无解
      如果C(n+m, n)次没有出解 那是死循环了..

  Duality
    给出求最大值的问题 定义一个相关的求最小的问题使得两个问题共解
    已知找最大值的线型规划 找到求最小的对偶问题
    求 sigma(bi*yi)的最小值
    满足约束 sigma(aij*yi)>=cj yi>=0

  The initial basic feasible solution
    做辅助线型规划
    求-x0最大值
    约束条件 sigma(aij*xj) - x0 <= bi xj>=0
    接出来x0=0就退

30 Polynomials and the FFT
  Representation of polynomials
    Coefficient representation
      系数表示
    Point-value representation
      用n个曲线上点确定

    Fast Multiplication of Polynomials in Coefficient Form
      A*B 求A(ω0) A(ω1)… A(ω2n-1) B(ω0) B(ω1)… B(ω2n-1)
      得到C(ω0)..C(ω2n-1) 还原C
      复杂度O(nlgn)

  The DFT and FFT
    Complex roots of unity
      ω^n = 1 ωn = cos(2πi/n) + i sin(2πi/n)
      Cancellation lemma ωdk_dn = ωk_n
      Halving lemma (ω^(k+n/2))^2 = (w^k)^2
      Summation lemma sigma((ωk)^j) = 0

    The DFT
      yk = A(ωk) Discrete Fourier Transform

    The FFT
      Fast Fourier Transform
      A0(x) = ao + a2x + a4x^2 + … + a_n-2 x^(n/2-1)
      A1(x) = a1 + a3x + a5x^2 + … + a_n-1 x^(n/2-1)
      A(x) = A0(x^2)+xA1(x^2)
      递归求 复杂度nlgn

    Interpolation at the complex roots of unity
      a = DFT~(y)zu
      aj = sigma(yk*ω-kj)/2n

  Efficient FFT implementations
    0~7为例 0-4 2-6 1-5 3-7 依次配对 然后延递归树上升  可知第i个位置上的数 是i的二进制补0写法颠倒后的值

Number-Theoretic Algorithms
  Elementary number-theoretic notions
    Divisibility and divisors
      整除
    Prime and composite numbers
      素数和合数
    The division theorem remainders and modular equivalence
      Division theorem a=qn+r 可表示
      Common divisors and gretest common divisors 公约数和最大公约数
      Relatively prime integers 互素数
      Unique factorization 能够唯一分解成若干素数的乘积

  Greatest Common Divisor
    GCD recursion theorem
      gcd(a,b) = gcd(b, a mod b)
    Euclid’s algorithm
      gcd(a, b) = gcd(b, a mod b) [b > 0]  = a [b =0]
    The extended form of Euclid’s Algorithmm
      gcd(a, b) = ax +by 有解
      (d’,x’,y’) = ext_gcd(b, a mod b)  (d,x,y) = (d’, y’, x’-[a/b]y’)

  Modular arithmetic
    Finite groups
      Closure  a∈S b∈S  a@b∈S
      Identity e∈S e@a = a@e = a a∈S
      Associativity (a@b)@c = a@(b@c)
      Inverse a@b = b@a = e

      a mod n = a’ b mod n = b’
      a+b = a’+b’ (mod n)
      ab = a’b’ (mod n)

      Euler’s phi function
        Phi(n) = n(1-1/p1)(1-1/p2)…(1-1/pi) p|n

  Solving modular linear equations
    ax = b (mod n) ax +ny = b gcd(a,n)|b
    gcd(a,n) ax = 1 (mod n)的解mod n唯一 否则无解

  The Chinese remainder theorem
    对于ai = a mod ni ni两两互素 n = n1*n2*..ni
    (ai+bi) mod ni = (a+b) mod ni
    (ai-bi) mod ni = (a-b) mod ni
    (aibi) mod ni = (ab) mod ni

    设mi = n1*n2*..*ni-1*ni+1*…*nk
    mi*ti = 1 (mod ni)
    ci = mi*ti
    a = sigma(ai*ci)
   
    对于ni 两两互素 n=n1*n2*..nk
    x mod ni = ai 的解 mod n 值恒定
    x mod ni = a 的解必为 x mod n = a

  Powers of an Element
    Euler’s theorem
    a^(Phi(n)) = 1 (mod n) a<n
    Fermat’s theorem
    a^(p-1) = 1 (mod p) p是素数 a < p
   
    Modular Exponentiation
      a^b mod n
      b的二进制表示<bk,bk-1,…,b0>
      从左到右 d = (d*d) mod n 如果bi=1 d = (d*a) mod n

  The RSA public-key cryptosystem
    用于加密传输和数字签名的东西 每个人用一个Public key P和一个Secret key S 满足P(S(M)) = M S(P(M)) = M
    加密传输的时候 A将S(M)传给B B用P(S(M)) 解密
    数字签名的时候 A将S(M)和M传给B B用P(S(M))和M比较 相等的话 就证明是A发出的

    随机选择大整数 p q  n=pq 选择和(p-1)(q-1)互素的小奇数e
    计算 d 使得 ed = 1(mod (p-1)(q-1))
    e,n 作为public Key  d,n作为secret key
    P(M) = M^e mod n   S(C) = C^d mod n

  Primality testing
    the density of primes  lim(Pi(n)lnn/n) = 1 n->inf

    Pseudoprimality testing
      a^(n-1) = 1(mod n)
      Carmichael numbers 例外

      The Miller-Rabin randomized primality test
        n-1 = u*2^t 算得a^u的值之后依次计算 当且仅当只有最后为1且前一个数非n-1的时候为素数

  Integer Factorization
    Pollard’s rho heuristic
      x1任取一个数小于n xi = ((xi-1)^2 -1) mod n; d=gcd(y-xi, n) d非1非n 输出 如果i是2次幂 y=xi

文章来源: http://thunderfyc.wodpress.com.cn/