Presentation is loading. Please wait.

Presentation is loading. Please wait.

关于复杂性理论的一点探讨 孙广中 sungz@mail.ustc.edu.cn.

Similar presentations


Presentation on theme: "关于复杂性理论的一点探讨 孙广中 sungz@mail.ustc.edu.cn."— Presentation transcript:

1 关于复杂性理论的一点探讨 孙广中

2 计算理论与计算复杂性理论 关于计算的形式描述 可计算与不可计算 计算复杂性的刻画 计算复杂性理论的应用 新的计算模型

3 算法的定义 为实现某个任务而构成的简单指令集 有穷的计算良过程 通过有限多次运算可以决定的过程 正确 直观,非形式

4 算法的定义 希尔伯特第十问题(1900) Alan Turing & Alonzo Church(1936) 算法:图灵机程序
设计一个算法来判断多项式是否有整数根 算法:通过有限多次运算可以决定的过程 Alan Turing & Alonzo Church(1936) 图灵机程序 算法:图灵机程序 形式化的,精确的

5 可计算与不可计算 停机问题 希尔伯特第十问题 软件验证

6 计算复杂性的刻画 P类(Polynomial) NP类(Nondeterministic Polynomial ) PSPACE类
IP类, RP类, … NP-完全理论

7 计算复杂性理论的应用 算法分析 近似算法的下界 随机算法

8 新的计算模型 DNA计算 量子计算 Richard Feynman 1982 David Deutsch 1985
A.C. Yao 1993 Peter Shor 1994 Grover L. K

9 复杂性理论 关于复杂的形式描述 可描述与不可描述 复杂性的刻画 复杂性理论的应用 新的模型

10 是否需要这方面的研究?

11 谢谢大家!


Download ppt "关于复杂性理论的一点探讨 孙广中 sungz@mail.ustc.edu.cn."

Similar presentations


Ads by Google