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

算法设计与分析

Design and Analysis puter Algorithm
有两种思想,,,而算法造就了现代世界.
——David Berlinski
算法的研究内容
问题是否可解
1930’s 研究集中于判断特定问题在计算机上是否可解,基本方法为:选定一个计算模型,观察是否能在该模型上创建能解决问题的算法。这些计算模型包括:Post machines、Turing machines等。这一阶段的成果是:大部分问题为不可解。
高效率的解决方法
随着计算机的发展和数据资源的增加,算法研究转向针对可解的问题,找到高效率的解决方法。
算法的应用
数据库中的检索
搜索引擎中的检索
公共密钥加密和数字签名技术
优化问题
最短路径
资源分配
…
章节安排
《计算机算法基础》,余祥宣、崔国华、邹海明著,华中科技大学出版社
第一章导引与基本数据结构√
第二章分治法√
第三章贪心方法√
第四章动态规划√
第五章检索与周游√
第六章回溯法√
第七章分枝-限界√
第八章 NP-问题⊙
第一章导引与基本数据结构
算法的定义及特性
什么是算法?
一系列将问题的输入转换为输出的计算或操作步骤。
2. 算法的五个重要特性
确定性、能行性、输入、输出、有穷性
1)确定性:算法的每种运算必须要有确切的定义,不能有二义性。
例:不符合确定性的运算
5/0
将6或7与x相加
未赋值变量参与运算
2)能行性
算法中有待实现的运算都是基本的运算,原理上每种运算都能由人用纸和笔在有限的时间内完成。
例:整数的算术运算是“能行”的
实数的算术运算是“不能行”的
3)输入
每个算法有0个或多个输入。这些输入是在算法开始之前给出的量,取自于特定的对象集合——定义域(或值域)
4)输出
一个算法产生一个或多个输出,这些输出是同输入有某种特定关系的量。