算法设计课件1.pdf

中国计算机学会 “21世纪大学本科计算机专业系列教材” 算法设计与分析 王晓东 编著 主讲教师：肖文 xw@ 办公地点：计算机楼312 1 关于本课程 无论是计算科学还是计算实践，算法都在其中扮演着重要角 色。翻开重要的计算机学术刊物，算法都占有一席之地，没有 算法，计算机程序将不复存在。 通过解决计算机中的经典问题，介绍算法设计的主要方法 和算法的计算复杂性分析。 学好本课程，可以提高分析问题、解决问题的能力。 授课形式：上课+课堂作业+期末考试 参考资料： 3 ID: xw PW: 123456 Web资源 , , … 图书资源 , … 2 龙应台写给儿子安德烈的一段话 孩子，我要求你读书用功，不是因为我要你跟别人 比成绩，而是因为，我希望你将来会拥有选择的权利， 选择有意义、有时间的工作，而不是被迫谋生。 当你的工作在你心中有意义，你就有成就感。当你 的工作给你时间，不剥夺你的生活，你就有尊严。成就 感和尊严，给你快乐。 3 主要内容介绍 • 第1章 算法概述 • 第2章 递归与分治策略 • 第3章 动态规划 • 第4章 贪心算法 • 第5章 回溯法 • 第6章 分支限界法 4 主要内容介绍（续） • 第7章 随机化算法 • 第8章 线性规划与网络流 • 第9章 NP完全性理论与近似算法 5 第1章 算法概述 学习要点: • 理解算法的基本概念。 • 掌握算法的复杂性分析。 • 掌握用C++语言描述算法的方法。 本章主要知识点: •1.1算法与程序 •1.2算法的描述方法 •1.3算法复杂性分析 6 1.1 算法与程序 算法：通俗地讲，是解决问题的方法或过程。 严格地讲，是满足下述性质的指令序列。 •输 入：有零个或多个外部量作为算法的输入。 •输 出：算法产生至少一个量作为输出。 •确定性：组成算法的每条指令清晰、无歧义。 •有限性：算法中每条指令的执行次数有限，执行 每条指令的时间也有限。 程序：是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)即有限性。 7 1.2 算法的描述方法 ⑴自然语言 ⑵流程图 ⑶程序设计语言 ⑷伪代码——算法语言 8 例：欧几里德算法——辗转相除法求两 个自然数 m 和 n 的最大公约数 m 欧几里德算法 r n