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

  32 String Matching
    The naive string-matching algorithm
      起始位置逐个移动进行匹配

    Rabin-Karp Algrithm
      转成数字表示 计算文本t的前m个数表示的数O(m) 计算后n-m个数O(n-m)
      然后比较 每次后移一下需要O(1)时间 总共O(n-m+1) 计算时可以转成计算对匹配串模值  相等时再进一步比较

    String matching with finite automata
      Finite Automata
        (Q,q0, A, Σ, δ)
        Q 状态集合 q0起始状态 A允许状态集合 Σ输入字母表 δ转换函数
        在自动机为状态q的时候 如果读入a 就转到δ(q,a)状态

      String-matching automata
        σ(x) = max{k| P的前k个字符 是x的后缀}
        δ(q, a) = σ(Pq+a)
        用i扫描文本串 q = δ(q, T[i]) 如果q=m 匹配成功

      Computing the transition function
        q从0枚举到m 对于每个可能输入的a 判断Pq+a的最长后缀

    The Knuth-Morris-Pratt algorithm
      The prefix function for a pattern
        π[q] = max{k|k<q and Pk 是Pq后缀}
        用i扫描文本 对于每个i 指针p扫描匹配串 匹配的时候p往右移 只要不匹配移到前一个的π[p]值位置上 p=0的时候继续 p=m的时候结束

        计算π[q]
        q扫描匹配串 求π[q] 如果P[k]和P[q]不匹配 k移动到π[k-1]上 匹配的话就k+1 π[q]=k

  33 Computational Geometry
    Line-segment properties
      Cross products
      p1×p2 = det(x1 x2 y1 y2) = x1y2-x2y1 = -p2×p1

      Determining whether consecutive segments turn left or right
      如果p1×p2为正  p1转向p2为逆时针方向 为负 顺治针方向 0 共线

      Determining whether two line segments intersect
      线段AB A两端点对于B不同向 B同 满足即相交 如果有断点在另外线段上亦可

    Determining whether any pair of segments intersects
      假设没有垂直线段 没有三线共点
      一根扫描线 x 如果x与两线段相交 那么 上面一条线段大于下面那条

      将端点排序 扫描线从最左开始往右 访问端点即可 如果是左端点 加入该线段 如果有线段比他大或者小 并且相交 就返回真 如果右端点 去掉该线段 如果上下都有线段 并且上线段和下线段相交 返回真

    Finding the convex hull
      convex hull 最小凸多边形 包括所有点
      Graham’s scan
        将点以最下的点为基准 按极角排序 栈中放入3个点 只要栈顶的三个点不满足左拐 就弹出栈顶 放入下一个元素 O(nlgn)

      Jarvis’s march
        用包裹的办法 形成的凸包满足后一个在所有点中对前一个和前前个形成的平线的极角最小 当到达最高点的时候转换另一半 O(nh)

    Finding the closet pair of points
      The divide-and-conquer algorithm
      只有3个点的时候 朴素算 找到垂线等分点 然后再两边分别找最近 最近的最小值为d 最后在垂线两边d范围内 对于每个点 只需要找这个点按Y值排序后7个点 计算最短距离 后得到最短距离

    Convex Layers
      凸包求完后 求剩余点的凸包
      O(n^2) Jarvis不停作

    Ghostbusters and ghosts
      Ghostbusters有质子包可以扔鬼 直线传播 到鬼就停 质子流不能交叉 配对扔鬼 没有三点共线
     
     
  34 NP-Completeness
    shortest vs longest simple path
    euler tour vs hamiltonian cycle
    2-CNF satisfiability vs 3-CNF satisfiability

    NP-completeness and the classes P and NP
      P   可在多项式时间内解决的问题
      NP  可在多项式时间内判断的问题
      NPC 难处理问题

    Overview of showing problems to be NPC
      是判定是否的问题
      能够将A问题在多项式时间内转化为B问题 并且解答一样 如果B是NPC 我们可以认为A是NPC

    A first NPC problem
      对于逻辑电路是否有真结果的判断

    P ?= NP

  35 Approximation Algorithms
    vertex-cover problem
      图中每条边至少有一个顶点在集合内 查找最小集合
      任取一边 加入两点 删除引申边 继续

    traveling-salesman problem
      平面上点求访问一周最短距离
      任取一点做根 求MST 记录先序遍历结果 求Hamiltonian cycle

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

VIII Appendix: Mathematical Background
  A Summation formulas and properties
    lim(ak) 存在 即收敛 不存在 发散
    Linearity
    Σ(cak+bk) = cΣ(ak) + Σ(bk)
    Σ(Θ(f(k))) = Θ(Σ(f(k)))

    Arithmetic series
    Σ(k) = Θ(n^2) = n(n+1)/2
    Σ(k^2) = n(n+1)(2n+1)/6
    Σ(k^3) = n^2(n+1)^2/4
   
    Geometric series
    Σ(x^k) = (x^(n+1) -1)/(x-1)
    lim(Σ(x^k)) = 1/(1-x)  |x|<1

    Harmonic series
    Hn = Σ(1/k) = ln n + O(1)

    Integrating and differentiating series
      lim(Σ(kx^k)) = x/(1-x)^2

    Telescoping series
      Σ(ak-ak-1) = an - a0
      Σ(1/(k(k+1))) = 1-1/n

    Products
      lg(Π(ak)) = Σ(lgak)

  Bounding summations
    Mathematical induction
    Σ(3^k) <= c*3^n + 3^(n+1) <= c*3^(n+1)

    Bounding the terms
    Σ(k) <= Σ(n) = n^2

    Splitting summations
    Σ(1..n) = Σ(1..n/2) + Σ(n/2+1..n) >= Σ(0) + Σ(n/2) = (n/2)^2 = Ω(n^2)

    Hn = Σ(1/k) <= Σ(Σ(1/(2^i+j) [j=0..2^i-1]) [i=0..lgn])

    Approximation by Integrals
    ∫(f(x)dx)[m-1..n] <= Σ(f(x)[m..n]) <= ∫(f(x)dx [m..n+1])

    Σ(1/k [1..n]) >= ∫(1/x*dx [1..n+1]) = ln(n+1)
    1+ Σ(1/k [2..n]) <= 1+∫(1/x*dx [1..n]) = 1+ lnn

  B Sets, Etc.
    Empty set laws 并空不变 交空为空
    Idempotency laws 自并不变 自交不变
    Commutative laws 交换律
    Associative laws 结合律
    Distributive laws A∩(B∪C) = (A∩B)∪(A∩C)   A∪(B∩C) = (A∪B)∩(A∪C)
    Absorption laws A∩(A∪B) = A  A∪(A∩B) = A
    DeMorgan’s laws A-(B∩C) = (A-B)∪(A-C)  A-(B∪C) = (A-B)∩(A-C)

  C Counting and Probability
    Pr{A∪B} = Pr{A} + Pr{B} - Pr{A∩B} <= Pr{A} + Pr{B}

    Two events are independent if Pr{A∩B} = Pr{A}Pr{B}

    Bayes’s theorem
      Pr{A∩B} = Pr{B}Pr{A|B} = Pr{A}Pr{B|A}

      Pr{A|B} = Pr{A}Pr{B|A}/Pr{B}

    Expected value of a random variable
      E[x] = ΣxPr{X=x}
      E[X+Y] = E[X] + E[Y]
      E[XY] = ΣΣxyPr{X=x and Y=y}

    Variance and standard deviation
      Var[X] = E[X^2] - E^2[X]

    Geometric distribution
      Pr{X=k} = q^(k-1)p
      E[X] = 1/p
      Var[X] = q/p^2

    Binomial distribution
      Pr{X=k} = C(n, k) p^k q^(n-k)
      E[X] = np
      Var[X] = npq

    The tails of the binomial distribution
      Pr{X>=k} <= C(n, k) p^k
文章来源: http://thunderfyc.wordpress.com.cn/