《计算机算法设计与分析》课程教学资源（讲义）第四章 分治算法

贪心算法的特点 贪心算法总是作出在当前来看是最好的选择 就是说,贪心算法并不从整体最优上来考虑 ,所作出的选择只是某种意义上的局部最优 选择

理解RAM，RASP和图灵机计算模型 理解非确定性图灵机的概念 理解P类与NP类语言的概念 理解NP完全问题的概念 理解近似算法的性能比及多项式时间近似格式的概念 通过范例学习NP完全问题的近似算法 （1）顶点覆盖问题 （2）旅行售货员问题 （3）集合覆盖问题 （4）子集和问题

迄今为止，所有的NP完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略。 (1)只对问题的特殊实例求解 (2)用动态规划法或分支限界法求解 (3)用概率算法求解

4.1 活动安排问题 4.2 贪心算法的基本要素 4.3 最优装载 4.4 哈夫曼编码 4.5 单源最短路径 4.6 最小生成树 4.7 多机调度问题 4.8 贪心算法的理论基础

算法与过程 过程(Procedure)与算法(Algorithm)是解决问题的一种方法的逐步描述,它 (1)是由若干条指令组成的有穷序列; (2)每条指令的意义都是确定的; (3)具有零个或多个输入; (4)产生若干个输出;

 C特性简介  第一个C程序 —— HelloWorld  C开发环境  HelloWorld分析  更多示例

上海交通大学：《C程序与算法设计》课程教学资源（课件讲稿）Lecture 02 Divide and Conquer

上海交通大学：《C程序与算法设计》课程教学资源（课件讲稿）Lecture 01 Greedy and Dynamic Programming

一、用计算机求解问题