Computation Theory Final Exam Review

Chapter 12:

  • undecidable decision problem不可解问题
    • 不是所有问题都能找到多项式级的算法
    • 有些问题甚至没有正确的算法
  • Understand what it means for a problem to be decidable (or not)
    • A decision problem is any arbitrary yes-or-no question on an infinite set of input.
    • 也就是任意的输入都能产生一个yes或者no的结果
  • Be able to state the Halting Problem and discuss its implications含义.
    • halting problem 停机问题
      • 因为不存在一个算法，是的我们无法写出一个程序来判断一个随机程序P能够对所有的输入停机
      • 判断任意一个程序是否会在有限的时间之内结束执行的问题。该问题等价于
        • 给定一个程序P和输入w，程序P再输入w下能够最终停止
      • 停机问题是无解的
  • Be able to outline概述 a proof of the Halting Problem.
    • 证明
      • 用反证
        • 假设停机问题有解
          • 那么就存在过程H(P,I)可以判断程序P再输入I的情况下是否可停机的问题
            • 如果P在输入的时候可以停机，那么H输出停机
            • 如果不能停机，就输出无限循环（无限循环那么其实也是停机），所以矛盾
  • Be able to carry out a reducibility（归约） argument辩论.
    • 一个问题A能够归约化为问题B的含义是，可以用问题B的解法解决A
    • e.g
      • 我们要求解一个一元一次方程和一个一元二次方程，那么我们可以说前者可以约化成后者
      • 也可以说求解一元二次方程的时间复杂度要高于求解一元一次方程
        • 因为如果求解一元二次方程的时间复杂度比求解一元一次方程的时间复杂度还低，那么就可以把算法优化
    • 约化的过程只有在用多项式的时间完成才有意义

Chapter 14:

  • Be able to give an informal definition for the sets P, NP, and NP-complete.
    • set P
      • 问题能够再多项式（polynomial）时间内解决
      • 也就是可以一步步很有效率的解决的问题
      • 或者说，可以用deterministic sequential machine在多项式时间内解决的decision problem
    • set NP
      • 在多项式时间内验证一个解的问题，也就是在多项式时间内猜出一个解的问题
      • 也就是你求出了一个问题的解，我要验证你的解是否正确，我用了多项式时间，至于你求解这个问题是否用多项式时间不关我事，可能这个问题有多项式的算法，可能没有。
      • 或者说，可以用non deterministic sequential machine在多项式时间内解决的decision problem。
        • 这类问题只要给个解答，可以很快验证这个解答是否正确
    • set NP-complete
      • 最麻烦的NP问题，基本不可能有P的解法
        • 例子：
          • 我们要在一堆整数内找出和为零的那些组合
            • 我们可以很容易验证一个组合的和是否为零，因此是NP问题
            • 但是要我们去找，是没有P的解法的
            • 所以这个是一个NP-complete问题
      • 通俗的讲就是一个时间复杂度最高，并且能够“通吃“所有NP问题的NP问题
        • 也就是解决了这个问题，所有的NP问题就解决了
      • 有以下两个条件
        • 1.是一个NP问题
        • 2.所有NP问题都能约化成它
      • 证明NP-complete问题
        • 首先证明他是一个NP问题
        • 然后证明其中一个NP-complete问题能够约化成它。
    • 关系
      • NP和NP-hard的交集是NP-complete
      • P在NP内
      • 所有NP问题都可以设计出一个多项式的算法，转换成另外一个NP问题
        • 也就是所有的NP问题都可以用多项式时间的算法来彼此转换
    • NP=P？
      • 也就是NP是否能够用P的时间解决？
        • 如果可一个话，NP问题就会都变成P问题
  • Be able to give an informal definition for the set NP hard and its relationship to the classes P, 
 NP, and NP-complete.
    • NP-hard问题
      • 满足NP-complete问题的第二个条件，但是不满足第一个条件
      • 也就是所有NP问题都能约化成它，但是它不是一个NP问题
      • 定义：一个问题被称为P-hard问题，当且仅当一个NP-complete问题可以在多项式时间内归约到这个问题
      • 也就是NP-hard问题比NP-complete问题还难
  • Be able to name some NP-complete problems.
    • traveling salesman problem旅行者问题
      • 这个问题是NP-complete问题，并且这个也是NP-hard问题
      • 是一个多局部最优的最优化问题
      • 问题描述：
        • 有n个城市，一个推销员要从其中一个城市出发，走遍所有城市（每个城市只能走一遍），再回到原点，求是否存在最短路
        • 如果暴力枚举，只能O(n!)
        • 动态规划可以加快到O((n2) * (2n))

Compiler theory:

  • There will be a question or two based on the compiler theory session (slides are online).
    • 编译过程：
      • 首先是lexical analyzer词法分析
      • 其次是syntax analyzer语法分析器
        • 至上而下分析
        • 至下而上分析
        • 用于解析字串，并且看看是否满足语法
          • 语法：
            • 上下文无关文法
              • pda能够识别任何上下文无关文法生成的语法
      • 其次是semantic analyzer语义分析
      • 其次是intermediate code generator中间代码生成
      • 其次是code optimizer代码优化
      • 最后是code generator代码生成
    • lexical analyzer
    • FSA:finite state machine
    • LL 的意思是scan left to right, substitute leftmost
    • LR 的意思是scan left to right, substitute rightmost
    • LL(k) 向前看前k个symbol，看是否能够决定每一句语法
    • 二义性：能够构造两颗语法树

Divide and Conquer:

  • Be able to describe the divide-and-conquer design technique and give at least one example of an algorithm that uses this technique.
    • 分而治之思想
      • 把一个大问题分成几个小问题
      • 分别解决这些小问题
      • 把小问题的解答组合起来，得到原来问题的答案
    • 例子；
      • 归并排序
        • sort数组
          • 如果子集为1，那么算法终止
          • 否则，把集合分割成两个子集，对每个子集排序
            • 然后把排序好的子集归并为一个集合
      • 并行算法

Dynamic Programming:

  • Be able to describe the characteristics of problems suitable for this design approach and give at least one example of an algorithm that uses this technique.
    • 动态规划是子问题最优化问题
    • 例子有最长公共子串，最长公共子序列，背包，TSP
      • 最长公共子串
        • 假设两个字符串s和t，s[i]和t[j]表示第i个和第j个字符
        • L[i][j]表示以s[i]和t[j]结尾的相同子串的最长长度
          • 那么L[i][j]和L[i+1][j+1]的关系是
            • L[i+1][j+1] = s[i]==t[j]?L[i][j]+1:0
  • Be able to solve a problem using dynamic programming given some hints.

Greedy Algorithms:

  • Be able to describe the greedy algorithm design technique and give at least one example of an algorithm that uses this technique.
    • 最优子结构问题
    • 每次都找最优解
  • Be able to trace Dijkstra’s shortest path problem on a given graph.
    • 首先从空的集合开始，选择离集合最近的点，把那个点加入集合
    • 然后再更新列表中离这个集合相邻的点的距离
      • 然后以这个新的点开始，找他的邻居
        • 然后对比到这个邻居的最短的路
          • 在原有的最短路上加上这个新的点的距离
            • 如果比前一步加上另外一条路径的距离还长，就更新最短路
              • 否则就把当前的这个值更新
      • 循环直到到达终点
  • Be able to generate Huffman codes for a given frequency analysis
    • A B C D E F G
      2 3 4 3 3 3 4
    • 解法是首先排序
      • A B F D E C G
        2 3 3 3 3 4 4
    • 然后递归的对数组中最小的两个元素进行合并
1
2
3
4
5
6
7

         （22）
         /    \
      （9）     (13)
      /  \      /   \
    G(4) (5)   (7)   (6)
         / \    | \     |\
       A(2)B(3) E(3)C(4)F(3)D(3)

Amortized Analysis:

  • Be able to describe the goal of an amortized analysis for a given algorithm.
    • 平摊分析
      • 执行一系列数据结构所需要的时间是通过执行的所有操作求平均得到的。
      • 平摊分析可以用来证明在一系列操作中，通过对所有操作求平均之后，即使对其中单一的操作具有较大的代价，平均代价还是很小的
    • aggregate method
      • 证明对所有的n，由n各操作所构成的序列的总时间再最坏情况下T(n)
      • 所有操作都是同样的cost
    • accounting method
      • 对不同的操作赋予不同的cost，某些操作的费用比他们的实际代价或多或少
      • 平摊代价：一个操作的收费数量
        • 如果一个操作的平摊代价超过他的实际代价的时候，差值就是credit
          • 这个credit用来补偿那些平摊代价地域实际代价的操作
      • 总的平摊代价是总的实际代价的上界
    • potential method
      • 平摊代价=实际代价+势能
      • 平摊代价依赖于势函数，不同的势函数会产生不同的平摊代价，但是都是实际代价的上限
      • e.g
        • 动态表
          • 当向满的表插入一个元素，把表扩大一倍
          • 当删除意向引起表不足1/4满时，把表缩小为原来的一半
        • 由平摊分析可知两项操作的平摊代价都是O(1)
  • Be able to carry out an amortized analysis (using the aggregate method, the accounting method, or the potential method, as specified) for a given algorithm given some hints.

Approximation Algorithms:

  • 近似算法的结果不一定是最优的（不是说结果不准确）
  • 对于一些已经被证明是NP-complete问题的优化问题，无法在多项式时间内得到最优解
  • Be able to give the characteristics of a good approximation algorithm
    • 假设最优值为K，求解一个问题的近似算法求得的近似最优解相应的目标函数值为C
      • 所以近似性能比x={K/C,C/K}
      • 假设通常情况下，性能比x是问题输入规模n的一个函数P(n)，也就是x<=P(n)
      • 相对误差定义为s=abs((K-C) / K)
        • 如果对问题有输入规模n，有一函数V(n)>=s,那么V(n)为该近似算法的相对误差界。
      • 那么有P(n)-1>=V(n)
  • Be able to define what it means for an approximation algorithm to give an answer “close” to the optimum result.
compiler
Comments

Comments