算法设计与分析平时要求：按时上下课、勤动脑动手，有事请提前与辅导员请假；考试成绩：平时表现（考勤、随堂提问、作业等）：20%实验（纸版和电子版）：10%课堂测验（三至四次）：20%期末考试（闭卷）：50%（注意：无故缺勤超过6学时(3次)以上取消本课程考试资格，直接进入重修；）上课时间：第一至十二周课程简介课程内容主要任务第1部分算法和算法分析主要内容第1章算法问题求解基础本章内容1.1算法概述70年代前计算机科学基础的主题没有被清楚地认清。70年代Knuth出版了《TheArtofComputerProgramming》以算法研究为主线确立了算法为计算机科学基础的重要主题1974年获得图灵奖。70年代后算法作为计算机科学核心推动了计算机科学技术飞速发展.解决一个计算问题的过程1.1.1什么是算法输入（input）：算法有零个或多个输入量；输出（output）：算法至少产生一个输出量；确定性（definiteness）：算法的每一条指令都有确切的定义，没有二义性；能行性（effectiveness）：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现；有穷性（finiteness）：算法必须总能在执行有限步之后终止。最早的算法是欧几里德的“求最大公因子算法”程序(Program)程序(Program)1.1.2为什么学习算法1.2问题求解方法常见的应用问题类型有：1、搜索问题所谓搜索，就是在给定的数据集合中寻找满足条件的数据对象。例如，在图书管理中，若要了解全部读者的借阅信息，就需要对每一位读者的借阅记录依次输出，这是数据对象的遍历问题。如果我们要查找借书超期的读者，则是按照规定的最大借书期限这一特征值去查找满足该条件的记录。2、排序问题所谓排序，就是把一组无序的数据按照一定的规则排列起来。排序结果有升序和降序两种。例如，为便于查询学生的考试成绩，对于成绩单，通常按照学号排序；而在招生录取中，也可以按照成绩的高低排序。对于同一个问题，排序的算法是多种的，如插入排序、选择排序、交换排序等。3、图论问题图论问题主要是研究数据结构是图形结构或树形结构的算法问题。简单的定义，可以认为图是由一些顶点和顶点之间的边所构成的集合。图结构可以用来对各种各样的实际应用问题建模，包括交通和通讯网络、工程项目时间表和各种竞赛。图应用算法主要包括图的遍历算法、最短路径算法、最小生成树算法、拓扑排序算法和网络流算法等。4、组合数学问题有一些问题要求寻找一个组合对象，比如一个排列、一个组合或者一个子集，这些对象能够满足特定的条件并具有我们想要的特性(如价值最大化或者成本最小化)。从更抽象的角度来看，这类问题是组合数学问题，例如旅行售货商问题和图着色问题。组合数学问题所涉及的应用领域更加广阔，例如拓扑学、图论、博弈论、线性规划等。组合数学问题的特点是随着问题规模的增加，已达到计算机的处理能力的极限。所以，称组合数学问题是计算机中的难解问题。5、几何问题几何算法处理类似于点、线、多面体这样的几何对象。经典的计算几何问题，如最近点对问题和凸包问题。顾名思义，最近点对问题求的是给定平面上的n个点中，寻找距离最近的两个点。凸包问题要求找一个能把给定集合中所有点包含都在里面最小凸多边形。当前，几何问题算法在计算机图形学、机器人技术和断层X摄像技术等方面都有广泛的应用。6、数值计算问题数值计算问题是另一大类问题，它要解决的问题包括：求解方程或者方程组和求数值积分等。这些问题常常只能给出一个近似的结果，而不是精确的解析答案。问题求解（problemsolving）是寻找一种方法来实现目标。计算机求解问题的关键之一是寻找一种问题求解策略（problemsolvingstrategy），得到求解问题的算法，从而得到问题的解。1.2.2算法设计的一般过程1.2.3系统生命周期软件生命周期划分为:分析（analysis）设计（design）编码（codingorprogramming）测试（testing）维护（maintenance）等5个阶段。1.3算法设计与分析1.3.1算法问题求解过程对于最优化问题，一个算法如果致力于寻找近似解而不是最优解，被称为近似算法（approximationalgorithm）。如果在算法中需做出某些随机选择，则称为随机算法（randomizedalgorithm）。1.3.2如何设计算法1.3.3如何表示算法1.3.4如何确认算法1.3.5如何分析算法1.4递归和归纳1.4.1递归例1-1斐波那契数列递归算法当一个算法采用递归方式定义时便成为递归算法。一个递归算法是指直接或间接调用自身的算法。【程序1-4】求FnlongF