算法设计与分析 赵端阳

“算法设计与分析”是一门理论性与实践性结合很强的课程。在信息技术高速发展的今天，计算机技术已经应用到了很多科学领域。从理论上来说，算法研究已经被公认是计算机科学的基石。David Harel在其《算法学： 计算精髓》一书中写道： “算法不仅是计算机科学的一个分支，它更是计算机科学的核心。可以毫不夸张地说，它和绝大多数的科学、商业和技术都是相关的。”
在ACM国际大学生程序设计竞赛中，在线裁判系统是开展竞赛的核心，它是一个在线的程序与算法设计的练习和竞赛平台。系统可以提供大量的关于程序和算法设计的题目供学生练习或竞赛，学生可以使用自己熟悉的语言提交相关题目的程序代码，如果系统编译提交代码没有错误，则生成可执行文件。利用系统的测试用例来测试，如果输出结果正确，则返回程序消耗的内存空间和时间。对于竞赛题目，系统可以从程序正确性、运行总时间、消耗内存空间、返回结果等方面来考查学生提交的代码。系统可以实现在规定的时间段举行竞赛的功能，根据学生解题数目和时间进行排名，也可以批量导出学生代码，进行分析。
基于程序设计竞赛的教学模式的优势如下： 
(1) 提供一个开放的、自主学习的实验环境。在线评测系统通过网络使用，学生可以随时随地提交程序代码； 在丰富的算法设计题库中寻找适合自己的题目，训练程序设计能力。
(2) 有效地训练学生程序设计能力，培养创新型IT人才。本课程的学习难点在于如何将常见的算法策略应用到实际的应用环境中。通过在线评测系统的实践训练，让学生熟练掌握常见的算法设计策略，训练学生的创新思维，加深学生对各种算法设计策略的认识，理解算法的意义及精髓，达到学以致用的目的。
(3) 形成了良好的学习氛围，加强了学生之间的交流。使用在线评测系统进行课程考核并举办程序与算法设计竞赛，以团队方式参与，可以形成良好的校园竞争和交流的学习氛围； 学生有了在课余时间自主进行本学科知识钻研的机会和环境； 也让学生体验团队协作的重要性，为软件项目团队化的合作要求做好准备。
“算法设计与分析”是面向设计的核心课程，主要通过介绍常见的算法设计策略及复杂度分析方法，培养学生分析问题和解决问题的能力，为开发高效的软件系统及相关领域的研究工作奠定坚实的基础。该课程理论与实践并重，内容具有综合性、广泛性和系统性，是一门集应用性、创造性及实践性为一体的综合性极强的课程。
目前，该课程的教学方法还是以传统的讲解为主，通常只是将经典算法在已有的数学模型和数据结构上解释给学生； 在实践环节只是盲目地验证算法，而对该算法的运行效率、测试数据规模以及实际的应用场景则很少考虑。学生的学习主要以理解和记忆的继承式学习为主，虽然记住了大量的算法理论，但没有“理解”和“消化”，不能灵活运用算法； 在实践环节学生代码抄袭严重，很难达到训练的效果。在这种教学模式下，学生缺乏问题抽象能力，在遇到实际问题时无从下手，思维创新能力和实践能力难以得到有效的提高，很难培养出高水平的程序员。
本书利用程序设计竞赛模式和在线评测系统的特点，结合课程特点和实际教学，弥补课程教学中存在的不足，以此探讨“算法设计与分析”课程的教学改革，培养高水平的编程人才。
本书共分为11章。
第1章，算法概述。主要是算法的基本概念、算法的复杂度、大学生程序设计竞赛概述和程序设计在线测试题库的基本情况。
第2章，数据结构和标准模板库。主要介绍栈(Stack)、向量(Vector)、映射(Map)、列表(List)、集合(Set)、队列(Queue)和优先队列(Priority Queue)以及典型例题。
第3章，递归与分治策略。主要介绍递归算法和分治策略以及典型例题。
第4章，动态规划。主要介绍动态规划算法的基本要素以及典型例题。
第5章，贪心算法。主要介绍贪心算法的理论基础以及典型例题。
第6章，回溯算法。主要介绍回溯算法的理论基础以及典型例题。
第7章，分支限界算法。主要介绍分支限界算法的基本理论以及典型例题。
第8章，图的搜索算法。主要介绍图的深度和广度优先搜索遍历算法以及典型例题。
第9章，图论。主要介绍网络流问题和二分图匹配问题，分析剩余网络的增广路径、FordFulkerson算法和EdmondsKarp算法，二分图匹配的匈牙利算法、HopcroftKarp算法和Kuhn Munkres算法以及典型例题。
第10章，数论。主要介绍扩展欧几里得算法、欧拉函数、中国剩余定理和一元线性同余方程组以及典型例题。
第11章，组合数学。主要介绍母函数、Stirling数、Catalan数、容斥原理与鸽巢原理以及典型例题。
本书配备有电子教案和源代码，请到清华大学出版社网站www．tup．tsinghua．edu．cn下载。
本书获得浙江省高等教育课堂教学改革、浙江工业大学精品课程、浙江工业大学重点教材建设和绍兴市精品课程建设等多个项目资助，并被评为浙江省普通高校“十二五”优秀教材和浙江省普通高校“十三五”新形态教材。
由于编者水平所限，书中难免有不足之处，恳请广大读者批评指正。
编者
于2021年2月

本书内容包括经典的算法设计技术，主要介绍数据结构和标准模板库、递归与分治策略、动态规划、贪心算法、回溯算法、分支限界算法、图的搜索算法、图论、数论和组合数学问题。本书包括大量的问题实例，并在北京大学、浙江大学和杭州电子科技大学在线题库中精选原题，详细地分析解题的方法，深入浅出地讲解用到的算法，章后的上机练习题也选自在线题库中的典型题目，供读者练习，以巩固所学算法。本书内容基本上涵盖了目前大学生程序设计竞赛所要掌握的算法。 本书结构清晰、内容丰富，适合作为计算机科学与技术、软件工程以及相关学科算法课程的教材或参考书，特别适合有志于参加信息学竞赛和ACM大学生程序设计竞赛的读者学习和训练。