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

算法课程总结指导教师 所在院（系） 班 级 学生姓名 学 号 1、 算法概述1.什么是算法？算法是解一确定类问题的任意一种特殊的方法。在计算机科学中，算法是使用计算机解一类问题的精确、有效方法的代名词。算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。2. 算法的五个重要特性：确定性、能行性、输入、输出、有穷性/有限性。1）确定性：算法每种运算必须有确切定义，不能有二义性。 2）能行性：算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间内完成。 3）输入：每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合定义域4）输出：一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量。5）有穷性/有限性：一个算法总是在执行了有穷步的运算之后终止。3.计算过程：只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。 4.准确理解算法和计算过程的区别：不能终止的计算过程：操作系统；算法是“可以终止的计算过程”；算法的时效性：只能把在相当有穷步内终止的算法投入到计算机上运行。5.算法的语言主要有：自然语言，流程图，盒图，PAD图，伪代码，计算机程序设计语言。6.算法分类：1)多项式时间算法：可用多项式（函数）对其计算时间限界的算法。常见的多项式限界函数有：(1) (logn) (n) (nlogn) (n2) (n3)2）指数时间算法：计算时间用指数函数限界的算法。常见的指数时间限界函数：(2n) (n！) =0，接着二分即可5)树的分治一般用来解决树上的路径或统计类问题，每次只考虑跟树根有关的信息，然后递归分治处理树的分治通常有基于点或基于边的分治，基于点的难合，基于边的复杂度太高，这里只介绍基于点的分治步骤：处理跟当前树根有关的信息，重新计算子树大小，在子树中选择重心为根，递归到相应子树处理。因为每次选了重心，所以递归总共logn层，每层O(n)的复杂度，总复杂度就是O(nlogn)6)二分搜索直接搜的复杂度是指数级的的话，一般是40左右的数据量，hash一半，搜一半，搜后面的时候利用之前的hash信息合并出原问题的解。而直接搜的复杂度达到阶乘级的话n一般就不超过20了，做法一般差不多经典例题：POI02szy，NOI2001方程的解数。3.搜索作为信息学竞赛中的所谓“万能算法”，搜索可以说是计算机学科所具有的最大特点了，自然地，搜索算法的应用自然也是非常之广泛，除了专门的搜索题，搜索一般可以用来部分预处理，打表找规律，当然还有骗分。搜索的一般步骤：确定状态选择搜索方式（dfs、bfs）确定产生式规则开始搜索。搜索的常见优化方式：1)改变状态表示这个需要根据题目而定，确定一个漂亮的状态表示，可能就有希望转向记忆化了，即使不行，搞出一个漂亮的状态表示是解决一道麻烦题的最重要的一步，再者，调试起来也会容易许多。2）优化搜索顺序这个优化在多数搜索中能起到摧枯拉朽的提速效果，通常我们选择枝叶较少的儿子先扩展，例如大名鼎鼎的dancing Links，除了利用双向十字链表去除冗余状态，每次选择可扩展数最少的儿子扩展同样给它的神速创造了条件。3）可行性剪枝以及最优性剪枝这是非常常用的剪枝思路之一，因题目而异，在迭代加深搜索中尤为重要一般思路：考虑每次解最多变优多少，从当前的层数来看还有多少改进空间，如果已经不可能成为解或更新答案则可以剪枝了A*及IDA*算法：本质就是给搜索加上一个满足相容性的估价函数，然后用估价函数剪枝，理论上很牛B，实际上不常用，因为考场上很难想出满足那么多条件的估价函数，但记得一些常见模型的估价函数还是有价值的。例如15数码的估价函数就可以选择除了0之外每个元素到自己该到的位置的曼哈顿距离之和，因为每次最多使一个数距离减少1，所以这个估价函数是相容的，再例如求k短路的A*算法就是用个堆维护 min f(s) + g(s) 估价函数就是从汇点反搜的“反向最短路”的长度。四、总结在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。作为IT行业学生，学习算法无疑会增强自己的竞争力，修炼自己的“内功”。经过这门课的学习，我深刻的领悟到数学是一切算法分析与设计的基础。这门课的很多时间多花在了数学公式定理的引入和证明上。虽然很枯燥，但是有必不可少。我们可以清晰的看到好多算法思路是从这些公式定理中得出来的，尤其是算法性能的分析更是与数学息息相关。其中有几个定理令我印象深刻。主定理本门课中它主要应用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一个大问题分解为a个子问题，其中子问题的规模为b。而f(n)可看作这些子问题的组合时的消耗。这些可以利用主定理的相关结论进行分析处理。当f(n)量级高于时，我们可以设法降低子问题组合时的消耗来提高性能。反之我们可以降低的消耗，即可以扩大问题的规模或者减小子问题的个数。因此主定理可以帮助我们清晰的分析出算法的性能以及如何进行有效的改进。随机算法中的许多定理的运用在这门课中，我学到了以前从未遇见过的随机算法，它给予我很大的启示。随机算法不随机，它可通过多次的尝试来降低它的错误率以至于可以忽略不计。这些都不是空穴来风，它是建立在严格的定理的证明上。如素数判定定理是个很明显的例子。它运用了包括费马小定理在内的各