算法导论 清华

Introduction to Algorithms 算法导论算法导论 主讲人 庄连生主讲人 庄连生 S i 2009 USTCSpring 2009, USTC 教材信息教材信息 y 书名：《算法导论》(第2版) y 著者： Thomas H. Cormen, Charles E LeisersonCharles E. Leiserson, Ronald L. Rivest, Clifford SteinClifford Stein y 译者：潘金贵,顾铁成等 y 出版社：机械工业出版社 y 出版时间 2006年9月y 出版时间：2006年9月 y 定价：85元 “计算机算法的圣经” 教材信息教材信息 y 延伸教材： ¾ 《The Art of Computer Programming》, Donald E, Knuth，1974, Turing Prize “计算机程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 ¾ 《计算机算法设计与分析》（第3版），王晓东，电子工业出版社， 2007。定价：29.50元； 理论的荷马史诗” Bill Gates: “如果你认为你是 一名真正优秀的程序员 请 一个比较不错的精品课程！名真正优秀的程序员，请读Knuth的《计算机程序设 计艺术》，如果你能读懂整 套书的话 请给我发 份你 课程！ 套书的话，请给我发一份你 的简历。” 教学目标教学目标 教学内容 y Part 1 基础知识 ¾算法基础 ¾算法分析基础 排序和顺序统计学y Part 2 排序和顺序统计学 ¾归并排序、堆排序、快去排序 数排序 数排序 桶排序¾计数排序、基数排序、桶排序 y Part 3 数据结构 ¾红黑树、数据结构的扩张 y Part 4 算法设计策略 ¾分治法、动态规划法、贪心法、回溯法、分枝限界法 y Part 5 算法研究问题 ¾ NP完全问题，有关数论的算法，…… Other y 授课安排(90) ¾ 课堂讲解（60学时）：基本理论讲解、基本方法的介绍分析；课堂讲解 学时 基本 论讲解 基本方法的介绍分析； ¾ 上机实践（30学时）：6~8个经典算法的上机实验； y 考核形式 ¾ 期末考试(闭卷)：60% ¾ 课堂作业+上机作业：30% ¾ 出勤+课堂纪律：10% y 课程主页课程主页 ¾ http://staff.ustc.edu.cn/~lszhuang/alg.htm 电子资源 课程信息¾ 电子资源、课程信息 第一节 算法基础 ¾算法概念 ¾算法特征¾算法特征 ¾问题与问题实例 ¾正确算法与不正确算法 ¾可求解的问题¾可求解的问题 ¾作为一门技术的算法 ¾算法与程序区别 算法概念：什么是算法？ y 定义：算法就是一个定义良好的可计算过程，它取一个或者一 组值作为输入，并产生出一个或者一组值作为输出。即，算法 就是一系列的计算步骤，用来将输入数据转换成输出结果。 Computational algorithm Input Computational Procedure Output g < 31,41,59,26,12,58 > < 31,41,59,26,12,58 > “冒泡”排序是个计算过程 <31,41,26,12,58,59> <31,26,12,41,58,59> 计算过程 8 …… <12,26,31,41,58,59> 算法的概念：算法的特征 y 一个算法通常具有如下特征： ① 输入：一个算法具有零个或者多个取自指定集合的输入值； ② 输出：对算法的每一次输入，算法具有一个或多个与输入值 相联系的输出值； ③ 确定性：算法的每一个指令步骤都是明确的；③ 确定性：算法的每一个指令步骤都是明确的； ④ 有限性：对算法的每一次输入，算法都必须在有限步骤（即 有 时 ）内结束有限时间）内结束； ⑤ 正确性：对每一次输入，算法应产生出正确的输出值； ⑥ 通用性：算法的执行过程可应用于所有同类求解问题，而不 是仅适用于特殊的输入。是仅适用于特殊的输 。 算法概念: 问题及问题实例算法概念: 问题及问题实例 y Problem — 问题 规定了输入与输出之间的关系，可以用通用语言来描述； y Instance of a Problem — 问题实例 某一个问题的实例包含了求解该问题所需的输入；某 个问题的实例包含了求解该问题所需的输 ； y 比如：将一系列数按非降顺序进行排序（排序问题）将 系列 非降顺序进行排序（排序问题） 输入: 由n个数组成的一个序列 输出: 对输入系列的一个排列(重排） ，使得 1 2< , , , >na a aL ' ' ' 1 2< , , , >a a aL ' ' ' 1 2 na a a≤ ≤ ≤L y 排序问题的一个实例： 输出: 对输入系列的 个排列(重排） ，使得1 2, , , na a a 1 2 n 1010 Input: <31,41,59,26,41,58> —— Output: <26,31,41,41,58,59> 算法概念: 输入实例与问题规模算法概念 输入实例与问题规模 y 输入实例输 实例 问题的具体计算例子。 如 排序 题 3个输 实例如，排序问题的3个输入实例： ① 13,5,6,37,8,92,12 ② 43,5,23,76,25 ③ 53,67,32,42,22,33,4,39,56③ 53,67,32,42,22,33,4,39,56 y 问题规模 算法的输入实例大小。 如上面排序问题的3个输入实例的规模大小分别为7,5,9如上面排序问题的3个输 实例的规模大小分别为7,5,9 算法概念：正确算法与不正确算法算法概念 正确算法与不正确算法 y 正确的算法 如果一个算法对问题每一个输入实例，都能输出正确的结果并停止，则称 它为正确的它为正确的。 y 不正确的算法y 不正确的算法 ¾可能根本不会停止； ¾停止时给出的不是预期的结果； ¾如果算法的错误率可以控制，也是有用的。 算法概念：可求解的问题 y 排序是计算机科学中的一种基本操作。 y 算法可以解决的问题 ¾人类基因项目 ¾在互联网中的应用（路由 搜索等）¾在互联网中的应用（路由、搜索等）； ¾电子商务中的应用 ¾图像检索图像检索 ¾隐私保护 ¾…… y 共同特点y 共同特点 ¾有很多候选的方案，其中大部分都不是我们所需要的。找到真正需要 的解决方案往往不是一件容易的事情；解 事 ¾有着实际的应用价值（如最短路径问题——运输公司） 作为一种技术的算法 y 如果计算机无限快、存储器都是免费的,算法研究是否还需要？ ① Yes！证明方案是正确的，可以给出正确结果。 ② Yes！希望自己的实现符合良好的软件工程实践要求，采用最容易的实 现方法。 y 算法对于当代计算机非常重要！类比硬件与软件的不同，算法的迥异带来 的意义可能更明显！ 比如 对100 个数字进 排序y 比如，对100万个数字进行排序： ‹ 插入排序: 21( )T n c n= ‹ 归并排序: 计算机B: 107 指令/s 2( ) lgT n c n n= „ 计算机A: 109 指令/s „ 世界最好的程序员 机器语言 „ 计算机B: 107 指令/s „ 普通程序员 „ 高级语言+低效编译器 „ 机器语言 2( ) 2T n n= ( ) 50 lgT n n n= 7 750 10 lg10 instruc7 2 5 9 2 (10 ) instruc 2 10 s 55.56h 10 instruc/s t ⋅= = × ≈ 7 50 10 lg10 instruc 19.38m 10 instruc/s t ⋅= ≈ 算法与程序区别算法与程序区别 y 算法的概念和程序十分相似，但实际上有很大不同。程序并不 都满足算法所要求的上述特征，如有限性特征。算法代 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 了对 特定问题的求解 而程序则是算法在计算机上的实现 因此特定问题的求解，而程序则是算法在计算机上的实现。因此， 算法也常常称为是一个能行过程。一个函数如果可以用一个算 法来计算，那么我们称该函数是能行可计算的。 y 如操作系统是 种程序 而不是算法y 如操作系统是一种程序，而不是算法。 Q & A Thanks!