算法设计与分析——基于计算教学论的解析

本教材是基于作者所创立的计算教学论编写的，是为实现教学效率显著提升而对计算教学论提出的思想、方法和工具的深广应用。本教材共12章。第1章由EuclidGCD算法引出算法的定义，并介绍基于可视化的算法学习方法，第2～5章分别介绍算法的穷举设计方法、算法复杂度分析、算法的递归设计方法和基于比较的排序算法，第6～10章分别介绍分治、动态规划、贪心、回溯和分支限界等经典的算法设计方法，第11章介绍RSA算法，第12章介绍NP理论。本教材可作为高等学校计算机科学与技术专业算法设计与分析课程的教材，也可作为计算机及相关专业研究生和科研、工程或技术人员自学算法设计与分析的参考书。

段会川 教授，长期致力于以计算改进教和学的效率，并创立了计算教学论学说。该学说以计算的本质能力即算法化的知识表达和解析改进教与学的效率，在《算法设计与分析》和《计算机网络原理》课程中取得了很好的效果。

第1章 算法及其可视化教学支持系统
1.1 初识算法：Euclid GCD算法
1.1.1 GCD及因子分解方法
1.1.2 Euclid GCD算法
1.2 算法的定义
1.2.1 算法是一种求解问题的科学方法
1.2.2 算法的克努特定义
1.2.3 算法的图灵机定义
1.3 算法的描述方法
1.3.1 算法的自然语言描述方法
1.3.2 算法的流程图描述方法
1.3.3 算法的伪代码描述方法
1.3.4 算法的现代版C++描述方法
1.3.5 设计算法求解问题的基本过程
1.4 可视化算法学习的支持工具
1.4.1 CAAIS的基本界面及其功能
1.4.2 算法CD-AV演示的基本操作
1.5 使用现代版C++进行算法实验
1.5.1 现代版C++的算法实验环境建议
1.5.2 算法的现代版C++实现方式——以Euclid GCD算法为例
1.6 算法国粹——《九章算术》中的二进制GCD算法
1.6.1 《九章算术》中的更相减损术——最早的二进制GCD算法
1.6.2 现代版的二进制GCD算法
习题
参考文献
第2章 算法的穷举设计方法
2.1 穷举算法设计基础
2.2 穷举算法设计示例
2.2.1 百钱买百鸡问题算法设计
2.2.2 素性测试的试除算法设计
2.2.3 顺序搜索算法设计及CD-AV演示
2.2.4 洗牌算法设计及CD-AV演示
2.3 伪随机数发生器及其在算法实验中的应用
2.3.1 生成伪随机数的线性同余法
2.3.2 传统C语言标准库中的伪随机函数及其应用
2.3.3 现代版C++标准库中的伪随机函数及其应用
2.4 算法国粹——图灵奖获得者姚期智院士的伪随机数理论
2.4.1 姚期智院士密码学安全的伪随机数理论
2.4.2 LCG不是密码学安全的
2.4.3 JavaJDK提供的密码学安全的伪随机数发生器
习题
参考文献
第3章 算法复杂度分析
3.1 算法复杂度分析基础
3.1.1 算法的输入规模及复杂度计量
3.1.2 算法的优选、最坏和平均情况复杂度
3.2 算法复杂度的渐近分析方法
3.2.1 算法的渐近复杂度及其记法
3.2.2 常见的算法复杂度阶及其关系
……
第4章 算法的递归设计方法
第5章 基于比较的排序算法
第6章 算法的分治设计方法
第7章 算法的动态规划设计方法
第8章 算法的贪心设计方法
第9章 算法的回溯设计方法
第10章 算法的分支限界设计方法
第11章 RSA算法
第12章 NP理论
附录：教材算法的现代版C++实现及计算教学论简介