《计算机算法设计与分析》由会员分享，可在线阅读，更多相关《计算机算法设计与分析（24页珍藏版）》请在金锄头文库上搜索。
1、中 国 地 质 大 学研 究 生 课 程 论 文课 程 名 称 : 算法设计与分析 教 师 姓 名: 戴光明 研究生姓名: 研究生学号: 120161* 研究生专业: * 所 在 院 系: 计算机学院 类别: A.博士 B.硕士 C.进修生 日期: 2017.01.13 计算机算法设计与分析2 / 25评 语对课程论文的评语：平时成绩： 课程论文成绩：总 成 绩： 评阅人签名：注：1、无评阅人签名成绩无效；2、必须用钢笔或圆珠笔批阅，用铅笔阅卷无效；3、 如有平时成绩，必须在上面评分表中标出，并计算入总成绩。计算机算法设计与分析3 / 25目录第一章 算法导引 .4一、 算法及其特性 .4二、
2、 算法分析 .4第二章 分治法 .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三、 决策树（博弈树）
3、.21第六章 回溯法 .22第七章 分支限界法 .22一、 一般方法 .22二、 回溯法解 0-1 背包问题 .22三、 分支限界法解 0-1 背包问题 .23第八章 总结 .24计算机算法设计与分析4 / 25第一章 算法导引课前题目：编写程序：1、 编写两个矩阵相乘的程序；2、 如图，菱形 ABCD 中，E 是 AD 的中点，EF 垂直于 AC 交 CB 的延长线于 F，求证四边形AFBE 是平行四边形。A E DF BNMC图 1-1 平行四边形一、 算法及其特性1、算法是什么？ 算法是计算的方法。2、什么是计算？1) 计算是基于规则的符号串的变换；2) 计算是基于规则的物理信息的变换；
4、3) 计算是基于规则的信息的变换。为了使计算机械化，图灵提出了图灵模型，在此基础上将理论进行技术实现，1946 年诞生了第一台计算机（读写头、纸带、四元组） ，在内存条上进行输入输出。3、 算法的特性？4) 无二义性：由于算法是由机器执行的，所以算法的每一步都必须是确定的。5) 能行性（可计算性与不可计算性）：算法的每一步机器都能够执行（计算机能够解决的问题是有限的） 。6) 有限性（可计算性与计算复杂性） 。二、 算法分析算法分析就是分析算法的复杂性。1、 算法分析的计算机模型：1） 冯诺依曼计算机：串行执行的计算机。2） 均匀存储：假设存储量是够的。3） 基本运算的时间为整数。2、 两个重
5、要的量：1） 问题的规模 n。2） 频率的计数 f(n)。3、求时间复杂度：1） 冒泡排序：计算机算法设计与分析5 / 25Bubblesort A(1-n)do i-1 to ndo j-i+1 to nif Aj 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，C 5 = C2/2）进行分析后可知，运算的上界为：g(n)= O(n2)当 n = n0 时，若 n 足够大，f(n) right)else hanoi (n-1, left, right, middle)print( left-
