计算机算法设计与分析

《计算机算法设计与分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、计算机算法设计与分析中国地质大学研究生课程论文课程名称:算法设计与分析教师姓名:戴光明研究生姓名:研究生学号:****研究生专业:***********所在院系:计算机学院类别:A.博士B.硕士√C.进修生日期:2017.01.1324/24计算机算法设计与分析评语对课程论文的评语：平时成绩：课程论文成绩：总成绩：评阅人签名：注：1、无评阅人签名成绩无效；2、必须用钢笔或圆珠笔批阅，用铅笔阅卷无效；3、如有平时成绩，必须在上面评分表中标出，并计算入总成绩。24/24计算机算法设计与分析目录第一章算法导引4一、算法及其特性4二、算法分析4第二章分

2、治法6一、一般方法6二、二分检索法6三、归并分类7四、特斯拉森矩阵乘法8五、总结8第三章贪心算法9一、一般方法9二、背包问题9三、最小生成树10四、单源点最短路径11第四章动态规划12一、优化问题12二、一般原理12三、多段图12四、每对结点间的最短路径14五、最优二分检索树14六、0-1背包问题16七、调度问题16八、TSP问题17第五章基本检索与周游算法18一、一般方法18二、双连通图和深度优先检索19三、决策树（博弈树）21第六章回溯法22第七章分支限界法22一、一般方法22二、回溯法解0-1背包问题22三、分支限界法解0-1背包问题23

3、第八章总结2424/24计算机算法设计与分析第一章算法导引课前题目：编写程序：1、编写两个矩阵相乘的程序；2、如图，菱形ABCD中，E是AD的中点，EF垂直于AC交CB的延长线于F，求证四边形AFBE是平行四边形。AEDFBNMC图1-1平行四边形一、算法及其特性1、算法是什么？算法是计算的方法。2、什么是计算？1)计算是基于规则的符号串的变换；2)计算是基于规则的物理信息的变换；3)计算是基于规则的信息的变换。为了使计算机械化，图灵提出了图灵模型，在此基础上将理论进行技术实现，1946年诞生了第一台计算机（读写头、纸带、四元组），在内存条上进

4、行输入输出。3、算法的特性？4)无二义性：由于算法是由机器执行的，所以算法的每一步都必须是确定的。5)能行性（可计算性与不可计算性）：算法的每一步机器都能够执行（计算机能够解决的问题是有限的）。6)有限性（可计算性与计算复杂性）。二、算法分析算法分析就是分析算法的复杂性。1、算法分析的计算机模型：1）冯诺依曼计算机：串行执行的计算机。2）均匀存储：假设存储量是够的。3）基本运算的时间为整数。2、两个重要的量：1）问题的规模n。2）频率的计数f(n)。3、求时间复杂度：1）冒泡排序：24/24计算机算法设计与分析BubblesortA(1->n)

5、doi->1tondoj->i+1tonifA[j]n);计算过程：f(n)=nC1+n(n+1)C2/2+nC3f(n)=n(C1+C2/2+C3)+n2C2/2对以上公式进行简化，表示如下：f(n)=n2C4+nC5（其中C4=C1+C2/2+C3，C5=C2/2）进行分析后可知，运算的上界为：g(n)=O(n2)当n>=n0时，若n足够大，f(n)<=Cn2。2）汉诺塔：hanoi(intn,charleft,charmi

6、ddle,charright){if(n==1)printf(left->right)else{hanoi(n-1,left,right,middle)print(left->right)hanoi(n-1,middle,left,right)}}设时间为f(n),规模为n:f(n)=2f(n-1)+C1=2(f(n-2)+C1)+C1=……=C12n所以g(n)=O(2n)。1、根据算法的时间界g(n)对算法进行分类：两类：1）多项式时间复杂度算法P（理论可行实际也可行）：O(c)

7、n3)2）指数时间复杂度算法NP（理论可行实际不可行，需要限制规模或用近似解）：O(2n)NP方法：智能算法(GA)、随机过程。24/24计算机算法设计与分析第一章分治法算法设计的三个基础技术：1.由难到易的校正技术例，泰勒公式：求2的值，每次取两项，经过多次泰勒公式展开可以得到方程中无线趋近合理的解。2.由粗到细的松弛技术例，割圆术求圆的面积，超松弛迭代：3.由大到小的分治技术（加权的方法）一、一般方法procedureDAN(p,q)globalifSmall(p,q)thenreturnG(p,q)els

8、em<-DIVIDE(p,q)return(Combine(DAN(p,m),DAN(m+1,q)))endifendDAN设算法规模为n=q-p+1