算法设计与分析

Design and Analysis of Algorithms

学习面对实际问题如何设计算法与分析算法。 课程概述 课程教学目标 针对实际问题需求,进行数学建模并选择高效求解…

北京大学

分享

算法设计与分析
  • 分类: 计算机
  • 平台: Coursera
  • 语言: 中文

学习面对实际问题如何设计算法与分析算法。

课程概述

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

课程内容安排
本课程的内容分成两大部分:算法的基础知识、通用算法设计技术与分析方法。

第一部分是算法基础知识,约占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

授课形式

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

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

声明:MOOC中国收录之课程均源自下列机构,版权均归他们所有。本站仅作报道并尊重其著作权益,感谢他们对MOOC事业做出的贡献!(排名不分先后)
  • Coursera
  • edX
  • OpenLearning
  • FutureLearn
  • iversity
  • Udacity
  • NovoEd
  • Canvas
  • Open2Study
  • Google
  • ewant
  • FUN
  • IOC-Athlete-MOOC
  • World-Science-U
  • Codecademy
  • CourseSites
  • opencourseworld
  • ShareCourse
  • gacco
  • MiriadaX
  • JANUX
  • openhpi
  • Stanford-Open-Edx
  • 网易云课堂
  • 中国大学MOOC
  • 学堂在线
  • 顶你学堂
  • 华文慕课
  • 好大学在线CnMooc

Copyright © 2008-2015 MOOC.CN 慕课改变你,你改变世界