基本信息
内容简介
目录
前言
教学建议
第一部分 计算模型
第1章 抽象的算法设计与分析2
1.1 RAM模型的引入2
1.1.1 计算的基本概念2
1.1.2 计算模型的基本概念3
1.1.3 RAM模型4
1.1.4 计算模型的选择：易用性和精确性6
1.2 抽象算法设计7
1.2.1 算法问题规约7
1.2.2 算法正确性证明：数学归纳法8
1.3 抽象算法分析10
1.3.1 抽象算法的性能指标10
1.3.2 最坏情况时间复杂度分析11
1.3.3 平均情况时间复杂度分析12
1.4 习题13
第2章 从算法的视角重新审视数学的概念16
2.1 数学运算背后的算法操作16
2.1.1 取整x和x16
教学建议
第一部分 计算模型
第1章 抽象的算法设计与分析2
1.1 RAM模型的引入2
1.1.1 计算的基本概念2
1.1.2 计算模型的基本概念3
1.1.3 RAM模型4
1.1.4 计算模型的选择：易用性和精确性6
1.2 抽象算法设计7
1.2.1 算法问题规约7
1.2.2 算法正确性证明：数学归纳法8
1.3 抽象算法分析10
1.3.1 抽象算法的性能指标10
1.3.2 最坏情况时间复杂度分析11
1.3.3 平均情况时间复杂度分析12
1.4 习题13
第2章 从算法的视角重新审视数学的概念16
2.1 数学运算背后的算法操作16
2.1.1 取整x和x16
前言
算法是计算的灵魂(spirit of computing)，而算法设计与分析的基础知识是计算机科学的基石。算法设计与分析的知识内容很丰富，可以从不同视角进行组织与阐述。一种视角是关注经典的算法问题，如排序、选择、查找、图遍历等；另一种视角是关注经典的算法设计策略，包括分治、贪心、动态规划等。本书的组织兼顾问题与策略两种视角。首先按照经典的算法设计策略，将书中的主体内容分为遍历、分治、贪心、动态规划4个部分。其次在每个部分之内，又围绕经典的算法问题来阐述该部分所着重讨论的策略。
本书集中讨论抽象的即与机器、实现语言无关的算法设计与分析。为此在主体内容之前，我们首先讲解计算模型的基础知识，它是后续抽象讨论算法设计与分析的基础。另外，在本书的最后，我们介绍计算复杂性的基础知识，试图让读者在了解了各类算法问题、学习了各种算法设计和分析技术之后，对算法问题的难度有一个总体性的认识。此外，一些对于算法设计与分析较为关键的数学知识将在附录中列出。本书的内容是作者在过去多年授课的过程中逐渐积淀而成的，所以它不是对算法设计与分析知识的一个百科全书式的覆盖，而是对一些重点内容的更专注的讨论。
本书内容和组织方式的设计针对一个学期的授课展开。在内容方面，本书可以分为前后两个部分。前一部分主要围绕元素的序关系展开，讨论排序、选择、查找这3个经典的算法问题。而这3个问题的求解同时又是分治策略的典型应用。后一部分主要围绕“图”这一数学结构展开，讲授图遍历、最小生成树、最短路径等经典图算法。同时，这些图算法背后的一个核心问题是图上特定结构——最小生成树、最短路径——的优化。围绕图优化，我们展示了贪心策略与动态规划策略的典型应用。
在授课形式方面，我们将课程分为主课与辅课这两种形式。主课主要围绕典型的算法问题、经典的算法展开。而辅课则围绕算法策略来展开，在讲述若干经典问题、经典算法之后，从策略的视角回顾最近阶段的经典算法，同时补充新的素材对相应的策略进行进一步的展示。除知识讲授之外，实践也是“算法设计与分析”课程的重要组成部分。算法设计与分析课程的实践分为两类：一类是传统的习题，即紧扣书本知识的习题，如一些简单定理的证明、紧扣算法细节的一些问题等；另一类是应用题，它需要读者对一个有一定现实意义的问题进行建模，并用书中的算法知识来求解。本书的应用题大都可以用于算法编程实现的训练。在实际授课中，我们挑选了部分应用题作为编程实现题，并基于开源的OnlineJudge平台进行自动评测，取得了良好的效果。
本书的素材主要源自于南京大学计算机系本科生“算法设计与分析”课程的授课内容。其中一部分素材来源于共同授课的其他老师，包括前期负责讲授主课并指导辅课教学的陈道蓄老师，以及后期共同分班讲授这门课程的钱柱中老师。还有一部分素材来自于经典的算法教科书和国外大学授课教师在其课程网站上发布的课程材料。另外，还要感谢“算法设计与分析”课程的两位助教魏恒峰和杨怡玲，他们对大量的课程资料进行了整理与提炼。最后要感谢上过这门课的学生，他们创造性的提问与解题时所犯的错误都为本书提供了宝贵的素材。
教学建议说明：南京大学计算机系“算法设计与分析”课程的讲授采用三种不同形式，即主课、辅课（tutorial）和习题课。
●主课围绕各个主要知识点进行专题讲授。下面列出主课的授课计划，包括每次课的主题以及所对应的书本中的章节。
●辅课的主要内容是对前一阶段主课知识的多角度解读，以及重点内容的强化。辅课的授课往往以围绕经典例题的讨论为主，以知识点的阐述为辅。
●习题课的讲授主要包括书上习题的讲解，以及上机评测问题的讲解。习题课的讲授可以根据具体的教学、上机、考试等情况进行相应的安排。
教学章节教学要求课时主课一准备知识
（第1章）计算模型的基础知识
抽象算法设计与分析的基本概念2主课二数学基础
（第2章）函数渐近增长率的基本概念
简单蛮力算法的逐步改进2递归方程的基本求解技术
基于Master定理的分治递归求解2辅课一从算法设计与分析的角度重新审视数学的概念2主课三排序
（第3、6、7章）线性表的遍历，从蛮力排序到快速排序2堆结构的维护
堆结构的应用：堆排序与优先队列2合并排序
基于比较的排序的下界2辅课二排序：从简单遍历到分而治之2主课四选择
（第8章）选择问题的简单特例
期望线性时间选择
本书集中讨论抽象的即与机器、实现语言无关的算法设计与分析。为此在主体内容之前，我们首先讲解计算模型的基础知识，它是后续抽象讨论算法设计与分析的基础。另外，在本书的最后，我们介绍计算复杂性的基础知识，试图让读者在了解了各类算法问题、学习了各种算法设计和分析技术之后，对算法问题的难度有一个总体性的认识。此外，一些对于算法设计与分析较为关键的数学知识将在附录中列出。本书的内容是作者在过去多年授课的过程中逐渐积淀而成的，所以它不是对算法设计与分析知识的一个百科全书式的覆盖，而是对一些重点内容的更专注的讨论。
本书内容和组织方式的设计针对一个学期的授课展开。在内容方面，本书可以分为前后两个部分。前一部分主要围绕元素的序关系展开，讨论排序、选择、查找这3个经典的算法问题。而这3个问题的求解同时又是分治策略的典型应用。后一部分主要围绕“图”这一数学结构展开，讲授图遍历、最小生成树、最短路径等经典图算法。同时，这些图算法背后的一个核心问题是图上特定结构——最小生成树、最短路径——的优化。围绕图优化，我们展示了贪心策略与动态规划策略的典型应用。
在授课形式方面，我们将课程分为主课与辅课这两种形式。主课主要围绕典型的算法问题、经典的算法展开。而辅课则围绕算法策略来展开，在讲述若干经典问题、经典算法之后，从策略的视角回顾最近阶段的经典算法，同时补充新的素材对相应的策略进行进一步的展示。除知识讲授之外，实践也是“算法设计与分析”课程的重要组成部分。算法设计与分析课程的实践分为两类：一类是传统的习题，即紧扣书本知识的习题，如一些简单定理的证明、紧扣算法细节的一些问题等；另一类是应用题，它需要读者对一个有一定现实意义的问题进行建模，并用书中的算法知识来求解。本书的应用题大都可以用于算法编程实现的训练。在实际授课中，我们挑选了部分应用题作为编程实现题，并基于开源的OnlineJudge平台进行自动评测，取得了良好的效果。
本书的素材主要源自于南京大学计算机系本科生“算法设计与分析”课程的授课内容。其中一部分素材来源于共同授课的其他老师，包括前期负责讲授主课并指导辅课教学的陈道蓄老师，以及后期共同分班讲授这门课程的钱柱中老师。还有一部分素材来自于经典的算法教科书和国外大学授课教师在其课程网站上发布的课程材料。另外，还要感谢“算法设计与分析”课程的两位助教魏恒峰和杨怡玲，他们对大量的课程资料进行了整理与提炼。最后要感谢上过这门课的学生，他们创造性的提问与解题时所犯的错误都为本书提供了宝贵的素材。
教学建议说明：南京大学计算机系“算法设计与分析”课程的讲授采用三种不同形式，即主课、辅课（tutorial）和习题课。
●主课围绕各个主要知识点进行专题讲授。下面列出主课的授课计划，包括每次课的主题以及所对应的书本中的章节。
●辅课的主要内容是对前一阶段主课知识的多角度解读，以及重点内容的强化。辅课的授课往往以围绕经典例题的讨论为主，以知识点的阐述为辅。
●习题课的讲授主要包括书上习题的讲解，以及上机评测问题的讲解。习题课的讲授可以根据具体的教学、上机、考试等情况进行相应的安排。
教学章节教学要求课时主课一准备知识
（第1章）计算模型的基础知识
抽象算法设计与分析的基本概念2主课二数学基础
（第2章）函数渐近增长率的基本概念
简单蛮力算法的逐步改进2递归方程的基本求解技术
基于Master定理的分治递归求解2辅课一从算法设计与分析的角度重新审视数学的概念2主课三排序
（第3、6、7章）线性表的遍历，从蛮力排序到快速排序2堆结构的维护
堆结构的应用：堆排序与优先队列2合并排序
基于比较的排序的下界2辅课二排序：从简单遍历到分而治之2主课四选择
（第8章）选择问题的简单特例
期望线性时间选择
