算法分析与设计第 1章

1、算法设计与分析Design and Analysis of Algorithms 任课教师：张小东联系方式：z_答疑地点：宋健研究院5178/9/20221教材、参考书与课时安排教材算法设计与分析吕国英 主编清华大学出版社8/9/2022 4:03 PM2Introduction to Algorithms（Second）Thomas H. CommonHIGHER EDUCATION PRESS参考资料计算机算法设计与分析（第2版）王晓东电子工业出版社8/9/2022 4:03 PM3Introduction to the Design and Analysis of AlgorithmsA

2、nany V.LevitinAddison-Wesley课时安排授课 ：32学时实验 : 16学时作业要求以组为单位进行算法设计，各有分工，且分工明确，独立完成自己的工作，并进行抽查实验要求以组为单位进行算法设计，各有分工，且分工明确，各自完成自己的工作，独立书写实验报告8/9/2022 4:03 PM4主要内容算法分析体系及计量算法基本工具及优化技巧基本的算法策略迭代算法蛮力法分治算法贪婪算法动态规划图的搜索算法广度优先搜索深度优先搜索回溯法分支限界法算法设计实践8/9/2022 4:03 PM5第1章 算法概述主要内容算法描述现代常用算法概览用计算机求解问题与算法8/9/2022 4:03

3、 PM6学习目标：用计算机求解问题用计算机求解问题与算法问题求解人工智能的成就博奕模拟人类的智能去解决问题用计算机求解问题的步骤一、问题分析（checklist）在原始表达中，所用术语都有准确的定义？题目中提供了哪些信息？它们的作用？题目要求的结果是什么？是否有潜在的信息？判定求解结果所需要的中间结果有哪些？8/9/2022 4:03 PM7二、数学模型的建立最适合于此问题的数学模型是什么？是否有已经解决的类似问题可以借鉴？注重对不同模型的分析与比较三、算法设计与选择从数据结构、模型等方面进行考虑四、算法表示流程图、盒图、PAD图和伪码等五、算法分析时间与空间上的开销建立衡量算法优劣的标准六、

4、算法实现七、程序调试选择测试方法与测试实例八、文档编制8/9/2022 4:03 PM8算法及其要素和特性算法定义算法的三要素操作控制结构数据结构算法的基本性质目的性、分步性、有序性、有限性、操作性算法的地位是计算机科学中最具有方法论性质的核心概念基本特征有穷性、确定性、可行性、有输入输出8/9/2022 4:03 PM9算法设计及基本方法质量指标正确性、可读性、健壮性、高效率与低存储需求结构化方法本书采用的方法自顶向下，逐步求精模块化设计简单、独立和完整模块间的接口面象对象方法抽象化、封装性、多态性、继承性从算法到实现数据类型的选择计算过程的差异结果的输出格式测试、调试8/9/2022 4:

5、03 PM10算法描述算法描述简介自然语言流程图盒图PAD图伪代码程序设计语言（不是很适合算法描述）PYNABWHILE pSS1S2S3P=P1P=P2P=Pn8/9/2022 4:03 PM11算法描述约定（类C）3种基本控制结构数据结构模块及模块间的接口方式的描述其他说明运算符采用较通用的形式mod、逻辑运算法表示整除；/带小数的除不等号注释用/input/print库函数的使用8/9/2022 4:03 PM12一个简单问题的求解过程数据处理要求问题逻辑结构基本功能数学模型存储结构算法实现性能文档评价问题分析算法设计算法分析例1-1求两个正整数的最大公约数数学模型：a、b0,求c。c能

6、整除a、b，且a/c与b/c互质算法设计：“短除法”。找出两数的所有公约数，累乘。main（）int a,b,i,t=1; input(a,b);for(i=2;i=a and i=b;i=i+1) while(a mod i=0 and b mod i=0) t=t*i;a=a/i;b=b/i;print(a,b,”maximal divisor is”,t);算法分析：算法中的主要操作是比较和累乘。由于算法是盲目地尝试可能的因数，比较操作次数较多，算法效率不高。8/9/2022 4:03 PM13现代常用算法概览压缩算法概念：采用特殊的编码方式来保存数据，使数据占用的存储空间比较小。应用：

7、文字、图形、图像分类：（非）即时压缩、数据和文件压缩、无损（2：15：1）与有损压缩压缩原理：冗余、频度、相关性压缩算法无损压缩：Huffman、字典压缩等有损压缩：脉冲编码调制（PCM）、线性预测（LPC）、矢量量化（VQ）离散小波变换（DWT）等8/9/2022 4:03 PM14加密算法概述：信息安全的核心技术加密/解密算法其它加密方法人工智能算法概念：人类智能的计算机模拟研究方法：仿生学、计算机数学、心理学等现状与未来：实现了人类左脑的逻辑推理；将来仿人类右脑的模糊处理能力和整个大脑的并行化处理并行算法概念：把一个事物的行为看成是多个事物互相作用的结果目的：提高计算速度；解决传统计算机无法解决的问题划分、子问题交互、映射8/9/2022 4:03 PM15其它实用算法数值算法Maple、MATLAB、Mathematica等运筹学相关算法统计分析算法 SPSS、SAS网络搜索引擎算法提高搜索引擎对用户检索提问的理解对检索结果进处理基于链接评价的搜索引擎（Google）基于大众性搜索引擎（Direct Hit