计算机算法基础(一).pptVIP

计算机算法基础 算法的研究内容 问题是否可解 1930’s 研究集中于判断特定问题在计算机上是否可解，基本方法为：选定一个计算模型，观察是否能在该模型上创建能解决问题的算法。这些计算模型包括：Post machines、Turing machines等。这一阶段的成果是：大部分问题为不可解。 高效率的解决方法 随着计算机的发展和数据资源的增加，算法研究转向针对可解的问题，找到高效率的解决方法。 算法的应用 数据库中的检索 有哪些信誉好的足球投注网站引擎中的爬找器和检索 公共密钥加密和数字签名技术 优化问题 最短路径 资源分配 … 章节安排 《计算机算法基础》，余祥宣、崔国华、邹海明著，华中科技大学出版社 第一章 导引与基本数据结构 √ 第二章 分治法 √ 第三章 贪心方法 √ 第四章 动态规划 √ 第五章 检索与周游 √ 第六章 回溯法 √ 第七章 分枝-限界 √ 第八章 NP-问题 ⊙ 预备知识 数学：集合、证明方法（直接、间接、反证、反例、归纳假设）、对数基础、FLOORCEILING函数、阶乘、递归关系 数据结构：链接表、图、树、二元树 第一章 导引与基本数据结构 1.1 算法的定义及特性 1. 什么是算法？ 算法是解一确定类问题的任意一种特殊的方法。 在计算机科学中，算法是使用计算机解一类问题的精确、有效方法的代名词： 算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。 2. 算法的五个重要特性 确定性、能行性、输入、输出、有穷性 2）能行性 算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间内完成。 例：整数的算术运算是“能行”的 实数的算术运算是“不能行”的 3）输入 每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合——定义域（或值域） 5）有穷性 一个算法总是在执行了有穷步的运算之后终止。 计算过程：只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。 准确理解算法和计算过程的区别： 不能终止的计算过程：操作系统 算法是“可以终止的计算过程” 算法的时效性：只能把在相当有穷步内终止的算法投 入到计算机上运行 3. 我们的主要任务 算法学习将涉及5个方面的内容： 1）设计算法：创造性的活动 2）表示算法：思想的表示形式 3）确认算法：证明算法的正确性 程序的证明 4）分析算法：算法时空特性分析 5）测试程序：调试和作出时空分布图 本课程集中于学习算法的设计与分析。通过学习，掌握计算机算法设计和分析基本策略与方法，为设计更复杂、更有效的算法奠定基础 1.2 分析算法 1. 分析算法的目的 在于：通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。 算法分析是计算机领域的古老而前沿的课题。 进行算法分析的基本技术：抽象 2. 重要的假设和约定 1）计算机模型的假设 Turing机模型：计算机形式理论模型 通用计算机模型： 单处理器 有足够的“内存” 能在固定的时间内存取数据单元 2）计算的约定 确定使用什么样的运算及其执行时间。 从计算时间上，运算的分类： 时间囿界于常数的运算：尽管每种运算的执行时间不同，但一般只花 一个固定量的时间（单位时间）就可完成。 ·基本算术运算，如整数、浮点数的加、减、乘、除 ·字符运算 ·赋值运算 ·过程调用等 2）计算的约定（续） 其他运算： ·字符串操作：与字符串中字符的数量成正比 ·记录操作：与记录的属性数、属性类型等有关 · 特点：运算时间无定量 如何分析非时间囿界于常数的运算：分解成若干时间囿