算法分析与设计-第01章.pptVIP

南京邮电大学计算机学院*1.2.2问题求解过程理解问题（understandtheproblem）设计方案（deviseaplan）实现方案（carryouttheplan）回顾复查（lookback）南京邮电大学计算机学院*1.2.3系统生命周期一个计算机程序的开发过程就是使用计算机求解问题的过程。软件工程(softwareengineering)将软件开发和维护过程分成若干阶段，称为系统生命周期(systemlifecycle)或软件生命周期。南京邮电大学计算机学院*软件生命周期划分为:分析（analysis）设计（design）编码（codingorprogramming）测试（testing）维护（maintenance）等5个阶段。前4个阶段属于开发期，最后一个阶段处于运行期。南京邮电大学计算机学院*1.3算法设计与分析南京邮电大学计算机学院*算法问题求解过程理解问题选择求解方法确定数据结构设计算法正确性证明分析算法编写代码1.3.1算法问题求解过程南京邮电大学计算机学院*算法分类一个精确算法(exactalgorithm)总能保证求得问题的解。一个启发式算法(heuristicalgorithm)通过使用某种规则、简化或智能猜测来减少问题求解时间。南京邮电大学计算机学院*对于最优化问题，一个算法如果致力于寻找近似解而不是最优解，被称为近似算法（approximationalgorithm）。如果在算法中需做出某些随机选择，则称为随机算法（randomizedalgorithm）。南京邮电大学计算机学院*1.3.2如何设计算法使用计算机的问题求解策略主要指算法设计策略（algorithmdesignstrategy）。如果所求问题符合某种算法设计策略处理的问题特性，就可使用该算法设计策略设计算法、求解问题。南京邮电大学计算机学院*1.3.3如何表示算法算法描述方法自然语言流程图伪代码程序设计语言本书使用C/C++语言描述南京邮电大学计算机学院*1.3.4如何确认算法算法确认(algorithmvalidation):确认一个算法是否正确的活动。算法证明(algorithmproof):使用数学方法证明算法的正确性。程序测试(programtesting):是指对程序模块或程序总体，输入事先准备好的样本数据（称为测试用例，testcase），检查该程序的输出，来发现程序存在的错误及判定程序是否满足其设计要求的一项积极活动。**南京邮电大学计算机学院*算法设计与分析DesignandAnalysisofAlgorithmsInC++南京邮电大学计算机学院*教材：陈慧南.算法设计与分析-C++语言描述先修课：面向对象程序设计语言C++，数据结构性质：计算机科学与技术中处于核心地位的一门专业基础课。南京邮电大学计算机学院*目的：通过学习掌握算法设计的主要方法，并对算法的时、空复杂性有正确分析的能力，能够针对具体的应用问题选择合适的数据结构和设计结构清晰、正确有效的算法，为独立设计算法和对算法进行复杂性分析奠定坚实的理论基础。基本任务:介绍算法的基本概念、算法设计的基本策略和方法，同时介绍算法复杂性的概念、性能分析的具体方法和技巧。教学重点:算法设计的基本思想和策略，以及算法性能分析的方法等。南京邮电大学计算机学院*难点:如何将算法优化的思想贯穿在设计过程中，以及算法平均性能的分析技巧。总学时：48学时。成绩考核办法：平时成绩30%，期末考试70%。南京邮电大学计算机学院*第1章算法问题求解基础基本要求：本章概述算法问题、求解方法等重要概念和方法。掌握算法的基本概念，了解使用计算机求解问题的过程和方法。南京邮电大学计算机学院*1.1算法概述1.2问题求解方法 1.3算法设计与分析 1.4递归和归纳 南京邮电大学计算机学院*1.1算法概述南京邮电大学计算机学院* “计算机科学是一门研究算法的科学” 计算机的运算速度很高，但是速度再高也有它的极限。为了充分发挥计算机的高速特点，应在计算机求解问题的过程中，尽量减少人工干预。 为使计算机的计算过程能够解决某一特定