《算法导论课件第一讲算法概述》由会员分享，可在线阅读，更多相关《算法导论课件第一讲算法概述（49页珍藏版）》请在金锄头文库上搜索。
1、Introduction to Algorithms 算法导论,李彬 山东轻工业学院 理学院,2,教材及参考书,Sara Baase and Allen Van Gelder, Computer AlgorithmsIntroduction to Design and Analysis (3rd Ed), Addison-Wesley, 2000 计算机算法：设计与分析导论，朱清新等编著，人民邮电出版社 2007,3,教材及参考书,Gelder, 乌迪 曼博（Udi Manber） 算法引论一种创造性方法，电子工业出版社，2009 算法导论，潘金贵（译），机械工业出版社，2006,4,教材及参
2、考书,计算机算法设计与分析，王晓东，电子工业出版社，2012,5,第一章 引论,算法的基本概念 算法的数学基础 集合论 逻辑学 概率论 求和与递归 快速估算法 算法的效率和复杂度,6,1.1 算法的基本概念,算法导论：进行算法的分析与设计（如何高效地进行转化）. 软件工程：使转化的过程更加规范化和易于管理.,输入,输出,7,可计算性,可计算性理论描述那些在算法上可解的问题的特征. 定义：我们说一个问题是算法上可解的，如果我们能够设计出一个计算机程序，对于该问题的任何一个输入都可以给出正确的答案. 在上述定义中我们假设所需要的计算资源（时间和存储空间）是充分大的. Enough storage
3、space Enough time,8,理论与现实可解性,下棋程序 棋盘的数学（西萨与舍罕王）,9,不可解问题,Alan Turing, On computable numbers, with an application to the Entscheidungs problem,（论可计算数及其在判定问题中的应用） Proceedings of the London Math. Society, Series 2, 42 (1936), pp 230-265. 在这篇划时代的论文中，图灵提出了图灵机的概念，给出了停机问题的定义并且证明了它是不可解问题.,10,Halting Problems
4、,Question: Does the following program stop for any n? While (n 1) If (odd(n) N = 3*n + 1 ; Else N = n / 2; End (while),11,Halting Problems,图灵停机问题的描述：不存在一个程序（或算法），它能够计算任何程序在给定输入上是否会结束（停机）. 停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题.如果这个问题可以在有限的时间之内解决，那么就可以有一个程序判断其本身是否会停机.但是，在程序停止之前，没有办法判断它会不会停止.所以这是一个不可解的问题.,1
5、2,阿兰图灵,Turing, Alan Mathison 1912年6月 23日生于英国伦敦, 1954年6月7日 卒于英国威姆斯洛(Wilmslow). 牛津大学安德鲁哈吉斯在谜一 样的图灵（Alan Turing: The Enigma）中做了这样的描述：“图灵似乎是上天派来的一个使者，匆匆而来，匆匆而去，为人间留下了深邃的思想，后人必须为之思索几十年或几百年甚至永远.”,13,历史注记,1900年罗素认识到数学是逻辑学的一部分。1910年罗素和他的老师阿尔弗雷德诺斯怀特海一起发表了三卷本的数学原理, 对这一概念做了系统阐述，创建了数理逻辑. 怀特海和罗素创建数理逻辑的原因主要是为了对付“
6、悖论”.他们认为“悖论”是由于人类语言的先天不精密造成的，而逻辑本身是天衣无缝的.他们坚信所有的数学成果都可以用逻辑推导出来.,14,希尔伯特纲领,1928年德国数学家大卫希尔伯特（DHillbert）提出著名的“希尔伯特纲领”，认为数学原理中所定义的系统既是一致的，也是完备的，换言之，一个系统的完备和一致性，可以由该系统本身得到证明. 1931年，“希尔伯特纲领”被奥地利逻辑学家库尔特哥德尔（Godel）捅出一个大窟窿，哥德尔认为没有一种公理系统可以导出数论中所有的真实命题，除非这种系统本身就有悖论。这就是著名的“哥德尔定理”.,15,哥德尔不完备性定理,哥德尔定理： 对每个丰富而可靠的数学
7、形式系统S.第一，在S中存在既不可证也不可否证，即不可判定的命题（第一不完全性定理）；第二，在S中不可证S的一致性（第二不完全性定理）. 哥德尔定理中最重要的是哥德尔第一不完备性定理.第二不完备性定理是第一定理的一个推论: “任何相容的形式体系不能用于证明它本身的相容性”. 哥德尔定理不仅推翻了“希尔伯特纲领”，还矛头直指数学原理，说它本身就是不一致的.,16,图灵机,为了验证数学系统的一致性，图灵提出一个设想：能否有这样一台机器，通过某种一般的机械步骤，能解决所有的数学命题.在论可计算数及其在判定问题中的应用这篇文章中图灵分析了计算的过程，给出了理论上可计算任何“可计算序列”某种0和1的序列
8、的“通用”计算机概念，并利用这一概念解决了希尔伯特提出的一个著名的判定问题这个问题涉及到逻辑的完备性，即是否所有的数学问题在逻辑上都是可解的. 图灵回答了这个问题: 有些数学问题是不可解的.,17,丘奇-图灵论点,1937年，图灵发表的另一篇文章“可计算性与可定义性” (Computability and-definability)则拓广了丘奇(A. Church)提出的“丘奇论点”，形成“丘奇-图灵论点”: 凡是可计算的函数都是一般递归函数（或都是图灵机可计算的，或都是演算可计算的，或都是波斯特系统可计算的）. 丘奇-图灵论点对计算理论的严格化，对理论计算机科学的形成和发展都具有奠基性的重要
9、意义,18,阿兰图灵,在42年的短暂生涯中，图灵在数理逻辑、量子力学、生物学、化学方面都有深入的研究，他在晚年还开创了一门新学科非线性力学.当然他最高的成就还是在计算机科学和人工智能方面，是这一领域开天辟地的大师.因此后来人们把计算机科学领域的最高奖以他的名字命名. 图灵的才气纵横大西洋，他脚跨剑桥和普林斯顿两校，上联罗素、怀特海、维特根斯坦、哥德尔，下接冯诺依曼、约翰麦卡锡、乔布斯、比尔盖茨，在数理逻辑和计算机科学之间搭一起一座不朽的桥梁.,19,图灵奖,图灵奖是美国计算机协会（ACM）于1966年所设立，是计算机科学领域的最高奖项. 图灵奖对获奖者的要求极高，评奖程序极严，一般每年只奖励一
10、名计算机科学家，极少有一名以上的在同一方向上做出贡献的科学家同时获奖. 每年，ACM将要求提名人推荐本年度的图灵奖候选人，美国计算机协会组成评选委员会对被提名者进行严格的评审，并最终确定当年的获奖者.,20,“算法”一词的来历,“算法” 的中文名称出自周髀算经中的“演算法”，英文名称Algorithm 来自于9世纪波斯数学家al-Khwarizmi. “算法”原为“algorism”，意思是阿拉伯数字的运算法则，在18世纪演变为“algorithm”. 欧几里得发明的最小公倍数算法（辗转相除法）被认为是人类历史上第一个算法.第一个实现程序是Ada Byron于1842年为巴贝奇分析机编写的求解
11、伯努利方程的程序，因此 Ada 被认为是世界上第一位程序员，一种计算机语言也用她命名.,21,算法的定义,19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难，因为“well-defined procedure”缺少数学上精确的定义.直到20世纪英国科学家图灵提出了著名的图灵机模型，解决了算法定义的难题. 对算法的发展起到了重要作用.,22,定义 1：算法是以一步接一步的方式来详细地描述计算机如何将输入转化为所要求的输出的过程； 定义 2：算法是在计算机上执行的计算过程的具体描述.,什么是算法,23,正确性.对于任意的一组输入，包括合理的输入与不合理的输入，总能得到预期的输出； 具体
12、性.由一系列的具体步骤所组成，每一步都能够被计算机所理解和执行，而不是抽象和模糊的概念； 确定性.每个步骤都有确定的执行顺序，即上一步在哪里、下一步是什么，都必须明确，无二义性； 有限性.在任何情况下，算法都不能陷入无限循环中.,算法的性质,24,定义：可计算问题（或算法可解问题）是一个需要计算执行或实现的任务. 如果从不同角度来看，问题的定义可以采用不同的形式化方法. 例如，我们可以把问题看做一组输入和输出之间的匹配关系，以及为找出这种匹配关系所需要的计算代价. 从数学角度来看，可以把问题定义为一个数学函数.,问题的定义,25,定义域：所有可能的输入的集合， 值域：所有输出的集合. 问题：一
13、个映射关系，把定义域中的任意一个元素，也就是任意一个输入，映射到值域中的一个点，即对应的输出. 在用函数来定义问题时，我们把一个问题的输入集合中的元素，即输入变量所取的值称为函数的参数或实参，而输入集合（输入变量）本身则称为函数的形参.,数学函数,26,问题的抽象化,如果把数学函数的定义进一步抽象化，则可以把问题 Q 定义为两个集合 I 和 S 的乘积空间 I S 上的一个二元关系，即 Q I S. 其中集合 I 叫做问题实例（instance）的集合，由所有的输入值所组成；集合S叫做问题的解集，相当于输出的集合. 而抽象化的问题 Q 就是集合 I 与集合 S 的乘积空间的一个子集.,27,三
14、种类型,判定性问题：这类问题的输出是给出一个是与否的判断.例如连通性问题、回路问题、查找与排序问题以及字符串匹配等. 最优值或最优化问题：这类问题是在所有可能的解中求出最优解. 例如求函数的最大值、最短路径问题以及最小生成树问题等. 数值计算问题：这类问题是在一定的约束条件（如精度范围）下求近似解。例如解方程组和矩阵运算等.,28,算法与程序,程序是算法用某种程序设计语言的具体实现. 程序可以不满足算法的性质(4). 例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法. 操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现.该子程序得到输出结果
15、后便终止.,29,算法设计方法,分治法（Divide and Conquer） 贪心法（Greedy Method） 回溯法（Back Tracking） 分支限界法（Branch Band） 动态规划（Dynamic Programming）,30,问题求解(Problem Solving),理解问题,精确解或近似解 选择数据结构 算法设计策略,设计算法,31,解决一个问题的算法不是唯一的.算法分析的任务就是估计算法的时间与空间复杂度，分析和比较各种算法的优劣. 算法设计的任务有两个： 第一是设计容易理解、容易编程实现且容易调试的算法； 第二是使算法能够有效地使用计算机资源，减少计算机的工作
16、量，即节省时间、空间和计算机硬件资源. 这两个目标通常是相互冲突的.在针对具体问题设计算法时，我们必须作出适当的折衷，在高效率和易理解性之间取得平衡.,算法分析与设计目标,32,集合论 逻辑学 概率论 求和与递归 快速估算方法,1.2 算法的数学基础,33,集合是由互不相同的元素组成的一个整体.通常这些元素都是属于同一种类型的，具有某些共同的性质. 一个元素e是集合S的成员，用符号 表示，读作e在S中或e属于S.,集合,34,集合的表达方式,一个特定的集合可以用列举或描述的方法来给出.列举就是将集合里的元素排列在花括号中.比如：S1 = a, b, c.集合中的元素是没有先后顺序的. 对于那些有很多个或无限多个元素的集合，可以采取把集合中的元素所满足的条件写出来，例如： S2 = x | x is an integer power of 2读作“所有元素x都是整数的平方的集合”. 一个特殊的集合叫做空集，用表示, S3 =
