算法设计与分析01

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

1、算法设计与分析陈崚lchen@yzcn.net扬州大学信息工程学院计算机系1CourseOutline课程性质：专业选修课先修课程：《数据结构》《离散数学》《程序设计》总学分：3考核方式①考试类型：闭卷②课程成绩：平时成绩(30%)+期未成绩(70%)2References1.ThomasH.Cormen，etc.《IntroductiontoAlgorithms,Secondedition》.MITPress,2001.32.A.V.Aho,J.E.Hopcroft,J.D.Ullman.《Thedesignand

2、analysisofcomputeralgorithms》3第一章引论Whatarealgorithms?Whyisthestudyofalgorithmsworthwhile?Whatistheroleofalgorithmsrelativetoothertechnologiesusedincomputers?41.1计算机科学的研究对象及基本问题51.早期关于“计算机科学”的争论最早的计算机科学学位课程是由美国普渡大学于1962年开设的。随后，斯坦福大学也开设了同样的学位课程。但针对“计算机科学”这一名称，在当时

3、引起了激烈的争论。毕竟，当时的计算机主要用于数值计算，因此，大多数科学家认为使用计算机仅仅是编程问题，不需要做任何深刻的科学思考，没有必要设立学位。另外，很多人还认为，计算机从本质上说是一种职业而非学科。620世纪70～80年代，计算技术得到迅猛的发展，并开始渗透到大多数学科领域，但以往激烈的争辩仍在继续。计算机科学能否作为一门学科？计算机科学是理科还是工科？或者只是一门技术或一个计算商品的研制者和销售者？针对激烈的争论，1985年春，ACM和IEEE-CS联手组成攻关组，开始了对“计算机作为一门学科”的存在性证明。

4、经过4年的工作，ACM攻关组提交了《计算机作为一门学科》（ComputerasaDiscipline）的报告，完成了这一任务。7“科学”的含义：反映自然、社会、思维等的客观规律的学科的知识体系。“技术”的含义：人类在利用自然和改造自然的过程中积累起来并在生产劳动中体现出来的经验和知识。“工程”的含义：土木建筑或其它生产制造部门用比较大而复杂的设备来进行的工作。如：机械工程、土木工程、交通工程8作为科学，必须要有：严密的理论系统系统的分析与思维方法完整的知识体系92.计算机科学的定义及其基本问题计算机科学的定义计算机科

5、学的根本问题10计算机科学技术的定义计算机科学技术是研究计算机的设计与制造和利用计算机进行信息获取、表示、存储、处理、控制等的理论、原则方法和技术的学科。它包括科学和技术两个方面。科学则重现象与揭示规律。技术则侧重于研制计算机及使用计算机进行信息处理的方法和技术手段。11计算机科学的定义计算机科学对描述和变换信息的算法过程，包括对其理论、分析、设计、效率、实现和应用等进行的系统研究。12计算机科学的根本问题问题1：可计算性什么能被（有效地）自动进行？图灵可计算类原始递归函数丘奇-图灵论题λ-可定义函数计算机之父--图

6、灵13图灵可计算：根据图灵的研究直观地说，所谓计算就是计算者（人或机器）对一条两端可无限延长的纸带上的一串0或1执行指令，一步一步地改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。图灵用形式化方法成功地表达了计算这一过程的本质。图灵的研究成果是：可计算性＝图灵可计算性。解决：“计算机能干什么？”的问题14图灵机15问题2：计算复杂性怎么能被（有效地）自动进行？算法设计算法复杂性的分析16算法的复杂性相传印度教一座神庙神庙里竖有三根宝石柱子柱子由一个铜座支撑梵天将64个直径大小不一的金盘子

7、按照从大到小的顺序依次套放在第一根柱子上形成一座金塔如图所示.天神让庙里的僧侣们将第一根柱子上的64个盘子借助第二根柱子全部移到第三根柱子上既将整个塔迁移同时定下3条规则：1每次只能移动一个盘子2盘子只能在三根柱子上来回移动不能放在他处3在移动过程中三根柱子上的盘子必须始终保持大盘在下小盘在上17123完成Hanoi塔三个盘子时的解法ABC18梵天塔问题是一个典型的只有用递归方法而不能用其他方法来解决的问题。n个盘子的梵天塔问题需要移动的盘子数是n-1个盘子的梵天塔问题需要移动的盘子数的2倍加1,于是h(n)=2h(

8、n-1)+1=2(2h(n-2)+1)+1=22h(n-2)+2+1=23h(n-3)+22+2+1……=2nh(0)+2n-1+…+22+2+1=2n-1+…+22+2+1=2n-1因此要完成梵天塔的搬迁需要移动盘子的次数为264-1=18446744073709551615就这个例子可以了解到理论上可以计算的问题，实际上并不一定能行，称为实