NP问题与计算模型讲义.pdf

算法设计与分析 算法设计与分析 算法设计与分析 Design and Analysis of Algorithms Design and Analysis of Algorithms Design and Analysis of Algorithms 主讲人 徐 云 主讲人 徐 云 Fall 2013, USTC Fall 2013, USTC Part 1 Foundation Part 1 Foundation Part 2 Sorting and Order Statistics Part 2 Sorting and Order Statistics Part 3 Data Structure Part 3 Data Structure Part 4 Advanced Design and Analysis Techniques Part 4 Advanced Design and Analysis Techniques Part 5 Advanced Data Structures Part 5 Advanced Data Structures Part 6 Graph Algorithms Part 6 Graph Algorithms Part 7 Selected Topics Part 7 Selected Topics … … chap 34 Computation Models and NP-Completeness chap 34 Computation Models and NP-Completeness … … Part 8 Supplement Part 8 Supplement 第34章 计算模型和NP完全 第34章 计算模型和NP完全 34.1 引言 34.1 引言 34.2 图灵机模型 34.2 图灵机模型 34.3 NP完全问题 34.3 NP完全问题 34.1 引言 早期的计算模型 算法与计算模型的关系 计算模型的作用 图灵机与语言识别问题 通用的图灵机 2013/11/10 算法设计与分析 4 早期的计算模型 Recursive Function Theory – Kleene, Church, Turing, Post, 1930’s Turing Machines – Turing, 1930’s RAM Machines – von Neumann, 1940’s Cellular Automata – von Neumann, 1950’s Finite-state machines, pushdown automata various people, 1950’s VLSI models – 1970’s Parallel RAMs, etc. – 1980’s 2013/11/10 算法设计与分析 5 算法与计算模型的关系 非形式地说，算法是为实现某个任务而构造的简单指令 集。这是一个非严格的算法定义。 1900年，Hilbert在巴黎举行的世界数学家大会上提出 了23个数学问题，其中第10个问题是要设计一个算法来 测试多项式是否有整数根，他没有用算法这个术语，而 用这样一句短语：“通过有限多次运算就可以决定的过 程”。 该问题是算法上不可解的，1970年由Yuri Matijasevic解决。 关键在于算法的精确定义，后来由Church和Turing 分别解决，