计算机辅助工程基础.ppt

《计算机辅助工程基础.ppt》由会员分享，可在线阅读，更多相关《计算机辅助工程基础.ppt（139页珍藏版）》请在三一办公上搜索。

1、1,第二章 计算机辅助工程基础,数据结构和算法计算机图形学工程数据库软件工程新技术趋势,2,2.1 数据结构和算法,3,数据结构,实际问题,数学模型,求解算法,抽象,设计,编程解答,求解实际问题的一般步骤：,信号相位是指在一个交叉口某个方向的交通流（或几个交通流的组合）同时得到的通行权及被分配得到这些通行权的时间带。在多叉路口需设几个相位才能既使车辆相互之间不冲突而又达到最大的流通呢？,交叉口信号相位的设置问题,假设有如图所示的五叉路，其中C和E为单行道，在路口有13条可行的通路，其中有的可以同时通行而不发生冲突，如AB和EC，而有的在同时通行时一定会冲突，如EB和AD，那末，在该交叉口应如何

2、设置相位？这个问题可以转换成一个图的染色问题。,5,在图上以一个圆圈表示一条通路，在不能同时通行的两个圆圈之间画一连线，对图中的圆圈上色，要求同一连线上的两个圆圈不同色且颜色种类最少；一种解决方案，图中13个圆圈表示13条通路，四种颜色分别表示四个相位。,交叉口信号相位的设置问题 图的染色问题,6,数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。数据结构就是一门研究非数值性程序设计中计算机操作的对象以及它们之间的关系和运算等的学科,基本概念,7,基本概念,数据：对客观事物的符号表

3、示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称 数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理 数据对象：性质相同的数据元素的集合，是数据的一个子集 数据结构：相互之间存在一种或多种特定关系的数据元素的集合,8,四类基本结构,集合 线性结构 树形结构 网状结构,数据元素1,数据元素2,数据元素1,数据元素2,数据元素1,数据元素2,数据元素3,数据元素1,数据元素2,数据元素3,9,线性表,线性表是最常用且最简单的一种数据结构，它是属同一数据对象的n个数据元素的有限序列若将线性表记为，称ai-1是ai 的直接前趋元素，ai+1是ai的直接后继元

4、素线性表中元素的个数n(n=0)定义为线性表的长度，n=0 时称为空表。在非空表中的每个数据元素都有一个确定的位置，比如ai是第i个数据元素，称i为ai在线性表中的位序,10,线性表1顺序表,顺序表以一组地址连续的存储单元依次存储线性表的数据元素，由此在逻辑上相邻的两个元素在物理位置上也是相邻的。只要给定了存储线性表的起始位置，表中任一数据元素都可以随机存取，因此顺序表是一种随机存取的存储结构。顺序表通常用数组类型来实现.,ai的地址计算函数为：addr(ai)=addr(a1)+(i-1)*d,11,线性表2链表,链表使用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可

5、以是不连续的，即逻辑上相邻的两个元素在物理位置不一定相邻）。数据元素ai的存储映象（称为结点）包括两个域：存储数据元素信息的数据域；存储直接后继位置信息的指针域，n个结点链接成一个链表。链表在高级程序语言中可用指针来实现,12,线性表2链表,删除元素,添加元素,13,栈,栈是限定在表尾进行插入或删除操作的特殊线性表。先进后出的线性表.a1为栈底元素，an为栈顶元素。栈中元素按a1,a2,an的次序进栈，出栈的第一个元素应为栈顶元素an。,14,栈,基本运算有：建立一个栈 检查栈中剩余容量 从栈顶推入一个元素 从栈顶取出一个元素 删除一个栈,应用举例：常用软件中的撤销 与恢复 操作,15,队列,

6、队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在表的另一端进行删除。在队列中，允许插入的一端叫做队尾，允许删除的一端则称为队首。假设队列为，则称a1为队首元素，an为队尾元素。队中元素按a1,a2,an的次序进入退出队列也只能按这个次序依次进行。,16,队列,基本运算有：建立一个队列 检查队列状态 从队尾插入一个元素 从队首删除一个元素 删除一个队列,应用举例：生活中的排队,17,例交叉口仿真系统控制结构,当采用仿真方法分析一系列交叉口所发生的交通状态时，需要采用分时处理技术分别逐个改变每一个交叉口的状态，同时系统整体环境也在发生着一些具有时间先后次序的情况。,18,树,结点A为树

7、的根，根的每个分支称为子树，子树也是一棵树 结点子树的根为结点的孩子，如B、C、D为结点A的孩子，而A为B、C、D的双亲 同一个双亲的孩子之间为兄弟关系，如B、C、D 没有孩子的结点为树的叶子，H、F、G、D为树的叶子,19,树的基本运算,初始化一棵树 得到树的根 得到一个结点的双亲 得到一个结点的兄弟 得到一个结点的孩子 插入子树 删除子树 遍历树 清空树,20,特殊的树,二叉树 二叉搜索树 哈夫曼树 B树 AVL树 红-黑树,用于具有层次结构的数据的组织、搜索和比较,各种特定的树结构被广泛应用于交通CAE软件中，它们可以加快查找的速度和分析处理的效率。,21,二叉树,二叉树在树结构的应用中

8、起着非常重要的作用对二叉树的许多操作算法简单;而任何树都可以与二叉树相互转换，解决了树的存储结构及其运算中存在的复杂性。定义：二叉树是由n(n=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。,22,二叉树的5种形式,(a)空二叉树,A,(b)根和空的左右子树,(c)根和左子树,(d)根和右子树,(e)根和左右子树,23,在二叉树的一

9、些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。,由二叉树的递归定义，二叉树的三个基本组成单元是：根结点、左子树和右子树。,遍历二叉树,24,假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规

10、定为：DLR先（根）序遍历，LDR中（根）序遍历，LRD后（根）序遍历。,25,先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。,先序遍历二叉树,124537,26,中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。,425137,中序遍历二叉树,27,后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。,452731,后序遍历二叉树,28,例题,例如图（1）所示的二叉树表达式(a+b*(c-

11、d)-e/f),按中序遍历：a+b*c-d-e/f按后序遍历：abcd-*+ef/-,按先序遍历：-+a*b-cd/ef,29,例题,已知一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出这棵二叉树。当前序序列为ABECDFGHIJ，中序序列为EBCDAFHIGJ时，逐步形成二叉树的过程如下图所示：,30,树的路径长度（PL）,PL是指从根到其它各结点的路径长度（分支数）之和。,31,完全二叉树,完全二叉树各结点的路径长度分别是数列0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,其路径长度为前n项之和，具有最小值：,32,霍夫

12、曼树,具有最小 WPL 的扩充二叉树叫霍夫曼树,33,霍夫曼树的构造方法,将n个权值视为具有n棵扩充二叉树的森林F，然后重复以下步骤，直到F中只有一棵树为止：,在F中选根的权值最小的两棵作为左右子树构造一棵新的二叉树，其根的权为左右子树根的权值之和。,在F中删除那两棵树，并把新的二叉树加入。,34,霍夫曼树的构造方法,35,霍夫曼编码霍夫曼树应用事例,1、最小冗余编码问题,设用0，1码来对一串字符信息进行等长编码：T 00，A 01，D 10，S 11,对于信息串“ATTSTATADT”所得到的编码为 01,00,00,11,00,01,00,01,10,00 共20位编码,字母集合T，A，D

13、，S出现的频度 W=5，3，1，1，若采用不等长编码表示 T 0，A 10，D 110，S 111 所得到的 编码是 10,0,0,111,0,10,0,10,110,0 共17位，这是最小冗 余编码。,36,霍夫曼编码霍夫曼树应用事例,2、霍夫曼树编码,以字符的频度为权构造霍夫曼树,左分支表示0，右分支表示1,从根到各外结点路径上经由的数字序列构成各字符的编码,37,3、霍夫曼树编码的优越性,是最小冗余码,非前缀码码 Ci 不是码 Cj 的前缀,译码简单唯一不断从根开始沿霍夫曼编码树查找。译码得到的只能是报文串：ATTSTATADT,霍夫曼编码霍夫曼树应用事例,38,习题,给定权值集合15,

14、03,14,02,06,09,16,17,构造相应的霍夫曼树,并计算它的带权外部路径长度。假定用于通信的电文仅由8个字母c1,c2,c3,c4,c5,c6,c7,c8组成,各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4。试为这8个字母设计不等长Huffman编码,并给出该电文的总码数。,39,解答,此树的带权路径长度WPL=229,40,已知字母集 c1,c2,c3,c4,c5,c6,c7,c8，频率 5,25,3,6,10,11,36,4，则Huffman编码为：,电文总码数为 4*5+2*25+4*3+4*6+3*10+3*11+2*36+4*4=257,解答,41,

15、例：路网规划,在路网规划过程中，需在现状路网的基础上不断改造、完善，由近及远地提出各个规划特征年的路网规划方案；类似这种由单个初始路网经过多个阶段的演变而衍生成的一系列有着直接或间接派生关系的路网方案可称之为动态路网。在动态路网中，不同路网方案的数据存在大量的重复部分。传统的交通分析软件，对动态路网大多是按多个独立路网建立和分析的。不但造成数据冗余过大，更致命的是掩盖了路网动态演变的过程。基于树结构的方案树可有效描述动态路网的动态性，揭示路网方案之间的联系。方案树的每个结点代表一个路网方案；根结点即为初始路网；连接结点的边代表方案间的直接派生关系；双亲结点即为基础方案，孩子结点即为派生方案，兄

16、弟结点代表了不同的比选方案；树的高度代表动态路网的层次数，一个层次代表动态路网的一个演变阶段。,42,图有向图,有向图G=(N,A)由节点集N和弧集A构成。N中的每个元素i称为节点（或顶点）。A中的每个元素a可由N中的有序节点对(i,j)表示，称为从i到j的弧（或边）对于弧(i,j)，i和j称为a的端点，其中i称为起点，j称为终点，并称j邻接到i 对于弧(i,j)，称(i,j)关联于i和j，称(i,j)为i的出弧、j的入弧 一个节点的出弧的数目称为该节点的出度，入孤的数目称为该节点的入度，出度与入度之和称为该节点的度 起点和终点均相同的2条及2条以上的弧称为多重弧，起点和终点为同一节点的弧称为

17、环。一个无环、无多重弧的有向图称为简单有向图，一个无环、但允许有多重弧的有向图称为多重有向图。没有任何弧与之关联的节点称为孤立点,43,图有向图,节点集N=1,2,3,弧集A=(1,2),(1,3),(2,1),(2,3),(3,2)节点1是弧(1,2)的起点，节点2是该弧的终点，节点2邻接到节点1弧(1,2)关联于节点1和2，弧(1,2)为节点1的出弧、节点2的入弧节点1的出度为2，入度为1，度为3,44,图无向图、网络,无向图的定义类似于有向图，根本的区别在于无向图中组成弧的节点对是无序的，即连接节点i和j的弧既可以记成(i,j)，也可记成(j,i)。有向图的相关概念都可自然地推广到无向图

18、上来，但在涉及方向性的概念时会有一些微小的差异，比如无向图的一条弧的端点不再有起点和终点之分。有向网络就是赋予节点和弧一定数值、权重的有向图，也就是赋权有向图；对应地，无向网络就是赋权无向图。网络和图的区别在于：它不仅代表着一种数学形式，而且具有物理结构。但是，由于图都是可以赋权的，因此在一般场合下，对图和网络的概念都不加细分，两者可以通用。,45,有向图的表示法关联矩阵,有向图G=(N,A)的关联矩阵B是一个nm的矩阵（n为节点数目，m为弧数目），每行对应于一个节点，每列对应于一条弧。若节点i是弧a的起点，则关联矩阵中对应的元素为1；若i是a的终点，则对应的元素为1；若i与a不关联，则对应的

19、元素为0。对于简单图，关联矩阵每列只含有两个非零元（一个1，一个1）。在关联矩阵中，每行元素1的个数正好是对应节点的出度，每行元素1的个数正好是对应顶点的入度。,46,有向图的表示法邻接矩阵,有向图G=(N,A)的邻接矩阵C是一个nn的矩阵，每行、每列均对应一个节点；如果两节点之间有一条弧，则邻接矩阵中对应的元素为1；否则为零。每行元素之和正好是对应节点的出度，每列元素之和正好是对应节点的入度。,47,有向图的表示法邻接表,有向图的邻接表就是所有节点的邻接节点集的列表。邻接表可以用多种数据结构加以实现，通常采用数组加链表的混合形式。在这样的邻接表中，节点存储在数组中，对每个节点用一个单向链表列

20、出该节点的所有邻接节点，链表中每个单元实际对应于一条弧（该弧的起点取决于链表头，终点取决于该单元存储的节点）。,48,有向图的表示法方法比较,有向图的关联矩阵和邻接矩阵的表示法非常简单、直接。但是，在关联矩阵的所有nm个元素中，只有2m个为非零元；在邻接矩阵的所有n2个元素中，只有m个为非零元，它们属于稀疏矩阵。对于比较稀疏的网络（比如交通网络，节点的平均出度在3左右），这两种表示法会浪费大量的存储空间。而邻接表的存储效率最高，只需要n+m个存储单位，尤其适合于稀疏网络。其他的有向图表示法包括：星形表、双向邻接表、邻接多重表等，可参考相关文献。,49,最短路径,求最短路径的Dijkstra算法

21、设有向图G=（V，E），其中，V=0,1，2，n，cost是表示G的邻接矩阵，costij表示有向边的权。若不存在有向边，则costij的权为无穷大。设s是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点1为源点，集合初态s0。数组dist记录从源点到其他各项点当前的最短距离，其初值为disti=cost0i，i=1,2，n。从s之外的顶点集合V-S中选出一个顶点w，使distw的值最小。于是从源点到达w只通过s中的顶点，把w加入集合s中，调整dist中从源点到V-S中每个顶点v的距离：distv=mindistv，dist(w)+costwv,50,最短路径,

22、重复上述过程，直到s中包含v中其余各项点的最短路径。最终结果是：s记录了存在从源点到达的路径的顶点集合，数组dist记录了从源点到V中到其余各项点之间的最短路径.,51,Example,52,Answer,53,Answer(Con 1),最后的输出结果如下：132 352 032 15432 3052 1062,54,算法及其复杂度分析,（1）有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。（2）确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出

23、。（3）可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（4）输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。（5）输出：一个算法有一个或多个的输出。这些输出是同输入有着某些特定关系的量。,55,算法及其复杂度分析,通常设计一个“好”的算法应考虑达到以下目标：（1）正确性：算法应当满足具体问题的需求。通常一个大型问题的需求，要以特定的规格说明方式给出，而一个不那么严格的问题至少应当包括对于输入、输出和加工处理等明确的无歧义性的描述。设计或选择的算法应当能正确地反映这种需求。（2）可读性：算法主要是为了人的阅读与交流，其次才是机

24、器执行。可读性好有助于人对算法的理解；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。（3）健壮性：当输入数据非法时，算法也能适当地作出反应或进行处理，而不会产生莫明其妙的输出结果。（4）效率与低存储量需求：通俗地说，效率指的是算法执行时间。存储量需求指算法执行过程中所需要的最大存储空间。一个好算法要有高的执行效率和低的存储量需求。,56,算法及其复杂度分析,通常设计一个“好”的算法应考虑达到以下目标：（1）正确性：算法应当满足具体问题的需求。通常一个大型问题的需求，要以特定的规格说明方式给出，而一个不那么严格的问题至少应当包括对于输入、输出和加工处理等明确的无歧义性的描述。设计或选择的算法应

25、当能正确地反映这种需求。（2）可读性：算法主要是为了人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。（3）健壮性：当输入数据非法时，算法也能适当地作出反应或进行处理，而不会产生莫明其妙的输出结果。（4）效率与低存储量需求：通俗地说，效率指的是算法执行时间。存储量需求指算法执行过程中所需要的最大存储空间。一个好算法要有高的执行效率和低的存储量需求。,57,2.2计算机图形学,58,概念,计算机图形学主要研究用计算机及其图形设备来输入、表示、变换、运算和输出图形的原理、算法及系统。图形主要分为两类，一类是基于线条信息表示的，如工程图、

26、等高线地图、曲面的线框图等，另一类是明暗图，也就是通常所说的真实感图形。,59,概念,计算机图形学主要研究用计算机及其图形设备来输入、表示、变换、运算和输出图形的原理、算法及系统。图形主要分为两类，一类是基于线条信息表示的，如工程图、等高线地图、曲面的线框图等，另一类是明暗图，也就是通常所说的真实感图形。,60,图形生成和变换：曲线绘制,规则曲线的绘制最小二乘法拟合三次样条曲线贝齐尔（Bezier）曲线B样条曲线,61,图形生成和变换：曲面绘制,双线性曲面 直纹曲面回转曲面孔思（coons）曲面,62,图形生成和变换：剪裁,平面裁剪（线段裁剪、曲线裁剪和多边形裁剪）分区编码剪裁三维裁剪,图形生

27、成和变换：二维几何变换、三维几何变换等,63,例,64,2.3工程数据库,65,数据库系统基础,数据库是通用化的相关数据的集合，它不仅包括数据本身，而且包括关于数据之间的联系。因此，一个数据库有四个主要成分：数据、联系、约束和模式。数据是所存储的逻辑实体在计算机中的二进制表示；联系表示数据项之间的某种对应；约束是定义正确数据状态的断言；一种模式描述数据库中数据的组织和联系。,66,67,数据库系统基础,模式为数据库管理系统各个组成部分的使用和应用的安全定义数据库的各种视图。模式将数据存储的物理外表与逻辑表示分开。内部模式定义数据在物理数据存储区中如何组织以及放在何处。概念模式按照适当的数据库数

28、据模型（如关系模型或对象模型）定义所存储数据的结构。外部模式为特定用户们定义数据库的一个或多个视图。,68,69,数据库的数据模型层次模型,层次模型是一种基本层次联系的集合，它实际上是一种有根定向的有序树。层次模型的基本结构是树结构根、枝、叶结构，数据存放的基本单位是片断（即层），片断是内在有逻辑联系的一组数据，总的来说，层次模型按照树形结构以片断为单位存放数据。层次模型比较容易实现，但是查找比较麻烦，数据的冗余度也比较大。,70,71,数据库的数据模型网状模型,所谓网状模型是指一个连通的基本层次联系的集合。复杂的网总可以分解成若干个基本结构，即分解成系。系有系主（只有一个）和系属（可以有多个

29、），系主和系属之间有关系，而且关系是双向的。网状模型存放的基本单位是记录，也就是按记录存放，查询时，从系（系主和系属）查起。网状模型查找时间较省，数据和冗余度比层次模型小，但比关系模型要大。,72,73,数据库的数据模型关系模型,关系模型是目前最为流行的数据模型，它是由许多二维关系表组成的集合。下表就是一张关系表，R是关系名，Ai是属性名，关系和属性（R,A1,A2An）组成了数据表的模式；Vij叫做分量，表中的一列是一个属性，相当于一个数据项，一行叫做一个元组，相当于一条记录。,74,75,(中国地图，面积，周长，名称),76,关系表的操作可以分为以下四种：通用的集合操作，如并、交、差运算等

30、；去除关系表的某些部分的操作，包括选择和投影，前者去除某些元组，后者则用于除去某些属性；两个关系表的合并，包括“笛卡尔积”以及各种方式的连接运算；更名操作，即对关系表属性名称的修改，它不改变元组，但是改变了关系表的模式。这些操作以及相关的都是通过结构化查询语言SQL完成的,77,78,数据库的数据模型面向对象模型,网络和层次以及关系模型都适合那些结构简单以及访问有规律的数据。面向对象数据库的引入就是为了满足一再出现的复杂信息的共享。在复杂数据进入数据库以后，数据库提供了存贮信息的统一视图，与具体存贮结构无关。把物理数据结构与逻辑数据结构分开，同时控制数据的共享及保持数据的正确性、完整性和一致性

31、，大大方便了应用程序的开发和维护，减少生命周期内的各种费用。通过一组优化的程序来管理数据，使得整体效果更优，性能更稳定。,79,数据库管理系统,数据库管理系统是为数据库访问提供服务的软件，同时维护所有数据必需的特性。数据库管理系统提供下列服务：1）事务处理有三种特定的事务操作：启动指示将开始一个新事务，提交指示事务已正常终止且其作用结果将持久存在，以及放弃指示事务被异常终止，其所有结果将被放弃。2）并发控制并发控制是一种数据库管理活动，它协调数据库操作进程的并发操作和对共享数据的访问，并且解决它们之间可能发生的潜在冲突。,80,数据库管理系统,3）恢复数据库中恢复的目标是确保异常终止或出错的事

32、务不会对数据库或其它事务产生不利影响。恢复可使得数据库在事务异常终止后返回某个一致状态。4）安全安全是保护数据免受非授权的泄露、更改或破坏。每个用户和应用程序都有特定的数据访问特权。这些过程中最常用的是注册名和口令保护服务。,81,数据库管理系统,5）语言接口提供对用于定义和操作数据的语言的支持。数据定义语言用于描述数据、数据间联系和对数据和联系的约束的表示法；数据操纵语言用于表达数据库上的操作。6）容错性不管发生什么故障仍能继续提供可靠服务的能力称为容错性。恢复与容错性密切相关。,82,数据库管理系统,7）数据目录也称数据字典，是一个系统数据库，含有主数据库中数据的描述。8）存储管理提供数据

33、持久存储的管理机制。,83,84,2.4 软件工程基础,85,软件与软件危机,什么是软件,什么是软件危机,软件 程序,软件危机首次爆发于二十世纪六十年代。在大型程序设计中，人们发现投入大量的人力、物力、时间开发出的软件，其成本、效率、质量等方面却处于失控状态，尤其软件维护异常困难。程序的修改扩充往往需要大量重复性投入。,86,软件危机产生的原因主要有三个：软件开发者不熟悉用户问题的领域，或没有理解用户需求，软件产品与要求不一致。软件是一种逻辑产品而非物理产品，软件的开发过程本质上是人的思考过程。人的智力在面对越来越复杂的问题时，处理问题的效率会越来越低。,软件与软件危机,87,软件工程,软件危

34、机的出现迫使人们重新认识软件和软件开发过程。大型软件开发也应该借鉴建筑、机械等行业的发展过程，由“手工方式”向“工程化”方向发展。1968年在北大西洋公约组织(NATO)的年会上首次提出软件工程的概念，此后又逐步提出软件生命期的概念。,88,软件工程,软件工程的提出和软件的定义,软件是程序、方法、规则、相关文档以及在计算机上运行所必需的数据的集合。而软件工程是开发、运行、维护软件的系统方法。,软件生命期,软件生命期指从开始研制到废弃不用的整个期间，可划分为五个阶段：需求分析、设计、编程、测试和运行维护。,软件的质量标准,正确性 健壮性 可维护性可用性 可重用性 效率等,89,正确性 软件的正确

35、性指的是软件系统在正常条件下能够正确工作，完成规定功能。这是软件的首要指标。例如，要求设计程序，输入一批数据，计算它们的累加和。在这里，正确性就是正确能正确计算累加和。,软件工程,90,健壮性软件的健壮性指的是在意外情况下（如输入数据不合理或某些硬件故障），软件系统仍能适当地工作，并对意外情况进行适当处理，而不致于导致错误结果甚至系统的瘫痪或死机。例如，要求设计程序，根据输入的三边a、b、c的长度判别三角形类型。现有如下设计思想：若a、b、c中只有两个量相等，则为等腰三角形，若三个量均相等，则为等边三角形，否则为一般三角形。如果输入为（-2，-2，-2）时，程序输出为：等边三角形。这个结果显然

36、是错误的。这是由于程序对不合理数据不能进行适当处理，我们就说这个程序的健壮性不好。,软件工程,91,软件工程,可维护性软件的维护包括发现并改正软件的错误，以及由于软件运行环境发生变化或软件功能扩充而对软件进行的改动。软件的可维护性指的是软件容易维护的程度。一般地说，软件的可读性好，容易理解，维护起来也就比较容易。因此可读性是可维护性的基础。,92,软件工程框架,软件工程的目标可以概括为“生产具有正确性、可用性以及开销合宜的产品”，其活动包括需求、设计、实现、确认以及支持等活动，围绕工程设计、支持以及管理，有以下的四条基本原则：选取适宜的开发模型；采用合适的设计方法；提供高质量的工程支持；重视开

37、发过程的管理。,93,软件工程框架,94,软件工程活动需求分析,需求分析阶段处于软件开发的前期，其基本活动是准确定义未来系统的目标，确定为了满足用户的需求必须做什么。需求分析又划分为两个阶段，即需求获取和需求规约，前者是用自然语言清楚地描述用户的要求，而需求规约的目的是消除获取需求的二义性和不一致性。建立需求面临着以下三个方面的困难：问题空间的理解；人与人之间的通信；需求的不断变化。面向对象的分析方法被认为是解决上述困难较好的技术。,95,软件工程活动系统设计,需求分析阶段的主要任务是确定系统“做什么”，而设计阶段则要解决“怎么做”的问题。通常设计阶段又划分为总体设计和详细设计，总体设计确定系

38、统的总体结构框架；而详细设计要具体地描述如何具体地实现系统，通常可以依据详细设计的结果进行编码。详细设计包括：详细的算法；数据表示和数据结构；实施的功能和使用数据之间的关系。,96,软件工程活动实现阶段,在软件实现阶段，要将设计的结果变换成程序设计语言编写的程序。在实现阶段，首先要确定程序设计语言，其影响因素包括：开发人员对语言的熟悉程度，语言的可移植性，编译程序的效率，编译工具的支持等等。目前，C+语言是普遍被采用的构造系统软件的编程语言，而Java则更多地应用于编写网络程序。无论采用哪一种编程语言，都要求编写高质量的源程序代码。,97,软件工程活动确认活动,系统完成后的软件测试是主要的确认

39、活动。软件测试是指按照特定规程，发现软件错误的过程。软件测试的技术大体上可以分为两类，即白盒测试技术和黑盒测试技术，前者依据的是程序逻辑结构，后者依据的是软件行为描述。根据测试的步骤，测试活动又可以划分为单元测试，集成测试，确认测试和系统测试。,98,软件工程活动软件维护,当软件开发完成并交付用户使用后，就进入运行/维护阶段，在运行/维护阶段仍需要对软件进行修改，称为软件维护。软件维护活动可以分为以下几类：正性维护；适应性维护；完善性维护；预防性维护。,99,软件工程活动软件维护,当软件开发完成并交付用户使用后，就进入运行/维护阶段，在运行/维护阶段仍需要对软件进行修改，称为软件维护。软件维护

40、活动可以分为以下几类：正性维护；适应性维护；完善性维护；预防性维护。,100,软件开发过程模型,软件开发模型是软件开发全部过程、活动和任务的结构框架。软件开发模型能够清晰、直观的表达软件开发过程，明确规定要完成的主要活动和任务，可以作为软件项目工作的基础。主要模型有：瀑布模型将各项活动规定为依照固定顺序连接的若干阶段工作，形如瀑布流水 演化模型当开发人员将核心需求实现后，用户提出反馈意见，以支持系统的最终设计和实现 螺旋模型在瀑布模型以及演化模型的基础上，加入风险分析所建立的模型 喷泉模型体现了软件开发过程中所固有的迭代和无间隙的特征,101,面向过程的程序开发方法,传统的程序设计方法可以归结

41、为“程序=算法+数据结构”，将程序定义为处理数据的一系列过程。这种设计方法的着眼点是面向过程的，特点是数据与程序分离，即数据与数据处理分离。结构化程序设计的基本思想是采用自顶向下、逐步细化的设计方法和单入单出的控制结构。,102,103,举一个简单的例子，要求读入一组整数，统计其中正整数和负整数的个数。该任务的模块结构及细化过程如下：,104,这种设计方法的优缺点在于：结构化程序设计可以把一个较为复杂的程序设计任务分解为许多易于控制和处理的子任务，分块解决，具有很大优点。但它把数据和处理数据的过程分离开来，当数据结构改变时，所有相关的处理数据过程都要进行相应的修改，程序的可重用性较差，对大型程

42、序设计很难适应。,105,面向过程程序设计缺点的根源在于数据与数据处理分离。面向对象程序设计模拟自然界认识和处理事物的方法，将数据和对数据的操作方法放在一起，形成一个相对独立的整体对象（object），同类对象还可抽象出共性，形成类（class）。一个类中的数据通常只能通过本类提供的方法进行处理，这些方法成为该类与外部的接口。对象之间通过消息（message）进行通讯。,面向对象的程序开发方法,106,基 本 概 念,调节旋钮,对 象,107,基 本 概 念,是一个抽象的概念，用来描述某一类对象所共有的、本质的属性和行为。,类,108,基 本 概 念,我们把对象之间产生相互作用所传递的信息称做

43、消息。,消 息,启 动,转 向,109,110,“面向对象”程序开发特点,封装性,对象是一个封装体，在其中封装了该对象的属性和操作。通过限制对属性和操作的访问权限，可以将属性“隐藏”在对象内部，对外提供一定的接口，在对象之外只能通过接口对对象进行操作。,封装性增加了对象的独立性，从而保证了数据的可靠性。一个定义完好的类可以作为独立模块使用。,111,“面向对象”程序开发特点,继承与派生,以汽车为例看客观世界描述事物的方式：,当定义了一个类后，又需定义一个新类，这个新类与原来的类相比，只是增加或修改了部分属性和操作，这时可以用原来的类派生出新类，新类中只需描述自己所特有的属性和操作。,面向对象程

44、序设计提供了类似的机制：,继承性大大简化了对问题的描述，大大提高了程序的可重用性，从而提高了程序设计、修改、扩充的效率。,新类称为子类或派生类，原来的类称为基类。派生可以一直进行下去，形成一个派生树。,112,“面向对象”程序开发特点,语文、数学、英语、政治、物理、化学、生物,多态性,多态性指，同一个消息被不同对象接收时，产生不同结果，即实现同一接口，不同方法。,高中生,计 算平均成绩,大学生,高数、英语、计算机、线性代数,113,“面向对象”程序开发特点,继承和多态性组合，可以生成很多相似但又独一无二的对象。继承性使得这些对象可以共享许多相似特性，而多态又使同一个操作对不同对象产生不同表现形

45、式。这样不仅提高了程序设计的灵活性，而且减轻了分别设计的负担。,114,面向对象软件开发的根本合理性在于它符合客观世界的组成方式和大脑的思维方式。在大型程序开发过程中，编码只是其中很小一部分，应当采用工程化的方法，并将面向对象的思想贯穿于软件开发全过程，这就是面向对象的软件工程。面相对象的软件工程同样遵循分层抽象、逐步细化的原则。软件开发过程包括以下五个阶段：分析、设计、编程、测试和维护,面向对象的程序开发过程,115,面向对象的程序开发过程1,面向对象的分析：从问题的陈述开始，逐步建立起客观事物的模型，分析模型中的对象，使得对象的描述与客观事物相一致。相同特性的对象为一类，一般类和特殊类之间

46、有继承关系。面向对象的设计：主要是把在面向对象分析阶段建立的模型，用面向对象的方法产生一个具体实现。包括：把面向对象的分析模型直接到面向对象的设计作为面向对象设计的一部分；针对具体实现中的人机界面、数据存储、任务管理等因素补充一些与实现有关的部分。,116,面向对象的程序开发过程2,面向对象的编程：编程是面向对象的软件开发最终落实的重要阶段。它主要是要用面向对象的语言实现面向对象设计方案中的每个成员。面向对象的调试：调试的任务是发现软件中的错误。以对象的类作为一个基本测试单位，查错范围是类定义之内的属性和服务以及接口所涉及的部分。这样可以更准确地发现错误，提高测试效率。面向对象的维护：软件作为

47、一件产品，无论经过多么严格的测试，总还会存在一些错误。所以，软件的维护是不能省略和停止的。,117,2.5 新技术趋势,118,人工智能,专家系统是人工智能研究中的个重要方面。专家系统与CAD技术的结合，形成设计型的专家系统，又称为智能化CAD。在交通CAE领域中，人工智能和专家系统的应用已成为研究的热点，但要真正能投入实际应用，尚有很多工作要做。国内曾对公路选线专家系统以及用专家系统的方法改进道路CAD系统方面做过探索性研究。,119,由于专家系统工具过分依赖用户或专家人工地将知识输入知识库中，而且分析结果往往带有偏差和错误，再加上耗时、费用高，故不可行。产生了一个新的研究方向基于数据库的知

48、识发现（Knowledge Discovery in Database），以及相应的数据挖掘（Data Mining）理论和技术的研究,数据矿山,信息金块,数据挖掘工具,数据挖掘,120,数据挖掘的发展,121,数据挖掘,数据库技术,统计学,高性能计算,人工智能,机器学习,可视化,数据挖掘是多学科的产物,122,KDD已经成为人工智能研究热点,目前，关于KDD的研究工作已经被众多领域所关注，如过程控制、信息管理、商业、医疗、金融等领域。作为大规模数据库中先进的数据分析工具，KDD的研究已经成为数据库及人工智能领域研究的一个热点。,123,数据挖掘算法,支持向量机 决策树学习 Bayes 分类

49、聚类 主分量分析方法 人工神经网络 EM算法 模糊逻辑 智能优化,124,机器学习,人工智能目前的研究热点是机器学习。机器学习是一种使获取知识自动化的计算方法的学习。机器学习在人工智能的研究中具有十分重要的地位。其应用已遍及人工智能的各个分支，如专家系统、自动推理、自然语言理解、模式识别、计算机视觉、智能机器人等领域。机器学习方法特征选择分类方法决策树人工神经网络与遗传算法支持向量机图论与聚类方法,125,网格技术,网格(Grid)概念源于电力公用网,其基本思想是使用户在应用网格技术时,就像日常生活从电力网中获取电能那样,可以方便地获取网络上高性能的计算能力。根据 Foster和 Kessel

50、man的定义,网格是构筑在互联网上的一组新兴技术,它将高速互联网、计算机、大型数据库、传感器、远程设备等融为一体,为科技人员和普通老百姓提供更多的资源、功能和服务。,126,网格的概念,127,网格计算,网格计算（Grid computing）是利用互联网技术，把分散在不同地理位置的计算机组成一台虚拟超级计算机。,128,IBM的网格远景：现在的计算机,129,未来：因特网是计算机!,130,优势：计算能力强，费用低 在实质上来说“网格计算”是一种分布式应用，网格中的每一台计算机只是完成工作的一个小部分，这样的计算方式就好像是“蚂蚁搬山”，虽然单台计算机的运算能力有限，但成千上万台计算机组合起