计算机算法设计与分析第1章算法概述

课程安排
理论课：1～10周，40学时 周二(5-6)、周五(1-2)
上机： 18学时
期末考试： 闭卷笔试，第 11周
上课点名三次不到者取消考试资格； 迟到或作业缺交，一次扣10分（平时成绩）。
教学目的和要求
本课程是计算机类专业的专业基础课程； 通过课程学习和上机实践，对计算机常用算
法有一个较全面的了解，掌握通用算法的一 般设计方法； 学会对算法的时间、空间复杂度分析，掌握 提高算法效率的方法和途径。
5)算法的程序实现 将算法正确地编写成机器语言程序.
6)算法分析 对执行该算法所消耗的计算机资源进行估算.
（三）如何设计算法
通过学习已被实践证明是有用的一些基本设 计策略，如递归、回溯等，掌握一般的算法 设计方法，学会设计高效的算法。
（四）如何确认算法（证明其正确性）
证明算法对所有可能的输入都能算出正确的 答案，这一工作称为算法确认。这一领域是 当前许多计算机工作者集中研究的对象，还 处于相当初期的阶段。
4、算法的一个c++程序语言实现
int Euclid（int m，int n） // 计算gcd（m，n） // 输入：非负整数m，n，其中m，n不同时为零 // 输出：m，n的最大公约数
{ int r=0;
if(m*n==0) return 0; // m，n不符合输入规范时返回0
数，称为模运算
2、算法的一个结构化的描述
计算gcd（m，n）的欧几里得算法： 第一步：如果n=0,返回m的值作为结果，同
时过程结束；否则，进入第二步。 第二步：用n去除m，将余数赋给r。 第三步：将n的值赋给m，将r的值赋给n，返
回第一步。
3、算法的一个伪代码描述
ALGORITHM Euclid（m，n） // 计算gcd（m，n） // 输入：非负整数m，n，其中m，n不同时为零 // 输出：m，n的最大公约数 while n ≠ 0 do r ← m mod n m ←n n ←r return m
什么是算法？
我们来编写一个烧开水的算法：
输入自来水 循环（反复）加热直到水开 输出开水
一、算法(Algorithm)
算法概念：通俗地讲，算法是指解决问题
的一种方法或一个过程。严格地讲，算法是 由若干条指令组成的有穷序列。
问题
输入
算法
“计算设备”输出 图1.1 算法的概念图
（一）算法的性质
1、算法具有某些特性，如下几条： (1)输入：有零个或多个外部提供的量作为算
二、算法的几种描述方式
1、计算两个整数的最大公约数问题的一个现 代数学术语表述 欧几里得算法基于的方法是重复应用下列 等式： gcd (m , n) = gcd (n , m mod n) ， 直到m mod n等于0。
gcd(60,24)=gcd(24,12)=gcd(12,0)=12 注：gcd (m , 0) =m，m mod n 表示m除以n之后的余
while (n > 0)
{ r = m mod n;
m = n;
n = r;
}
return m;
}
其他方法
程序流程图等，不再一一列举。
三、算法复杂性分析
算法复杂性是算法效率的度量，是评价算法优劣的 重要依据。
算法复杂性的高低体现在运行算法所需要的计算机 资源，即时间和空间（存储器）资源的多少上。
授课内容
第1章 算法概述 第2章 递归与分治策略 第3章 动态规划 第4章 贪心算法 第5章 回溯法 第6章 分支限界法 *7-9章属研究生学习内容，可自学了解。
第1章 算法概述
学习要点: • 一、理解算法的概念，以及问题求解的
过程。 • 二、掌握算法的几种描述方式。 • 三、理解算法的计算复杂性概念。 • 四、掌握算法渐近复杂性的数学表述。
（一）算法性质
2、关于算法有几个要点： (1) 算法所处理的输入的值域必须严格定义。 (2) 同样一种算法可以用几种不同的形式来描
述。
（一）算法性质
(3) 同一个问题可以存在多种解决的算法。 (4) 同一个问题的几种算法可能会基于完全不
同的解题思路，而且解题速度也会有显著不 同。
（二）问题求解过程
在学习本课程中，我们仅对算法的正确性进 行一般的非形式化讨论，以及对算法的程序 实现进行测试验证。
（五）如何分析（评价）算法
分析算法包括 定量的分析算法需要多少计算 时间和存储空间，分析算法不仅可以预计 算 法能否有效得完成任务，而且可以知道算法 在最坏、最好和平均情况下的运算时间，对 解决同一问题的不同算法的优劣作出比较。
算法的时间复杂性T(n)，空间复杂性S(n)。 其中n是问题的规模（输入大小）。
三、算法复杂性分析
本课程主要对算法的时间复杂性进行分析。 关于算法的复杂性，有两个问题要弄清楚： （1）用怎样的一个量（指标）来表达一个算法的
法的输入。 (2)输出：算法产生至少一个量作为输出。这
些输出是和输入有某种特定关系的量。
（一）算法的性质
(3)确定性：组成算法的每条指令是清晰，无 歧义的。
(4)有限性（有穷性）：算法中每条指令的执 行次数是有限的，执行每条指令的时间也是 有限的。
（一）算法的性质
(5)可实现性：此性质是指算法中有待实现的 运算都是相当基本的，每种运算至少在原理 上能由人用纸和笔在有限的时间内完成。 （补充）
1)问题的陈述 用科学规范的语言,对所求解的问题做准确的 描述.
2)建立数学模型 通过对问题的分析,找出其中的所有操作对象 及操作对象之间的关系并用数学语言加以描 述.
3)算法设计 根据数学模型设计问题的计算机求解算法.
（二）问题求解过程
4)算法的正确性证明 证明算法对一切合法输入均能在有限次计算 后产生正确输出.
学习算法的重要性
（一） 从理论和实践的角度理解 —计算机科学的基石；掌握标准算法
（二）从算法对于程序的重要性来讲 —皮之不存，毛将附焉？
（三） 数据结构课程
（一）数据结构关心的对象 各种数据结构的作用和效率、具体的问题
（二）算法设计与分析关心的对象 算法设计技术的适用性和效率、一般性方 法