算法分析与设计
算法分析与设计
1000+ 人选课
更新日期:2025/06/17
开课平台学银在线
开课高校山东财经大学
开课教师李恒武林培光高珊珊耿蕾蕾
学科专业工学计算机类
开课时间2023/03/07 - 2023/07/07
课程周期18 周
开课状态已结课
每周学时-
课程简介

  本课程是软件工程、计算机科学及相关专业技术基础课程和关键性核心课程,是系统软件及大型应用软件的重要基础。课程系统的介绍了软件设计中常用的算法设计与分析方法,锻炼学生分析问题和解决问题的能力,为开发高效的软件系统及相关领域的研究工作奠定坚实的基础。

  本课程从解决问题和应用实例入手,按照提出问题、分析问题、解决问题、总结问题的步骤,培养学生算法基本理论来分析和解决问题的能力。以实践为导向,专题案例与思考讨论相结合, 自动评测和互动交流相结合,引导学生参加小组活动和科技竞赛,培养学生的实践能力、科研创新能力和团队合作能力。适应探究性和碎片化学习,聚集和重组课程内容;适应自主性和多样化学习,线上开放与线下实践相结合;适应多元化和个性化需求,培养学生主动学习、研究和创新意识。

教学目标:
通过本课程的学习,使学生具备下列能力:
1. 能够掌握算法分析与设计的基本理论,学会枚举、递推、贪心、分治、动态规划、回溯、分支限界、网络流、图算法、随机算法等基本方法和分析技巧。
2. 能够正确分析程序的计算复杂性,以及提高算法性能。培养其分析算法复杂度和设计算法的初步能力。
3. 能够针对具体的应用问题,进行有效的分析,建立合理的数学模型,选择合适的数据结构,设计结构清晰、正确有效的算法解决之。培养其计算思维及用计算机分析与解决问题等基本能力。
4. 能够应用程序设计语言和数据结构实现程序开发,培养其程序设计、实现、调试测试的基本能力,强化学生专业核心意识和职业素养,培养学生的动手能力和解决实际问题的能力。
5.能够引导学生学习算法分析和设计的新方法和新技术,引导学习分析解决新问题,锻炼其逻辑思维能力和想象力,培养学生的独立科研能力和理论联系实践的能力,培养学生的创新能力和团队合作能力,为计算机应用和科学研究工作中有效求解问题打下基础。



课程大纲

第一单元 算法与问题

  • 1.1 第一课时 稳定匹配问题
  • 1.2 第二课时 Hi!什么是算法?
  • 1.3 第三课时 大学入学申请问题
  • 1.4 第一单元 章节测验

第二单元 算法分析

  • 2.1 第一课时 算法分析
  • 2.2 第二课时 几个符号
  • 2.3 第三课时 复杂度比较
  • 2.4 第四课时 分析实例
  • 2.5 第五课时 时空均衡
  • 2.6 第二单元 章节测验

第三单元 枚举算法

  • 3.1 第一课时 枚举算法
  • 3.2 第二课时 集合与排列
  • 3.3 第三单元 章节测验

第四单元 贪心算法

  • 4.1 第一课时 背包问题
  • 4.2 第二课时 基本要素
  • 4.3 第三课时 区间问题
  • 4.4 第四课时 MST问题
  • 4.5 第五课时 哈夫曼编码
  • 4.6 第四单元 章节测验

第五单元 递推算法

  • 5.1 第一课时 递归与递推
  • 5.2 第二课时 正推与倒推
  • 5.3 第三课时 递推方程求解
  • 5.4 第五单元 章节测验

第六单元 分治算法

  • 6.1 第一课时 分治算法
  • 6.2 第二课时 分治类型
  • 6.3 第三课时 减少子问题个数
  • 6.4 第四课时 改进分治的均衡度
  • 6.5 第五课时 减少合并时间
  • 6.6 第六单元 章节测验

第七单元 动态规划

  • 7.1 第一课时 动态规划
  • 7.2 第二课时 数字三角形
  • 7.3 第三课时 增加变量
  • 7.4 第四课时 区间动归
  • 7.5 第五课时 DAG图
  • 7.6 第六课时 树图动归(上)
  • 7.7 第七课时 树图动归(下)
  • 7.8 第七课时 序列比对
  • 7.9 第七单元 章节测验

第八单元 回溯算法

  • 8.1 第一课时 装载问题
  • 8.2 第二课时 旅行商问题
  • 8.3 第三课时 基本特征
  • 8.4 第八单元 章节测验

第九单元 分支限界

  • 9.1 第一课时 0-1背包问题
  • 9.2 第二课时 旅行商问题
  • 9.3 第三课时 基本思想
  • 9.4 第九单元 章节测验

第十单元 网络流算法

  • 10.1 第一课时 最大流最小割
  • 10.2 第二课时 最大流算法
  • 10.3 第三课时 预流推进算法
  • 10.4 第四课时 最大流推广
  • 10.5 第五课时 最小费用最大流
  • 10.6 第六课时 二分匹配(上)
  • 10.7 第七课时 二分匹配(下)
  • 10.8 第十单元 章节测验

第十一单元 随机算法

  • 11.1 第一课时 随机算法1
  • 11.2 第二课时 随机算法2
  • 11.3 第十一单元 章节测验

第十二单元 P与NP

  • 12.1 第一课时 P与NP
  • 12.2 NP完全证明
  • 12.3 NP完全求解
  • 12.4 第十二单元 章节测验

近似算法

  • 13.1 绝对近似
  • 13.2 相对近似(一)
  • 13.3 相对近似(二)
  • 13.4 近似方案
  • 13.5 第十三单元 章节测验