[算法学习报告.docVIP

算法设计与分析 学习报告 姓 名： 学 号： 院 系： 日 期：2014.01.14 总结归纳学习内容 1.1 综述 算法在CS中占有重要的地位，在之前的学习中只是了解和运用部分算法来解决实际问题，并没有对算法内容进行系统的学习与总结。算法的分析与设计这门课的目的就在于使我们非数值计算方法的层面上具备抽象描述、解决实际问题的能力，学会运用算法设计与分析的典型方法进行算法的设计，具备分析算法效率的能力。 本学期的算法课程主要讲了三个方面的内容：第一，在计算机应用中经常遇到的问题和求解的算法；第二，设计算法的基本原理、技巧以及算法复杂性的分析（包括分治法、动态规划法、集合上的算法、随机算法等）；第三，计算理论简介（Turing机、递归函数、NP-完全性等）。 1.2 算法相关基本概念及数学知识 这一单元主要先学习计算机算法的一些基本常识和发展历史，对其发展有个整体的把握，了解算法在CS中的重要性。 其次，学习算法的一些基本概念，包括算法的概念、算法研究步骤、算法的评价、算法的时间复杂性分析研究等。 最后，学习算法分析的数学基础，包括母函数、普通与指数生成函数、普通生成函数的应用（排列组合问题和递归方程）和主定理。其中，主定理对于算法的研究和设计具有重要的意义。 1.3 分治法 分治法，是算法常用技术之首。总的来讲，分治法是分为将原问题分解为子问题（Divide）、求解子问题（Conquer）、组合子问题的解得到原问题的解（Combine）三个步骤来进行。 首先是学习分治法的要领和主要步骤、分治法求最大最小元问算法、strassen矩阵相乘算法的思路和意义。其次是对平衡概念的理解以及分治法与平衡的密切关系。最后分别学习求第K小元算法、寻找最近点对算法以及离散傅立叶变换（DFT）、快速傅立叶变换（FFT）（利用FFT计算多项式乘积），通过对这些利用分治法思想的算法的理解和学习来把握分治法的要领和精髓。 1.4 动态规划 动态规划法，是跟分治法类似的方法，它们都是把大规模的问题分解为小规模的问题来解决问题。但是，动态规划法分解后的子问题是重复的。一个问题具备两个条件：1）可分解为若干高度重复的子问题。2）问题具有最优子结构性质，那么这个问题就可以用动态规划法来求解。 了解动态规划法的基础上分别讨论学习了矩阵连乘问题、最长公共子序列问题、最优二分有哪些信誉好的足球投注网站树问题，这些问题都利用动态规划法可以得到良好的解决方法，提高算法的效率。此外，了解了备忘录方法（它是动态规划的变形应用）。最后，学习了一个不能直接使用动态规划的例子（需要改进才能得到更好的效率）-流水作业问题。 1.5 集合算法 首先学习了平摊分析的算法分析方法以及平摊分析常用的三种方法（聚集方法、会计方法、势能方法），总体来讲平摊分析是对若干指令整体进行考虑时间复杂度而不是逐一考虑执行每条指令所需时间再累加。 其次是简单不相交集的合并算法的学习、Union-Find的树结构，主要是union和find指令的应用和改进，通过对link指令和find指令的修改实现路径压缩功能和两个森林的合并，还有union-find算法的应用及推广。 此外，学习了什么是2-3树以及2-3树节点的的插入和删除以及应用，学习了能够实现不同的指令的一些数据结构，包括字典（实现MEMBER、INSERT、DELETE）、优先队列、可堆并（实现INSERT、DELETE、UNION、MIN）、可连接队列（实现INSERT、DELETE、FIND、CONCATENATE），以及在这些数据结构上各种操作的实现。 1.6 随机算法 随机算法，可以用于解决一些利用确定性算法常规时间内得不到所需结果的问题，而且随着问题规模的扩大，随机算法的结果也是相当可信的。主要学习了两种随机算法：Las Vegas算法和Monte Carlo算法。 基于随机算法的思想先后学习了Random Sampling（随机取数）问题、找第K小元素的随机算法、Sherwood随机化方法、Testing String Equality算法以及误判率的分析。 重点实现了KMP、Monte Carlo、Las Vegas三种模式匹配算法以及根据运行结果对三种算法进行全面的性能分析。 最后是素数测试问题，学习了在Fermat小定理和其推论的基础上建立起来的Miller-Rabin素数判定算法。 1.7 计算模型 计算模型的提出对现代计算机的问世有着重要的影响，有重要的意义。 这里学习了几种计算模型以及相互之间的关系等，主要包括随机存取机（RAM）和RAM程序的时间复杂度分析、存储程序模型RASP以及RAM和RASP之间的关系（分别从均匀耗资和对数耗资标准下比较）。 其次学习了另外一个计算模型-Turing Machine的概念、特点、分