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

计算机算法基础(第一章)22239*计算机算法基础*教材计算机算法基础(第二版)余祥宣等华中科技大学出版社参考书::王晓东,:(美)古德里奇,(美)塔玛西亚,霍红卫译人民邮电出版社课时安排:28+12考试形式:闭卷成绩:平时40%+考试60%*序计算机算法是计算机科学和计算机应用的核心数据结构+算法=程序算法(algorithm)是一个在有限时间内逐步执行某种任务的过程数据结构(datastructure)是一种系统组织和访问数据的方法算法:计算机软件的灵魂*问题求解(ProblemSolving)设计程序证明正确性分析算法理解问题精确解或近似解选择数据结构算法设计策略设计算法*章节安排第一章导引与基本数据结构 √第二章分治法 √第三章贪心方法 √第四章动态规划 √第五章检索与周游√第六章回溯法⊙第七章分枝-限界⊙第八章NP-问题?算法研讨环节*?算法如数字、计算一样,是一个基本概念。算法是解一类确定问题的任意一种特殊的方法。在计算机科学中,算法是使用计算机解一类问题的精确、有效方法的代名词:算法是一组有穷的规则,它规定了解决某一特定类型问题的一系列运算。*、能行性、输入、输出、有穷性1)确定性:算法的每种运算必须要有确切的定义,不能有二义性。例:不符合确定性的运算5/0将6或7与x相加未赋值变量参与运算*2)能行性算法中有待实现的运算都是基本的运算,原理上每种运算都能由人用纸和笔在有限的时间内完成。例:整数的算术运算是“能行”的实数(无理数)的算术运算是“不能行”的*3)输入每个算法有0个或多个输入。这些输入是在算法开始之前给出的量,取自于特定的对象集合——定义域(或值域)4)输出一个算法产生一个或多个输出,这些输出是同输入有某种特定关系的量。*5)有穷性一个算法总是在执行了有穷步的运算之后终止。计算过程:只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。准确理解算法和计算过程的区别:不能终止的计算过程:操作系统。算法是“可以终止的计算过程”。算法的时效性:只能把在相当有穷步内终止的算法投入到计算机上运行。