spContent=本课程以计算机经典问题求解为导向，通用算法思维和编码能力培养为目标，引入ACM 国际大学生程序设计竞赛的有益元素，精心安排课程的理论教学和编程实践。本课程学习将帮助同学提高算法思维和程序设计能力，为后续课程打下良好基础。
本课程以计算机经典问题求解为导向，通用算法思维和编码能力培养为目标，引入ACM 国际大学生程序设计竞赛的有益元素，精心安排课程的理论教学和编程实践。本课程学习将帮助同学提高算法思维和程序设计能力，为后续课程打下良好基础。
—— 课程团队
课程概述
“软件 = 算法 + 数据结构”，算法是软件的灵魂。在信息时代，计算思维是分析复杂工程问题的重要思维方式， 计算机则是求解问题的重要工具。本课程以计算机经典问题求解为导向，通用算法思维和编码能力培养为目标，引入ACM 国际大学生程序设计竞赛的有益元素，精心安排课程的理论教学和编程实践。
本课程主要讲授计算机问题求解的经典算法设计方法和算法复杂度分析方法，主要内容包括算法复杂度分析，枚举算法，递归与分治策略，动态规划，贪心算法和通用搜索技术。本课程除了强调经典的算法理论和模型，亦兼顾编程实践能力。力图使得学员面对复杂问题时，既能“想到”还能“做到”。
授课目标
培养算法思维，掌握枚举算法、分治策略、动态规划、贪心算法和搜索算法等经典算法模型；
培养实践能力，掌握在存储空间和时间开销受限情况下的程序设计方法；
培养理论思维，掌握复杂问题的算法设计与分析方法。
成绩 要求
学习本课程，积极参与课程讨论，完成本课的单元测试、单元作业、OJ在线算法实训和期末测验。
评分依据：课程满分100分。单元作业占40分，课程讨论占10分，OJ在线算法实训占10分，考试占40分。
课程大纲
第一章 绪论
1.1 什么是算法
1.2 计算机问题求解周期
1.3 为什么要学习算法
1.4 算法复杂度之大O定义
1.5 算法复杂度之大O运算
1.6 算法复杂度分析实例-非递归
1.7 算法复杂度分析实例-递归
1.8 小结
时间复杂度分析作业
第二章 枚举算法（大道至简）
2.1 基本原理
2.2 模糊数字问题
2.3 百钱百鸡问题
2.4 数组配对问题
2.5 绳子切割问题
2.6 石头移动问题
2.7 小结
枚举算法实践
第三章 递归与分治（庖丁解牛）-1
3.1 递归基本思想
3.2 递归实例
3.3 分治基本原理
3.4 Master定理
3.5 合并排序
递归算法实践
第三章 递归与分治（庖丁解牛）-2
3.6 逆序对问题
3.7 快速排序
3.8 最接近点对
3.9 乘方运算
3.10 线性时间选择
3.11 小结
分治算法实践
第四章. 动态规划（跬步千里）-1
4.1 基本原理
4.2 矩阵连乘 - 问题分析
4.3 矩阵连乘 - 算法与实现
4.4 矩阵连乘 - 备忘录方法
4.5 多段图最短路径 - 问题分析
4.6 多段图最短路径 - 算法与实现
动态规划算法实践-1
第四章. 动态规划（跬步千里）-2
4.7 最长公共子序列 - 问题分析
4.8 最长公共子序列 - 算法与实现
4.9 0-1背包 - 问题分析
4.10 0-1背包 - 算法与实现
4.11 0-1背包 - 优化方法
4.12 最大上升子序列 - 问题分析
4.13 最大上升子序列 - 算法与实现
4.14 小结
动态规划算法实践-2
第五章. 贪心算法（局部寻优）-1
5.1 基本原理
5.2 活动安排问题-算法与实现
5.3 活动安排问题-正确性证明
5.4 小数背包问题
5.5 哈夫曼编码-算法与实现
5.6 哈夫曼编码-正确性证明
5.7 单源最短路径-Dijkstra与实现
5.8 单源最短路径-正确性证明
贪心算法实践-1
第五章. 贪心算法（局部寻优）-2
5.9 最小生成树-问题分析
5.10 最小生成树-Prim算法与实现
5.11 最小生成树-Prim证明
5.12 并查集基础
5.13 最小生成树- Kruskal算法与实现
5.14 最小生成树- Kruskal证明
5.15 小结
贪心算法实践-2
第六章. 搜索技术（按图索骥）-1
6.1 状态空间图
6.2 深度优先搜索
6.3 广度优先搜索
6.4 回溯算法-原理
6.5 回溯算法-实例
搜索算法实践-1
第六章. 搜索技术（按图索骥）-2
6.6 分支限界法-原理
6.7 分支限界法-实例
6.8 启发式搜索-原理
6.9 A*算法-原理
6.10 启发式搜索-实例
6.11 小结
搜索算法实践-2
展开全部
预备知识
高级程序设计语言基础，熟悉C/C++，Java，Python中的任何一种；
高等数学、线性代数等基本工科数学基础；
了解基本的数据结构知识；
了解 Online Judge。
参考资料
李清勇. 算法设计与问题求解-编程实践, 电子工业出版社, 2013.
Cormen, T.H.等著，潘金贵等译. 算法导论，机械工业出版社，2006.
浙公网安备 33010802012594号
