计算机算法基础.ppt

2018/4/27
计算机算法基础
华中科技大学计算机学院
韩建军
******@.
2018/4/27
序
专业基础课程:
数据结构、计算机语言
操作系统、编译
如何编写计算机程序:
数据结构+算法= 程序
算法:计算机软件的“灵魂”
算法是计算机科学和计算机应用的核心
2018/4/27
教材:
计算机算法基础余祥宣等编著华中科技大学出版社
参考书:
算法设计与分析王晓东编著清华大学出版社
计算机算法导引——设计与分析卢开澄编著清华大学出版社
Introduction To Algorithm 高教出版社,MIT Press

学时:36+4学时
2018/4/27
章节安排
第一章导引与基本数据结构√
第二章分治法√
第三章贪心方法√
第四章动态规划√
第五章检索与周游√
第六章回溯法⊙
第七章分枝-限界⊙
第八章 NP-问题?
2018/4/27
第一章导引与基本数据结构
算法的定义及特性
1. 什么是算法?
★算法如数字、计算一样,是一个基本概念。
★算法是解一确定类问题的任意一种特殊的方法。
★在计算机科学中,算法是使用计算机解一类问题的精确、有效方法的代名词;
算法是一组有穷的规则,它规定了解决某一特定类型
问题的一系列运算。
2018/4/27
2. 算法的五个重要特性
确定性、能行性、输入、输出、有穷性
1)确定性:算法的每种运算必须要有确切的定义,不能有二义性。
例:不符合确定性的运算
5/0
将6或7与x相加
未赋值变量参与运算
2018/4/27
2)能行性
算法中有待实现的运算都是基本的运算,原理上每种运算都能由人用纸和笔在“有限”的时间内完成。
例:整数的算术运算是“能行”的
实数的算术运算是“不能行”的
2018/4/27
3)输入
每个算法有0个或多个输入。这些输入是在算法开始之前给出的量,取自于特定的对象集合——定义域(或值域)
4)输出
一个算法产生一个或多个输出,这些输出是同输入有某种特定关系的量。
2018/4/27
5)有穷性
一个算法总是在执行了有穷步的运算之后终止。
计算过程:只满足确定性、能行性、输入、输出四个特性的一组规则。

算法和计算过程的区别:
计算过程:操作系统(不终止的运行过程)
算法是“可以终止的计算过程”
算法的时效性:只能把在相当有穷步内终止的算法投
入到计算机上运行
2018/4/27
4. 我们的主要任务
算法学习将涉及5个方面的内容:
1)设计算法:创造性的活动
2)表示算法:思想的表示形式,SPARKS语言
3)确认算法:证明算法对所有可能的合法输入都能得出正确的答案。
算法证明:证明算法的正确性,与语言无关
程序证明:证明程序的正确性
4)分析算法:对算法的时、空特性做定量分析,以了解算法的好坏
5)测试程序:
调试:“调试只能指出有错误,而不能指出它们不存在错误”
作时空分布图:验证分析结论,优化算法设计
本课程集中于学习算法的设计与分析。通过学习,掌握计算机算法设计和分析基本策略与方法,为设计更复杂、更有效的算法奠定基础