加州理工学院-计算系统导论 (4)

Introduction to Algorithms October 29, 2005 Massachusetts Institute of Technology 6.046J/18.410J Professors Erik D. Demaine and Charles E. Leiserson Handout 18Problem Set 4 SolutionsProblem 4-1. TreapsIf we insert a set of n items into a binary search tree using T REE-I NSERT, the resulting tree may be horribly unbalanced. As we saw in class, however, we expect randomly built binary search trees to be balanced. (Precisely, a randomly built binary search tree has expected height O(lg n).) Therefore, if we want to build an expected balanced tree for a fixed set of items, we could randomly permute the items and then insert them in that order into the tree.What if we do not have all the items at once? If we receive the items one at a time, can we still randomly build a binary search tree out of them?We will examine a data structure that answers this question in the affirmative. A treap is a binary search tree with a modified way of ordering the nodes. Figure 1 shows an example of a treap. As usual, each item x in the tree has a key key[x]. In addition, we assign priority[x], which is a random number chosen independently for each x. We assume that all priorities are distinct and also that all keys are distinct. The nodes of the treap are ordered so that (1) the keys obey the binary-search-tree property and (2) the priorities obey the min-heap order property. In other words,•if v is a left child of u, then key[v]<key[u];•if v is a right child of u, then key[v]>key[u]; and•if v is a child of u, then priority(v)>priority(u).(This combination of properties is why the tree is called a “treap”: it has features of both a binary search tree and a heap.)Figure 1: A treap. Each node x is labeled with key[x]:p riority[x]. For example, the root has key G and priority 4.It helps to think of treaps in the following way. Suppose that we insert nodes x1,x2,...,x n, each with an associated key, into a treap in arbitrary order. Then the resulting treap is the tree that wouldhave been formed if the nodes had been inserted into a normal binary search tree in the order given by their (randomly chosen) priorities. In other words, priority[x i]<priority[x j]means that x i is effectively inserted before x j.(a) Given a set of nodes x1,x2,...,x n with keys and priorities all distinct, show that thereis a unique treap with these nodes.Solution:Prove by induction on the number of nodes in the tree. The base case is a tree withzero nodes, which is trivially unique. Assume for induction that treaps with k−1orfewer nodes are unique. We prove that a treap with k nodes is unique. In this treap, theitem x with minimum priority must be at the root. The left subtree has items with keys<key[x]and the right subtree has items with keys >key[x]. This uniquely defines theroot and both subtrees of the root. Each subtree is a treap of size ≤k−1, so they areunique by induction.Alternatively, one can also prove this by considering a treap in which nodes are in­serted in order of their priority. Assume for induction that the treap with the k−1nodes with smallest priority is unique. For k=0t his is trivially true. Now considerthe treap with the k nodes with smallest priority. Since we know that the structureof a treap is the same as the structure of a binary search tree in which the keys areinserted in increasing priority order, the treap with the k nodes with smallest priorityis the same as the treap with the k−1nodes with smallest priority after inserting thek-th node. Since BST insert is a deterministic algorithm, there is only one place thek-th node could be inserted. Therefore the treap with k nodes is also unique, provingthe inductive hypothesis.(b) Show that the expected height of a treap is O(lg n), and hence the expected time tosearch for a value in the treap is O(lg n).Solution: The idea is to realize that a treap on n nodes is equivalent to a randomlybuilt binary search tree on n nodes. Recall that assigning priorities to nodes as theyare inserted into the treap is the same as inserting the n nodes in the increasing orderdefined by their priorities. So if we assign the priorities randomly, we get a randomorder of n priorities, which is the same as a random permutation of the n inputs, sowe can view this as inserting the n items in random order.The time to search for an item is O(h)where h is the height of the tree. As we saw inlecture, E[h]=O(lg n). (The expectation is taken over permutations of the n nodes,i.e., the random choices of the priorities.)Let us see how to insert a new node x into an existing treap. The first thing we do is assign x a random priority priority[x]. Then we call the insertion algorithm, which we call T REAP-I NSERT, whose operation is illustrated in Figure 2.(e) (f)Figure 2: Operation of T REAP-I NSERT. As in Figure 1, each node x is labeled with key[x]: priority[x]. (a) Original treap prior to insertion. (b) The treap after inserting a node with key C and priority 25. (c)–(d) Intermediate stages when inserting a node with key D and priority 9.(e) The treap after insertion of parts (c) and (d) is done. (f) The treap after inserting a node with key F and priority 2.(c) Explain how T REAP-I NSERT works. Explain the idea in English and give pseudocode.(Hint: Execute the usual binary search tree insert and then perform rotations to restorethe min-heap order property.)Solution: The hint gives the idea: do the usual binary search tree insert and thenperform rotations to restore the min-heap order property.T REAP-I NSERT (T,x)inserts x into the treap T(by modifying T). It requires that xhas defined key and priority values. We have used the subroutines T REE-I NSERT,R IGHT-R OTATE, and R IGHT-R OTATE as defined in CLRS.T REAP-I NSERT (T,x)1T REE-I NSERT (T,x)2 while x =root[T]and priority[x]<priority[p[x]]3 do if x=left[p[x]]4 then R IGHT-R OTATE (T,p[x])5 else L EFT-R OTATE (T,p[x])Note that parent pointers simplify the code but are not necessary. Since we only needto know the parent of each node on the path from the root to x(after the call toT REE-I NSERT), we can keep track of these ourselves.(d) Show that the expected running time of T REAP-I NSERT is O(lg n). Solution:T REAP-I NSERT first inserts an item in the tree using the normal binary search treeinsert and then performs a number of rotations to restore the min-heap property.The normal binary-search-tree insertion algorithm T REE-I NSERT always places thenew item at a new leaf of tree. Therefore the time to insert an item into a treap isproportional to the height of a randomly built binary search tree, which as we saw inlecture is O(lg n)in expectation.The maximum number of rotations occurs when the new item receives a priority lessthan all priorities in the tree. In this case it needs to be rotated from a leaf to the root.An upper bound on the number of rotations is therefore the height of a randomly builtbinary search tree, which is O(lg n)in expectation. (We will see that this is a fairlyloose bound.) Because each rotation take constant time, the expected time to rotate isO(lg n).Thus the expected running time of T REAP-I NSERT is O(lg n+lg n)=O(lg n).T REAP-I NSERT performs a search and then a sequence of rotations. Although searching and ro­tating have the same asymptotic running time, they have different costs in practice. A search reads information from the treap without modifying it, while a rotation changes parent and child pointers within the treap. On most computers, read operations are much faster than write operations. Thus we would like T REAP-I NSERT to perform few rotations. We will show that the expected number of rotations performed is bounded by a constant (in fact, less than 2)!(a) (b)Figure 3: Spines of a binary search tree. The left spine is shaded in (a), and the right spine is shaded in (b).In order to show this property, we need some definitions, illustrated in Figure 3. The left spine of a binary search tree T is the path which runs from the root to the item with the smallest key. In other words, the left spine is the maximal path from the root that consists only of left edges. Symmetrically, the right spine of T is the maximal path from the root consisting only of right edges. The length of a spine is the number of nodes it contains.(e) Consider the treap T immediately after x is inserted using T REAP-I NSERT. Let Cbe the length of the right spine of the left subtree of x. Let D be the length of theleft spine of the right subtree of x. Prove that the total number of rotations that wereperformed during the insertion of x is equal to C+D.Solution: Prove the claim by induction on the number of rotations performed. Thebase case is when x is the parent of y. Performing the rotation so that y is the new rootgives y exactly one child, so C+D=1.Assume for induction that the number of rotations k performed during the insertionof x equals C+D. The base case is when 0 rotations are necessary and x is insertedas a leaf. Then C+D=0. To prove the inductive step, we show that if after k−1rotations C+D=k−1, then after k rotations C+D=k. Draw a picture of aleft and right rotation and observe that C+D increases by 1 in each case. Let y bethe parent of x, and suppose x is a left child of y. After performing a right rotation, ybecomes the right child of x, and the previous right child of x becomes the left childof y. That is, the left spine of the right subtree of x before the rotation is tacked onto y, so the length of that spine increases by one. The left subtree of x is unaffectedby a right rotation. The case of a left rotation is symmetric. Therefore after one morerotation C+D increases by one and k=C+D, proving the inductive hypothesis.We will now calculate the expected values of C and D. For simplicity, we assume that the keys are 1,2,...,n. This assumption is without loss of generality because we only compare keys.�For two distinct nodes x and y , let k = key [x ]and i = key [y ], and define the indicator random variableX 1 if y is a node on the right spine of the left subtree of x (in T ),i,k =0 otherwise .(f) Show that X i,k =1if and only if (1) priority [y ]> priority [x ], (2) key [y ]< key [x ], and(3) for every z such that key [y ]< key [z ]< key [x ],we have p riority [y ]< priority [z ].Solution:To prove this statement, we must prove both directions of the “if and only if”. Firstwe prove the “if” direction. We prove that if (1) priority [y ]> priority [x ], (2) key [y ]<key [x ], and (3) for every z such that key [y ]< key [z ]< key [x ]are true, priority [y ]< priority [z ], then X i,k =1. We prove this by contradiction. Assume that X i,k =0. That is, assume that y is not on the right spine of the left subtree of x . We show thatthis leads to a contradiction. If y is not on the right spine of the left subtree of x ,it could be in one of three places:1. Suppose y is in the right subtree of x . This contradicts condition (2) becausekey [y ]< key [x ].2. Suppose y is not in one of the subtrees of x . Then x and y must share somecommon ancestor z . Since key [y ]< key [x ], we know that y is in the left subtreeof z and x is in the right subtree of z and key [y ]< key [z ] < key [x ]. Since y isbelow z in the tree, priority [z ]< priority [x ]and priority [z ]< priority [y ]. Thiscontradicts condition (3).3. Suppose that y is in the left subtree of x but not on the right spine of the leftsubtree of x . This implies that there exists some ancestor z of y in the left subtreeof x such that y is in the left subtree of z . Hence key [y ]< key [z ]< key [x ]. Sincez is an ancestor of y , priority [z ]< priority [y ], which contradicts condition (3).All possible cases lead to contradictions, and so X i,k =1.Now for the “only if” part. We prove that if X i,k =1, then statements (1), (2), and (3) are true. If X i,k =1, then y is in the right spine of the left subtree of x . Since y is ina subtree of x , y must have been inserted after x ,so p riority [y ]> priority [x ], proving(1). Since y is in the left subtree of x , key [y ]< key [x ], proving (2). We prove (3) by contradiction: suppose that X i,k =1and there exists a z such that key [y ]< key [z ]< key [x ]and priority [z ]< priority [y ]. In other words, z was inserted before y . There arethree possible cases that satisfy the condition key [z ]< key [x ]:1. Suppose z is in the right spine of the left subtree of x .For y to be inserted into theright spine of the left subtree of x , it will have to be inserted into the right subtreeof z . Since key [y ]< key [z ], this leads to a contradiction.2. Suppose z is in the left subtree of x but not in the right spine. This implies thatz is in the left subtree of some node z in the right spine of x . Therefore for y tobe inserted into the right spine of the left subtree of x , it must be inserted into theright subtree of z . This leads to a contradiction by reasoning similar to case 1.3. Suppose that z is not in one of the subtrees of x . Then z and x have a commonancestor z such that z is in the left subtree of z and x is in the right subtree of x .This implies key [z ] < key [z ] < key [x ]. Since key [y ]< key [z ]< key [z ], y cannotbe inserted into the right subtree of z . Therefore it cannot be inserted in a subtreeof x , which is a contradiction.Therefore there can be no z such that key [y ] < key [z ] < key [x ] and priority [z ] < priority [y ]. This proves statement (3). We have proven both the “if” and “only if” directions, proving the claim.(g) Show that(k − i − 1)! 1 Pr {X i,k =1} == . (k − i +1)! (k − i +1)(k − i )Solution: We showed in the previous part that X i,k =1if and only if the priorities of the items between y and x are ordered in a certain way. Since all orderings are equally likely, to calculate the probability we count the number of permutations of priorities that obey this order and divide by the number of total number of priority permutations. We proved in (e) that whether or not X i,k =1depends only on the relative ordering of the priorities of y , x , and all z such that key [y ] < key [z ] < key [x ]. Since we assumed that the keys of the items come from {1,...,n }, the keys of the items in question are i,i +1,i +2,...,k − 1,k . There are (k − i +1)!permutations of the priorities of these items. Of these permutations, the ones for which X i,k =1are those where i has minimum priority, k has the second smallest priority, and the priorities of the remaining k − i − 1 items follow in any order. There are (k − i − 1)! of these permutations. Thus the probability that we get a “bad” order is (k −i −1)!/(k −i +1)!= 1/(k − i )(k − i +1).(h) Show thatk −1 � 1 1 E [C ]= =1− . j (j +1)k j =1 Solution:X For a node x with key k , E [C ]is the expected number of nodes in the right spine of the left subtree of x . This equals the sum of the expected value of the random variables i,k for all i in the tree. Since X i,k =0for all nodes i ≥ k , we only need to consider i <k .� � � k −1 �k −1 � E [C ]=E [X i,k ]=E X i,k i =1 i =1 k −1 =Pr {X i,k =1}i =1 k −1 � 1 =(k − i )(k − i +1) i =1 k −1 � 1= j (j +1)j =1 1To simplify this sum, observe that j (j 1+1) = j +1−j = − 1 . Therefore the sumj (j +1) j j +1 telescopes and we have 1 E [C ]=1− . kIf you didn’t see this, you could have proven that the equationk −1 � 1 1 =1− j (j +1)k j =1 holds by induction on k . In the proving the inductive hypothesis you might have 11discovered 1 − = .j j +1 j (j +1)(i) Use a symmetry argument to show that1 E [D ]=1− . n − k +1Solution: The idea is to consider the treap produced if the ordering relationship amongthe keys is reversed. That is, for all items x , leave priority [x ]unchanged but replacekey [x ]with n − key [x ]+1.Let T be the binary tree we get when inserting the items (in increasing order of pri­ority) using the original keys. Once we remap the keys and insert them into a newbinary search tree, we get a tree T whose shape is the mirror image of the shape ofT . (reflected left to right). Consider the item x with key k in T and therefore has key n − k +1 i n T . The length of the left spine of x ’s right subtree in T has becomethe length of the right spine of x ’s left subtree in T . We know by part (g) that the expected length of the right spine of a left subtree of a node y is 1− 1/idkey [y ],so the expected length of the right spine of the left subtree of x in T is 1− 1/(n − k +1), which means that 1 E [D ]=1− . n − k +1(j) Conclude that the expected number of rotations performed when inserting a node into a treap is less than 2.Solution:11 E [number of rotations ]= E [C +D ]=E [C ]+E [D ]=1− +1− k n − k +1 ≤ 1+1=2. Problem 4-2. Being balancedCall a family of trees balanced if every tree in the family has height O (lg n ), where n is the number of nodes in the tree. (Recall that the height of a tree is the maximum number of edges along any path from the root of the tree to a leaf of the tree. In particular, the height of a tree with just one node is 0.)For each property below, determine whether the family of binary trees satisfying that property is balanced. If you answer is “no”, provide a counterexample. If your answer is “yes”, give a proof (hint: it should be a proof by induction). Remember that being balanced is an asymptotic property, so your counterexamples must specify an infinite set of trees in the family, not just one tree. (a) Every node of the tree is either a leaf or it has two children.Solution: No. Counterexample is a right chain, with each node having a leaf hanging off to the left(b) The size of each subtree can be written as 2k − 1, where k is an integer (k is not the same for each subtree).Solution: Yes.Consider any subtree with root r . We know from the condition that the size of this subtree is 2k 1 − 1. We also know that the size of the subtree rooted at the left child of r is 2k 2 − 1, and the size of the subtree rooted at the right child of r is 2k 3 − 1. But the size of the subtree at r is simply the node r together with the nodes in the left and right subtrees. This leads to the equation 2k 1 − 1=1+(2k 2 − 1)+(2k 3 − 1),or 2k 1 =2k 2 +2k 3. Now we show that k 2 =k 3. This is easy to see if you consider the binary representations of k 1, k 2, and k 3.Otherwise, if we assume WLOG that k 2 ≤ k 3, then we have 2k 1−k 2 =1+2k 3−k 2. 2Now, the only pair of integer powers of 2 that could satisfy this equation are 21 and 0 . Thus k 3 − k 2 =0,or k 2 =k 3, and the left and right subtrees of r have an equal number of nodes. It follows that the tree is perfectly balanced.(c) There is a constant c>0such that, for each node of the tree, the size of the smallerchild subtree of this node is at least c times the size of the larger child subtree.Solution:Yes1. The proof is by induction. Assume that the two subtrees of x with n nodes in itssubtree has two children y and z with subtree sizes n1 and n2. By inductive hypothesis,the height of y’s subtree is at most d lg n1 and the height of z’s subtree is at most d lg n2for some constant d. We now prove that the height of x’s subtree is at most d lg n.Assume wlog that n1 ≥n2. Therefore, by the problem statement, we have n2 ≥cn1.Therefore, we have n=n1 +n2 +1≥(1+c)n1 +1≥(1+c)n1 and the height hof x’s subtree is d lg n1 +1≤d lg(n/(c+1))+1≤d lg n−d lg(1+c)+1≤d lg nif d lg(1+c)≥1. Therefore, for sufficiently large d, the height of a tree with n nodesis at most d lg n.(d) There is a constant c such that, for each node of the tree, the heights of its childrensubtrees differ by at most c.Solution: Yes1. Let n(h)be the minimum number of nodes that a tree of height h thatsatisfies the stated property can have. We show by induction that n(h)≥(1+α)h−1,for some constant 0<α≤1. We can then conclude that for a tree with n nodes,h≤log1+α(n+1)=O(lg n).For the base case, a subtree of height 0has a single node, and 1≥(1+α)0 −1forany constant α≤1.In the inductive step, assume for all trees of height k<h, that the n(k)≥(1+α)k−1.Now consider a tree of height h, and look at its two subtrees. We know one subtreemust have height h−1, and the other must have height at least h−1−c. Therefore,we known(h)≥n(h−1)+n(h−1−c)+1.Using the inductive hypothesis, we getn(h) ≥(1+α)h−1 −1+(1+α)h−1−c−1+1≥2(1+α)h−1−c−1.Suppose we picked αsmall enough so that (1+α)<21/(c+1). Then (1+α)c+1 <2.Therefore, we getn(h)≥2(1+α)h−1−c−1≥(1+α)h−1.1Note that in this problem we assume that a nil pointer is a subtree of size 0, and so a node with only one child has two subtrees, one of which has size 0. If you assume that a node with only one child has only one subtree, then the answer to this problem part is “no”.�11Handout18: Problem Set4SolutionsTherefore, we satisfy the inductive hypothesis.Note that if we plug this value for αback into h≤log1+α(n+1),we getlg(n+1)h≤≤(c+1)l g(n+1).lg(1+2c+1)(e) The average depth of a node is O(lg n). (Recall that the depth of a node x is thenumber of edges along the path from the root of the tree to x.)Solution: No.√Consider a tree with n−n nodes organized as a complete binary tree, and the other √ √n nodes sticking out as a chain of length n from the balanced tree. The height of√√√the tree is lg(n−n)+n=Ω(n), while the average depth of a node is at most�√√ √(1/n)n·(n+lg n)+(n−n)·lg n√√=(1/n)(n+n lg n+n lg n−nlgn)=(1/n)(n+n lg n)=O(lg n)√Thus, we have a tree with average node depth O(lg n), but height Ω(n).。

新加坡TMC学院互联网电脑系统理学士课程
新加坡TMC
学院和利物浦约翰摩尔大学合作开设的互联网电脑系统(荣誉）理学士课程可以让学生体验为期14个星期的英国本部学习，从而享受正统的英国教育。

接下来新加坡教育网就带大家全面了解下该专业的设置情况：
第一阶段：TMC信息科技大专课程（共6个月）
计算机系统要点、数据库系统、商业沟通、信息科技简介、Java编程、网络和多媒体
第二阶段： TMC信息科技高级大专课程（共12个月）
1.网络原则
数据库系统与应用、信息系统分析、项目管理、Java编程
2.网页开发专业
操作系统基础、多媒体系统、网页编程、互动式服务器编程语言、项目设计
3.网络专业
信息科技安全、网络和数据通信、网络操作系统、逻辑基础、项目设计
第三阶段：互联网电脑系统（荣誉）理学士（9个月）
1.新加坡完成课程
多媒体开发、电子商务管理、XML技术基础、项目设计
2.英国完成课程
商业系统的方法、信息科技现代问题、网络安全、面向对象数据库、用户界面设计、基于Web的信息系统
以上是新加坡TMC学院互联网电脑系统理学士课程的具体情况，想要了解更多关于新加坡留学
的内容请关注新加坡教育网。

原文摘自：
http://www.iedu.sg。

第1章引论本章要点：1.什么是计算；2.计算机科学与计算科学的区别；3.来自计算机发展史的启示；4.计算机应用；5.计算机发展趋势。

1.1 什么是计算？简单计算，如我们从幼儿就开始学习和训练的算术运算，如“3 + 2 = 5”“3 2 = 6”等，是指“数据”在“运算符”的操作下，按“规则”进行的数据变换。

我们不断学习和训练的是各种运算符的“规则”及其组合应用，目的是通过计算得到正确的结果。

广义地讲，一个函数如“”把x变成了f(x)就可认为是一次计算，在高中及大学阶段我们不断学习各种计算“规则”并应用这些规则来求解各种问题，得到正确的计算结果。

如对数与指数、微分与积分等。

“规则”可以学习与掌握，但应用“规则”进行计算则可能超出了人的计算能力，即人知道规则但却没有办法得到计算结果。

如何解决呢？一种办法是研究复杂计算的各种简化的等效计算方法(数学)使人可以计算，另一种办法是设计一些简单的规则，让机械来重复的执行完成计算，即考虑能否用机械来代替人按照“规则”自动计算。

例如：能否机械地判断方程“a1x1b1+a2x2b2+…+a n x n b n = c”是否有整数解?”，即机械地证明一个命题是否有解? 是否正确?类似的上述问题，促进了计算机科学和计算科学的诞生和发展，促进了人们思考：◆什么能够被有效地自动计算？现实世界需要计算的问题是很多的，哪些问题是可以自动计算的，哪些问题是可以在有限时间有限空间内自动计算的？这就出现了计算及计算复杂性问题。

以现实世界的各种思维模式为启发，寻找求解复杂问题的有效规则，就出现了算法及算法设计与分析问题。

例如观察人的思维模式而提出的遗传算法、观察蚂蚁行动的规律而提出的蚁群算法等。

◆如何低成本、高效地实现自动计算？如何构建一个高效的计算系统：计算机器的构建问题和软件系统的构建问题。

◆如何方便有效地利用计算系统进行计算？利用已有计算系统，面向各行各业的计算问题求解。

什么能、且如何被有效地自动计算问题就是计算学科的科学家不断在研究和解决的问题。

level 4Level 4内容：计算机科学是一门广泛而深奥的学科，涵盖了许多不同的主题。

以下是一些与计算机科学相关的内容，以及对它们的简要介绍。

1. 数据结构与算法：数据结构是组织和存储数据的方式，而算法是用于解决问题的一系列指令。

学习数据结构和算法可以帮助我们更有效地处理和操作数据，从而提高程序的效率。

2. 编程语言：编程语言是用于编写计算机程序的工具。

不同的编程语言有不同的语法和规则，可以用于不同的应用。

一些常见的编程语言是Java、Python、C++等。

3. 软件工程：软件工程是研究如何开发高质量软件的学科。

它包括从需求分析、设计到测试和维护的整个软件开发过程。

软件工程还研究如何管理和组织软件项目，以确保项目的成功。

4. 数据库：数据库是用于存储和管理数据的系统。

它可以用于存储大量的结构化数据，并提供数据的查询和操作功能。

数据库管理系统（DBMS）是用于管理数据库的软件工具，常见的DBMS有MySQL、Oracle等。

5. 计算机网络：计算机网络是连接计算机和其他设备的通信系统。

它包括局域网、广域网和互联网等，是实现计算机之间通信和共享资源的基础。

6. 人工智能：人工智能是研究如何使计算机具备智能的学科。

它涉及机器学习、自然语言处理、图像识别等技术，旨在开发出能够模仿人类智能行为的计算机系统。

7. 计算机图形学：计算机图形学是研究如何生成和处理图像和动画的学科。

它涵盖了三维建模、渲染、虚拟现实等领域，广泛应用于游戏开发、电影制作等行业。

8. 操作系统：操作系统是管理计算机硬件和软件资源的系统。

它提供了一组基本的功能，如进程管理、文件管理和内存管理，使得计算机可以有效地运行应用程序。

9. 计算机安全：计算机安全是保护计算机系统和数据免受未经授权访问、损坏或泄露的学科。

它包括网络安全、密码学等领域，旨在确保计算机系统的可靠和安全。

10. 软件测试：软件测试是验证和评估软件功能和质量的过程。

计算机科学与导论-思想与方法习题答案习题一1.1简述计算学科的定义及其根本问题。

答：计算学科是对描述和变换信息的算法过程进行的系统研究，包括理论、分析、设计、效率、实现和应用等。

学科的根本问题是：什么能被（有效地）自动进行。

1.2简述计算学科专业名称的演变。

答：计算学科专业名称主要包括：计算机科学、信息系统、软件工程、计算机工程、和信息技术。

1962年，美国普渡大学开设了最早的“计算机科学”学位课程。

当时，在美国的一些高校还开设有与计算相关的两给学位课程：电子工程和信息系统。

而在我国，早在1956年，就开设了“计算装置与仪器”专业。

20世纪70年代，在美国，“计算机工程”（也被称为“计算机系统工程”）从电子工程学科中脱离出来，成为一个独立的二级学科，并被人们所接受。

随着软件规模及其复杂度的增加，制造可靠软件的困难越来越大，出现了所谓的软件危机；针对这种情况，1968年秋，北大西洋公约组织（NA TO）在当时的联邦德国召开了一次会议，提出了软件工程的概念。

20世纪70年代未、80年代初，在一些计算机科学专业的学位课程中，引入了软件工程的内容，然而，这些内容，只能让学生了解软件工程，却不能使学生明白如何成为一名软件工程师。

于是，人们开始构建单独的软件工程学位课程。

20世纪80年代，英国和澳大利亚，最早开设了“软件工程”这样的学位课程。

20世纪90年代，计算机已成为公司各级人员使用的基本工具，而计算机网络则成为公司信息的中枢，人们相信它有助于提高生产力，而原有的学术学位课程并不能满足社会的需求，于是，在美国等西方国家，不少大学相继开设了“信息系统”、“信息技术”等学位课程。

至此，需要指出的是，即使在美国，5个分支学科（专业）同时在一所大学开设的情况也是不多的，更多的高校仍然是以传统的“计算机科学”为主；在我国，则是以“计算机科学与技术”为主。

1.3简述计算学科主要专业培养的不同。

答：对计算学科五个主要专业的培养侧重点简述如下。

《麻省理工学院-算法导论》(MIT - Introduction to Algorithms)这是麻省理工学院2001年秋季课程《算法导论》的所有课程资料，包括有：课本(含有习题，chm格式)，课堂讲稿(ppt转pdf格式)，作业及其答案(pdf格式)，测验及其答案(pdf格式)，教师参考(含习题答案，很难得，pdf格式)，课堂录像(rmvb格式)。

关于课本的介绍如下：本书自第一版出版以来，已经成为世界范围内广泛使用的大学教材和专业人员的标准参考手册。

本书全面论述了算法的内容，从一定深度上涵盖了算法的诸多方面，同时其讲授和分析方法又兼顾了各个层次读者的接受能力。

各章内容自成体系，可作为独立单元学习。

所有算法都用英文和伪码描述，使具备初步编程经验的人也可读懂。

全书讲解通俗易懂，且不失深度和数学上的严谨性。

第二版增加了新的章节，如算法作用、概率分析与随机算法、线性编程等，几乎对第一版的各个部分都作了大量修订。

学过计算机的都知道，这本书是全世界最权威的算法课程的大学课本了，基本上全世界的名牌大学用的教材都是它。

这本书一共四位作者，Thomas H. Cormen，Charles E. Leiserson和Ronald L. Rivest是来自MIT的教授，Clifford Stein是MIT出来的博士，现在哥伦比亚大学做教授，四人姓氏的首字母联在一起即是此书的英文简称(CLRS 2e)，其中的第三作者Ronald L. Rivest是RSA算法的老大(算法名字里面的R即是指他)，四个超级大牛出的一本书，此书不看人生不能算完整。

再介绍一下课堂录像里面授课的两位MIT的老师，第一位，外表“绝顶聪明”的，是本书的第二作者Charles E. Leiserson，以逻辑严密，风趣幽默享誉MIT。

第二位，留着金黄色的络腮胡子和马尾发的酷哥是Erik Demaine，21岁即取得MIT教授资格的天才，1981出生，今年才25岁，业余爱好是俄罗斯方块、演戏、琉璃、折纸、杂耍、魔术和结绳游戏。

第5章算法与复杂性习题一、选择题1. B2. D3. C4. A5. B6. B7. D8.B9.C 10.A11.A 12.C 13.A 14.A二、简答题1．什么是算法，算法的特性有哪些？答：“算法(Algorithm)是一组明确的、可以执行的步骤的有序集合，它在有限的时间内终止并产生结果”。

算法的特性有：(1) 有穷性(可终止性)：一个算法必须在有限个操作步骤内以及合理的有限时间内执行完成。

(2) 确定性：算法中的每一个操作步骤都必须有明确的含义，不允许存在二义性。

(3) 有效性(可执行性)：算法中描述的操作步骤都是可执行的，并能最终得到确定的结果。

(4) 输入及输出：一个算法应该有零个或多个输入数据、有1个或多个输出数据。

2．什么是算法的时间复杂度和空间复杂度，如何表示？答：时间复杂度是与求解问题规模、算法输入相关的函数，该函数表示算法运行所花费的时间。

记为，T(n)，其中，n代表求解问题的规模。

算法的空间复杂度(Space complexity)度量算法的空间复杂性、即执行算法的程序在计算机中运行所占用空间的大小。

简单讲，空间复杂度也是与求解问题规模、算法输入相关的函数。

记为，S(n)，其中，n代表求解问题的规模。

时间复杂度和空间复杂度同样，引入符号“O”来表示T(n)、S(n)与求解问题规模n之间的数量级关系。

3．用图示法表示语言处理的过程。

答：语言处理的过程如图所示：4．简述算法设计的策略。

答：作为实现计算机程序实现时解决问题的方法，算法研究的内容是解决问题的方法，而不是计算机程序的本身。

一个优秀的算法可以运行在比较慢的计算机上，但一个劣质的算法在一台性能很强的计算机上也不一定能满足应用的需要，因此，在计算机程序设计中，算法设计往往处于核心地位。

要想充分理解算法并有效地应用于实际问题，关键是对算法的分析。

通常可以利用实验对比分析、数学方法来分析算法。

实验对比分析很简单，两个算法相互比较，它们都能解决同一问题，在相同环境下，一般就会认为哪个算法的速度快这个算法性能更好。

-----WORD格式--可编辑--专业资料-----Introduction to Computers B IntroductionIntroduction to Computers BCourse Number：B08010120Course Property：professional basic courseSemester and Periods Allocation ：the first semester, 4 hours per weekApplied Specialty：students of Computer Science double majorPrior Courses：noneSucceed Courses：Data Structure Operating Systems Software Engineering Computer NetworkTeaching Material：《Computer Science Conception》（eleven edition），J. GlennBrookshear，People's Posts and Telecommunications Press，2011Recommended References Books ：1．《Software Craftsmanship》，Joel spolsky,People's Posts and Telecommunications Press，20092．《Computer Introduction》（third edition），Wangyulong，Fuxiaolong，Publishing House of electronics industry，20093．《Computer Introduction》，Chenming，Tsinghua University press，2009Purpose ,Contents and Requierments of the Course：This course is a pilot introductory course for students of computer science and technology double major, aiming to provide a basic understanding of the main knowledge and skills of the major , and to construct a basic framework of knowledge of subsequent courses and lay a foundation for later professional knowledge learning and scientific research. It also cultivates the students' conceptions of the global and awareness of updating knowledge constantly.This course involves all aspects of computer science and focuses on the basic conception rather than mathematical model and technology details with requirements of “breadth first, wide rather than fine”. The emphasis of the course is to outline the framework of computer science system, lay a foundation of computer science knowledge and pave the way for subsequent learning of the professional theory courses in computer information technology. The course is parallelly opened with the course of Office Automation Technology, letting the students to master the basic operation technique, enhance the perceptual knowledge and lay a solid a foundation for computer using in their own major.author：Caolingauditor--完整版学习资料分享----。