算法设计与实现个人课程总结.doc

算法课程总结 指导教师 所在院（系） 班 级 学生姓名 学 号 算法概述 1.什么是算法？ 算法是解一确定类问题的任意一种特殊的方法。在计算机科学中，算法是使用计算机解一类问题的精确、有效方法的代名词。算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。 算法的五个重要特性：确定性、能行性、输入、输出、有穷性/有限性。 1）确定性：算法每种运算必须有确切定义，不能有二义性。 2）能行性：算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间内完成。 3）输入：每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合——定义域 4）输出：一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量。 5）有穷性/有限性：一个算法总是在执行了有穷步的运算之后终止。 3.计算过程：只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。 4.准确理解算法和计算过程的区别：不能终止的计算过程：操作系统；算法是“可以终止的计算过程”；算法的时效性：只能把在相当有穷步内终止的算法投入到计算机上运行。 5.算法的语言主要有：自然语言，流程图，盒图，PAD图，伪代码，计算机程序设计语言。 6.算法分类： 1)多项式时间算法：可用多项式（函数）对其计算时间限界的算法。常见的多项式限界函数有：Ο(1) Ο(logn) Ο(n) Ο(nlogn) Ο(n2) Ο(n3) 2）指数时间算法：计算时间用指数函数限界的算法。常见的指数时间限界函数：Ο(2n) Ο(n！) Ο(nn) 7.算法基本工具：循环与递归， 算法与数据结构，优化算法的数学模型。 8.主要算法：迭代算法，蛮力法，分治法，动态规划法，贪婪算法，图有哪些信誉好的足球投注网站基础。 算法的核心是思想 我们学习这门课不是仅仅掌握那几个经典算法例子，更重要的是为了学习蕴含在其中的思想方法。为什么呢？举个例子。有同学曾问我这样一个问题：1000只瓶子装满水，但有一瓶有毒，且毒发期为1个星期。现在用10只老鼠在一个星期内判断那只瓶子有毒，每只老鼠可以喝多个瓶子的水，每个瓶子可以只喝一点。问如何解决？其实一开始我也一头雾水，但是他提醒我跟计算机领域相关，我就立马有了思路，运用二进制。因为计算机的最基本思想就是二进制。所以说，我们不仅要学习算法，更得学习思想方法。 ①算法最基本的设计方法包括分治法，动态规划法，贪婪算法，周游法，回溯法，分支定界法。我们可利用分治法做快速排序，降低找n个元素中最大元和最小元的量级，降低n位二进制x和y相乘的量级，做Strassen矩阵乘法等等。它的思想就是规模很大的问题分解为规模较小的独立的子问题，关键是子问题要与原问题同类，可以采取平衡法来提高性能。 动态规划法是把大问题分解为子问题，但是子问题是重复的，后面的问题可以利用前面解决过的问题的结果。如构造最优二叉查找树，解决矩阵连乘时最小计算次数问题，寻找最长公共子序列等等。 贪婪算法就是局部最优法，先使局部最优，再依次构造出更大的局部直至整体。如Kruscal最小生成树算法，求哈夫曼编码问题。 周游法就是简单理解就是采取一定的策略遍历图中所有的点，典型的应用就是图中的深度优先有哪些信誉好的足球投注网站(DFS)和广度优先有哪些信誉好的足球投注网站(BFS)。 回溯法就是就是在满足一定的条件后就往前走，当走到某步时，发现不满足条件就退回一步重新选择新的路线。典型的应用就是8皇后问题，平面点集的凸包问题和0-1背包问题。 分支定界法：它是解决整数规划问题一种最常用的方法。典型应用就是解决整数规划问题。 ②评价算法性能的方法如平摊分析中的聚集法，会计法和势能法。聚集法就是把指令分为几类，计算每一类的消耗，再全部叠加起来。会计法就是计算某个指令时提前将另一个指令的消耗也算进去，以后计算另一个指令时就不必再算了。势能法计算每一步的势的变化以及执行这步指令的消耗，再将每一步消耗全部累计。 这几种方法都是平摊分析法，平摊分析的实质就是总体考虑指令的消耗时间，尽管某些指令的消耗时间很大也可以忽略不计。上述三种方法难易程度差不多，每种方法都有属于它的难点。如聚集法中如何将指令有效分类，会计法中用什么指令提前计算什么指令的消耗，势能法中如何选取势能。因此掌握这些方法原理还不够，还要学会去应用，在具体的问题中去判断分析。 三、重点学习 1.贪婪算法 贪婪+其他算法：由于贪婪往往能大幅化简状态，利用问题的某些“单调性”，加上贪婪的思想，往往能是问题大幅简化，从而结合其他算法解决问题经典例题：田忌赛马，利用贪婪来确定状态。 2.分治法 分而治之的思想在信息学竞赛中是非常重要的，下面主