教学计划
1 导引和基本数据结构 2 分治法 4学时 3 贪心方法 4学时 4 动态规划 4学时 5 基本检索与周游方法 6 回溯法 4学时 7 分枝界限法 4学时 2学时
4学时
第 1章
绪论
算法理论的两大论题：
1. 算法设计
2. 算法分析
1.1 算法
1. 为什么要学习算法
2. 算法及其重要特性
3. 算法的描述方法
⑸ 可行性（Effectiveness） ：算法描述的操作可以通过已 经实现的基本操作执行有限次来实现。
好算法的特征
（1） 正确 算法必须满足问题的要求，即对合 法的输入能产生求解问题的正确结果；对不合 法的输入能作出相适应的反映并进行处理。 （2） 可读 能交流，它有助于人们对算法的 理解、调试和修改。 （3） 运行时间短。 （4） 占用内存尽量少。
4. 算法设计的一般过程
5. 重要的问题类型
1. 为什么要学习算法
理由1：算法——程序的灵魂
问题的求解过程：
分析问题→设计算法→编写程序→整理结果
程序设计研究的四个层次：
算法→方法学→语言→工具
理由2：提高分析问题的能力
算法的形式化→思维的逻辑性、条理性
2. 算法及其重要特性
算法（Algorithm）：对特定问题求解
算法设计的原则
1．正确性——合理的数据输入下，在有限的运行 时间内得出正确的结果。 2. 可读性——供人们阅读的方便程度。 3．健壮性——对不合理的数据输入的反应和处理 能力。 4．简单性——采用数据结构和方法的简单程度。 5. 时间复杂度(计算复杂度)——算法运行时间的 相对量度。 6. 空间复杂度——算法运行中临时占用空间大小 的量度。
什么是算法（续）
•一个算法是对于任何的输入元素x，都在有穷步骤内 终止的一个计算方法。 •在算法的形式化定义中，对任何一个元素x∈I，x均 满足性质 x0=x，xk+1=F(xk)，（k≥0）
该性质表示任何一个输入元素x均为一个计算序列， 即x0，x1，x2，…，xk；该序列在第k步结束计算。
算法的五大特性：
步骤的一种描述，是指令的有限序列。
பைடு நூலகம்
什么是算法
早在公元前 300 年左右出现的著名的欧几里德算法， 就描述了求解两个整数的最大公因子的解题步骤。 要求解的问题描述为：“给定两个正整数m和n，求 它们的最大公因子，即能同时整除 m 和 n 的最大整 数”。欧几里德当时给出的算法如下： ⑴ 以n除m，并令所得余数为r（必有r<n）； ⑵ 若r=0，输出结果n，算法结束；否则继续步骤 ⑶； ⑶ 令m=n和n=r，返回步骤⑴继续进行。
学时
总学时32＝理论学时26＋实验学时6
在这一学期里，希望我们能共同努力， 学好这门功课！
教学目的
• 本课程是一门专业选修课，计算机科学是一种创 造性思维活动，其教育必须面向设计。计算机算 法设计与分析正是一门面向设计且处于计算机科 学核心地位的课程。该课程系统地介绍了计算机 算法的设计方法与分析技巧，对从事计算机软件 和计算机应用的研究者来说是非常重要和必不可 少的。通过本课程的学习： 1．系统的学习和研究计算机领域常见而有代表性的 算法； 2．理解并掌握算法设计的主要方法； 3．培养对算法复杂性进行分析的能力。 • 为独立地设计算法和对算法进行分析奠定坚实的 知识基础。
克努斯-莫里斯-普拉特算法
• Knuth-Morris-Pratt 字符串查找算法（常简称 为 “KMP算法”）是在一个“主文本字符串” S 内查找一个“词” W 的出现，通过观察发现， 在不匹配发生的时候这个词自身包含足够的信 息来确定下一个匹配将在哪里开始，以此避免 对以前匹配过的字符重新检查。 • 这个算法是由高德纳（Donald Ervin Knuth）和 沃恩· 普拉特在1977年合作发明的，同年詹姆 斯· H· 莫里斯也独立地设计出该算法，但是最 终由三人联合发表。
克努斯
1938年出生，25岁毕业于加州理工 学院数学系，博士毕业后留校任教， 28岁任副教授。30岁时，加盟斯坦 福大学计算机系，任教授。从31岁 起，开始出版他的历史性经典巨著： The Art of Computer Programming
他计划共写7卷，然而出版三卷之后， 已震惊世界，使他获得计算机科学 界的最高荣誉图灵奖，此时，他年 仅36岁。
什么是算法（续）
由此，我们可以得出这样的结论，算法就是求解问题 的方法和步骤。这里的方法和步骤是一组严格定义了 运算顺序的规则；每一个规则都是有效的，且是明确 的；按此顺序将在有限次数下终止。 有关算法（Algorithm）一词的定义不少，但其内涵 基本上是一致的。最为著名的定义是计算机科学家 D.E.Knuth 在其巨著《计算机程序的艺术》（ Art of Computer Program）第一卷中所做的有关描述。其非 形式化的定义是： 一个算法，就是一个有穷规则的集合，其中之规则 定义了一个解决某一特定类型问题的运算序列。
⑴ 输入（Input） ：一个算法有零个或多个输入。
⑵ 输出（Output） ：一个算法有一个或多个输出。
⑶ 有穷性（Finiteness） ：一个算法必须总是在执行有穷 步之后结束，且每一步都在有穷时间内完成。
⑷ 确定性（Definiteness） ：算法中的每一条指令必须有 确切的含义，对于相同的输入只能得到相同的输出。
武汉理工大学计算机学院
算法设计与分析
何九周
教材与参考书
• 教材： 《算法设计与分析》王红梅 编 清华大学出版社 • 参考书： 《算法设计与分析》王晓东编 清华大学出版社 《算法设计与分析习题解答》王晓东编 清华大学 出版社 • Algorithm Design Techniques and Analysis M.H. Alsuwaiyel(Saudi Arabia) 电子工业出版社
什么是算法（续）
算法的形式化定义如下所述： 算法是一个四元组，即（Q，I，Ω，F）。 其中：
– Q是一个包含子集I和Ω的集合，它表示计算的状态； – I表示计算的输入集合； – Ω表示计算的输出集合； – F表示计算的规则，它是由Q至它自身的函数，且具有自 反性，即对任何一个元素q∈ Q，有F(q)=q。