算法设计与分析基础知识

《算法设计与分析基础知识》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、主讲：李淑琴Lishuqin2005@bistu.edu.cn2013.9课程简介（课程设置意义）DonaldE.knuth（1974年获图灵奖）：计算机科学就是算法的研究算法是计算机科学的核心，在众多的计算机应用领域也充满了各种算法算法是程序设计的精髓，程序设计的实质就是构造解决问题的算法，将其解释为计算机语言掌握算法分析的基本方法与算法设计的基本策略是一个软件工作者的必备条件本课程是计算机科学与技术专业的专业必修课课程简介（课程设置意义）李开复谷歌公司担任全球副总裁兼大中华区总裁、微软公司全球副总裁。李博士于1998

2、创办微软中国研究院写篇文章“算法的力量”算法是计算机科学领域最重要的基石之一编程语言虽然该学，但是学习计算机算法和理论更重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法和理论既能用科学家的严谨思维来求证，也能用工程师的务实手段来解决问题——而这种思维和手段的最佳演绎就是“算法”。有人也许会说：“今天计算机这么快，算法还重要吗?”其实永远不会有太快的计算机，因为我们总会想出新的应用。虽然在摩尔定律的作用下，计算机的计算能力每年都在飞快增长，价格也在不断下降。可我们不要忘记，需要处理的信息量更是呈指数级的增

3、长。现在每人每天都会创造出大量数据（照片，视频，语音，文本等等）。日益先进的记录和存储手段使我们每个人的信息量都在爆炸式的增长。互联网的信息流量和日志容量也在飞快增长。每天Google的网站要处理十亿个以上的搜索，GMail要储存几千万用户的2G邮箱，GoogleEarth要让数十万用户同时在整个地球上遨游，并将合适的图片经过互联网提交给每个用户。如果没有好的算法，这些应用都无法成为现实。课程简介（课程目的）本课程主要介绍计算机科学领域及其应用领域有代表性算法设计方法，同时介绍算法分析的基础知识，旨在培养学生分析问题和解

4、决问题的能力。通过本课程的学习，使学生掌握算法设计的基本方法，熟悉算法分析的基本技术，并能熟练运用一些常用算法解决实际问题，为学生进一步学习奠定良好的基础。教材与参考书教材自编教材“算法设计与分析”吴敏华参考书算法设计技巧与分析[沙特]M.H.Alsuwaiyel著吴伟昶方世昌等译电子工业出版社算法设计与分析郑宗汉郑晓明清华大学出版社计算机算法基础余祥宣等华中理工大学出版社计算机算法：设计与分析引论[美]S.巴斯著朱洪等译复旦大学出版社算法分析与设计王晓东清华大学出版社课时安排授课：54学时，1-18周，周一下午（6-8

5、节）成绩评定：课堂参与（10分）、作业（30分）、考试成绩（60分）考试方式：闭卷,笔试考试、课时安排主要内容介绍第1章算法设计与分析基础第2章递归与分治策略第3章动态规划第4章贪心算法第5章回溯法第6章分支限界法第7章随机化算法NP-完全问题图的遍历第1章算法设计与分析基础学习要点:理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握算法分析常用数学方法1.1引言——算法的定义和特征算法是指解决问题的一种方法或一个过程。算法是由若干指令组成的有穷序列，

6、满足性质：10算法五个重要特征：确切性:算法的每一步骤必须有确切的定义；输入：零个或多个外部量作为输入，所谓0个输入是指算法本身给定了初始值；输出：至少产生一个量作为输出。以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；可行性：算法中有待实现的运算都是基本运算。算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。有穷性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。3000年也行算法与程序程序与算法的不同：（1）程序是算法用某种程序设计语言的具体实现。（2）程序可以不满足算法的有

7、限性。----性质5算法与程序例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。问题求解(ProblemSolving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法例：旅行商问题设一个商人一天之内要到五个城市去推销货物。已知一个城市到其它城市的花费，希望从某个城市出发，走遍其它4个城市，找到花费最小的路线。已知：5个城市的道路通畅情况和相应的花费了解：

8、出发城市，一天是否能走遍5个城市是否考虑货物推销的花费每个城市是否只能到达一次最后是否回到出发城市城市之间是否有优先到达的关系求解：依次通过5个城市的顺序，要求花费之和最小模型的选择：无向图----用5个点表示5个城市，用边表示5个城市之间的道路，用数组表示花费矩阵。算法设计：假设有n个城市对n个城市从1到n编号，出