fseasy#blog#2015-09-16-算法设计与分析-课后总结11

--- layout: post title: 算法设计与分析-课后总结1 date: 2015-09-16 categories: 笔记 tags: 算法 onewords: 第一节课主要是对算法课程的概述。 --- > 算法课程概述。 ### 问题 1. 计算机能够解决的问题 1. 数值计算问题 2. 非数值计算问题 2. NP问题、Non-NP问题、P问题、NP-H、NP完全问题 图示（待补充）  1. 问题分为NP问题和Non-NP问题 *NP*就是指**非确定图灵机**在**多项式时间**里可解的问题。 Non-NP就是非确定图灵机在多项式时间内不可解。 > 非确定图灵机 : 每一步的执行不是确定的。对立面是确定的图灵机，每步按照基础指令确定的执行。**当前的计算机是确定的图灵机。** > 多项式时间： 多项式，即 $ n $ , $ n^2 $ , $ nlog n $之类的。$x^n$是关于n的非多项式，是关于n的指数形式。 2. P问题 P问题是完全属于NP问题的子集。 **P问题是指用确定图灵机可在多项式时间内可解的问题。** 3. NP-H及NP完全问题