学校云 建设你的专属在线教育平台
中国大学MOOC
SPOC学校专有课程
算法分析与设计
分享
spContent=“有两种思想,就像摆放在天鹅绒上的宝石那样熠熠生辉,一个是微积分,另一个就是算法。微积分以及在微积分基础上建立起来的数学分析体系造就了现代科学,而算法则造就了现代世界” ——大卫.伯林斯基
—— 课程团队
课程概述

算法是计算机科学的核心,绝大多数科学、商业和技术都与其密切相关。课程将从算法表示、分析、设计策略三个方面开展线上线下混合教学,以实际工程应用问题为导向,开展探究式实践教学,使学生能从数学上分析算法的时间、空间复杂度;针对特定的问题,能形式化描述问题,选择合适的算法设计策略开展算法设计、分析、证明等,能对问题的算法复杂性进行讨论。

教学团队长期从事程序设计、算法分析等课程的教学,多年指导程序设计类学科竞赛,同时具有丰富的软件开发工程经验,能将算法设计策略与工程实际问题进行有效结合,有效训练学生的计算思维及解决实际问题的能力。


授课目标

目标1:能够对复杂软件中设计的递归算法、非递归算法的时间复杂度进行数学描述及分析,并能选择合适的渐进符号进行表达。

目标2:理解精确算法、近似算法、算法正确性证明、算法时间复杂性、空间复杂性、算法时间渐进表示等算法时间复杂的分析的概念和符号,能使用标准伪代码对软件工程中的算法进行表达。

目标3理解分治法、变治法、减治法、时空权衡、动态规划、贪婪策略、迭代改进、分支限界、回溯法等算法设计策略的基本原理及特点,对软件开发中的特定问题,能形式化描述问题,并能选择合适的设计策略进行算法设计与实现,说明算法的正确性,计算算法的时间复杂度,并进行复杂性讨论。


成绩要求

百分制,满分100分,60分合格。

考核方式:

线上单元测验:10%

线上单元作业:10%

线上课程讨论:10%

课后研究报告:10%

上机考试:期中(30%)、期末(30%)


课程大纲
预备知识

先修知识点:集合、排列、矩阵、高级程序设计语言、图、树、递归等。

先修能力和素质基础:能使用高级程序设计语言完成代码编写、运行与调试的能力,具备一定分析问题和解决问题的能力。

先修主要课程:离散数学、程序设计(C语言)、数据结构。

参考资料

1. (美) Anany Levtin著. 算法分析与设计基础(第三版),潘彦译,清华大学出版社,2015年2月

2. Thomas H.Cormen等著,殷建平,徐云,王刚等译.算法导论(第三版).机械工业出版社.20131