[理学]第1章 算法概述Introduction.ppt

计算机学科是对描述和变换信息的算法过程，包括其理论、分析、设计、效率、实现和应用等进行的系统研究。 它涉及计算过程的分析以及计算机的设计和使用，从算法与可计算性的研究到可计算性硬件和软件的实际实现问题的研究。 （IEEE－CS和ACM 联合调查组 ） 算法是计算机科学的重要研究领域之一,应用领域不断扩大是现代软件系统的核心。 “算法和数据结构”被列为计算学科的九个主题的第一个ＡＣＭ／ＩＥＥＥ－ＣＳ 1993. (算法与数据结构，计算机体系结构，人工智能与机器人学，数据库与信息检索，人一机通信，数值与符号计算，操作系统，程序设计语言，软件方法学与工程。 ) 1998年秋，IEEE－CS和ACM联手组成任务组，开始了关于计算学科教学计划的CC2001（Computing Curricula 2001）的起草工作。 2001年12月提交了最终报告。 CC2001将计算学科划分为14个主领域：离散结构、程序设计基础、算法与复杂性、数据结构、操作系统、网络计算、程序设计语言、人机交互、图形学与可视化计算、智能系统、信息管理、软件工程、社会和职业的问题和科学计算。 IEEE/ACM 在CC2001中将计算机学科称为计算学科，并将计算学科分为四个领域（也称专业方向）， 计算机科学 计算机工程 软件工程 信息系统。 于2004年6月1日公布的CC2004报告，在上述四个领域的基础上，增加了一个信息技术领域。 我国计算机学科研究方向（研究生） 0812 一级学科：计算机科学与技术 　　081201 计算机系统结构 081202 计算机软件与理论 　　081203 计算机应用技术 软件工程一级学科： 软件工程理论 软件工程技术 软件工程管理 软件服务工程 课程起源 《计算机程序设计技巧》 “The Art of Computer Programming” 第一卷 《基本算法》1968 第二卷《半数字化算法》1969 第三卷《排序与有哪些信誉好的足球投注网站》1973 第四卷《组合算法》(2006部分出版) 1968 唐.欧.克努特教授（高德纳）著 Donald.E.Knuth at Standford University 1938年 出生， 1974获图灵奖 克努特至今主要进行了两项工程， 一个已经完成， 一个尚未完成 。 第一个： “The Art of Computer Programming” （KMP算法 ，LR(K)算法） 第二个：TEX排版软件和METAFONT字型设计软件 ，九年时间。 对整个西文印刷行业带来了革命性变革 ，1986年度ACM的的软件系统奖(Software System Award) --自由软件 ，免费使用。 课程简介 算法设计与分析是计算机科学技术、软件工程及相关专业的重要课程之一。 培养分析问题和解决问题的能力； 掌握算法设计的基本方法； 熟悉算法分析的基本技术； 为软件系统开发奠定扎实的理论基础。 课程简介 多数高校越来越重视算法课程的教学 分离算法与数据结构课程 以算法设计策略为知识单元 系统介绍算法的设计方法与分析技巧 什么是算法? 问题求解(Problem Solving) 算法概述 学习要点: 理解算法的概念。 理解什么是程序，程序与算法的区别和内在联系。 掌握算法的计算复杂性概念。 掌握算法渐近复杂性的数学表述。 掌握用C++语言描述算法的方法。 算法是指解决问题的一种方法或一个过程。 对于算法，D.E.Knuth给出了一个非形式化的定义： 一个算法，就是一个有穷规则（指令）的集合，它为某个特定类型问题提供了解决问题的运算序列。 程序(Program) 程序是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)。 例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。 操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止，所以是算法。 如何对算法进行分析与衡量？ 算法分析是对一个算法所消耗资源进行估算。 资源消耗指时间、空间的耗费。 算法分析的目的就是通过对同一问题的多个不同算法进行时空耗费这两方面的分析. 在时空资源兼受限制时，找出时空代价的平衡点，即时间相对少，空间耗费也相对少的算法。在两种资源之一受限时，选出适合这一限制的算法。 算法复杂性分析 算法复杂性 = 算法所需要的计算机资源 算法的时间复杂性T(n)； 算法的空间复杂性S(n)。 其中n是问题的规模（输入大小）。 算法的时间复杂性 （1）最坏情况下的时间复杂性 Tmax(n) = max{ T(i) | size(i)=n } 可操作性最好，最有实际价值，本书重点。 （2