Algorithms.ppt

《Algorithms.ppt》由会员分享，可在线阅读，更多相关《Algorithms.ppt（107页珍藏版）》请在麦多课文档分享上搜索。

1、Algorithms,Chapter 8,天津大学软件学院,8.1 CONCEPT,INFORMAL DEFINITION Algorithm（算法）: a step-by-step method for solving a problem or doing a task.（逐步解决问题或完成任务的方法）In this definition, an algorithm is independent of the computer system（独立于计算机系统). More specifically, we should also note that the algorithm accepts

2、 a list of input data and creates a list of output data.（输入一组数据，产生一组输出数据）,Finding the largest integer among five integers,Input The algorithm accepts the list of five integer as input. Processing The algorithm uses five steps to find the largest integer.Output Because there are no more integers to b

3、e processed, the algorithm outputs the value of Largest, which is 13.,DEFINING ACTIONS,REFINEMENT,GENERALIZATION,8.2 THREE CONSTRUCTS,判断,顺序,循环,8.3 ALGORITHM REPRESENTATION,FLOWCHART（流程图）A flowchart is a pictorial representation of an algorithm. It shows how the algorithm flows from beginning to end.

4、,PSEUDOCODE（伪代码）Pseudocode is an Englishlike representation of an algorithm. It is part English and part structured code.（类似英语的表示方法）,Write an algorithm in pseudocode that finds the average of two numbers.,AverageOfTwoInput: Two numbers Add the two numbers Divide the result by 2 Return the result by

5、step 2End,Algorithm 8.1:,Average of two,8.4 MORE FORMAL DEFINITION,Algorithm: an ordered set of unambiguous steps that produces a result and terminates in a finite time（一组明确步骤的有序集合，它产生结果并在有限时间内终止）.ORDERED SET（有序集合） An algorithm must be a well-defined, ordered set of instruction.UNAMBIGUOUS STEPS （明确

6、步骤） Each algorithm must be clearly and unambiguously defined. PRODUCE A RESULT （产生结果） An algorithm must produce a result; otherwise, it is useless. The result can be data that are returned to the calling algorithm or same other effect (e.g., printing). TERMINATE IN A FINITE TIME（在有限时间内终止）An algorith

7、m must terminate (halt). If it does not (e.g., has an infinite loop), you have not created an algorithm.,8.5 SUBALGORITHMS（子算法）,The principles of structured programming, require that an algorithm be broken into small units called subalgorithms (the terms subprograms, subroutines, procedures, functio

8、n, methods, and modules are also used). Each subalgorithm is in turn divided into smaller subalgorithms. The process continues until the subalgorithms become intrinsic (understood immediately).,FindLargestInput: A list of positive integers Set Largest to 0 while (more integers) 2.1 FindLarger End wh

9、ile Return LargestEnd,Algorithm 8.6:,Find largest,FindLargerInput: Largest and current integer if (the integer is greater than Largest) then 1.1 Set Largest to the value of the integer End if End,8.6 BASIC ALGORITHMS,Summation,Product,Search concept,Example of a sequential search（顺序查找）,Example of a

10、binary search（折半查找）,Example of bubble sort（冒泡排序）,Bubble sort,Selection sort 选择排序,Insertion sort 插入排序,Correctness and Efficiency,two that should linger in your mind as you develop algorithms on your own: Correctness（正确性） Efficiency（效率）,Graph of the worst-case analysis of the insertion sort algorithm,

11、Graph of the worst-case analysis of the binary search algorithm,Data Structures,天津大学软件学院,Chapter 11,A data structure uses a collection of related variables that can be accessed individually or as a whole. In other words, a data structure represents a set of data items with a specific relationship be

12、tween then.数据结构使用相关变量的集合，这些变量能够单独或作为整体被访问。数据结构代表了有特殊关系的数据的集合。,ARRAYS（数组）,Imagine you have a problem that requires 20 numbers to be processed. You need to read them, process them, and print them. You must also keep these 20 numbers in memory for the duration of the program.,数组：有固定大小的、相同数据类型元素的顺序集合,TW

13、O-DIMENSIONAL ARRAY（二维数组）,RECORDS（记录）,A record is a collection of related elements, possibly of different types, having a single name. Each element in a record is called a field（域）. A field is the smallest element of values, which in turn can be accessed for selection or manipulation. A field differ

14、s from a variable primarily in that it is part of a record.,记录是一组相关元素的集合，它们的类型可能不同，整个记录有一个名字 域是具有含义的命名数据的最小元素 域不同于变量，它是记录的一部分； 数组中所有元素都是同一类型的；记录中的元素是相同或不同的类型,Linear list（线性列表）具有顺序结构，每个元素都有唯一的后继元素,Categories of linear lists,广义表对处理列表的操作没有任何限制，数据可在任意地方进行插入和删除操作,Insertion in a linear list,Deletion from

15、a linear list,Retrieval from a linear list（检索）,Traversal of a linear list（遍历）,LINKED LISTS（链表）,A linked list is an ordered collection of data in which each element contains the location of the next element; that is, each element contains two parts: data and link.,链表是一个有序数据的集合，每个元素包含下个元素的地址,带有头指针的Pli

16、st链表,空链表,Queue representation（队列）,插入（入列）,删除（出列）,Enqueue operation,Dequeue operation,Three representations of a stack（堆栈）,Pop operation in a stack,Push operation in a stack,Representation of a tree（树）,Directed and undirected graphs（有向图和无向图）,Databases,Chapter 14,天津大学软件学院,14.1 DATABASE MANAGEMENT SYSTE

17、M,A database management system (DBMS) defines, creates, and maintains a database. The DBMS also allows users controlled access to data in the database数据库管理系统是定义、创建、维护数据库的一种工具，也允许用户控制数据库中数据的存取. A DBMS is a combination of five components: hardware, software, data, users, and procedures.,A database is

18、a collection of data that is logically, but not necessarily physically, coherent. 数据库是数据在逻辑上的集合,DBA,涉及到的课程,数据结构 算法分析 数据库原理数据库应用技术 数据仓库与数据挖掘,作业,8-168-23 11-2， 11-17，11-18， 11-20，11-2211-30 12-1912-23 14-1814-22,Software Engineering,Chapter 10,天津大学软件学院,SOFTWARE LIFE CYCLE （软件生命周期）,开发系统,过时吗？,使用该系统,修正该系

19、统,ANALYSIS PHASE （分析阶段）The development process starts with the analysis phase, which shows what the package should do显示程序应该做什么. In this phase, the systems analyst defines requirements that specify what the proposed system is to accomplish系统分析员定义需求，指出系统所要实现的目标. The requirements are usually stated in

20、terms that the user understands.,Define the User（定义用户） A software package may be designed for a generic user or a specific user. The user of the package must be clearly defined.Define the Needs（定义要求） In this step, the best answer comes from the user. The user, or the representative of the user, clea

21、rly defines his/her expectations of the package. Define the Requirements （定义需求） Based on the needs of the user, the analyst can exactly define the requirements for the system.Define the Methods（定义方法） Finally, after the requirements are defined in clear terms, the analyst can choose the appropriate m

22、ethods to meet those requirements.,ANALYSIS PHASE （分析阶段）,DESIGN PHASE （设计阶段）The design phase defines how the system will accomplish what was defined in the analysis phase.定义系统如何完成在分析阶段所定义的需求 In the design phase, the systems are determined, and the design of the files and/or the databases is complete

23、d. 完成文件和数据库的设计Modularity （模块化） The whole package is divided into small modules. Each module is designed and tested and is linked to other modules through a main program. Tools The design phase uses several tools, the most common being a structure chart（结构图）. A structure chart shows how to break your

24、 package into logical steps; each step is a separate module. The structure chart also shows the interaction between all the parts (modules).,IMPLEMENTATION PHASE （实现阶段）In this phase, you create the actual programs. Tools This phase uses several tools to show the logical flow of the programs before t

25、he actual writing of code. 在编码之前使用工具来显示程序的逻辑流程One tool, still popular, is the flowchart. A flowchart uses standard graphical symbols to represent the logical flow of data through a module.The second tool used by programmers is pseudocode. Pseudocode is part English and part program logic that descri

26、bes, in precise algorithmic detail, what the program is to do. Coding The choice of the language is based on the efficiency of the language for that particular application.编程语言的选择是基于针对特殊应用程序的效率,TESTING PHASE （测试阶段）The programmers are completely responsible for testing their programs. In large develo

27、pment projects, there are often specialists known as test engineers who are responsible for testing the system as a wholethat is, for testing to make sure all the programs work together. Black Box Testing （黑盒测试） Black box testing gets its name from the concept of testing a program without knowing wh

28、at is inside it and without knowing how it works. In other words the program is like a black box that you cant see into. Black box testing is done by the system test engineer and the user. White Box Testing （白盒测试） White box testing assumes that you know everything about the program. In this case, th

29、e program is like a glass house in which everything is visible. White box testing is the responsibility of the programmer.,10.2 DEVELOPMENT PROCESS MODELS,There are several models for the development process. We discuss the two most common: the waterfall model and the incremental model.WATERFALL MOD

30、EL（瀑布模型）,In this model, the development process flows in only one direction. This means that a phase cannot be started until the previous phase is completed. 前一阶段工作完成后才能开始下一阶段的工作,INCREMENTAL MODEL（增量模型）,In the incremental model, the process is developed in a series of steps. The software group first

31、 completes a simplified version of the whole package but dose not include the details.不包含细节的简化版,This first version usually consists of only the main modules with calls to empty submodules. In the second version, one or more submodules are completed, while the rest are left unfinished (they just comm

32、unicate). The package is tested again to prove that the main module can use these sub-modules without problems. This process continues until all submodules are added.,10.4 QUALITY （质量）,QUALITY FACTORS,优质软件能够满足用户的显示或隐式的需求，文档齐全，符合组织的操作标准，在其开发使用的硬件上高效运行,可操作性,可维护性,可迁移性,10.5 DOCUMENTATION,USER DOCUMENTAT

33、ION SYSTEM DOCUMENTATION,涉及到的课程,软件工程概论 软件人员英语沟通方法 软件需求工程 统一建模语言 软件测试技术 软件开发成熟度模型 软件系统分析与设计软件项目管理,作业,10-1110-16 10-3710-39,艾伦麦席森图灵 Alan Mathison Turing 1912年6月23日1954年6月7日 英国数学家 1931年图灵进入剑桥大学国王学院，毕业后到美国普林斯顿大学攻读博士学位，二战爆发后回到剑桥，后曾协助军方破解德国的著名密码系统Enigma，帮助盟军取得了二战的胜利。 1936年，24岁发表著名论文论可计算数及其在密码问题的应用，提出了“理想计

34、算机”，后人称之为“图林机”。图林通过数学证明得出理论上存在“通用图林机”，这为可计算性的概念提供了严格的数学定义，图林机成为现代通用数字计算机的数学模型，它证明通用数字计算机是可以制造出来的。 1950年的另一篇著名论文Computing Machinery and Intelligence 提出了“计算机能思考吗？” （Can Machine Think?） ，对计算机的人工智能进行了探索，并设计了著名的“图林测验”。至今，每年都有试验的比赛。 1954年图林英年早逝，年仅42岁。,图灵奖：是美国计算机协会（Association for Computing Machinery,ACM）于

35、1966年设立的，又叫“A.M.图灵奖“，专门奖励那些对计算机事业作出重要贡献的个人。其名称取自计算机科学的先驱、英国科学家艾伦图灵，这个奖设立目的之一是纪念这位科学家。 图灵奖对获奖者的要求极高，评奖程序极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名在同一方向上做出贡献的科学家同时获奖。因此，尽管“图灵”的奖金数额不算高，但它却是计算机界最负盛名的奖项，有“计算机界诺贝尔奖”之称。,图灵机-1,构成：一条两端可无限伸展的带子（被划分成均匀的方格）；读 写头；控制器； 操作：读写头可沿带子方向左右移动；读写头可对每个方格进行 读写； 带子上的符号：有穷字母表S0,S1,Sp，简化为

36、S0,S1，“0”和“1”,机器的控制状态：q1,q2,qm；通常设初始状态为q1，结束状态为qw 一个给定机器的“程序”认为是机器的5元组（qiSjSkR（或L或N）ql）形式的指令集 5元素的含义 qi机器目前所处的状态 Sj机器从方格中读入的符号 Sk机器用来代替Sj写入方格的符号 R 、L、N分别表示右移一格、左、不移动 ql下一步机器的状态,图灵机-2,工作原理：机器从给定带子上的某起始点出发，其状态完全由其初始状态及机内五元组来决定 就图灵机的计算能力而言，可以模拟任何现代计算机，甚至还包含了存储程序的思想 在实际计算机的研制中，需要有具体的实现方法与实现技术,图灵机-3,例：设b

37、表示空格，q1表示机器的初始状态，q4表示机器的结束状态，如果带子上的输入信息是10100010，读写头对准右边第一个为0的方格，状态为初始状态q1 。按照以下规则执行之后，输出正确的结果。,图灵机-4,q101Lq2 q110Lq3 q1bbNq4,q200Lq2 q211Lq2 q2bbNq4,q301Lq2q310Lq3 q3bbNq2,执行结果：10100011 实现功能：S(x)=x+1,计算机科学典型问题示例哥尼斯堡七桥问题,寻找走遍这7座桥且只许走过每座桥一次，最后又回到原出发点的路径,十八世纪东普鲁士哥尼斯堡城（今俄罗斯加里宁格勒）的普莱格尔河，它有两个支流，在城市中心汇成大河

38、，中间是岛区，河上有7座桥，将河中的两个岛和河岸连结。由于岛上有古老的哥尼斯堡大学，有教堂，还有哲学家康德的墓地和塑像，因此城中的居民经常沿河过桥散步。渐渐地，爱动脑筋的人们提出了一个问题：一个散步者能否一次走遍7座桥，而且每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。,哥尼斯堡七桥问题,两岸的陆地与河中的小岛，都是桥梁的连接点，它们的大小、形状均与问题本身无关。因此，把它们看作是4个点； 7座桥是7条必须经过的路线，它们的长短、曲直，也与问题本身无关。因此，任意画7条线来表示它们。,这个问题看起来似乎很简单，然而许多人作过尝试始终没有能找到答案。因此，一群大学生

39、就写信给当时年仅20岁的大数学家欧拉。欧拉从千百人次的失败，以深邃的洞察力猜想，也许根本不可能不重复地一次走遍这七座桥，并很快证明了这样的猜想是正确的。,欧拉将七桥问题抽象成了一个“一笔画”问题。怎样不重复地通过7座桥，变成了怎样不重复地画出一个几何图形的问题。 原先，人们是要求找出一条不重复的路线，欧拉接下来着手判断：这种不重复的路线究竟存在不存在？由于这么改变了一下提问的角度，欧拉抓住了问题的实质。 欧拉注意到，如果一个图能一笔画成，那么一定有一个起点开始画，也有一个终点。图上其它的点是“过路点”画的时候要经过它。 “过路点” 应该是“有进有出”的点，有一条边进这点，那么就要有一条边出这点

40、，不可能是有进无出，如果有进无出，它就是终点，也不可能有出无进，如果有出无进，它就是起点。因此，在“过路点”进出的边总数应该是偶数，即“过路点”是偶点。 如果起点和终点是同一点，那么它也是属于“有进有出”的点，因此必须是偶点，这样图上全体点都是偶点。 如果起点和终点不是同一点，那么它们必须是奇点，因此这个图最多只能有二个奇点。 现在对照七桥问题的图，所有的顶点都是奇点，共有四个，所以这个图肯定不能一笔画成。,计算机科学典型问题示例,哥尼斯堡七桥问题,欧拉的论文为图论的形成奠定了基础。今天，图论已广泛地应用于计算机科学、运筹学、信息论、控制论等科学之中，并已成为我们对现实问题进行抽象的一个强有力

41、的数学工具。随着计算机科学的发展，图论在计算机科学中的作用越来越大，同时，图论本身也得到了充分的发展。,汉诺塔(Hanoi)问题,1）每次只能移动一个盘子；2）盘子只能在三根柱子上来回移动不能放在他处 ；3）在移动过程中三根柱子上的盘子必须始终保持大盘在下小盘在上 天神说，当这64个盘子全部移到第三根柱子上后，世界末日就要到了。,汉诺塔(Hanoi)问题源自一个古老的传说:相传在古印度的一座神庙前,有一根串着64个祭神用的圆盘的柱子,这些圆盘是按大小顺序叠放的,大的在下,小的在上,僧侣们要将这些圆盘借助一个柱子移到另一个柱子上,移动过程中,一次只能移动一个,并且要始终保证每个柱子上的圆盘大的在

42、下,小的在上,什么时候移完,就意味着世界末日.,用计算机求解一个实际问题，首先要从这个实际问题中抽象出一个数学模型，然后设计一个解此数学模型的算法，最后根据算法编写程序，经过调试和运行，从而完成该问题的求解。从实际问题抽象出一个数学模型的实质，其实就是要用数学的方法抽取问题主要的、本质的内容，最终实现对该问题的正确认识。,汉诺塔问题是一个典型的用递归方法来解决的问题。递归是计算机学科中的一个重要概念。所谓递归，就是将一个较大的问题归约为一个或多个子问题的求解方法。而这些子问题比原问题简单，且在结构上与原问题相同。,根据递归方法，我们可以将64个盘子的汉诺塔问题转化为求解63个盘子的汉诺塔问题，

43、如果63个盘子的汉诺塔问题能够解决，则可以将63个盘子先移动到第二个柱子上，再将最后一个盘子直接移动到第三个柱子上，最后又一次将63个盘子从第二个柱子移动到第三个柱子上。,汉诺塔问题示意图,63个盘子的汉诺塔求解问题可以转化为62个盘子的汉诺塔求解问题，62个盘子的汉诺塔求解问题又可以转化为61个盘子的汉诺塔求解问题，直到1个盘子的汉诺塔求解问题。再由1个盘子的汉诺塔的解求出2个盘子的汉诺塔，直到解出64个盘子的汉诺塔问题。,按照上面的算法，n个盘子的汉诺塔问题需要移动的盘子数是n-1个盘子的汉诺塔问题需要移动的盘子数的2倍加1。于是h(n)=2h(n-1)+1=2(2h(n-2)+1)+1=

44、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,因此，要完成汉诺塔的搬迁，需要移动盘子的次数为：264-1=18446744073709551615如果每秒移动一次，一年有31536000秒，则僧侣们一刻不停地来回搬动，也需要花费大约5849亿年的时间。假定计算机以每秒1000万个盘子的速度进行搬迁，则需要花费大约58490年的时间。,证比求易算法问题,算法分析是计算机科学的一项主要工作。为了进行算法比较，我们必须给出算法效率的某种衡量标准。,很久以前，有一个年轻的国王，名叫艾述。他酷爱数学，聘请了当时最有名的数

45、学家孔唤石当宰相。邻国有一位聪明美丽的公主，名字叫秋碧贞楠。艾述国王爱上了这位邻国公主，便亲自登门求婚。公主说：“你如果向我求婚，请你先求出48 770 428 433 377 171的一个真因子，一天之内交卷。” 艾述听罢，心中暗喜，心想：我从2开始，一个一个地试，看看能不能除尽这个数，还怕找不到这个真因子吗？,艾述国王十分精于计算，他一秒钟就算完一个数。可是，他从早到晚，共算了三万多个数，最终还是没有结果。国王向公主求情，公主将答案相告：223 092 827是它的一个真因子。国王很快就验证了这个数确能除尽48 770 428 433 377 171。,公主说：“我再给你一次机会，如果还求

46、不出，将来你只好做我的证婚人了”。国王立即回国，召见宰相孔唤石，大数学家在仔细地思考后认为这个数为17位，如果这个数可以分成两个真因子的乘积，则最小的一个真因子不会超过9位。于是他给国王出了一个主意：按自然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后，立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即上报，赏黄金万两。,于是，国王发动全国上下的民众，再度求婚，终于取得成功。在“证比求易算法”的故事中，国王最先使用的是一种顺序算法，其复杂性表现在时间方面，后来由宰相提出的是一种并行算法，其复杂性表现在空间方面。直觉上，我们认为顺序算法解决不了的问题完全可以用并行算法

47、来解决，甚至会想，并行计算机系统求解问题的速度将随着处理器数目的不断增加而不断提高，从而解决难解性问题，其实这是一种误解。,国王有众多百姓的帮助，求亲成功是自然的事。但是，如果换成是一个贫民百姓的小伙子去求婚，那就困难了。不过，小伙子可以从国王求亲取得成功所采用的并行算法中得到一个启发，那就是：他可以随便猜一个数，然后验证这个数。当然，这样做成功的可能性很小，不过，万一小伙子运气好猜着了呢？由于一个数和它的因子之间存在一些有规律的联系，因此，数论知识水平较高的人猜中的可能性就大。,在算法计算复杂性的研究中，将所有可以在多项式时间内求解的问题称为P类问题，而将所有在多项式时间内可以验证的问题称为

48、NP类问题，由于P类问题采用的是确定性算法，NP类问题采用的是非确定性算法，确定性算法是非确定性算法的一个特例，因此PNP。,对于大多数实际问题来说，找到一个解可能很难，检验一个解常常比较容易，所以都属于NP类问题。现在计算机科学研究中一个悬而未决的重要问题是P=?NP。到目前为止，已经发现了一批可计算但有相当难度的问题是属于NP类问题，并且常通过证明一个问题与已知属于NP类中的某个问题等价，将其归入NP类问题。,计算机科学典型问题示例,哲学家共餐问题,哲学家的生活进程 思考问题 饿了停止思考，左手拿一支筷子（拿不到就等） 右手拿一支筷子（拿不到就等） 进餐 放右手筷子 放左手筷子 重新回到思

49、考问题的状态1,哲学家的生活进程的极端情况： 当所有哲学家都同时拿起左手筷子时，则所有哲学家都拿不到右手的筷子，并处于等待状态，则哲学家将都无法进餐，最终饿死； 改变进程，如拿不到右手筷子则放下左手筷子。在某一瞬可能所有的哲学家都拿起左手的筷子，因拿不到右手的筷子又都同时放下左手的筷子，如此下去，所有的哲学家同样无法进餐。,哲学家进餐问题在计算机科学中所反映的问题： 程序并发执行时进程同步的问题：死锁（Deadlock）和饥饿（Starvation） 为了提高系统的处理能力和机器的利用率，并法程序被广泛地使用，因此必须彻底解决并发进程中的死锁和饥饿问题,Deadlock,Starvation,Starvation,Starvation,旅行商问题,旅行商问题（Traveling Salesman Problem，简称TSP）是威廉哈密尔顿（W.R.Hamilton）爵士和英国数学家克克曼（T.P.Kirkman）于19世纪初提出的一个数学问题。这是一个典型的NP完全性问题。其大意是：有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发，必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市。问如何事先确定好一条最短的路线，使其旅行的费用最少。,