文档介绍：主讲:李淑琴
******@bistu.
课程简介(课程设置意义)
Donald (1974年获图灵奖) :计算机科学就是算法的研究
算法是计算机科学的核心,在众多的计算机应用领域也充满了各种算法
算法是程序设计的精髓,程序设计的实质就是构造解决问题的算法,将其解释为计算机语言
掌握算法分析的基本方法与算法设计的基本策略是一个软件工作者的必备条件
本课程是计算机科学与技术专业的专业必修课
课程简介(课程设置意义)
李开复谷歌公司担任全球副总裁兼大中华区总裁、微软公司全球副总裁。李博士于1998创办微软中国研究院
写篇文章“算法的力量”
算法是计算机科学领域最重要的基石之一
编程语言虽然该学,但是学****计算机算法和理论更重要,因为计算机语言和开发平台日新月异,但万变不离其宗的是那些算法和理论
既能用科学家的严谨思维来求证,也能用工程师的务实手段来解决问题——而这种思维和手段的最佳演绎就是“算法”。
有人也许会说:“今天计算机这么快,算法还重要吗?”其实永远不会有太快的计算机,因为我们总会想出新的应用。虽然在摩尔定律的作用下,计算机的计算能力每年都在飞快增长,价格也在不断下降。可我们不要忘记,需要处理的信息量更是呈指数级的增长。现在每人每天都会创造出大量数据(照片,视频,语音,文本等等)。日益先进的记录和存储手段使我们每个人的信息量都在爆炸式的增长。互联网的信息流量和日志容量也在飞快增长。
每天Google的网站要处理十亿个以上的搜索,GMail要储存几千万用户的2G邮箱,Google Earth要让数十万用户同时在整个地球上遨游,并将合适的图片经过互联网提交给每个用户。如果没有好的算法,这些应用都无法成为现实。
课程简介(课程目的)
本课程主要介绍计算机科学领域及其应用领域有代表性算法设计方法,同时介绍算法分析的基础知识,旨在培养学生分析问题和解决问题的能力。通过本课程的学****使学生掌握算法设计的基本方法,熟悉算法分析的基本技术,并能熟练运用一些常用算法解决实际问题,为学生进一步学****奠定良好的基础。
教材与参考书
教材
自编教材“算法设计与分析”吴敏华
参考书
算法设计技巧与分析[沙特]
算法设计与分析郑宗汉郑晓明清华大学出版社
计算机算法基础余祥宣等华中理工大学出版社
计算机算法:设计与分析引论[美]
算法分析与设计王晓东清华大学出版社
课时安排
授课:54学时,1-18周,周一下午(6-8节)
成绩评定:
课堂参与(10分)、作业(30分)、考试成绩(60分)
考试方式:
闭卷,笔试
考试、课时安排
主要内容介绍
第1章 算法设计与分析基础
第2章 递归与分治策略
第3章 动态规划
第4章 贪心算法
第5章 回溯法
第6章 分支限界法
第7章 随机化算法
NP-完全问题
图的遍历
第1章算法设计与分析基础
学****要点:
理解算法的概念。
理解什么是程序,程序与算法的区别和内在联系。
掌握算法的计算复杂性概念。
掌握算法渐近复杂性的数学表述。
掌握算法分析常用数学方法
引言——算法的定义和特征
算法是指解决问题的一种方法或一个过程。
算法是由若干指令组成的有穷序列,满足性质:
10