软件开发与软件工程

第6讲软件开发与软件工程,1算法(3.3)2程序设计(3.3)3软件工程(补充),开发计算机软件的过程,(1)确定并理解问题(2)寻找解决问题的方法与步骤，并将其表示成算法(algorithm)(3)程序设计：使用某种程序设计语言描述该算法及其处理的对象,并编译成目标程序(4)调试(debug)和运行(run)程序，获得问题的解答(5)进行评估,改进算法和程序,1.算法,什么是算法？算法是解决问题的方法与步骤,例：有三个硬币，其中一个是伪造的，另两个是真的，伪币与真币重量略有不同。现在提供一座天平，如何找出伪币呢？分析：按给定条件进行操作明确而有序地进行共享智能(任何人均可进行),ABC,解决问题必须找到算法！,例1：买鸡问题,公元5世纪末(南北朝)，我国古代数学家张丘建在他所撰写的算经中，提出了这样的一个问题：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”,假设:公鸡数目为x，母鸡数目为y，则小鸡数目为(100-x-y)则：5x+3y+(100-x-y)/3=100，即7x+4y=100这是2元一次不定方程,共有有3组解：(4,18，78)、(8，11，81)、(12，4，84),用“枚举法”解决买鸡问题,假设:公鸡数目为x，母鸡数目为y，则小鸡数目z=100-x-y从x=0,y=0开始，反复检查各种可能的组合是否所求答案：x=0,y=0、x=1,y=0x=100,y=0 x=0,y=1、x=1,y=1x=99,y=1x=0,y=99、x=1,y=99x=0,y=100直到找出全部答案为止！,枚举法也叫做“穷举法”或Brute-force,例2：货郎担问题(TSP-TravelingSalesmanProblem),售货员从城市A出发，到B、C、D等若干城市销售货物。已知各城市之间的距离，要求选择一条旅行路线，使总路程最短。条件：每个城市只能经过一次，最后仍回到出发城市A。,用枚举法解决TSP问题,TSP问题与组合爆炸,4个城市，共有3！=6种路径5个城市，共有4！=24种路径10个城市，共有9！=36万种路径50个城市，有49！=1062路径f(n)=(n1)!2001年解决了15112个城市之间的TSP问题，使用110台计算机，共费时2.5月（组合爆炸）,理论上，枚举法可以解决可计算领域的许多问题实际上，枚举法仅适用于解决一些较小规模的问题,3,3x2,3x2x1,例3：寻找最大数（分治法）,原始数据为：49,38,65,97,76,13、27,分治法的基本思想,例：找最大/最小数；合并排序；矩阵乘法；二分法搜索等,原始问题,规模较小的子问题,例4：迷宫问题(回溯法、试探法),出口,入口,迷宫问题,将问题的候选解按某种顺序逐一检验，在检验过程中取消上一步或几步、再寻找下一个可能候选解的过程叫做“回溯”,Demo,Backtracking,例5：Hanoi塔问题（递归法）,设A,B,C是3个塔座，塔座A上有一叠由小到大叠在一起的n个圆盘，现要求将塔座A上的这一叠圆盘移到塔座C上，并仍按同样顺序叠置。移动规则是：(1)每次只能移动1个圆盘(2)不允许大盘压在小盘上,2个圆盘的情况,一共需要搬动3次！,3个圆盘的情况,一共需要搬动7次！,4个圆盘的情况,一共需要搬动15次！,Hanoi塔问题分析,假定每秒移动一次，一年有31536000秒，则需要花费大约5849亿年的时间假定计算机以1000万次/s的速度进行传送操作，则需要大约58490年的时间若n=100，在运算速度是1012/s（1万亿次/秒），该算法需要运行4x1010年，几乎是宇宙年龄,设圆盘数目为n，移动次数为h(n),则h(n)=2h(n-1)+1=2(2h(n-2)+1)+1=22h(n-2)+2+1=23h(n-3)+22+2+1=2nh(0)+2n-1+22+2+1=2n-1+22+2+1=2n-1当n=64时，需要移动盘子的次数为：264-1=18446744073709551615,即使理论上可以计算的问题，实际上并不一定能解决!,小结：算法设计是解决问题的关键,不同问题往往需要使用不同的算法，客观世界非常复杂，问题是无限的，所以算法也层出不穷！借鉴已有问题的求解算法是设计新算法的“捷径”：枚举法、回溯法、递归法、分治法、迭代法、贪心法、动态规划法，等等设计算法是一项富有挑战性的工作，它既有严格的技术因素，必须进行缜密的思考，又需要丰富的想象力和创新思维，是惟一能使人既成为工程师又成为艺术家的一种工作即使有了算法，也不一定能够解决问题,同一问题往往有多种算法！,例：排序问题(sorting),基本问题:有一组数据(例如整数或字符),把它们按某种规则(例如数值大小或编码顺序)进行排列例:,排序前,1简单排序算法(demo),任给一组未排序的整数重复下面的步骤35,直到未排序的数为空:对未排序的数进行比较选出未排序数中的最小数把最小数移动至已排序数的末尾,2插入排序算法(demo),1任给一组未排序的整数2在第1个数的右面设置1个标记，标记左面为已排序的数，标记右面为未排序的数3重复下面的步骤4至6,直到未排序的部分为空:4选择未排序部分的第1个数5将该数与已排序的数进行比较/交换，直到它到达正确的位置6将标志向右面移动1个位置,初态,6c,3选择排序算法(demo),任给一组未排序的整数在未排序数的左面设置1个标志,以区分已排序部分和未排序部分重复步骤4步骤7,直到未排序部分只剩下1个数为止:对未排序部分的数进行比较从中选择最小的1个数将它与未排序部分的第1个数相互交换位置将标志向右移动1个位置,算法分析：怎样选择合适的算法？,正确：给定有效输入后，经过有限时间的计算，产生正确的输出结果直观、易理解：算法容易理解，容易验证其正确性，程序容易调试快：运行该算法所需要的时间比较少时间复杂性(TimeComplexity)低：省：节省存储空间，额外占用的存储器少空间复杂性(SpaceComplexity)低：,是不是所有问题都有算法？,许多问题迄今还无有效算法！,哥德巴赫猜想语音识别股市预测地震预报长期大范围天气预报,人的认知过程是不是一种算法行为？人类的意识是否就是一种复杂机械计算的表现？人脑是否就是一种机器？,小结,小结1：计算机算法的4个特点,明确性：算法中每一步操作的含义必须清楚明确，无二义性可行性：算法中有待实现的操作都是计算机可执行的，即必须在计算机的能力范围之内有穷性：算法在执行了有限步操作后必须结束算法结束后必须产生输出,小结2：算法是计算机软件的灵魂,计算机的通用性是因为它能运行各种各样的程序，而程序之所以能解决问题，是因为它所体现了正确的算法开发计算机应用的核心是：根据实际问题给出解题的算法，然后再将该算法在计算机上予以实现(即开发成为软件)计算机中处处是算法！例1：Word程序如何在文档中查找用户指定的词语？例2：在Word文档中如何发现拼写错误？例3：Word中的插图如何随意改变其大小？例4：媒体播放器如何把MP3文件转换成动听的音乐？例5：数码相机如何自动进行人脸检测？例6：搜索引擎如何在WWW网中找到用户需要的网页或图片？,Demo-过河,2.程序设计,什么是程序设计语言？程序设计语言的分类程序设计语言处理系统,什么是程序设计语言？,什么是程序？为了用计算机解决某个问题而采用程序设计语言编写的一个指令序列，程序是解决该问题所采用算法的体现什么是程序设计语言？语言的目的是用于通信程序设计语言用于人与计算机之间的通信程序设计语言是由人使用但计算机可以理解的一种语言程序设计语言用于编制程序，表达需要计算机完成什么任务和怎样完成任务，然后交给计算机去完成,程序设计语言填补了人与计算机交流的鸿沟,程序设计语言分类,机器语言：CPU的指令系统就是机器语言，指令用二进制表示，用机器语言编程序,也就是直接使用二进制编写程序，极其困难，工作效率很低汇编语言：用助记符号和十进制数表示机器指令中的操作符与操作数，工作难度略有降低高级程序设计语言：接近人们日常使用的自然语言（主要是英语），容易理解、记忆和使用对使用的符号、词汇、语法和语义等各种语言成分都有严格的规定在不同计算机上可以通用,高级程序设计语言的出现，使程序设计的难度降低，导致了计算机的发展进入新的阶段！,高级程序设计语言的发展,50年代：Fortran，ALGOL60年代：COBOL语言，BASIC语言70年代：Pascal语言，C语言80年代：Ada语言，PROLOG语言，LISP语言90年代起：面向对象语言BASIC、C+、JAVA、C#等,程序设计语言的翻译程序,用途：把使用程序设计语言编写的程序，翻译成为等价的机器语言程序，前者称为源程序，后者称为目标程序,最终用户安装在计算机中使用的软件，都是这些软件的目标程序，用户一般不会得到开发厂商的源程序（源代码）,3.软件工程,3.1软件开发活动3.2软件工程,3.1软件开发活动,软件开发活动的主要内容,1需求分析,需求规格说明(specification)初步用户手册项目开发计划可行性(风险)分析,需求分析,用户的需要(needs),对软件的需求(requirements),使用计算机术语,比较严格的语言,全面理解,准确表达,2软件设计,软件模块划分算法设计数据结构设计用户界面设计,软件设计,需求规格说明(specification),概要设计说明书详细设计说明书,从实现角度出发自顶向下逐步细化(stepwiserefinement),3软件构造,软件构造(程序设计),可执行的软件模块，集成后的软件成品,算法数据结构用户界面,程序设计语言(如C，C+,JAVA,VB等)软件运行平台(使用何种操作系统，向应用程序提供哪些服务。一般通过API（应用程序接口）提供，如Windows系统的API：Win32SDK和MFC类库等)编程和开发工具(集成开发环境；Delphi、C+Builder、VisualStudio；VisualStudio.NET),设计说明书,4软件测试,软件测试,经过测试和修改的软件产品,测试说明书测试工具测试用例和测试数据,可执行的软件模块集成后的软件成品,软件产品测试的重要性,微软产品开发组的人员构成：,2007年嫦娥一号探月卫星：100万行软件，测试软件达160万行！,5软件维护,软件维护内容：改正性维护运行中发现了软件中的错误需要修正适应性维护为适应变化了的软硬件环境，需对软件做适当变更完善(改进)性维护为了满足用户新的业务需求、增强软件功能而需要修改、扩充软件预防性维护为增强系统可靠性和安全性所采取的预防性措施,软件维护,经过修改的软件产品,使用中发现的问题修改后的需求规格说明书,交付的软件产品,软件维护的重要性,在整个软件开发活动中，软件维护的工作量最大，其费用大约是软件开发总成本的2/3左右在整个软件维护阶段的全部工作量中，预防性维护只占很小的比例，而完善性维护占了几乎一半的工作量,小结：软件开发活动的特点,需要多人参与的分阶段进行的工作量很大的智力活动不仅仅是编程序，比编程更重要的是需求分析和软件设计编程不但要熟悉程序语言，还需要熟悉运行平台，掌握编程和开发工具编程需要熟悉应用领域的业务知识测试和编程同样重要投入运行后仍需要提供大量的支持和服务整个开发活动需要精心组织与管理,3.2软件工程,Quiz：,1开发一个典型的软件项目大约需要多少个月？2-3月4-6月8-12月12-24月2包含多少行可执行语句的软件被认为是大型软件？1000行5000行10000行50000行3每年上千亿美元销售额的软件市场中，Office、IE之类的PC常用软件占多少份额？10%25%50%75%4中等规模软件的开发期中每人每天平均开发多少行可执行语句？100行5开发过程中，平均每1000行可执行代码中大约会发现多少个错误？5-1010-2050-60100-1506由用户发现的软件错误大部分是什么原因引起的？编程错误需求理解有误软件集成设计错误,软件规模、工作量与成本,软件规模,软件危机,软件产业滞后于应用的需求和硬件的发展软件开发效率低、成本高，进度和成本难以控制软件质量得不到保证,硬件成本与软件开发、维护费用比例的变化,60%左右的软件项目不能按期完成50%左右软件项目的费用超过预算45%左右软件项目最终无法投入使用29%左右软件项目没有交付软件19%左右的软件项目必须返工才能使用,软件项目失败的原因,“Whenprojectsfail,itsrarelytechnical.”JimJohnson,TheStandishGroup,软件的目标与功能分离(separation)需求不够明确，软件的商务(business)与技术分离，缺乏共同的语言和过程开发过程没有统一的、公认的方法和规范做指导，参与人员自行其是，联系少，不像一个团队开发过程不能灵活改变，测试不充分,Solution?软件工程,什么是软件工程？,1968年提出“软件工程”的概念根据美国IEEE的定义，软件工程是“以系统的、规范的、可以度量的方法应用于软件的开发、运行和维护，以及对这些方法和技术的研究”通俗地说，软件工程是指导软件开发和维护的一门工程学科。它采用工程的概念、原理、技术和方法，把经过实践证明是正确的管理技术和当前能够得到的最好的软件技术与方法结合起来，用于开发和维护软件,软件工程的七条基本原则,按分阶段的生命周期计划严格进行管理坚持进行阶段评审实行严格的产品质量控制采纳现代程序设计技术开发成果应能清楚地进行审查开发小组的人员要少而精承认不断改进软件工程实践的必要性,软件工程的目标,实现软件的工业化生产，提高软件的质量与生产效率，达到：付出较低的开发成本；实现要求的软件功能；取得较好的软件性能；开发的软件易于移植；需要较低的维护费用；按时完成开发任务，及时交付使用,复习题,1什么是算法？算法与程序有何联系和区别？2算法有哪些特点？好的算法有什么要求？3程序设计语言的作用是什么？它有哪些类型？4软件开发过程包含有哪些主要的活动（内容）？5软件工程的含义是什么？其目标是什么？,排序算法使用的基本操作,传送(move)操作把数据移动到另一个位置交换(swap)操作把2个数据相互交换位置比较(compare)操作判定2个数据谁大谁小,计算机中使用多种“语言”,程序设计语言：主要用于描述算法机器语言、汇编语言、高级语言数据描述语言：主要用于描述数据（文档、音乐、图形、图像、视频等）的规范、结构和文件格式HTML、XML、MIDI、MP3、OpenGL、JPEG、MPEG、脚本语言：用于编写嵌入在文档中的程序的程序设计语言VBA、VBScript、JavaScript计算机通信语言（通信协议）：用于描述计算机-计算机之间的会话（请求-应答）的语法和语义HTTP、POP3、SMTP、FTP、Telnet、TCP、IP、数据库语言：用于数据操作，如SQL语言,机器语言,机器语言就是计算机的指令系统指令是使用二进制编码表示的用机器语言编程序,也就是直接使用二进制代码编写程序优点：可以直接被计算机执行缺点：记不住、难理解、效率低、不易维护不同的机器语言程序，相互不兼容现在已不直接用机器语言编制程序！,汇编语言,用助记符号来表示机器指令中的操作符与操作数,优点：操作数直接使用十进制程序相对容易理解,缺点：大型程序难以开发依赖于具体计算机,将383传送到AX寄存器,将545传送到BX寄存器,将BX内容加AX内容，结果在BX中,将1055传送到AX寄存器,将AX内容减BX内容，结果在AX寄存器中,高级程序设计语言,目的：克服汇编语言的缺陷，提高编程和维护的效率特点：接近人们日常使用的自然语言（主要是英语）容易理解、记忆和使用可在不同计算机上通用对使用的符号、词汇、语法和语义等各种语言成分都有严格的规定意义：使程序设计的难度降低，导致了计算机的发展进入新的阶段,3种翻译程序,编译程序与解释程序的区别,解释：解释器直接解释并且执行源语言程序，不产生目标程序（相当于“口译”）编译：把源程序编译为机器语言目标程序后，再由计算机运行（相当于“笔译”）,BASIC、Visua