数据与算法课件：19 计算复杂性理论.pdf

计算复杂性理论 计算复杂性理论是计算机科学的一个重要分支，旨在依据计算的难度对计算问题进行分类，以及分析不同难度类别问题之间的关联。计算复杂性理论的发展历史可以追溯到1936年，Alan Turing提出的图灵机模型能够灵活的定义计算。1965年，Hartmanis和Stearns发表论文阐述了计算的时间、空间复杂度的定义。1965年，Edmonds提出多项式时间复杂度的问题。1971年，Cook和Levin各自独立证明了NP-Complete问题的存在。1972年，Karp发表论文证明了21个不同的组合优化和图论问题属于NP-Complete。 图灵机是计算复杂性理论的基础模型，由于英国数学家Alan Turing提出的一种抽象的计算模型，可以用来描述任何有限的数学逻辑过程。图灵机的构成包括划分成若干小格子的无限长度纸带，一个读写头可以在纸袋上左右移动，能读出或改写当前格子中的符号，一套控制规则规定在当前机器所处状态以及当前格子中符号的情况下，读写头下一步的动作，以及机器的下一个状态，还有一个状态寄存器记录机器当前的状态，状态数目是有限的，且存在特殊状态称为停机。 图灵机可以描述任何的计算过程（算法、程序）；如果一个图灵机可以模拟任何其他图灵机的操作，就称为通用图灵机（计算机）。图灵机工作过程是：初始时，图灵机状态为起始状态，输入符号串从左到右填写在纸带上，其他格子填写空格，读头指向最左侧格子；开始运行后，读取符号，依照转移函数的描述改写符号、移动读头、改变状态；若某个时刻，图灵机状态为接受状态，则接受输入串并停机；若图灵机状态为拒绝状态，则拒绝输入串并停机。 计算问题可以分为判定性问题、搜索问题、计数问题和优化问题等。判定性问题是指在某些形式系统下回答为是或者否的问题。搜索问题是指问题的解答可能是任何的串。计数问题是指解答一个搜索问题中所有可能解的数目。优化问题是指找到所有可能解中最‘优’的一个。 计算复杂性理论在计算机科学中的重要性不言而喻，因为它可以帮助我们更好地理解计算问题的难度，设计更加高效的算法，提高计算机科学的发展。