01算法设计与分析---引言

本章主要为引言,其中包括算法的重要性;图灵奖获得者;算法的相关概念:有穷性,确定性,可行性,输入,输出;算法的正确性分析;算法好坏的衡量尺度:问题的规模,基本运算,算法的计算量函数;最坏情况时间复杂性:顺序查找,二分查找;平均情况时间复杂性:顺序查找,二分查找,等
展开查看详情

1.东南大学计算机学院 方效林 算法设计与分析

2.课程说明 课程编号: S009101 授课学时: 54 学时( 1 至 18 周, 3 学时 / 周) 课程分类:专业基础 考核形式: 期末 笔试 80 %+ 平时 成绩 20 % 作业: 从布置作业起,到下一次课前两天 ( 周六 23:00) 电子版,发送到 homeworkseu@163.com 文件命名 (04012501_ 肖迪 ) ,文件格式 (. pdf 、 .doc 、 . docx 、 .jpg) ,大小≤ 500K 联系方式 计算机 楼 21 2 电话 : 13951855973 Email: xiaolin@seu.edu.cn 2

3.教材与参考书 算法导论 (MIT 第 2/3 版 ). Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein. 算法设计 . Kleinberg J., Tardos E. 清华大学出版社 ( 张立昂等译 ) 计算机算法基础 . 沈孝钧 . 机械工业出版社 算法设计技巧与分析 . M. H. Alsuwaiyel . 电子工业出版社影印本 ( 方世昌等译 ) 3

4.东南大学计算机学院 方效林 引言

5.课程主要内容 在计算机应用中经常遇到的问题和求解的算法 设计算法基本原理、技巧以及算法复杂性分析 分治法 动态规划法 贪心法 随机算法 近似算法 计算理论简介 NP- 完全性 5

6.课程目的 具备抽象描述、解决实际问题的能力 学会运用算法设计与分析的典型方法进行算法的设计 具备分析算法效率的能力。 6

7.算法的重要性 有超过 1/3 的 Turing 奖 获奖者, 其成果与算法有关 图灵奖于 1966 年开始设立,是 ACM ( 美国计算机协会 ) 在计算机科学技术领域中所授予的最高奖项 7

8.图灵奖获得者 1972 , Edsger W.Dijkstra 求最短路径的 Dijkstra 算法 , PV 操作 , 解决了“哲学家聚餐” 问题 第一个 Algol 60 编译器 结构化程序设计 , “ goto 有害 ” 等 8

9.图灵奖获得者 1974 , Donald E.Knuth ( stanford ) 算法最早的奠基人之一 ( 计算机程序设计艺术 ) 现代 “ 算法 ” 与 “ 数据结构 ” 名词及内涵的提出, KMP 算法, LR(k) 文法, Tex 编辑器等 9

10.图灵奖获得者 1976 , Michael O.Rabin ( 以色列 )  Dana S.Scott ( 英 ) 师兄弟 ( 导师 A.Church ) 非确定有穷自动机的提出、判定问题等 Rabin :计算复杂性概念的雏形、随机算法的思想奠定、寻找及判定素数算法,单向函数等 Scott: 语义学等 。 10

11.图灵奖获得者 1978 , Robert W.Floyd ( 美 ) 求最短路径的 Floyd 算法, Heap-sort 算法等 编译及优化(优先文法等) 程序正确性证明等 11

12.图灵奖获得者 1980 , C. Anthony R.Hoare ( 英 ) 1983 年 ACM 评出的 1/4 世纪最有影响的 25 篇论文 中, Hoare 与 Dijkstra 有两篇入选 ( 其余人只有一篇 ) 算法的代表作: Quick-sort 算法, 程序设计 (CASE 、 While 语句等 ) ,数据通信 等 12

13.图灵奖获得者 1982 , Steven A.Cook ( 加 Toronto 大学 ) “NP- 完全 ” 概念的提出与理论的奠定,算法复杂性 13

14.图灵奖获得者 1984 , Niklaus Wirth ( 瑞士苏黎世高工 ) “ 程序 = 算法 + 数据结构 ” ,结构化程序设计创始人 “Pascal 之父 ”, 数据结构, Extended BNF 等 14

15.图灵奖获得者 1985 , Richard M.Karp (UC-Berkeley) : 分枝限界法的创始人(与 Held ), Rabin-Karp 子串匹配算法, 求网络最大流的 Edmonds-Karp 算法, NP- 完全理论( Karp 规约等),随机算法,并行算法等 15

16.图灵奖获得者 1993 , Juris Hartmanis (Cornell) & Richard E. Stearns (Albany) 计算复杂性理论的主要奠基人 Hartmanis : Hartmanis 矩阵乘法, Hartmanis 快速离散傅立叶变换 Stearns :首先提出将上下文无关文法理论应用于编译器设计等 16

17.图灵奖获得者 2000 , Andrew Yao( 姚期智 ) 唯一华裔图灵奖获得者 计算复杂性,量子计算,密码学 (e.g. 单向函数 ) 、通信理论 等 17

18.图灵奖获得者 2002 , Ronald L. Rivest , Adi Shamir , Leonard M. Adelman : 公共密钥算法 (RSA 算法是当前在互联网传输、银行以及信用卡产业中被广泛使用的安全基本机制 ) 18

19.算法的相关概念 是对特定问题求解步骤的一种描述,是指令的有限序列。 具有下列 5 个特性: 有穷性:算法有限步结束,指令有限时间完成 确定性:每条指令都是明确的、无二义的 可行性:每条指令都能够被执行 输入:有 0 个或多个输入量 输出:有 1 个或多个输出量 19

20.算法的正确性分析 一个算法是正确的,如果它对于每一个输入都最终停止,而且产生正确的输出 不正确算法 : 不停止(在某个输入上) 对所有输入都停止,但对某输入产生不正确结果 近似算法 对所有输入都停止 产生近似正确的解或产生不多的不正确解 调试程序  程序正确性证明 程序调试只能证明程序有错, 不能证明程序无错误 ! 20

21.算法好坏的衡量尺度 最初,用所需计算时间来衡量算法的好坏 但不同的机器相互之间无法比较 故需要用独立于具体计算机的客观衡量标准 问题的规模 基本运算 算法的计算量函数 21

22.算法好坏的衡量尺度 时间复杂度 基本运算(原子操作)执行次数 空间复杂度 需要的存储空间大小 22

23.算法好坏的衡量尺度 问题的规模 一个或多个整数,作为输入数据量的测度 数 组 的长度 ( 数据项的个数 ) 问题:在一个数 组 中寻找 X 矩阵的最大维数 ( 阶数 ) 问题:求两个实矩阵相乘的结果 输入规模通常用 n 来表示 也可有两个以上的参数,如图中的顶点数和边数 ( 图论中的问题 ) 23

24.算法好坏的衡量尺度 基本运算 解决给定问题时占支配地位的运算 在一个表中寻找数据元素 x x 与表中的一个项进行比较 两个实矩阵的乘法 实数的乘法 ( 及加法 )C=AB 则 c ij =∑a ik *b kj 将一个数 组 进行排序 数组 中的两个数据项进行比较 24

25.算法好坏的衡量尺度 基本运算 通常情况下,讨论一个算法优劣时,我们只讨论基本运算的执行次数 因为它是占支配地位的,而其它的运算可以忽略不计 25

26.算法好坏的衡量尺度 算法的计算量函数 用输入规模的某个函数来表示算法的基本运算量 该 函数称为算法的时间复杂性 ( 度 ) ,一般 用 T(n) 或 T(n,m) 等表示 T(n)=5n , T(n)=3n*logn , T(n)=4n 3 , T(n)=2 n , T(n,m)=2(n+m) 26

27.最坏情况时间复杂性 规模为 n 的所有输入中,基本运算执行次数 最多的 时间复杂性 在一个顺序表中寻找数据元素 x 顺序查找:最坏情况为 O(n) ; 二分查找:最坏情况为 O( logn ) 27

28.平均情况时间复杂性 规模为 n 的所有输入的算法时间复杂度的平均值(一般均假设每种输入情况以等概率出现) 在一个顺序表中寻找数据元素 x 顺序查找:平均情况仍为 O(n) ; 二分查找:平均情况仍为 O(logn) 28