高级数据结构与算法分析

课程介绍

本课程是面向图灵创新实验班开设的专业核心必修课，向前衔接高级程序设计语言、面向对象程序设计方法、数据结构与基础算法，向后衔接计算理论、机器学习、人工智能、大数据分析方法等课程。课程面向计算机专业领域竞赛实践、工程应用与学术研究，通过讲授算法的概念及设计方法，锻炼学生的抽象思维、计算思维，培养学生的创造性思维，提升学生在理论指导下分析实际问题、解决实际问题的能力，为开发高效的软件系统，以及解决相关领域问题奠定坚实的基础。

在理论课中，本课程衔接数据结构与算法基础，主要讲授高级数据结构原理与应用，算法复杂性分析理论与方法，以及包括分治思想、动态规划、贪心算法、搜索技术、随机算法等在内的经典算法原理与应用。每类算法讲授主要包括算法的思想与性质，经典算法案例与典型扩展应用。

在实践课中，着重训练学生利用典型算法解决复杂问题的能力，培养学生分析、描述、解决复杂问题的能力，锻炼学生针对复杂问题的数据结构描述，训练学生针对复杂问题的算法设计与程序实现能力，以及算法方案评估能力。

[展开]

1 算法概述与典型问题

1.1算法概念

1.2算法复杂性分析

1.3NP完全理论

1.4代表性问题

1.5总结与拓展

2 算法数学基础

2.1数学归纳法

2.2数论与组合数学

2.3计算几何

2.4概率与随机

2.5算法竞赛中的数学难题

2.6总结与拓展

3 数据结构进阶

3.1数据的表示与存储

3.1.1 二进制与倍增

3.1.2 单调队列

3.1.3 链表与跳跃表

3.1.4 链式前向星

3.2区间问题专题

3.3面向查找的树结构设计与优化

3.3.1 堆的扩展

3.3.2 伸展树

3.3.3 红黑树

3.3.4 B树及其扩展

3.4图结构算法

3.4.1 最短路径

3.4.2 图匹配

3.4.3 网络流

3.5算法竞赛中的数据结构难题

3.6总结与拓展

4 分治与贪心

4.1分治思想应用

4.2贪心算法设计

5 动态规划进阶

5.1动态规划思想

5.2典型动态规划方法设计

5.2.1 线型DP与区间DP

5.2.2 树状DP与状压DP

5.2.3 概率DP与插头DP

5.3动态规划优化技巧

5.4总结与拓展

6 搜索技术进阶

7 字符串处理

8 典型随机算法

9 前沿算法研究

下一课上一课

杜祥军高级实验师

单位：青岛大学

部门：计算机科学技术学院

职位：院长助理

个人介绍

研究领域

1.机器学习、深度学习、大数据分析与复杂网络

2.计算机创新创业教育与创新人才培养模式改革

论文与著作

1.SCI论文等10余篇

2.《C语言学习指导与课程设计实践》等教材5部

荣誉与奖励

国家级教学成果二等奖1项，山东省高等教育教学成果特等奖1项、一等奖2项、二等奖1项

青岛大学“最美教师”、“教育先锋”、...

本课程是专业核心必修课，对培养计算机专业创新人才有着重要的作用，教学中应给予极大的重视。在理论课的讲述中特别注重讲解问题的分析过程，将设计方法、分析技术与具体范例的讲解相结合，多举应用实例，由浅入深、分步讲解，从而使学生逐步掌握所学内容。

每次课均要求学生课前预习、课后复习，同时配以相应的习题讨论、实验实践与作业练习。由于课程学习难度较大，应多鼓励学生坚持不懈，并对有难度的练习给予一定的弹性时间完成，同时允许学生分组研究共同完成。

（一）教材

算法设计，[美] Jon Kleinberg, Éva Tardos著，王海鹏译，人民邮电出版社，2021.

（二）学习资源

[1] 算法导论公开课：http://open.163.com/special/opencourse/algorithms.html，麻省理工学院.

[2] 算法导论(原书第3版)，（美）Thomas H.Cormen,Charles E.Leiserson,RonaldL.Rivest,Clifford Stein著，潘金贵等译，机械工业出版社，2013

[3] 数据结构与算法分析:C语言描述(原书第2版)，（美）Mark AllenWeiss著，冯舜玺译，机械工业出版，2004.

[4] 算法引论:一种创造性方法，（美）Udi Manber著，黄林鹏等译，电子工业出版社，2010.