文档介绍：算法设计与分析 Design and Analysis of Computer Algorithm ?有两种思想,,, 而算法造就了现代世界. —— David Berlinski 算法的研究内容?问题是否可解? 1930 ’s 研究集中于判断特定问题在计算机上是否可解,基本方法为:选定一个计算模型,观察是否能在该模型上创建能解决问题的算法。这些计算模型包括: Post machines 、 Turing machines 等。这一阶段的成果是: 大部分问题为不可解。?高效率的解决方法?随着计算机的发展和数据资源的增加,算法研究转向针对可解的问题,找到高效率的解决方法。算法的应用?数据库中的检索?搜索引擎中的检索?公共密钥加密和数字签名技术?优化问题?最短路径?资源分配?…章节安排?《计算机算法基础》,余祥宣、崔国华、邹海明著,华中科技大学出版社?第一章导引与基本数据结构√?第二章分治法√?第三章贪心方法√?第四章动态规划√?第五章检索与周游√?第六章回溯法√?第七章分枝-限界√?第八章 NP- 问题⊙预备知识?数学:集合、证明方法(直接、间接、反证、反例、归纳假设)、对数基础、 FLOOR&CEILING 函数、阶乘、递归关系?数据结构:链接表、图、树、二元树第一章导引与基本数据结构算法的定义及特性 ? 一系列将问题的输入转换为输出的计算或操作步骤。 2. 算法的五个重要特性确定性、能行性、输入、输出、有穷性 1)确定性:算法的每种运算必须要有确切的定义,不能有二义性。例:不符合确定性的运算? 5/0 ?将6或7与x相加?未赋值变量参与运算 2)能行性算法中有待实现的运算都是基本的运算, 原理上每种运算都能由人用纸和笔在有限的时间内完成。例:整数的算术运算是“能行”的实数的算术运算是“不能行”的 3)输入每个算法有 0个或多个输入。这些输入是在算法开始之前给出的量,取自于特定的对象集合——定义域(或值域) 4)输出一个算法产生一个或多个输出,这些输出是同输入有某种特定关系的量。