计算机算法基础(第一章)资料.ppt

  1. 1、本文档共77页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
计算机算法基础(第一章)资料

计算机算法基础 参考书目 算法导论(第二版 影印版)Introduction to Algorithms(Second Edition ) (美)Thomas H.Cormen等 高等教育出版社 计算机程序设计艺术(英文影印版)(1-3卷精装全套)The Art of Computer Programming Volumes 1-3 Boxed Set (美)Donald E.Knuth 清华大学出版社 序 计算机算法是计算机科学和计算机应用的核心 数据结构+算法 = 程序 算法:计算机软件的灵魂 章节安排 第一章 导引与基本数据结构 √ 第二章 分治法 √ 第三章 贪心方法 √ 第四章 动态规划 √ 第五章 检索与周游 √ 第六章 回溯法 √ 第七章 分枝-限界 √ 第八章 NP-问题 ⊙ 第九章 并行算法 ⊙ 第一章 导引与基本数据结构 1.1 算法的定义及特性 1. 什么是算法? 算法如数字、计算一样,是一个基本概念。 算法是解一确定类问题的任意一种特殊的方法。 在计算机科学中,算法是使用计算机解一类问题的精确、有效方法的代名词: 算法是一组有穷的规则,它规定了解决某一特定类型问题的一系列运算。 2. 算法的五个重要特性 确定性、能行性、输入、输出、有穷性 2)能行性 算法中有待实现的运算都是基本的运算,原理上每种运算都能由人用纸和笔在有限的时间内完成。 例:整数的算术运算是“能行”的 实数的算术运算是“不能行”的 3)输入 每个算法有0个或多个输入。这些输入是在算法开始之前给出的量,取自于特定的对象集合——定义域(或值域) 5)有穷性 一个算法总是在执行了有穷步的运算之后终止。 计算过程:只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则。 准确理解算法和计算过程的区别: 不能终止的计算过程:操作系统 算法是“可以终止的计算过程” 算法的时效性:只能把在相当有穷步内终止的算法投 入到计算机上运行 算法和程序 程序:一个计算机程序是对一个算法使用某种程序设计语言的具体实现 任何一种程序设计语言都可以实现任何一个算法 算法的有穷性意味着不是所有的计算机程序都是算法 3. 我们的主要任务 算法学习将涉及5个方面的内容: 1)设计算法:创造性的活动 2)表示算法:思想的表示形式 3)确认算法:证明算法的正确性 程序的证明 4)分析算法:算法时空特性分析 5)测试程序:“调试只能指出有错误,而不能指出它们 不存在错误” 本课程集中于学习算法的设计与分析。通过学习,掌握计算机算法设计和分析基本策略与方法,为设计更复杂、更有效的算法奠定基础 4. 课程关系 数据结构、离散数学 程序设计语言:结构化设计 数学基础 非数值计算领域的基本知识 1.2 分析算法 计算机程序设计的核心目标: 1、设计一个容易理解、编码和调试的算法 2、设计一个能有效利用计算机资源的算法 怎样度量效率?--算法分析 2. 重要的假设和约定 1)计算机模型的假设 Turing机模型:计算机形式理论模型 通用计算机模型: 顺序计算机 有足够的“内存” 能在固定的时间内存取数据单元 2)计算的约定 算法的执行时间=∑Fi*ti 其中,Fi是算法中用到的某种运算i的次数, ti是该运算执行一次所用的时间。 确定使用什么样的运算及其执行时间。 从计算时间上,运算的分类: 时间囿界于常数的运算: ·基本算术运算,如整数、浮点数的加、减、乘、除 ·字符运算 ·赋值运算 ·过程调用等

文档评论(0)

jiayou10 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

版权声明书
用户编号:8133070117000003

1亿VIP精品文档

相关文档