第01章算法引论

《第01章算法引论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1算法设计基础吴刚2算法生活中的算法——菜谱3制作过程45算法的定义初始状态状态1状态2状态n结果状态Step1Step2StepnStepn+1算法6算法的地位和作用实际问题数学问题数据模型算法设计算法求解7与前趋课程之间的关系顶层运算步骤底层运算步骤数据结构程序设计语言算法设计与分析从菜谱看算法同一个菜，可能有多个菜谱（简单vs.复杂）同一个菜谱，可以有多种表达方式：文字，图片，口述，中文，英文同一个菜谱，用不同工具完成的效率和效果也不同同一个菜谱，不同的人去做（厨师？）菜谱的指导作用：正确性和效率8解决同一个问题可以有多种算法程序不等于算法算法与程序设计语言的关系算法与数据结构

2、的关系算法设计原则9算法的设计与分析设计：针对具体问题设计出相应的求解方案（相应的步骤）。能得到解，能得到好的解(effectiveness)计算时间可以接受(efficiency)分析：对一类问题而不是个别问题估计其时间和空间需求（通常为时间复杂度）分析解的好坏，通过比较别人算法的解进行评价（本课程重点为算法设计）10教材及参考书王晓东.算法设计与分析.清华大学出版社，2003.ThomasH.Cormen.Introductiontoalgorithms：MIT，2000.有关算法的历史周髀算经——演算法Al-KhwarizmiEuclidAugustaAdaByronAlanM

3、athisonTuring11a÷b，令r为所得余数（0≤r＜b）若r=0，算法结束；b即为答案。2.互换：置a←b，b←r，并返回第一步。12主要内容第1章算法引论第2章递归与分治策略第3章动态规划第4章贪心算法第5章回溯法第6章分支限界法第7章概率算法第8章专题讲座13第1章算法引论1.1算法的分类1.2算法与程序1.3表达算法的抽象机制1.4*描述算法1.5算法复杂性分析141.1算法的分类算法迭代法直接法（非迭代）未证明为收敛的算法（启发法）启发式算法Heuristics元启发式算法Metaheuristics(GA,SA,ANN,TS,AC)收敛算法有限算法路状结构算法树状

4、结构算法(动态规划、分支定界、...)算法近似算法151.1算法的分类一个问题问题的解一个问题的算法解空间解空间解空间一个问题一个问题一类问题一类问题的算法16第1章算法引论1.1算法的分类1.2算法与程序1.3表达算法的抽象机制1.4*描述算法1.5算法复杂性分析1.2算法与程序9/3/202117/68AlgorithmsProgramming181.2算法与程序（续）算法是满足下述性质的指令序列：输入：有零个或多个外部量作为算法的输入输出：算法产生至少一个量作为输出确定性：组成算法的每条指令清晰、无歧义有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限程序是算法用某

5、种程序设计语言的具体实现，程序可以不满足算法的性质(4)即有限性。191.2算法与程序（续）DB和OS中的算法：搜索算法：深度搜索、广度搜索、最短路径、查找树排序算法：插入排序、快速排序、希尔排序、归并排序、堆排序、基数排序、外排序先来先服务、短时间优先、时间片轮转调度、页面置换等等……20第1章算法引论1.1算法的分类1.2算法与程序1.3表达算法的抽象机制1.4*描述算法1.5算法复杂性分析211.3表达算法的抽象机制算法：探索从数据模型的已知状态到达要求的结果状态所需要的运算步骤。抽象数据类型：算法的一个数据模型连同定义在该模型上作为算法构件的一组运算。221.3表达算法的抽象

6、机制数学问题数据结构、对数据结构的操作顶层运算步骤（变量、顶层运算）抽象数据类型底层运算步骤（数据结构、顶层运算的具体实现）程序设计语言23第1章算法引论1.1算法的分类1.2算法与程序1.3表达算法的抽象机制1.4*描述算法1.5算法复杂性分析24在本书中，采用Java语言描述算法。1.Java程序结构1.4描述算法（1）Java程序的两种类型：应用程序和applet区别：应用程序的主方法为main，其可在命令行中用命令语句java应用程序名来执行；applet的主方法为init，其必须嵌入HTML文件，由Web浏览器或applet阅读器来执行。（2）包：java程序和类可以包(p

7、ackages)的形式组织管理。（3）import语句：在java程序中可用import语句加载所需的包。例如，importjava.io.*;语句加载java.io包。251.4描述算法2.Java数据类型数据类型基本数据类型：详见下页表1-1非基本数据类型：如Byte,Integer,Boolean,String等。Java对两种数据类型的不同处理方式：对基本数据类型：在声明一个具有基本数据类型的变量时，自动建立该数据类型的对象（或称实例）。如:int