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

算法设计与分析韩建军 ******@. ********** 序?计算机算法是计算机科学和计算机应用的核心?数据结构+算法= 程序?算法:计算机软件的灵魂章节安排?第一章导引与基本数据结构√?第二章分治法√?第三章贪心方法√?第四章动态规划√?第五章检索与周游√?第六章回溯法⊙?第七章分枝-限界⊙?第八章 NP- 问题? 第一章导引与基本数据结构 算法的定义及特性 1. 什么是算法? 算法如数字、计算一样,是一个基本概念。算法是解一确定类问题的任意一种特殊的方法。在计算机科学中,算法是使用计算机解一类问题的精确、有效方法的代名词: 算法是一组有穷的规则,它规定了解决某一特定类型问题的一系列运算。 2. 算法的五个重要特性确定性、能行性、输入、输出、有穷性 1)确定性:算法的每种运算必须要有确切的定义,不能有二义性。例:不符合确定性的运算? 5/0 ?将6或7与x相加?未赋值变量参与运算 2)能行性算法中有待实现的运算都是基本的运算, 原理上每种运算都能由人用纸和笔在有限的时间内完成。例:整数的算术运算是“能行”的实数的算术运算是“不能行”的 3)输入每个算法有 0个或多个输入。这些输入是在算法开始之前给出的量,取自于特定的对象集合——定义域(或值域) 4)输出一个算法产生一个或多个输出,这些输出是同输入有某种特定关系的量。 5)有穷性一个算法总是在执行了有穷步的运算之后终止。计算过程:只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。?准确理解算法和计算过程的区别: ?不能终止的计算过程:操作系统?算法是“可以终止的计算过程”?算法的时效性:只能把在相当有穷步内终止的算法投入到计算机上运行 4. 我们的主要任务算法学****将涉及 5个方面的内容: 1)设计算法:创造性的活动 2)表示算法:思想的表示形式 3)确认算法:证明算法的正确性程序的证明 4)分析算法:算法时空特性分析 5)测试程序:“调试只能指出有错误,而不能指出它们不存在错误”本课程集中于学****算法的设计与分析。通过学****掌握计算机算法设计和分析基本策略与方法,为设计更复杂、更有效的算法奠定基础。 5. 课程关系数据结构程序设计语言:结构化设计数学基础非数值计算领域的基本知识