算法导论学习报告参考

2020-11-18

算法导论学习报告参考

　　第一部分学习内容归纳

　　“计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，或者说，算法是对计算机上执行的计算过程的具体描述。”（参考文献：百度百科）《算法设计与分析》是一门面向设计，在计算机科学中处于核心地位的课程。这门课程主要讲授了在计算机应用中经常遇到的问题和求解的方法，分治法、动态规划法、随机算法等设计算法的基本原理、技巧和算法复杂性的分析，以及计算理论简介。

　　第一部分“概论和数学准备”在简单了解了算法的基本概念和复杂性、研究步骤等几个重要知识点后，着重学习了算法的数学基础，包括生成函数、差方方程的求解等，主要适用于求解算法的时间复杂性。

　　“任何可以用计算机求解的问题所需要的计算时间都与其规模有关：问题的规模越小，解题所需的计算时间往往也越短，从而也就比较容易处理。”（参考文献：《计算机算法设计与分析（第3版）》）而第二部分介绍的算法常用技术之首——分治法就运用了这样的思想。分治法的要领在于Divide（子问题的划分）-Conquer（子问题的求解）-Combine（子问题解的组合）。由于子问题和原问题是同类的，递归的思想在分治法中显得尤其重要，它们经常同时运用在算法设计中。这部分内容从Select（求第k小元）算法，寻找最近点对算法和快速傅立叶变换FFT等实际应用中深化对分治法思想的理解，同时也强调了平衡思想的重要性。

　　第三部分“动态规划”与分治法类似，同样是把问题层层分解成规模越来越小的同类型的子问题。但与分治法不同的是，分治法中的子问题通常是相互独立的，而动态规划法中的子问题很多都是重复的，因此通常采用递推的方法以避免重复计算。然而，也不是所有的情况下都采用递推法，当有大量的子问题无需求解时，更好的方式是采用动态规划法的变形——备忘录方法。通常需要用到动态规划法求解的问题都具有子问题的高度重复性和最优子结构性质两大特征，这也是我们分析问题和设计算法时的关键点。最长公共子序列LCS问题和最优二分搜索树就是从动态规划法的两个主要特征角度分析问题，进而设计出相应的解决算法的。而这部分内容中的另一个问题——流水作业调度，则告诉我们采用动态规划时偶尔也得不到高效的算法，我们要学会将已有的知识灵活运用，适当加工。

　　第四部分“集合算法”中首先介绍了一种分析算法复杂度的手法——平摊分析（Amortized Analysis）。与之前我们所接触的算法分析方法即逐一考虑执行每条指令所需的时间复杂度再进行累加的`方法不同，平摊分析是对若干条指令从整体角度考虑其时间复杂度，通过这样的方法获得的时间复杂度更加贴近实际的情况。平摊分析的主要方法有聚集方法，会计方法和势能方法。聚集方法将指令的时间复杂度分类计算再相加；会计方法采用了耗费提前计算的思想；势能方法引入了势函数的概念，从每步操作的数据结构状态和势函数的关系角度分析得出操作的平摊代价。“集合算法”这一部分主要分析了Union（合并集合）和Find（给出元素所在集合名）这两种运算。从上学期的《数据结构》课程的学习中，我们就已经发现集合和树之间的关系是密不可分的，我们经常用树结构来表示集合。而2-3树是一种特殊的每个内结点都只有2个或3个儿子的树，广泛的应用于可实现Member（查找）、Insert（插入）、Delete（删除）操作的数据结构——字典，可实现Insert、Delete、Union和Min（查找最小叶结点）的数据结构——可并堆，可实现Insert、Delete、Find、Concatenate（保序合并）和Split（分裂）的数据结构——可连接队列等。

　　之前讨论的算法中每一步计算步骤都是确定的，然而第五部分“随机算法”中所讨论的随机化算法允许算法在执行的过程中随机的选择下一个执行步骤。“在许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时。因此随机化算法可在很大程度上降低算法的复杂度。”（参考文献：《计算机算法设计与分析（第3版）》）随机化算法对问题用同一输入算法求解时可能会得到完全不同的效果，这是它的基本特征——算法在执行时产生真正随机的结果。一般情况下，随即算法分为两大类——Las Vegas算法和Monte Carlo算法。Las Vegas算法不会得到不准确的结果，但有时却会找不到解，这时就需要重复调用算法进行计算。而Monte Carlo算法用来求取问题的准确解。它能保证求得一个截但无法保证其正确性，这是Monte Carlo算法的主要缺点。不过由于每次执行的算法都是独立的，通过反复执行算法可以有效的将发生错误的概率大大降低。另外，对于一个已经有了平均性质较好的确定性算法的问题，通过Sherwood随机化方法可将确定性算法改成随机算法，以解决其在最坏情况下效率不高的问题，提高了算法的性能。随机化算法为很多用确定性算法难以很好的解决的难解问题提供了高效的解决途径，具有很高的实用价值。

　　第六部分“NP完全性理论与近似算法”首先介绍了计算模型、确定性和非确定性图灵（Turing）机。“在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型，包括定义该计算模型中所用的基本运算，其目的是使问题的计算复杂性分析有一个共同的客观尺度。”（参考文献：《计算机算法设计与分析（第3版）》）随机存取机RAM（Random Access Machine）、随机存取存储程序机RASP（Random Access Stored Program Machine）和图灵机（Turing Machine）是三种基本的计算模型。RAM和RASP的相同处在于都有各种寻址指令且时间复杂性数量级相同，不同处在于RAM程序的不允许修改和RASP程序的可修改性。RAM程序和RASP程序之间可以相互模拟。图灵机可以计算函数部分的递归函数，涉及到递归可枚举集、递归集、原始递归集、部分递归函数、完全递归函数和原始递归函数。确定性图灵机DTM和非确定性图灵机NDTM的差别在于，NDTM的每一步动作允许有若干个选择，且它的ID序列通常是由树描述的，而DTM的ID序列是线性的。这部分接着又进一步深入介绍NP完全性理论和解NP难问题的近似算法。NP是能在多项式时间内被一台NDTM所接受的语言。NP完全问题是当前计算机算法领域的热点研究课题。

　　第二部分学习心得

　　学习之初刚开始看到那些函数以及一大堆数学公式的时候都觉得头大，一时都摸不清这些复杂的式子是用来干什么的，甚至都以为学的不是算法而是高数了。后来在接触到分治法等算法思想后，在老师讲解的例子中学会了对那些式子的应用。课后也在实际的应用中真正掌握了第一部分所讲的数学知识，懂得了那些数学基础对算法研究的重要性。所以说，只有当自己学会在问题中运用了，才算是真正学会了那些知识。

　　算法的思想看着都似乎简单易懂，就算思路复杂的只要认真研究也比较容易理解，但要真正的在实验中、在实际问题的解决过程中运用出来就不是那么容易的一件事了。对于同一个问题，往往都有好几种不同的算法，就像要求分别运用。

【算法导论学习报告参考】相关文章：