计算机算法基础(第一章)2006.ppt

计算机算法基础主讲:周丽芳重庆邮电大学软件学院算法的研究内容问题是否可解1930’s研究集中于判断特定问题在计算机上是否可解,基本方法为:选定一个计算模型,观察是否能在该模型上创建能解决问题的算法。这些计算模型包括:Postmachines、Turingmachines等。这一阶段的成果是:大部分问题为不可解。高效率的解决方法随着计算机的发展和数据资源的增加,算法研究转向针对可解的问题,找到高效率的解决方法。算法的应用数据库中的检索搜索引擎中的爬找器和检索公共密钥加密和数字签名技术优化问题最短路径资源分配…章节安排《计算机算法基础》,余祥宣、崔国华、邹海明著,华中科技大学出版社第一章导引与基本数据结构 √第二章分治法√第三章贪心方法√第四章动态规划√第五章检索与周游√第六章回溯法√第七章分枝-限界√第八章NP-问题⊙预备知识数学:集合、证明方法(直接、间接、反证、反例、归纳假设)、对数基础、FLOOR&CEILING函数、阶乘、递归关系数据结构:链接表、图、树、?算法是解一确定类问题的任意一种特殊的方法。在计算机科学中,算法是使用计算机解一类问题的精确、有效方法的代名词:算法是一组有穷的规则,它规定了解决某一特定类型问题的一系列运算。、能行性、输入、输出、有穷性1)确定性:算法的每种运算必须要有确切的定义,不能有二义性。例:不符合确定性的运算5/0将6或7与x相加未赋值变量参与运算2)能行性算法中有待实现的运算都是基本的运算,原理上每种运算都能由人用纸和笔在有限的时间内完成。例:整数的算术运算是“能行”的实数的算术运算是“不能行”的3)输入每个算法有0个或多个输入。这些输入是在算法开始之前给出的量,取自于特定的对象集合——定义域(或值域)4)输出一个算法产生一个或多个输出,这些输出是同输入有某种特定关系的量。5)有穷性一个算法总是在执行了有穷步的运算之后终止。计算过程:只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。准确理解算法和计算过程的区别:不能终止的计算过程:操作系统算法是“可以终止的计算过程”算法的时效性:只能把在相当有穷步内终止的算法投入到计算机上运行