展开查看详情
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
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
热门城市
