中科院陈玉福算法课件ch1ppt

《中科院陈玉福算法课件ch1ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机算法设计与分析计算机算法设计与分析TheDesignandAnalysisofTheDesignandAnalysisofComputerAlgorithmsComputerAlgorithms中国科学院研究生院陈玉福关于计算机算法关于计算机算法ò计算机科学是一种创造性思维活动，其教育必须面向设计；ò计算机算法是任何定义好了的计算程式，它取某些值或值ò的集合作为输入，并产生某些值或值的集合作为输出。ò计算机算法的特征–数据输入与输出；–确定性：算法的每一步计算（包括判断）必须要有确切的定义，即每一步计算动作必须是清楚的，无二义性。–可实现性：每种计算至少在原理上能由人用纸和笔在有限的

2、时间内完成。–有穷性：一个算法总是在执行了有穷步之后终止。关于算法设计与分析关于算法设计与分析ò如何设计算法：问题的数学模型、经典算法、分析改进。ò如何表示算法：输入数据结构、描述算法的语言、算法ò流程、逻辑结构。C++或ALGEN（伪代码）。ò如何分析算法：发现算法特性、估计对各种应用的适合程度、相同应用中与其它算法的比较。确定输入数据模型、确定每项基本操作所用时间及出现频率、统计数据、分析推求。ò如何测试算法：正确性、有穷性；白盒法、黑盒法。教教学学要要求求ò教学内容ò参考文献ò余祥宣等，《计算机算法基础》，华中理ò复杂性分析初步工大学出版社，2005。ò图与遍历算法òAlfredV.

3、Aho等，《计算机算法的设计与ò分治算法分析》（英文影印版），机械工业出版ò贪心算法社，2006。ò动态规划算法òS.Baase,A.VanGelder，《COMPUTERALGORITHMS-IntroductiontoDesignandò回溯算法Analysis》,ThirdEdition,HigherEducationò分枝定界算法Press,2001.òNP－完全问题òCormen，T.H.等，《算法导论》，高等教育出版社，2001。ò考核ò王晓东，《计算机算法设计与分析》，电ò40学时/2学分子工业出版社，2001。ò平时20%,出席、作业ò期末80%,课堂开卷ò联系：yfche

4、n@gucas.ac.cn第一章第一章复杂性分析初步复杂性分析初步ò计算复杂性的本质是研究完善的模型，在这样的模型范围内可以评估重要问题的固有困难，并得以进一步研究“有效的”算法。对于许多重要问题，已知算法的复杂度在最坏情形下的渐近下界和上界之间存在显著的差距。计算复杂性研究能够在探索这些问题的新算法方面提供指导。ò计算复杂性体现在算法占用机器空间资源和时间资源的情况，是关于选定模型下输入数据规模的函数。起决定作用的是这些函数当输入数据规模趋于无穷大时的渐进性态。ò一种输入数据模型的选用可能使复杂性分析更简单，而另一种输入模型可能更好地反映程序将被使用的情况。空间复杂性空间复杂性¾考虑空间

5、复杂性的理由在多用户系统中运行时，需指明分配给该程序的内存大小；想预先知道计算机系统是否有足够的内存来运行该程序；用空间复杂性来估计一个程序可能解决的问题的最大规模；一个问题可能有若干个不同的内存需求解决方案，从中择优。指令空间:存储编译后的程序指令ò指令空间的大小取决于如下因素：ò把程序编译成机器代码的编译器，编译器不同，则产生的机器代码的长度就会有差异；ò编译时实际采用的编译器选项，如优化模式、覆盖模式，选用优化模式可缩短代码长度，但会增加运行时间；ò目标计算机的配置，如带有浮点处理硬件的，每个浮点操作转换为一条机器指令，否则，必须生成仿真的浮点计算代码，使整个机器代码加长。ò一般情况

6、下，指令空间对于所解决的特定问题不够敏感。数据空间：存储所有常量和变量的值存储常量和简单变量：所需的空间取决于所使用的计算机和编译器,以及变量与常量的数目；存储复合变量：包括数据结构所需的空间及动态分配的空间；计算方法：复合变量所占空间等于各个成员所占空间的累加。例如：数组变量所占空间等于数组大小乘以单个数组元素所占的空间。doublea[100];所需空间为100×8＝800intmatrix[r][c];所需空间为4×r×cBorlandC++基本数据类型（32位字长机器）类型名说明字节数使用范围char字符型1-128~127unsignedchar无符号字符型10~255point

7、er指针型2short[int]短整型2-32768~32767signedshort[int]有符号短整型2-32768~32767unsignedshort[int]无符号短整型20~65535int整型4-2147483648~2147483647signed[int]有符号整型4-2147483648~2147483647unsigned[int]无符号整型40~4294967295long[int]长整型4-2