课程简介

本课程的内容分成两大部分:算法的基础知识、通用算法设计技术与分析方法。 第一部分是算法基础知识,约占20%,主要介绍算法相关的基本概念和数学基础。比如,什么是算法的伪码描述?什么是算法最坏情况下和平均情况下的时间复杂度?算法时间复杂度函数的主要性质,算法复杂度估计中常用的数学方法,如序列求和及递推方程求解。 第二部分是通用的算法设计技术与分析方法,主要介绍分治策略、动态规划、贪心法、回溯与分支限界。主要介绍这些设计技术的使用条件、分析方法、改进途径,并给出一些重要的应用。

课程大纲


第一周    1章 基础知识:算法的基本概念及伪码描述,函数的渐近的界

第二周    1章 基础知识:序列求和方法,递推方程求解

第三周    2章 分治策略(1)

第四周    2章 分治策略(2)

第五周    3章 动态规划(1)

第六周    3章 动态规划(2)

第七周    4章 贪心法(1)

第八周    4章 贪心法(2)

第九周    5章 回溯与分支限界(1)

第十周    5章 回溯与分支限界(2)


课程说明

课程教学目标

针对实际问题需求,进行数学建模并选择高效求解算法的训练,为提高学生的素质和创新能力打下必要的基础。主要内容涉及:面对实际问题建立数学模型、设计正确的求解算法、算法的效率估计、改进算法的途径、问题计算复杂度的估计、难解问题的确定和应对策略等等。本课程是算法课程的基础部分,主要涉及算法的设计、分析与改进途径,其他有关计算复杂性的内容将在后续课程中加以介绍。


授课形式

本课程的内容包含“课程视频”和“练习题”。

课程视频根据知识点组织,每个视频基本上对应于一个独立的话题,相关知识点的视频放在同一教学周中。每周布置有练习题,用于重申课程的要点,巩固相关的概念,学习使用相关的设计技术和分析方法。练习题是在线练习,学习时可以在线提交结果。


先修知识

本课程需要一些高等数学的基础知识,如函数极限与积分,也需要了解一些基本的数据结构,如数组、链表、图等,学习中只需要了解相关概念。在课程开始对部分基础知识做了概括的介绍,大家可以根据自己的情况安排学习。


参考资料

基本资料

主要参考本课程所提供的讲义、资料与测试题。

参考资料

1. 屈婉玲,刘田,张立昂,王捍贫,算法设计与分析,清华大学出版社,2011年版,2013年重印.

2. 屈婉玲,刘田,张立昂,王捍贫,算法设计与分析习题解答与学习指导,清华大学出版社,2014.

3.  Jon Kleinberg, Ėva Tardos, Algorithm Design,(张立昂,屈婉玲译,《算法设计》),清华大学出版社,2006.

4.  Thomas H. Cormen, Charles E.Leiserson, Ronald L. Rivest, Introduction to Algorithms(3rd edition), McGraw-Hill Book Company,2009


拓展阅读

其他

主讲教师

屈婉玲   

多年主讲北京大学信息科学技术学院本科生离散数学课程(代数结构与组合数学),系国家级精品课离散数学课程主持人。多年主讲算法分析与复杂性理论、算法分析与设计等研究生必修课。主持过多项教改课题,出版过20多本教材,其中含4本国家级规划教材。承担过多项国家科研项目,主要研究方向是算法设计与分析、软件形式化方法,发表学术论文30多篇。

课程助教

  • duruihuan

  • jingpinmooc

相关课程推荐

  • 正在进行
    Java程序设计
    《Java程序设计》课程是使用Java语言进行应用程序设计的课程,针对各专业的大学本科生开设。课程的主要目标有三: 一、掌握Java语言的语法,能够较为深入理解Java语言机制,掌握Java语言面向对象的特点。 二、掌握JavaSE中基本的API,掌握在集合、线程、输入输出、图形用户界面、网络等方面的应用。三、能够编写有一定规模的应用程序,养成良好的编程习惯,会使用重构、设计模式、单元测试、日志、质量管理工具提高代码的质量。 对于学过“计算机基础、计算概论或C语言的学生”尤为适用。
  • 正在进行
    面向对象技术高级课程
    《面向对象技术高级课程》深入、系统、完整地讲解当今主流的面向对象软件开发方法的分析、设计、实现及重构方法,深入讲解UML语言的高级技术细节,以及近年来面向对象方法最新的发展趋势。课程集百家之所言,并结合主讲者最新的研究成果,并通过大量、丰富、完整、不同领域、应用不同技术的案例将其中的关键知识点串联起来,便于理解和应用。 此课程适用人群:面向广大软件开发爱好者,并不局限专业与学历层次。最佳选课者为计算机科学和软件工程专业的大学生和硕士研究生。选课者最好具有一门面向对象的编程语言的基本知识和软件工程的基本知识。
  • 正在进行
    解密教育的技术变革史
    互联网并非人类历史上第一次“信息技术”革命。人类历史上一共出现过5种媒介技术:口头语言、手工抄写/羊皮书、印刷技术、广播电视和互联网。 媒介技术提供的记录和传承功能,对人类的群体社会认知,带来了革命性的影响。西方历史上曾经发生的两次文明的大发展,都正好处于媒介技术变革前后。希腊文明处于希腊从口传到手工抄写的媒介技术变革中;近代科学史上的哥白尼革命,又正好处于欧洲从手工抄写到机器印刷的技术转型中;今天,轮到了信息技术…… 吟唱、诗歌、戏曲、绘画、文字书写等,都曾经是一种表达“技术”;《荷马史诗》、《圣经》都曾经充当过识字课本;口头语言、羊皮纸卷、印刷书、广播电视,都是曾经的“教育技术”。 这门课程从重新定义教育和人这两个核心概念开始,带着你从媒介史、知识产业分工配套体系、教学模式和教育组织方式等不同的视角,游历人类一路走来传播生态环境、知识产业、教育教学的发展过程,从中寻找媒介技术影响教育变革的规律,指导学习者迎接未来教育变革的挑战,寻找创新和发展方向!

恭喜,报名成功

进入学习中心

恭喜,报名成功

确定

请进入开课界面预览

确定

X

请去您的邮箱验证

还没收到验证邮件?

1. 试试去广告邮件、垃圾邮件目录看看

2. 再次发送验证邮件

对不起,班次容量已满

请报名下一班次

知道了~!

对不起,您没有操作权限

知道了~!