第1章-算法引论-yz.pdf

算法设计与分析 The Design and Analysis of Algorithms 游珍 E-mail: youzhenjxnu@126.com 关于本课程  课程目的：计算机算法设计与分析导引 •不是一门程序设计语言课程 •也不是一门数学课程  课程目标 • 理解和掌握各种主要算法设计策略（方法）及其应用； • 培养对算法的计算复杂性的正确分析能力； • 掌握重要算法设计范例及分析方法 • 独立设计算法能力：针对一般实际问题设计并实现有效算法； • 独立分析算法的渐进效率。 领会并融合算法设计的思想  所学方法不能包治百病，需要自己创新、发挥；  算法设计由复杂简单，由不可解近似解；使得算法 设计由难变易,有章可循。  更高级，可计算性、计算复杂性(N Ｐ难问题) 3/44 为什么需要学习算法  学习需要 • 实践角度 •需要了解计算领域中不同问题的标准算法 • 理论角度 •算法学是计算机科学的基础  能力需要 • 学习算法的构造、分析 • 帮助提高理解、分析、解决问题的能力 为什么需要学习算法  李开复：  “算法是计算机科学领域最重要的基石之一，但却受到了国内一些程序 员的冷落。许多学生看到一些公司在招聘时要求的编程语言五花八门就 产生了一种误解，认为学计算机就是学各种编程语言，或者认为，学习 必威体育精装版的语言、技术、标准就是最好的铺路方法。其实大家都被这些公司 误导了。编程语言虽然该学，但是学习计算机算法和理论更重要，因为 计算机语言和开发平台日新月异，但万变不离其宗的是那些算法和理论 ，例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原 理等等。在 “开复学生网”上，有位同学生动地把这些基础课程比拟为 “内功”，把新的语言、技术、标准比拟为 “外功”。整天赶时髦的人 最后只懂得招式，没有功力，是不可能成为高手的”——摘自 “算法的 力量” 教材与参考资料  算法设计与分析 王晓东编著 清华大学出版社  算法设计技巧与分析 M. H. Alsuwaiyel [沙特]编 吴伟昶方世昌等译 电子工业出版社 6/44 算法设计与分析 上课：16周，其余：复习+机动  第一章 算法引论  第二章 递归与分治策略  第三章 动态规划  第四章 贪心算法  第五章 回溯法  第六章 分枝限界法  第七章 NP问题（了解） 7/44 第一章 算法引论  1．算法含义及相关背景  2 ．算法学习涉及的若干方面  3．算法分析的基本原则和框架  4. 算法复杂性分析 8/44 1. 算法含义及相关背景  1.1 算法起源与含义  1.2 算法的若干特性  1.3 算法的学科背景  1.4 算法与程序、规则、数据结构 9/44 1.1 算法的起源与含义  算法的起源 Algorism Algorithm algiros+arithmos 数学史学家发现,algorism一词 来源于 《Persian Text Book》 (波斯教科书)作