第1章算法引论

1

算法设计与分析王卫红wangwhs@163.com2015.09课程概述一、算法分析与设计介绍二、学习目标三、参考教材四、课程特点和学习的注意事项五、主要内容六、考核方式一、算法分析与设计介绍算法即演算法，出自《周髀算经》，英文名称Algorithm,算法是计算机科学的核心主题之一。“算法”原为"algorism"，意思是阿拉伯数字的运算法则，在18世纪演变为"algorithm"。欧几里得算法被人们认为是史上第一个算法。第一次编写程序是AdaByron于1842年为巴贝奇分析机编写求解伯努利方程的程序。20世纪的英国数学家图灵提出了著名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题一、算法分析与设计介绍（续）计算机算法指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。算法代表着用系统的方法描述解决问题的策略机制，即：能够对一定规范的输入，在有限时间内获得所要求的输出。开发高效软件的前提和基础。算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。一、算法分析与设计介绍（续）形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括：库尔特•哥德尔、JacquesHerbrand和斯蒂芬•科尔•克莱尼分别于1930年、1934年和1935年提出的递归函数阿隆佐•邱奇于1936年提出的λ演算1936年EmilLeonPost的Formulation1艾伦•图灵1937年提出的图灵机。一、算法分析与设计介绍（续）算法分析与设计是计算机科学与技术类（计算机应用、软件）研究生的一门重要专业学位课程。“算法设计与分析”很有用算法是计算机科学的核心主题之一。从就业来看，算法基础是许多名企面试必考的内容。从科学研究来看，算法设计与分析是计算机科学诸多领域研究中必须的技能。“算法设计与分析”很有趣算法给了我们一个看待世界和看待生活的新方式，从中学到的不仅是让计算机做事情的方式，还有“递归”、“分治”“优化”、“剪枝”等等一系列可能改变生活的思维方法。一、算法分析与设计介绍（续）课程名称算法分析与设计课程学时/学分讲授：51/3开课时间：周五3-5开课地点：C512学习方法：理论+实践二、学习目标通过对算法分析与设计课程的学习：研究,理解和掌握算法设计的主要方法培养学生对算法的计算复杂性进行正确分析的能力为独立设计算法和对给定算法进行复杂性分析奠定坚实的理论基础。三、参考教材算法设计与分析，王晓东，清华大学出版社算法设计与分析，张德富，国防工业出版社，2009-8-1。IntroductiontoAlgorithms,SecondEdition,

ThomasH.Cormen

《算法导论》，译者:潘金贵。算法设计与分析基础，(美)莱维丁，清华大学出版社。《算法分析与设计》，古德里奇、塔玛西亚编著，人民邮电出版社算法设计技巧与分析，M.H.Alsuwaiyel，电子工业出版社，2010-10-1。四、课程特点和学习的注意事项课程特点是一门重视能力的课程，理论+实践学习算法设计与分析既需要像数学课一样的证明、又需要像程序设计语言一样的写码，因而需格外的努力才可学得好。需具备数据结构、离散数学的基础，以及C\C++、Java等语言编程能力，熟悉MATLAB等仿真工具。注意事项：勤于思考、积极动手实践。善于应理论联系实际问题，在提高本领域知识的能力的同时，提高独立解决问题的能力。通过进一步阅读相关英文文献资料，巩固了学习成果、拓宽了思路，了解领域前沿。11五、主要内容介绍算法设计与分析领域的经典内容，并介绍了算法设计的发展趋势。内容主要包括非常经典的算法设计技术，例如递归与分治、动态规划、贪心、回溯、分支限界、图算法，也包括了一些高级的算法设计主题，例如网络流和匹配、启发式搜索、线性规划等。基础篇第1章 算法引论第2章 递归与分治策略第3章 动态规划12五、主要内容介绍（续）第4章 贪心算法第5章 回溯法第6章 分支限界法第7章 概率算法*第8章 NP完全性理论*第9章 近似算法*第10章 算法优化策略*13五、主要内容介绍（续）提高篇蚁群算法遗传算法……常用工具：C\C++、Java等开发工具MATLABSPSS……六、考核与成绩评定（**）学生出勤：10%课堂表现：10%作业完成：10%实验、实训：10%期末成绩：60%

课程论文……15第1章算法引论1.1 算法与程序1.2从问题到程序1.3 表达算法的抽象机制1.4 描述算法1.5 算法复杂性分析本章主要知识点：161.1 算法与程序算法（algorithms）的研究是计算机科学的核心课题之一。算法是解决某一特定类型问题的有限运算序列。从数据表示的观点来看，算法是指对数据结构施加的一些操作，例如对一个线性表进行检索、插入、删除等操作。17输入：有零个或多个外部量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。可行性：算法中要执行的每一个计算步骤都是可以在有限时间内做完的。可行性、有穷性和确定性是相容的。是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)即有限性。

是满足下述性质的指令序列。算法：程序：181.2从问题到程序要用计算机解决问题，必须首先用简明、严格的方式将问题表述清楚，所以算法形式的最初解法－建立数学模型，可以依据这一模型求解。

19算法设计和分析的步骤可概括:

（1）问题的陈述。（2）模型的选择。（3）算法的设计。（4）算法的程序实现。（5）算法分析。

201.从机器语言到高级语言的抽象1.3 表达算法的抽象机制高级程序设计语言的主要好处是：（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；212.抽象数据类型1.3 表达算法的抽象机制

抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。

抽象数据类型带给算法设计的好处有：

（1）算法顶层设计与底层实现分离；（2）算法设计与数据结构设计隔开，允许数据结构自由选择；（3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；（4）用抽象数据类型表述的算法具有很好的可维护性；（5）算法自然呈现模块化；（6）为自顶向下逐步求精和模块化提供有效途径和工具；（7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。

22采用Java语言、类C语言等描述算法。1.Java程序结构

1.4 描述算法例如，Java语言的若干重要特性如下。

（1）Java程序的两种类型：应用程序和applet 区别：应用程序的主方法为main，其可在命令行中用命令 语句java应用程序名来执行；

applet的主方法为init，其必须嵌入HTML文件，由

Web浏览器或applet阅读器来执行。（2）包：java程序和类可以包(packages)的形式组织管理。

（3）import语句：在java程序中可用import语句加载所需的包。 例如，importjava.io.*;语句加载java.io包。

231.4 描述算法2.Java数据类型数据类型

基本数据类型：详见下页表1-1

非基本数据类型：如

Byte,Integer,Boolean,String等。

Java对两种数据类型的不同处理方式：

对基本数据类型：在声明一个具有基本数据类型的变量时，自 动建立该数据类型的对象（或称实例）。如:intk;对非基本数据类型：语句Strings;并不建立具有数据类型 String的对象，而是建立一个类型String的引用对象， 数据类型为String的对象可用下面的new语句建立。s=newString(“Welcome”);Strings=newString(“Welcome”);241.4 描述算法3.方法在Java中，执行特定任务的函数或过程统称为方法(methods)。例如，java的Math类给出的常见数学计算的方法如下表所示：方法功能方法功能abs(x)x的绝对值max(x,y)x和y中较大者ceil(x)不小于x的最小整数min(x,y)x和y中较小者cos(x)x的余弦pow(x,y)xyexp(x)exsin(x)x的正弦floor(x)不大于x的最大整数sqrt(x)x的平方根log(x)x的自然对数tan(x)x的正切251.4 描述算法3.方法

计算表达式 值的自定义方法ab描述如下：

publicstaticint

ab(inta,intb){return(a+b+Math.abs(a-b))/2;}

（1）方法参数：Java中所有方法的参数均为值参数。上述方法ab中，a和b 是形式参数，在调用方法时通过实际参数赋值。

（2）方法重载：Java允许方法重载，即允许定义有不同签名的同名方法。 上述方法ab可重载为：

publicstaticdoubleab(doublea,doubleb){return(a+b+Math.abs(a-b))/2.0;}

261.4 描述算法4.通用方法

下面的方法swap用于交换一维整型数组a的位置i和位置j处的值。

publicstaticvoidswap(int[]a,inti,intj){

inttemp=a[i];

a[i]=a[j];

a[j]=temp;}

publicstaticvoidswap(object[]a,inti,intj){objecttemp=a[i];

a[i]=a[j];

a[j]=temp;}

该方法只适用于整型数组该方法具有通用性，适用于Object类型及其所有子类以上方法修改如下：271.5 算法复杂性分析

算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有：T=T(N,I)和S=S(N,I)

。 （通常，让A隐含在复杂性函数名当中）

281.5 算法复杂性分析算法复杂性在渐近意义下的阶：渐近意义下的记号：O、Ω、θ、o

设f(N)和g(N)是定义在正数集上的正函数。

O的定义：如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N))。即f(N)的阶不高于g(N)的阶。291.5 算法复杂性分析Ω的定义：如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界，记为f(N)=Ω(g(N))。即f(N)的阶不低于g(N)的阶。θ的定义：定义f(N)=θ(g(N))当且仅当f(N)=O(g(N))且f(N)=Ω(g(N))。此时称f(N)与g(N)同阶。30小结掌握算法的特性学会算法描述的基本方法能够对算法复杂度进行有效分析讨论及作业31附：C中的标准数据类型整型数的几种类型

数据类型字长（字）范围说明signedshortint

2-32768~32767有符号短整型数，简写为short或int

signedlongint

4-2147483648~2147483647有符号长整型数，简写为longunsignedshortint

20~65535无符号短整型数，简写为unsignedint

unsignedlongint

40~4294967295无符号长整型数，简写为unsignedlong32附：C中的标准数据类型

2.浮点型（float）

数据类型字长（字）数值范围说明float43.410-38E~3.410+38E单浮点数double81.710-308E~1.710+308E双浮点数33附：C中的标准数据类型

3.字符型（char）字符在计算机中以其ASCII码方式表示，其长度为1个字节，有符号字符型数取值范围为-128~127，无符号字符型数取值范围为0~255。34附：C中的标准数据类型指针型（*）根据所指的变量类型不同，可以是整型指针（int*）、浮点型指针（float*）、字符型指针（char*）、结构指针（struct*）和联合指针（union*）35附：C中的标准数据类型

5.无值型（void）无值型字节长度为0，主要有两个用途：一是明确地表示一个函数不返回任何值；一是产生一个同一类型指针（可根据需要动态分配给其内存）36附：C中的运算符

1.算术运算符2.关系运算符操作符作用+加，一目取正-减，一目取负*乘/除++自增--自减%取模（求余）操作符作用>大于<小于>=大于等于<=小于等于==等于!=不等于37附：C中的运算符

3.逻辑运算符4.按位运算符操作符作用&&逻辑与||逻辑或!逻辑非操作符作用&位逻辑与|位逻辑或^位逻辑异或-位逻辑反<<左移>>右移38附：C中的运算符

5.C的特殊运算符

1）“?:”运算符

2）“*”和“&”运算符

3）“,”运算符

4）sizeof运算符

5）联合操作6.优先级39附：C中的语句简介1.算法形式函数类型函数名（函数参数表）{//算法说明语句序列

}//函数名2.语句

1）赋值语句

2）条