算法分析与设计

出版时间：2012-2  出版社：清华大学出版社  作者：赵端阳,左伍衡  
Tag标签：无  

前言

　　“算法分析与设计”是一门理论性与实践性结合很强的课程。在信息技术高速发展的今天，计算机技术已经应用到了很多科学领域。从理论上来说，算法研究已经被公认为是计算机科学的基石。David Harel在他的《算法学： 计算精髓》一书中说道： “算法不仅是计算机科学的一个分支，它更是计算机科学的核心。可以毫不夸张地说，它和绝大多数的科学、商业和技术都是相关的。”　　近年来，针对大学生的各种类型的程序设计竞赛开展得越来越多，比较常见的有ACM?ICPC、TopCoder、百度之星、Google挑战赛、有道难题等。其中ACM国际大学生程序设计竞赛（ACM International Collegiate Programming Contest，ACM?ICPC），是历史最悠久、规模最大的竞赛。竞赛题目涉及的知识面广，难度大； 主要强调算法的高效性，不仅要解决一个指定的命题，而且必须要以最佳的方式解决指定的命题； 涉及知识与大学计算机专业本科以及研究生如程序设计、离散数学、数据结构、人工智能、算法分析与设计等相关课程直接关联，对数学要求很高。　　在ACM国际大学生程序设计竞赛中，在线裁判系统是开展竞赛的核心，它是一个在线的程序与算法设计的练习和竞赛平台。系统可以提供大量的关于程序和算法设计的题目供学生练习或竞赛，学生可以使用自己熟悉的语言提交相关题目的程序代码，系统编译提交代码，如果没有错误，则生成可执行文件。利用系统的测试用例来测试，如果输出结果正确，则返回程序消耗的内存空间和时间。对于竞赛题目，系统可以从程序正确性、运行总时间、消耗内存空间、返回结果等方面来考查学生提交的代码。系统可以实现在指定的时间段举行竞赛的功能，根据学生解题数目和时间进行排名，也可以批量导出学生代码进行分析。　　基于程序设计竞赛的教学模式的优势： 　　（1） 提供了一个开放的、自主学习的实验环境，在线评测系统通过网络使用，学生可以随时随地地提交程序代码，并可在丰富的程序与算法设计题库中寻找适合自己的题目，训练程序设计能力。　　（2） 有效地训练了学生程序设计能力，培养创新型IT人才。本课程的学习难点在于如何将常见的算法策略应用到实际的应用环境中。通过在线评测系统的实践训练，让学生熟练掌握常见的算法设计策略，训练学生的创新思维，加深学生对各种算法设计策略的认识，使学生理解算法的意义及精髓，达到学以致用。　　（3） 形成了良好的学习氛围，加强了学生之间的交流。使用在线评测系统进行课程考核并举办程序与算法设计竞赛，学生以团队方式参与，可以形成良好的校园竞争和交流的学习氛围； 使学生有了在课余时间自主进行本学科知识钻研的机会和环境； 也让学生体验团队协作的重要性，为软件项目团队化的合作要求做好准备。　　算法分析与设计是面向设计的核心课程，主要通过介绍常见的算法设计策略及复杂性分析方法，培养学生分析问题和解决问题的能力，为开发高效的软件系统及参加相关领域的研究工作奠定坚实的基础。该课程理论与实践并重，内容具有综合性、广泛性和系统性，是一门集应用性、创造性及实践性为一体的综合性极强的课程。　　目前，该课程的教学方法还是以传统的讲解为主，通常只是将经典算法在已有的数学模型和数据结构上解释给学生； 在实践环节只是盲目地验证算法，而对该算法的运行效率、测试数据规模以及实际的应用场景则很少考虑。学生的学习则主要以理解和记忆的继承式学习为主，虽然记住了大量的算法理论，但没有“理解”和“消化”，不能灵活运用算法； 在实践环节学生代码抄袭严重，很难达到训练的效果。在这种教学模式下，学生缺乏问题抽象能力，在遇到实际问题时无从下手，思维创新能力和实践能力难以得到有效的提高，很难培养出高水平的程序员。　　本书利用程序设计竞赛模式和在线评测系统的特点，结合课程特点和实际教学，弥补课程教学中存在的不足，以此探讨算法分析与设计的课程教学改革，培养高水平的编程人才。　　本书共分为8章。　　第1章算法概述： 主要是算法的基本概念、算法的复杂性、大学生程序设计竞赛概述和程序设计在线题库的基本情况。　　第2章数据结构和标准模板库STL： 主要介绍栈（Stack）、向量（Vector）、映射（Map）、列表（List）、集合（Set）、队列（Queue）和优先队列（Priority Queue），并应用这些STL解题： ZOJ1004?Anagrams by Stack，ZOJ1094?Matrix Chain Multiplication，ZOJ1062?Trees Made to Order和ZOJ1944?Tree Recovery等。　　第3章递归与分治策略： 主要介绍递归算法和分治策略。典型例题有循环赛日程表、棋盘覆盖问题、选择问题和整数因子分解等。　　第4章动态规划： 主要介绍动态规划算法的基本要素。典型例题有矩阵连乘积、最长公共子序列、最大子段和、0?1背包问题和最长单调递增子序列等，并求解ZOJ1013?Great Equipment、Human Gene Functions、To the Max、FatMouse and Cheese和Railroad等问题。　　第5章贪心算法： 主要介绍贪心算法的理论基础。典型例题有活动安排问题、背包问题、最优装载问题、单源最短路径和最小生成树等，并求解ZOJ1012?Mainframe、ZOJ1025?Wooden Sticks、ZOJ1076?Gene Assembly和ZOJ2109?FatMouse? Trade等问题。　　第6章回溯算法： 主要介绍回溯算法的理论基础。典型例题有装载问题、0?1背包问题、图的m着色问题、n皇后问题、旅行商问题和流水作业调度问题等，并求解ZOJ1145?Dreisam Equations、ZOJ1157?A Plug for UNIX和ZOJ1166?Anagram Checker等问题。　　第7章分支限界算法： 主要介绍分支限界算法的基本理论，并对回溯算法与分支限界算法进行比较。典型例题有单源最短路径问题、装载问题、0?1背包问题和旅行商问题，并求解ZOJ1136?Multiple。　　第8章图的搜索算法： 主要介绍图的深度和广度优先搜索遍历算法。求解ZOJ1002?Fire Net、ZOJ1142?Maze、ZOJ1245?Triangles、ZOJ1079? Robotic Jigsaw、ZOJ1217?Eight和ZOJ1091?Knight Moves等问题。　　袁鹤、冯志林、吴艳、金献珍、金海溶和曹平老师参加了本书的编写工作。

内容概要

　　《21世纪高等学校规划教材·计算机科学与技术·算法分析与设计：以大学生程序设计竞赛为例》主要介绍经典的算法设计技术，内容包括数据结构和标准模板库STL、递归与分治策略、动态规划、贪心算法、回溯算法、分支限界算法和图的搜索算法。《21世纪高等学校规划教材·计算机科学与技术·算法分析与设计：以大学生程序设计竞赛为例》内容基本上涵盖了目前大学生程序设计竞赛所要掌握的算法。《21世纪高等学校规划教材·计算机科学与技术·算法分析与设计：以大学生程序设计竞赛为例》通过大量的问题剖析实例，并在浙江大学在线题库中精选了部分题目，详细地分析解题的方法，深入浅出地讲解所使用的算法。还把在浙江大学在线题库中精选的题目作为每章后面的习题，供读者练习，以巩固所学的算法。　　《21世纪高等学校规划教材·计算机科学与技术·算法分析与设计：以大学生程序设计竞赛为例》可作为计算机科学与技术系、软件学院、数学系等专业本科及研究生课程的教材，特别适合有志于参加大学生程序设计竞赛的学生学习和训练。

书籍目录

第1章 算法概述1.1 引言1.1.1 算法的描述1.1.2 算法的设计1.2 算法的复杂性1.2.1 时间复杂性1.2.2 空间复杂性1.3 大学生程序设计竞赛概述1.4 程序设计在线测试题库第2章 数据结构和标准模板库2.1 栈2.2 向量2.3 映射2.4 列表2.5 集合2.6 队列2.7 优先队列2.8 ZOJ1004-Anagramsby Stack2.9 ZOJ1094-Matrix Chain Multiplication2.10 ZOJ1011-NTA2.11 ZOJ1062-Trees Madeto Order2.12 ZOJ1097-Codethe Tree2.13 ZOJ1156-Unscrambling Images2.14 ZOJ1167-Trees on the Level2.15 ZOJ1016-Parencodings2.16 ZOJ1944-Tree Recovery2.17 ZOJ2104-Letthe Balloon Rise上机练习题第3章 递归与分治策略3.1 递归算法3.1.1 Fibonacci数列3.1.2 集合的全排列问题3.1.3 整数划分问题3.2 分治策略3.2.1 分治法的基本步骤3.2.2 分治法的适用条件3.2.3 二分搜索技术3.2.4 循环赛日程表3.2.5 棋盘覆盖问题3.2.6 选择问题3.2.7 输油管道问题3.2.8 半数集问题3.2.9 整数因子分解3.2.10 取余运算3.3 Big String上机练习题第4章 动态规划4.1 矩阵连乘积问题4.1.1 分析最优解的结构4.1.2 建立递归关系4.1.3 计算最优值4.1.4 构造最优解4.2 动态规划算法的基本要素4.2.1 最优子结构4.2.2 重叠子问题4.2.3 备忘录方法4.3 最长公共子序列4.3.1 最长公共子序列的结构4.3.2 子问题的递归结构4.3.3 计算最优值4.3.4 构造最长公共子序列4.4 最大子段和4.5 01背包问题4.5.1 递归关系分析4.5.2 算法实现4.6 最长单调递增子序列4.7 数字三角形问题4.8 ZOJ1013-Great Equipment4.9 ZOJ1027-Human Gene Functions4.10 ZOJ1074-Tothe Max4.11 ZOJ1093-Monkeyand Banana4.12 ZOJ1100-Mondriaans Dream4.13 ZOJ1102-Phylogenetic Trees Inherited4.14 ZOJ1107-Fat Mouseand Cheese4.15 ZOJ1108-Fat Mouses Speed4.16 ZOJ1132-Railroad4.17 ZOJ1147-Formatting Text4.18 ZOJ1149-Dividing4.19 ZOJ1163-The Staircases4.20 ZOJ1183-Scheduling Lectures4.21 ZOJ1196-Fast Food4.22 ZOJ1206-Winthe Bonus4.23 ZOJ1227-Free Candies4.24 ZOJ1234-Chopsticks上机练习题第5章 贪心算法5.1 活动安排问题5.2 贪心算法的理论基础5.2.1 贪心选择性质5.2.2 最优子结构性质5.2.3 贪心算法的求解过程5.3 背包问题5.4 最优装载问题5.5 单源最短路径5.6 最小生成树5.6.1 最小生成树的性质5.6.2 Prim算法5.6.3 Kruskal算法5.7 删数问题5.7.1 问题的贪心选择性质5.7.2 问题的最优子结构性质5.8 多处最优服务次序问题5.8.1 问题的贪心选择性质5.8.2 问题的最优子结构性质5.9 ZOJ1012 Mainframe5.10 ZOJ1025 Wooden Sticks5.11 ZOJ1029 Moving Tables5.12 ZOJ1076 Gene Assembly5.13 ZOJ1161 Gone Fishing5.14 ZOJ1171 Sortingthe Photos5.15 ZOJ2109 Fat Mouse Trade上机练习题第6章 回溯算法6.1 回溯算法的理论基础6.1.1 问题的解空间6.1.2 回溯法的基本思想6.1.3 子集树与排列树6.2 装载问题6.3 01背包问题6.4 图的m着色问题6.5 n皇后问题6.6 旅行商问题6.7 流水作业调度问题6.8 子集和问题6.9 ZOJ1145-Dreisam Equations6.10 ZOJ1157-A Plug for UNIX6.11 ZOJ1166-Anagram Checker6.12 ZOJ1213-Lumber Cutting上机练习题第7章 分支限界算法7.1 分支限界算法的基本理论7.1.1 分支限界算法策略7.1.2 分支结点的选择7.1.3 提高分支限界算法的效率7.1.4 限界函数7.2 单源最短路径问题7.3 装载问题7.4 01背包问题7.5 旅行商问题7.6 ZOJ1136-Multiple7.7 回溯算法与分支限界算法的比较上机练习题第8章 图的搜索算法8.1 图的深度优先搜索遍历8.2 ZOJ1002 FireNet8.3 ZOJ1008 GnomeTetravex8.4 ZOJ1047 ImagePerimeters8.5 ZOJ1084 ChannelAllocation8.6 ZOJ1142 Maze8.7 ZOJ1190 OptimalPrograms8.8 ZOJ1191 TheDieIsCast8.9 ZOJ1204 AdditiveEquations8.10 ZOJ1245 Triangles8.11 ZOJ2100 Seeding8.12 图的广度优先搜索遍历8.13 ZOJ1055 Oh,ThoseAchinFeet8.14 ZOJ1079 RoboticJigsaw8.15 ZOJ1085 AlienSecurity8.16 ZOJ1103 HikeonaGraph8.17 ZOJ1148 TheGame8.18 ZOJ1217 Eight8.19 ZOJ1091 KnightMoves上机练习题参考文献

章节摘录

版权页：插图：5.可行性在有限时间内完成计算过程。算法1.1用一个正整数来除另一个正整数，判断一个整数是否为0以及整数赋值等，这些运算都是可行的。因为整数可以用有限的方式表示，所以至少存在一种方法来完成一个整数除以另一个整数的运算。必须注意到，在实际应用中，有限性的限制是不够的。一个实用的算法，不仅要求步骤有限，同时要求运行这些步骤所花费的时间是人们可以接受的。如果一个算法需要执行数万亿亿计数的运算步骤，从理论上说，它是有限的，最终可以结束。但是，以当代计算机每秒数亿次的运算速度，也必须运行数百年以上，这是人们所无法接受的，因而它是不实用的算法。1.1.2 算法的设计算法设计的整个过程，可以包含对问题需求的说明、数学模型的拟制、算法的详细设计、算法的正确性验证、算法的实现、算法分析、程序测试和文档资料的编制。计算机科学家尼克劳斯·沃思曾著过一本著名的书《数据结构+算法一程序》，可见算法在计算机科学界与计算机应用界的地位。同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择适用算法和改进算法。一个算法的评价主要从时间复杂性和空间复杂性来考虑。算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法和并行算法。算法大致分为以下三类。

编辑推荐

《算法分析与设计:以大学生程序设计竞赛为例》内容主要介绍经典的算法设计技术，包括数据结构和标准模板库STL等。教学门标明确，注重理论与实践的结合。教学方法灵活，培养学生自主学习的能力。教学内容先进，反映了计算机学科的最新发展。教学模式完善，提供配套的教学资源解决方案。

用户评论 (总计13条)

•   算法设计与分析方面非常好的一本书，对学习很有帮助
•   有关算法的书有多少本都不是错啊，哈哈哈哈哈哈。
•   各类题目入门必读
•   內容灰常充實 書本不薄也不厚
•   该书的特点是和作者所在学校的训练平台试题结合比较紧密，针对性强，但是题目稍难。
•   书还好吧，没有题目全部，只是从翻译开始的，不过写的也好。
•   不错的一本书，建议大家买~~~
•   这本书居然缺页，貌似网上不止我缺，看了下其他人的评论，都说缺页，不建议买
•   因为师哥们没修这个不得不买的新书
•   书不错，讲解很详细，很喜欢
•   书的内容还没详细看，但感觉不错，书的纸质差了一点
•   书有缺页，真有点坑爹呀！
•   就需要这样的书 给力看过以后可以再OJ上自己实现一次