《ch2 计算机辅助工程基础》由会员分享，可在线阅读，更多相关《ch2 计算机辅助工程基础（139页珍藏版）》请在金锄头文库上搜索。
1、第二章第二章 计算机辅助工程基础计算机辅助工程基础n数据结构和算法n计算机图形学n工程数据库n软件工程n新技术趋势12.1 数据结构和算法2数据结构实际问题数学模型求解算法抽象设计编程解答求解实际问题的一般步骤：3信号相位是指在一个交叉口某个方向的交通流（或几个交通流的组合）同时得到的通行权及被分配得到这些通行权的时间带。在多叉路口需设几个相位才能既使车辆相互之间不冲突而又达到最大的流通呢？交叉口信号相位的设置问题ABCDE假设有如图所示的五叉路，其中C和E为单行道，在路口有13条可行的通路，其中有的可以同时通行而不发生冲突，如AB和EC，而有的在同时通行时一定会冲突，如EB和AD，那末，在该
2、交叉口应如何设置相位？这个问题可以转换成一个图的染色问题。4u在图上以一个圆圈表示一条通路，在不能同时通行的两个圆圈之间画一连线，对图中的圆圈上色，要求同一连线上的两个圆圈不同色且颜色种类最少；u一种解决方案，图中13个圆圈表示13条通路，四种颜色分别表示四个相位。交叉口信号相位的设置问题交叉口信号相位的设置问题 图的染色问题图的染色问题ABCDEABACADBABCBDDADBDCEAEBECEDDCABACADBAEDBCBDEADADBEBEC5数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互
3、之间的关系称为结构。数据结构就是一门研究非数值性程序设计中计算机操作的对象以及它们之间的关系和运算等的学科基本概念6基本概念n数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称n数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理n数据对象：性质相同的数据元素的集合，是数据的一个子集n数据结构：相互之间存在一种或多种特定关系的数据元素的集合7四类基本结构n集合n线性结构n树形结构n网状结构数据元素1数据元素2数据元素1数据元素2数据元素1数据元素2数据元素3数据元素1数据元素2数据元素38线性表n线性表是最常用且最简单的一种数据结
4、构，它是属同一数据对象的n个数据元素的有限序列n若将线性表记为，称ai-1是ai的直接前趋元素，ai+1是ai的直接后继元素n线性表中元素的个数n(n=0)定义为线性表的长度，n=0时称为空表。n在非空表中的每个数据元素都有一个确定的位置，比如ai是第i个数据元素，称i为ai在线性表中的位序9线性表1顺序表顺序表以一组地址连续的存储单元依次存储线性表的数据元素，由此在逻辑上相邻的两个元素在物理位置上也是相邻的。只要给定了存储线性表的起始位置，表中任一数据元素都可以随机存取，因此顺序表是一种随机存取的存储结构。顺序表通常用数组类型来实现.12n-1nai的地址计算函数为：addr(ai)=add
5、r(a1)+(i-1)*d10线性表2链表n链表使用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的，即逻辑上相邻的两个元素在物理位置不一定相邻）。n数据元素ai的存储映象（称为结点）包括两个域：存储数据元素信息的数据域；存储直接后继位置信息的指针域，n个结点链接成一个链表。链表在高级程序语言中可用指针来实现11线性表2链表数据指针数据指针数据指针数据指针数据指针数据指针删除元素数据指针数据指针数据指针添加元素数据指针12栈n栈是限定在表尾进行插入或删除操作的特殊线性表。先进后出的线性表.na1为栈底元素，an为栈顶元素。n栈中元素按a1,a2, an的次序进
6、栈，出栈的第一个元素应为栈顶元素an。13栈基本运算有：n建立一个栈n检查栈中剩余容量n从栈顶推入一个元素n从栈顶取出一个元素n删除一个栈应用举例：常用软件中的撤销与恢复操作14队列n队列是一种先进先出的线性表。n它只允许在表的一端进行插入，而在表的另一端进行删除。在队列中，允许插入的一端叫做队尾，允许删除的一端则称为队首。n假设队列为，n则称a1为队首元素，an为队尾元素。n队中元素按a1,a2, an的次序进入n退出队列也只能按这个次序依次进行。15队列基本运算有：n建立一个队列n检查队列状态n从队尾插入一个元素n从队首删除一个元素n删除一个队列应用举例：生活中的排队16例交叉口仿真系统控
7、制结构n当采用仿真方法分析一系列交叉口所发生的交通状态时，需要采用分时处理技术分别逐个改变每一个交叉口的状态，同时系统整体环境也在发生着一些具有时间先后次序的情况。17树ABCDEFGHn 结点A为树的根，根的每个分支称为子树，子树也是一棵树n 结点子树的根为结点的孩子，如B、C、D为结点A的孩子，而A为B、C、D的双亲n 同一个双亲的孩子之间为兄弟关系，如B、C、Dn 没有孩子的结点为树的叶子，H、F、G、D为树的叶子18树的基本运算n初始化一棵树n得到树的根n得到一个结点的双亲n得到一个结点的兄弟n得到一个结点的孩子n插入子树n删除子树n遍历树遍历树n清空树19特殊的树n二叉树n二叉搜索树
8、n哈夫曼树nB树nAVL树n红-黑树用于具有层次结构的数据的组织、搜索和比较各种特定的树结构被广泛应用于交通CAE软件中，它们可以加快查找的速度和分析处理的效率。 20二叉树n二叉树在树结构的应用中起着非常重要的作用n对二叉树的许多操作算法简单;n而任何树都可以与二叉树相互转换，解决了树的存储结构及其运算中存在的复杂性。n定义：二叉树是由n(n=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。n这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。n二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行
9、区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。21二叉树的5种形式 (a)空二叉树AABABACB (b)根和空的左右子树 (c)根和左子树(d)根和右子树 (e)根和左右子树22在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。 遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。bca(根结点)(右子树)(左子树)由二叉树的递归定义，二叉
10、树的三个基本组成单元是：根结点、左子树和右子树。遍历二叉树23假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为： DLR先（根）序遍历， LDR中（根）序遍历， LRD后（根）序遍历。24先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先序遍历二叉树12345712453725中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。
11、123457425137中序遍历二叉树26后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。123457452731后序遍历二叉树27例题例题例如图（1）所示的二叉树表达式(a+b*(c-d)-e/f)*a/b-dcfe按中序遍历按中序遍历：a+b*c-d-e/f按后序遍历按后序遍历：abcd-*+ef/-按按先序遍历先序遍历：-+a*b-cd/ef 28例题已知一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出这棵二叉树。当前序序列为ABECDFGHIJ，中序序列为EBCDAFHI
12、GJ时，逐步形成二叉树的过程如下图所示：EBCDFHIGJAABEFCDHIGJABEFCDGJHIABEFCDGJHI29树的路径长度（树的路径长度（PL）PL是指从根到其它各结点的路径长度（分支数）之和。0143256(a) PL = 137(b) PL = 150143256730完全二叉树完全二叉树abcdefghijkl完全二叉树各结点的路径长度分别是数列0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4, 其路径长度为前n项之和，具有最小值：31霍夫曼树霍夫曼树具有最小 WPL 的扩充二叉树叫霍夫曼树2 4 5 7 (a) WPL = 36(b) WPL = 4
13、624577524(c) WPL = 35 (霍夫曼树)32霍夫曼树的构造方法霍夫曼树的构造方法 将n个权值视为具有n棵扩充二叉树的森林F，然后重复以下步骤，直到F中只有一棵树为止： 在F中选根的权值最小的两棵作为左右子树构造一棵新的二叉树，其根的权为左右子树根的权值之和。 在F中删除那两棵树，并把新的二叉树加入。33霍夫曼树的构造方法霍夫曼树的构造方法254(a)7， ，(b)2547，6(c)7 ，6254116(d)7254111834霍夫曼编码霍夫曼编码霍夫曼树应用事例霍夫曼树应用事例1、最小冗余编码问题设用0，1码来对一串字符信息进行等长编码： T 00，A 01，D 10，S 11
14、对于信息串“ ATTSTATADT ”所得到的编码为 01,00,00,11,00,01,00,01,10,00 共20位编码字母集合T，A，D，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位，这是最小冗 余编码。35霍夫曼编码霍夫曼编码霍夫曼树应用事例霍夫曼树应用事例2、霍夫曼树编码以字符的频度为权构造霍夫曼树左分支表示0，右分支表示1 从根到各外结点路径上经由的数字序列构成各字符的编码25131510111000TADS363、霍夫曼树编码的优越性是最小
15、冗余码非前缀码码 Ci 不是码 Cj 的前缀 译码简单唯一不断从根开始沿霍夫曼编码树查找。10001110100101100 译码得到的只能是报文串：ATTSTATADT霍夫曼编码霍夫曼编码霍夫曼树应用事例霍夫曼树应用事例37习题n给定权值集合 15, 03, 14, 02, 06, 09, 16, 17 , 构造相应的霍夫曼树, 并计算它的带权外部路径长度。 n假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, c7, c8组成, 各字母在电文中出现的频率分别为5, 25, 3, 6, 10, 11, 36, 4。试为这8个字母设计不等长Huffman编码, 并给出
16、该电文的总码数。38解答1503140206091617F：02031514060916170502031514060916170511()()()0203151409161705110620()02031415091617051106202902031415091617051106202933()0203141509051106202916173349()020315090511062029161733491482()此树的带权路径长度WPL=22939已知字母集c1,c2,c3,c4,c5,c6,c7,c8，频率5,25,3,6,10,11,36,4，则Huffman编码为： c1 c2
17、c3 c4 c5 c6 c7 c8 0110 10 0000 0111 001 010 11 0001 电文总码数为4*5+2*25+4*3+4*6+3*10+3*11+2*36+4*4=25710061393625221771011114365C3C8C5C6C1C4C2C700000001111111解答40例：路网规划在路网规划过程中，需在现状路网的基础上不断改造、完善，由近及远地提出各个规划特征年的路网规划方案；类似这种由单个初始路网经过多个阶段的演变而衍生成的一系列有着直接或间接派生关系的路网方案可称之为动态路网。在动态路网中，不同路网方案的数据存在大量的重复部分。传统的交通分析软件
18、，对动态路网大多是按多个独立路网建立和分析的。不但造成数据冗余过大，更致命的是掩盖了路网动态演变的过程。基于树结构的方案树可有效描述动态路网的动态性，揭示路网方案之间的联系。n方案树的每个结点代表一个路网方案；n根结点即为初始路网；n连接结点的边代表方案间的直接派生关系；n双亲结点即为基础方案，孩子结点即为派生方案，兄弟结点代表了不同的比选方案；n树的高度代表动态路网的层次数，一个层次代表动态路网的一个演变阶段。41图有向图n 有向图G=(N, A) 由节点集N和弧集A构成。N中的每个元素i称为节点（或顶点）。A中的每个元素a可由N中的有序节点对(i, j)表示，称为从i到j的弧（或边）n 对
19、于弧(i, j) ，i和j称为a的端点，其中i称为起点，j称为终点，并称j邻接到in 对于弧(i, j) ，称(i, j)关联于i和j，称(i, j)为i的出弧、j的入弧n 一个节点的出弧的数目称为该节点的出度，入孤的数目称为该节点的入度，出度与入度之和称为该节点的度n 起点和终点均相同的2条及2条以上的弧称为多重弧，起点和终点为同一节点的弧称为环。一个无环、无多重弧的有向图称为简单有向图，一个无环、但允许有多重弧的有向图称为多重有向图。没有任何弧与之关联的节点称为孤立点42图有向图节点集N=1, 2, 3, 弧集A=(1,2), (1,3), (2,1), (2,3), (3,2)节点1是弧
20、(1,2)的起点，节点2是该弧的终点，节点2邻接到节点1弧(1,2)关联于节点1和2，弧(1,2) 为节点1的出弧、节点2的入弧节点1的出度为2，入度为1，度为343图无向图、网络n 无向图的定义类似于有向图，根本的区别在于无向图中组成弧的节点对是无序的，即连接节点i和j的弧既可以记成(i,j) ，也可记成(j,i)。有向图的相关概念都可自然地推广到无向图上来，但在涉及方向性的概念时会有一些微小的差异，比如无向图的一条弧的端点不再有起点和终点之分。n 有向网络就是赋予节点和弧一定数值、权重的有向图，也就是赋权有向图；对应地，无向网络就是赋权无向图。网络和图的区别在于：它不仅代表着一种数学形式，
21、而且具有物理结构。但是，由于图都是可以赋权的，因此在一般场合下，对图和网络的概念都不加细分，两者可以通用。44有向图的表示法关联矩阵有向图G=(N,A)的关联矩阵B是一个nm的矩阵（n为节点数目，m为弧数目），每行对应于一个节点，每列对应于一条弧。若节点i是弧a的起点，则关联矩阵中对应的元素为1；若i是a的终点，则对应的元素为1；若i与a不关联，则对应的元素为0。对于简单图，关联矩阵每列只含有两个非零元（一个1，一个1）。在关联矩阵中，每行元素1的个数正好是对应节点的出度，每行元素1的个数正好是对应顶点的入度。45有向图的表示法邻接矩阵有向图G=(N,A)的邻接矩阵C是一个nn的矩阵，每行、每
22、列均对应一个节点；如果两节点之间有一条弧，则邻接矩阵中对应的元素为1；否则为零。每行元素之和正好是对应节点的出度，每列元素之和正好是对应节点的入度。46有向图的表示法邻接表有向图的邻接表就是所有节点的邻接节点集的列表。邻接表可以用多种数据结构加以实现，通常采用数组加链表的混合形式。在这样的邻接表中，节点存储在数组中，对每个节点用一个单向链表列出该节点的所有邻接节点，链表中每个单元实际对应于一条弧（该弧的起点取决于链表头，终点取决于该单元存储的节点）。47有向图的表示法方法比较有向图的关联矩阵和邻接矩阵的表示法非常简单、直接。但是，在关联矩阵的所有nm个元素中，只有2m个为非零元；在邻接矩阵的所
23、有n2个元素中，只有m个为非零元，它们属于稀疏矩阵。对于比较稀疏的网络（比如交通网络，节点的平均出度在3左右），这两种表示法会浪费大量的存储空间。而邻接表的存储效率最高，只需要n+m个存储单位，尤其适合于稀疏网络。其他的有向图表示法包括：星形表、双向邻接表、邻接多重表等，可参考相关文献。48最短路径求最短路径的求最短路径的DijkstraDijkstra算法算法n设有向图G=（V，E），其中，V=0,1，2，n，cost是表示G的邻接矩阵，costij表示有向边的权。若不存在有向边，则costij的权为无穷大。n设s是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设
24、顶点1为源点，集合初态s0。n数组dist记录从源点到其他各项点当前的最短距离，其初值为disti=cost0i，i=1,2，n。n从s之外的顶点集合V-S中选出一个顶点w，使distw的值最小。于是从源点到达w只通过s中的顶点，把w加入集合s中，调整dist中从源点到V-S中每个顶点v的距离：distv =mindistv，dist(w)+costwv 49最短路径n重复上述过程，直到s中包含v中其余各项点的最短路径。n最终结果是：s记录了存在从源点到达的路径的顶点集合，数组dist记录了从源点到V中到其余各项点之间的最短路径.50Example51Answer52Answer(Con1)n
25、最后的输出结果如下：n13235n20n3215n43230n5210n6253算法及其复杂度分析n（1）有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。n（2）确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。n（3）可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。n（4）输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。n（5）输出：一个算法有一个或多个的输出。这些输出是同输入
26、有着某些特定关系的量。54算法及其复杂度分析n通常设计一个“好”的算法应考虑达到以下目标：n（1）正确性：算法应当满足具体问题的需求。通常一个大型问题的需求，要以特定的规格说明方式给出，而一个不那么严格的问题至少应当包括对于输入、输出和加工处理等明确的无歧义性的描述。设计或选择的算法应当能正确地反映这种需求。n（2 2）可读性：）可读性：算法主要是为了人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。n（3）健壮性：当输入数据非法时，算法也能适当地作出反应或进行处理，而不会产生莫明其妙的输出结果。n（4 4）效率与低存储量需求：）效
27、率与低存储量需求：通俗地说，效率指的是算法执行时间。存储量需求指算法执行过程中所需要的最大存储空间。一个好算法要有高的执行效率和低的存储量需求。55算法及其复杂度分析n通常设计一个“好”的算法应考虑达到以下目标：n（1）正确性：算法应当满足具体问题的需求。通常一个大型问题的需求，要以特定的规格说明方式给出，而一个不那么严格的问题至少应当包括对于输入、输出和加工处理等明确的无歧义性的描述。设计或选择的算法应当能正确地反映这种需求。n（2 2）可读性：）可读性：算法主要是为了人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。n（3）健壮
28、性：当输入数据非法时，算法也能适当地作出反应或进行处理，而不会产生莫明其妙的输出结果。n（4 4）效率与低存储量需求：）效率与低存储量需求：通俗地说，效率指的是算法执行时间。存储量需求指算法执行过程中所需要的最大存储空间。一个好算法要有高的执行效率和低的存储量需求。562.2计算机图形学计算机图形学57概念计算机图形学主要研究用计算机及其图形设备来输入、表示、变换、运算和输出图形的原理、算法及系统。图形主要分为两类，一类是基于线条信息表示的，如工程图、等高线地图、曲面的线框图等，另一类是明暗图，也就是通常所说的真实感图形。58概念计算机图形学主要研究用计算机及其图形设备来输入、表示、变换、运算
29、和输出图形的原理、算法及系统。图形主要分为两类，一类是基于线条信息表示的，如工程图、等高线地图、曲面的线框图等，另一类是明暗图，也就是通常所说的真实感图形。59图形生成和变换：图形生成和变换：曲线绘制规则曲线的绘制最小二乘法拟合三次样条曲线贝齐尔（Bezier）曲线B样条曲线60图形生成和变换：图形生成和变换：曲面绘制双线性曲面直纹曲面回转曲面孔思（coons）曲面61图形生成和变换：图形生成和变换：剪裁平面裁剪（线段裁剪、曲线裁剪和多边形裁剪）分区编码剪裁三维裁剪图形生成和变换：图形生成和变换：二维几何变换、三维几何变换等62例632.3工程数据库工程数据库64数据库系统基础数据库是通用化的
30、相关数据的集合，它不仅包括数据本身，而且包括关于数据之间的联系。因此，一个数据库有四个主要成分：数据、联系、约束和模式。数据是所存储的逻辑实体在计算机中的二进制表示；联系表示数据项之间的某种对应；约束是定义正确数据状态的断言；一种模式描述数据库中数据的组织和联系。65数据库数据库数据联系约束模式66数据库系统基础模式为数据库管理系统各个组成部分的使用和应用的安全定义数据库的各种视图。模式将数据存储的物理外表与逻辑表示分开。内部模式定义数据在物理数据存储区中如何组织以及放在何处。概念模式按照适当的数据库数据模型（如关系模型或对象模型）定义所存储数据的结构。外部模式为特定用户们定义数据库的一个或多
31、个视图。67物理数据库内部模式内部模式外部模式1外部模式1外部模式n68数据库的数据模型层次模型层次模型是一种基本层次联系的集合，它实际上是一种有根定向的有序树。层次模型的基本结构是树结构根、枝、叶结构，数据存放的基本单位是片断（即层），片断是内在有逻辑联系的一组数据，总的来说，层次模型按照树形结构以片断为单位存放数据。层次模型比较容易实现，但是查找比较麻烦，数据的冗余度也比较大。6970数据库的数据模型网状模型所谓网状模型是指一个连通的基本层次联系的集合。复杂的网总可以分解成若干个基本结构，即分解成系。系有系主（只有一个）和系属（可以有多个），系主和系属之间有关系，而且关系是双向的。网状模型
32、存放的基本单位是记录，也就是按记录存放，查询时，从系（系主和系属）查起。网状模型查找时间较省，数据和冗余度比层次模型小，但比关系模型要大。7172数据库的数据模型关系模型关系模型是目前最为流行的数据模型，它是由许多二维关系表组成的集合。下表就是一张关系表，R是关系名，Ai是属性名，关系和属性（R,A1,A2An）组成了数据表的模式；Vij叫做分量，表中的一列是一个属性，相当于一个数据项，一行叫做一个元组，相当于一条记录。73A1A2AjAnV11V12VljVlnVilVi2VijVinVm1Vm2VmjVmn74(中国地图，面积，周长，名称)75关系表的操作可以分为以下四种：n 通用的集合操
33、作，如并、交、差运算等；n 去除关系表的某些部分的操作，包括选择和投影，前者去除某些元组，后者则用于除去某些属性；n 两个关系表的合并，包括“笛卡尔积”以及各种方式的连接运算；n 更名操作，即对关系表属性名称的修改，它不改变元组，但是改变了关系表的模式。这些操作以及相关的都是通过结构化查询语言SQL完成的7677数据库的数据模型面向对象模型网络和层次以及关系模型都适合那些结构简单以及访问有规律的数据。面向对象数据库的引入就是为了满足一再出现的复杂信息的共享。在复杂数据进入数据库以后，数据库提供了存贮信息的统一视图，与具体存贮结构无关。把物理数据结构与逻辑数据结构分开，同时控制数据的共享及保持数
34、据的正确性、完整性和一致性，大大方便了应用程序的开发和维护，减少生命周期内的各种费用。通过一组优化的程序来管理数据，使得整体效果更优，性能更稳定。78数据库管理系统数据库管理系统是为数据库访问提供服务的软件，同时维护所有数据必需的特性。数据库管理系统提供下列服务：1）事务处理有三种特定的事务操作：启动指示将开始一个新事务，提交指示事务已正常终止且其作用结果将持久存在，以及放弃指示事务被异常终止，其所有结果将被放弃。2）并发控制并发控制是一种数据库管理活动，它协调数据库操作进程的并发操作和对共享数据的访问，并且解决它们之间可能发生的潜在冲突。79数据库管理系统3）恢复数据库中恢复的目标是确保异常
35、终止或出错的事务不会对数据库或其它事务产生不利影响。恢复可使得数据库在事务异常终止后返回某个一致状态。4）安全安全是保护数据免受非授权的泄露、更改或破坏。每个用户和应用程序都有特定的数据访问特权。这些过程中最常用的是注册名和口令保护服务。80数据库管理系统5）语言接口提供对用于定义和操作数据的语言的支持。数据定义语言用于描述数据、数据间联系和对数据和联系的约束的表示法；数据操纵语言用于表达数据库上的操作。6）容错性不管发生什么故障仍能继续提供可靠服务的能力称为容错性。恢复与容错性密切相关。81数据库管理系统7）数据目录也称数据字典，是一个系统数据库，含有主数据库中数据的描述。8）存储管理提供数
36、据持久存储的管理机制。82832.4 软件工程基础84软件与软件危机什么是软件什么是软件什么是软件危机什么是软件危机软件 程序 软件危机首次爆发于二十世纪六十年代。在大型程序设计中，人们发现投入大量的人力、物力、时间开发出的软件，其成本、效率、质量等方面却处于失控状态，尤其软件维护异常困难。程序的修改扩充往往需要大量重复性投入。85软件危机产生的原因主要有三个：p软件开发者不熟悉用户问题的领域，或没有理解用户需求，软件产品与要求不一致。p软件是一种逻辑产品而非物理产品，软件的开发过程本质上是人的思考过程。p人的智力在面对越来越复杂的问题时，处理问题的效率会越来越低。软件与软件危机86软件工程软
37、件危机的出现迫使人们重新认识软件和软件开发过程。大型软件开发也应该借鉴建筑、机械等行业的发展过程，由“手工方式”向“工程化”方向发展。1968年在北大西洋公约组织(NATO)的年会上首次提出软件工程的概念，此后又逐步提出软件生命期的概念。87软件工程软件工程的提出和软件的定义 软件是程序、方法、规则、相关文档以及在计算机上运行所必需的数据的集合。而软件工程是开发、运行、维护软件的系统方法。软件生命期软件生命期指从开始研制到废弃不用的整个期间，可划分软件生命期指从开始研制到废弃不用的整个期间，可划分为五个阶段：为五个阶段：需求分析需求分析、设计设计、编程编程、测试测试和和运行维护运行维护。 软件
38、的质量标准正确性正确性 健壮性健壮性 可维护性可维护性可用性可用性 可重用性可重用性 效率等效率等88正确性 软件的正确性指的是软件系统在正常条件下能够正确工作，完成规定功能。这是软件的首要指标。例如，要求设计程序，输入一批数据，计算它们的累加和。在这里，正确性就是正确能正确计算累加和。软件工程89健壮性软件的健壮性指的是在意外情况下（如输入数据不合理或某些硬件故障），软件系统仍能适当地工作，并对意外情况进行适当处理，而不致于导致错误结果甚至系统的瘫痪或死机。例如，要求设计程序，根据输入的三边a、b、c的长度判别三角形类型。现有如下设计思想：若a、b、c中只有两个量相等，则为等腰三角形，若三个
39、量均相等，则为等边三角形，否则为一般三角形。如果输入为（-2，-2，-2）时，程序输出为：等边三角形。这个结果显然是错误的。这是由于程序对不合理数据不能进行适当处理，我们就说这个程序的健壮性不好。软件工程90软件工程可维护性软件的维护包括发现并改正软件的错误，以及由于软件运行环境发生变化或软件功能扩充而对软件进行的改动。 软件的可维护性指的是软件容易维护的程度。一般地说，软件的可读性好，容易理解，维护起来也就比较容易。因此可读性是可维护性的基础。 91软件工程框架软件工程的目标可以概括为“生产具有正确性、可用性以及开销合宜的产品”，其活动包括需求、设计、实现、确认以及支持等活动，围绕工程设计、
40、支持以及管理，有以下的四条基本原则：选取适宜的开发模型；采用合适的设计方法；提供高质量的工程支持；重视开发过程的管理。92软件工程框架93软件工程活动需求分析需求分析阶段处于软件开发的前期，其基本活动是准确定义未来系统的目标，确定为了满足用户的需求必须做什么。需求分析又划分为两个阶段，即需求获取和需求规约，前者是用自然语言清楚地描述用户的要求，而需求规约的目的是消除获取需求的二义性和不一致性。建立需求面临着以下三个方面的困难：问题空间的理解；人与人之间的通信；需求的不断变化。面向对象的分析方法被认为是解决上述困难较好的技术。94软件工程活动系统设计需求分析阶段的主要任务是确定系统“做什么”，而
41、设计阶段则要解决“怎么做”的问题。通常设计阶段又划分为总体设计和详细设计，总体设计确定系统的总体结构框架；而详细设计要具体地描述如何具体地实现系统，通常可以依据详细设计的结果进行编码。详细设计包括：详细的算法；数据表示和数据结构；实施的功能和使用数据之间的关系。95软件工程活动实现阶段在软件实现阶段，要将设计的结果变换成程序设计语言编写的程序。在实现阶段，首先要确定程序设计语言，其影响因素包括：开发人员对语言的熟悉程度，语言的可移植性，编译程序的效率，编译工具的支持等等。目前，C+语言是普遍被采用的构造系统软件的编程语言，而Java则更多地应用于编写网络程序。无论采用哪一种编程语言，都要求编写
42、高质量的源程序代码。96软件工程活动确认活动系统完成后的软件测试是主要的确认活动。软件测试是指按照特定规程，发现软件错误的过程。软件测试的技术大体上可以分为两类，即白盒测试技术和黑盒测试技术，前者依据的是程序逻辑结构，后者依据的是软件行为描述。根据测试的步骤，测试活动又可以划分为单元测试，集成测试，确认测试和系统测试。97软件工程活动软件维护当软件开发完成并交付用户使用后，就进入运行/维护阶段，在运行/维护阶段仍需要对软件进行修改，称为软件维护。软件维护活动可以分为以下几类：正性维护；适应性维护；完善性维护；预防性维护。98软件工程活动软件维护当软件开发完成并交付用户使用后，就进入运行/维护阶
43、段，在运行/维护阶段仍需要对软件进行修改，称为软件维护。软件维护活动可以分为以下几类：正性维护；适应性维护；完善性维护；预防性维护。99软件开发过程模型软件开发模型是软件开发全部过程、活动和任务的结构框架。软件开发模型能够清晰、直观的表达软件开发过程，明确规定要完成的主要活动和任务，可以作为软件项目工作的基础。主要模型有：n瀑布模型将各项活动规定为依照固定顺序连接的若干阶段工作，形如瀑布流水n演化模型当开发人员将核心需求实现后，用户提出反馈意见，以支持系统的最终设计和实现n螺旋模型在瀑布模型以及演化模型的基础上，加入风险分析所建立的模型n喷泉模型体现了软件开发过程中所固有的迭代和无间隙的特征1
44、00面向过程的程序开发方法传统的程序设计方法可以归结为“程序=算法+数据结构”，将程序定义为处理数据的一系列过程。这种设计方法的着眼点是面向过程的，特点是数据与程序分离，即数据与数据处理分离。结构化程序设计的基本思想是采用自顶向下、逐步细化的设计方法和单入单出的控制结构。101模块模块 22.12.2模块模块 11.21.11.31.3.11.3.21.3.3模块模块 33.13.23.1.13.1.2 程程 序序102举一个简单的例子，要求读入一组整数，统计其中正整数和负整数的个数。该任务的模块结构及细化过程如下：1.1.读入数据读入数据2.2.统计正数、负数统计正数、负数的个数的个数; ;
45、 3. 输出结果输出结果 2.1 2.1 如数大于如数大于0 0，正整数个数加，正整数个数加1 12.2 2.2 如数小于如数小于0 0，负整数个数加，负整数个数加1 12.3: 2.3: 取下一个整数取下一个整数正整数个数为正整数个数为0 0；负整数个数；负整数个数0 0 取取第一个整数第一个整数重复重复至统至统计完计完103这种设计方法的优缺点在于：u结构化程序设计可以把一个较为复杂的程序设计任务分解为许多易于控制和处理的子任务，分块解决，具有很大优点。u但它把数据和处理数据的过程分离开来，当数据结构改变时，所有相关的处理数据过程都要进行相应的修改，程序的可重用性较差，对大型程序设计很难适
46、应。104面向过程程序设计缺点的根源在于数据与数据处理分离。面向对象程序设计模拟自然界认识和处理事物的方法，将数据和对数据的操作方法放在一起，形成一个相对独立的整体对象（object），同类对象还可抽象出共性，形成类（class ）。一个类中的数据通常只能通过本类提供的方法进行处理，这些方法成为该类与外部的接口。对象之间通过消息（message）进行通讯。面向对象的程序开发方法105基基 本本 概概 念念属性属性行为行为表针表针旋钮旋钮其他机械机构其他机械机构调节旋钮调节旋钮对 象106基基 本本 概概 念念是一个抽象的概念，用来描述某一类对象所共是一个抽象的概念，用来描述某一类对象所共有的、
47、本质的属性和行为。有的、本质的属性和行为。 类类类的一个具体实现，称为实例类的一个具体实现，称为实例闹钟闹钟 一只闹钟一只闹钟类类 对象对象描述这类对象共有的、本质的属性和行为描述这类对象共有的、本质的属性和行为闹钟共有的属性（表针、旋钮、内部结构）闹钟共有的属性（表针、旋钮、内部结构）和行为（调节旋钮）和行为（调节旋钮）具体到一只圆形的或方形的闹钟具体到一只圆形的或方形的闹钟107基基 本本 概概 念念我们把对象之间产生我们把对象之间产生相互作用相互作用所传递的所传递的信息信息称做消息。称做消息。消消 息息启启 动动发送消息发送消息接收并响应消息接收并响应消息转转 向向108对象对象类类计计
48、算算机机世世界界实体实体抽象类别抽象类别现实世界现实世界客观世界客观世界抽象抽象抽象抽象实实例例化化映射映射主观世界主观世界对象、实体与类对象、实体与类109“面向对象面向对象”程序开发特点程序开发特点封装性封装性内内外外机机械械零零件件动动作作调调节节旋旋钮钮读读表表盘盘对象是一个封装体，在其中封装了该对象是一个封装体，在其中封装了该对象的属性和操作。通过限制对属性和操对象的属性和操作。通过限制对属性和操作的访问权限，可以将属性作的访问权限，可以将属性“隐藏隐藏”在对在对象内部，对外提供一定的接口，在对象之象内部，对外提供一定的接口，在对象之外只能通过接口对对象进行操作。外只能通过接口对对象
49、进行操作。封装性增加了封装性增加了对象的独立性对象的独立性，从而保，从而保证了证了数据的可靠性数据的可靠性。一个定义完好的类。一个定义完好的类可以作为可以作为独立模块独立模块使用。使用。110汽车汽车客车客车货车货车小轿车小轿车大客车大客车载货载货载人载人小，速度快小，速度快大，速度慢大，速度慢“面向对象面向对象”程序开发特点程序开发特点继承与派生继承与派生以以汽车为例看客观世界描述事物的方式：汽车为例看客观世界描述事物的方式：当定义了一个类后，又需定义当定义了一个类后，又需定义一个新类，这个新类与原来的类一个新类，这个新类与原来的类相比，只是增加或修改了部分属相比，只是增加或修改了部分属性和
50、操作，这时可以用原来的类性和操作，这时可以用原来的类派生出新类，新类中只需描述自派生出新类，新类中只需描述自己所特有的属性和操作。己所特有的属性和操作。面向对象程序设计提供了类似的机制：面向对象程序设计提供了类似的机制：继承性大大简化了对问题的描述，大大提高了程序的可重继承性大大简化了对问题的描述，大大提高了程序的可重用性，从而提高了程序设计、修改、扩充的效率。用性，从而提高了程序设计、修改、扩充的效率。新类称为子类或派生类，原来的类称为基类。派生可以一直新类称为子类或派生类，原来的类称为基类。派生可以一直进行下去，形成一个派生树。进行下去，形成一个派生树。111“面向对象面向对象”程序开发特
51、点程序开发特点语文、数学、英语、政治、语文、数学、英语、政治、物理、化学、生物物理、化学、生物多态性多态性多多态性指，同一个消息被不同对象接收时，产态性指，同一个消息被不同对象接收时，产生不同结果，即实现同一接口，不同方法。生不同结果，即实现同一接口，不同方法。高中生计计 算算平均成绩平均成绩大学生高数、英语、计算机、线高数、英语、计算机、线性代数性代数112“面向对象面向对象”程序开发特点程序开发特点继承和多态性组合，可以生成很多相继承和多态性组合，可以生成很多相似但又独一无二的对象。继承性使得这似但又独一无二的对象。继承性使得这些对象可以共享许多相似特性，而多态些对象可以共享许多相似特性，
52、而多态又使同一个操作对不同对象产生不同表又使同一个操作对不同对象产生不同表现形式。这样不仅提高了程序设计的灵现形式。这样不仅提高了程序设计的灵活性，而且减轻了分别设计的负担。活性，而且减轻了分别设计的负担。113面向对象软件开发的根本合理性在于它符合客观世界的组成方式和大脑的思维方式。在大型程序开发过程中，编码只是其中很小一部分，应当采用工程化的方法，并将面向对象的思想贯穿于软件开发全过程，这就是面向对象的软件工程。面相对象的软件工程同样遵循分层抽象、逐步细化的原则。软件开发过程包括以下五个阶段：分析、设计、编程、测试和维护面向对象的程序开发过程114面向对象的程序开发过程1面向对象的分析：从
53、问题的陈述开始，逐步建立起客观事物的模型，分析模型中的对象，使得对象的描述与客观事物相一致。相同特性的对象为一类，一般类和特殊类之间有继承关系。面向对象的设计：主要是把在面向对象分析阶段建立的模型，用面向对象的方法产生一个具体实现。包括：把面向对象的分析模型直接到面向对象的设计作为面向对象设计的一部分；针对具体实现中的人机界面、数据存储、任务管理等因素补充一些与实现有关的部分。115面向对象的程序开发过程2面向对象的编程：编程是面向对象的软件开发最终落实的重要阶段。它主要是要用面向对象的语言实现面向对象设计方案中的每个成员。面向对象的调试：调试的任务是发现软件中的错误。以对象的类作为一个基本测
54、试单位，查错范围是类定义之内的属性和服务以及接口所涉及的部分。这样可以更准确地发现错误，提高测试效率。 面向对象的维护：软件作为一件产品，无论经过多么严格的测试，总还会存在一些错误。所以，软件的维护是不能省略和停止的。1162.5 新技术趋势新技术趋势117人工智能n专家系统是人工智能研究中的个重要方面。专家系统与CAD技术的结合，形成设计型的专家系统，又称为智能化CAD。n在交通CAE领域中，人工智能和专家系统的应用已成为研究的热点，但要真正能投入实际应用，尚有很多工作要做。国内曾对公路选线专家系统以及用专家系统的方法改进道路CAD系统方面做过探索性研究。118n由于专家系统工具过分依赖用户
55、或专家人工地将知识输入知识库中，而且分析结果往往带有偏差和错误，再加上耗时、费用高，故不可行。n产生了一个新的研究方向n基于数据库的知识发现（Knowledge Discovery in Database），以及相应的数据挖掘（Data Mining）理论和技术的研究数据矿山数据矿山信息金块信息金块数据挖掘工具数据挖掘工具数据挖掘119数据挖掘的发展数据挖掘的发展1988Expert Systems19951990Expert Systems2004120数据挖掘数据库技术统计学高性能计算人工智能机器学习可视化数据挖掘是多学科的产物121KDD已经成为人工智能研究热点n目前，关于KDD的研究工
56、作已经被众多领域所关注，如过程控制、信息管理、商业、医疗、金融等领域。 n作为大规模数据库中先进的数据分析工具，KDD的研究已经成为数据库及人工智能领域研究的一个热点。122数据挖掘算法 支持向量机支持向量机 决策树学习决策树学习 Bayes Bayes 分类分类 聚类聚类 主分量分析方法主分量分析方法 人工神经网络人工神经网络 EMEM算法算法 模糊逻辑模糊逻辑 智能优化智能优化123机器学习n人工智能目前的研究热点是机器学习。机器学习是一种使获取知识自动化的计算方法的学习。机器学习在人工智能的研究中具有十分重要的地位。其应用已遍及人工智能的各个分支，如专家系统、自动推理、自然语言理解、模式
57、识别、计算机视觉、智能机器人等领域。n机器学习方法n特征选择n分类方法n决策树n人工神经网络与遗传算法n支持向量机n图论与聚类方法n124网格技术n网格(Grid)概念源于电力公用网,其基本思想是使用户在应用网格技术时,就像日常生活从电力网中获取电能那样,可以方便地获取网络上高性能的计算能力。根据Foster和Kesselman的定义,网格是构筑在互联网上的一组新兴技术,它将高速互联网、计算机、大型数据库、传感器、远程设备等融为一体,为科技人员和普通老百姓提供更多的资源、功能和服务。125网格的概念126网格计算n网格计算（Gridcomputing）是利用互联网技术，把分散在不同地理位置的计
58、算机组成一台虚拟超级计算机。127IBM的网格远景：现在的计算机的网格远景：现在的计算机128未来：因特网是计算机未来：因特网是计算机!129n优势：计算能力强，费用低计算能力强，费用低在实质上来说“网格计算”是一种分布式应用，网格中的每一台计算机只是完成工作的一个小部分，这样的计算方式就好像是“蚂蚁搬山”，虽然单台计算机的运算能力有限，但成千上万台计算机组合起来的计算能力就可以和超级计算机相比了。130网格计算的功能特点n高宽带高宽带：主干网络计划的带宽一般都在1Gbpsn计算速度，处理速度高：计算速度，处理速度高：n可动态的调动资源，而且能够有效的共享资源可动态的调动资源，而且能够有效的共
59、享资源n网上社区增多，地球村指日可待网上社区增多，地球村指日可待n可根据用户的要求自动地生产知识，使合作解可根据用户的要求自动地生产知识，使合作解决问题的能力大大提高决问题的能力大大提高131虚拟现实n虚拟现实（Virtual Reality，VR)是近年来出现的高新技术，也称灵境技术或人工环境。虚拟现实中的“现实”是泛指在物理意义上或功能意义上存在于世界上的任何事物或环境，它可以是实际上可实现的，也可以是实际上难以实现的或根本无法实现的。而“虚拟”是指用计算机生成的意思。n虚拟现实是用计算机生成逼真的三维视、听、嗅觉等感觉，使人作为参与者通过适当装置，自然地对虚拟世界进行体验和交互作用。该技
60、术集成了计算机图形技术、计算机仿真技术、人工智能、传感技术、显示技术、网络并行处理等技术的最新发展成果，是一种由计算机技术辅助生成的高技术模拟系统。n虚拟现实主要有三方面的含义：（1）虚拟现实是借助于计算机生成逼真的实体，“实体”是对于人的感觉（视、听、触、嗅）而言的；（2）用户可以通过人的自然技能与这个环境交互，自然技能是指人的头部转动、眼动、手势等其他人体的动作；（3）虚拟现实往往要借助于一些三维设备和传感设备来完成交互操作。132虚拟现实在规划领域的应用范围n虚拟现实在规划信息存储和查询系统中的应用n例如土质数据库系统，地域信息系统，地理信息系统，城市政策信息系统等。这一类系统多采用数据
61、库系统的形式。现行数据库的一个缺陷在于数字化程度高，可视化程度低，这种数据表现出来是抽象的，可接受性差，例如，地理信息系统对地形地貌的表现，n如果只是由数字来表现，则可读性很差，n如果表现为地形图的形式，则相对容易接受。n而采用虚拟现实技术，在系统中输入地形、地貌的数据，则可以从不同的角度去观察，不但可以取得必要的数据，而且能够有直观的感受，不用再劳神费力地想象地形图所表现的实际地形情况。133虚拟现实在规划领域的应用范围n虚拟现实在规划的辅助表现集成系统中的应用虚拟现实在规划的辅助表现集成系统中的应用n例如景观表现系统，交通规划系统等。目前，景观表现系统其表现物段主要是二维的图片，如果能够让
62、用户产生一种身临其境“人在画中游”的感觉，则景观的规划将更加科学合理、全面，而这种身临其境的感觉，正是虚拟现实技术要解决的问题。n应用于景观表现的虚拟现实系统已经开始试用，德国的Frankfort的中心城市，最近将城市模型输入虚拟环境，这一系统可以让人得到在其中漫游的感觉，以后还可望在此基础继续修正。134虚拟现实在规划领域的应用范围n虚拟现实规划和建筑设计可行性论证系统中的应用n目前，规划和建筑方案的设计还处在一个凭主观想象和经验基础上及抽象数据模型基础上的，而且对规划和建筑设计方案的可行性没有一个系统的评价论证，因此，在城市建设过程中，很容易出现实际情况跟预期效果偏差很大的情况，并且，这样
63、造成的损失是无法挽回的。n如果，利用虚拟技术对须控制的要素（周围环境、建筑高度、建筑体量、建筑色调等）对项目建成前后进行描绘，从而发现设计中的不完善的部分，反复修改，再根据修改后的参数虚拟现实，直到在虚拟现实中达到预期效果，这样就可减少甚至杜绝实际建成效果与设计意图偏差很大的情况。135虚拟现实在规划领域的应用范围n虚拟现实在规划管理辅助决策系统中的应用n目前，国内规划和建筑项目的审批辅助决策大多是两条途径：1、对于一般项目规划管理者参考国家或地方性技术规定来决定项目的可行性2、规划管理对于重大项目的审批通过设计单位撰写项目可行性研究报告书和组织专家评审等办法来决定项目的可行性。n上述规划辅助
64、决策的两条途径都有它的局限性。完全根据国家或地方性技术规定来决定项目的可行性显得太僵化，它不一定适应于城市的每一地块和每一个项目。对于重大项目的审批，专家的意见也是根据自己的经验和个人的爱好，也没有一个科学的根据。因此，规划管理、决策者需要一个决策的可靠依据。而虚拟现实技术则可通过模拟仿真为规划管理者决策提供有力、可靠依据。136虚拟现实137数字地球n数字地球的概念最早出现于1997年下半年，1998年美国副总统戈尔在一次演讲中将数字地球正式提了出来。n严格地讲，数字地球是以计算机技术、多媒体技术和大规模存储技术为基础，以宽带网络为纽带运用海量地球信息对地球进行多分辨率、多尺度、多时空和多种
65、类的三维描述，并利用它作为工具来支持和改善人类活动和生活质量。n通俗地讲，就是要求地球上的信息全部实现数字化，用数字的方法将地球、地球上的活动及整个地球环境的时空变化装入电脑中，实现在网络上的流通，并使之最大限度地为人类的生存、可持续发展和日常的工作、学习、生活、娱乐服务。138数字城市n数字城市是将城市地理、资源、环境、人口、经济、社会社情和各种社会服务等复杂系统进行数字化、网络化、虚拟仿真、优化决策支持和可视化。通过宽带多媒体信息网络、地理信息系统、虚拟现实技术等基础技术，整合城市信息资源，构建基础信息平台，建立电子政务、电子商务等信息系统和信息化社区，实现全市国民经济信息化和社会公众服务信息化数字化。139
