1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 9
Текст из файла (страница 9)
We shall use inductionon n. The result certainly holds when n = O. So, suppose that it holds for allnatural numbers up to and including n. Then we havewhere in the first inequality we used the induction hypothesis, and in the secondwe used the fact that 1 -:; 2n for all n.We shall now extend this easy fact to all polynomials. We shall show thatfor any i ~ 1, ni E 0(2n); that is,(1)for appropriate constants e and d. Take e = (2i) i and d = (i 2 ) i.
There aretwo cases: If n -:; i 2 , then the inequality holds because n; -:; d. If on the otherhand n ~ i 2 , then we shall show that the inequality (1) again holds because nown i -:; e2n. In proof, let m be the quotient of n divided by i -the unique integer34Chapter 1: SETS, RELATIONS, AND LANGUAGESsuch that im ::; n< im + i. Then we haveir+=ii(m + l)iby thr definition of m::;ii(2m+l)iby the inequality n::; 2n applied to n = mni ::;(im<c2 miby recalling that c = (2i)i<c2/lagain by the definition of m.+1Thus the rate of growth of any polynomial is no faster than that of 2n. Cana polynomial have the same rate of growth as 2n ? If so, then any polynomialof larger degree would have the same rate of growth as well; and we saw in theprevious example that polynomials of different degrees have different rates ofgrowth.
We conclude that 2n has a higher rate of growth than any polynomial.2nn2Other exponential functions, such as 5n , n n, n!, 2 , or, worse, 2 , have evenhigher rates of growth.OAnalysis of AlgorithmsPolynomial and exponential rates of growth arise very naturally in the analysisof algorithms. For example, let us derive a rough estimate of the number ofsteps taken by the algorithm for the reflexive transitive closure introduced inthe beginning of this section.The algorithm examines each sequence (b 1 , ... , bi ) of length up to n todetermine whether it is a path of R, and, if the answer is "yes," it adds (b 1 , bi ) tbR*. Each such repetition can definitely be carried out in n or fewer "elementaryoperations" -testing whether (a, b) E R, adding (a, b) to R*.
Thus, the totalnumber of operations can be no more thanwhich is in O(n/l+l). We have thus detehnined that the rate of growth of thetime requirements of this algorithm is O(nn+l).This outcome is rather disappointing because it is an exponential function,with an even higher rate of growth than 2/l. This algorithm is not efficient atall!The question then arises, is there a faster algorithm for computing thereflexive transitive closure? Consider the following:Initially R* := Ru {(ai,ai) : ai E A}while there are three elements ai, aj, ak E A such that(ai, aj), (aj, ak) E R* but (ai, ak) ~ R* do:add (ai, ak) to R*.1.6: Closures and Algorithms35This algorithm is perhaps even more natural and intuitive than the firstone. It starts by adding to R* all pairs in R and all pairs of the form (ai, ai)-thus guaranteeing that R* contains R and is reflexive. It then repeatedly looksfor violations of the transitivity property.
Presumably this search for violationsproceeds in some organized way not spelled out exactly in the algorithm, say byrunning through all values of ai, for each of them through all values of aj, andfinally of ak. If such a violation is discovered then it is corrected by adding anappropriate pair to R*, and the search for a violation must start all over again.If at some point all triples are examined and no violation is found, the algorithmterminates.When the algorithm terminates, R* will certainly contain R, and it will bereflexive; besides, since no violation was found in the last iteration of the whileloop, R* must be transitive.
Furthermore, R* is the smallest relation that hasall these properties (and it is thus the sought reflexive transitive closure of R).To see why, suppose that there is a proper subset of R*, call it Ro, that containsR, and is reflexive and transitive. Consider then the first pair that does notbelong to Ro, and still was added to R* by the algorithm. It cannot be a pair inR, or a pair of the form (ai, ai), because all these pairs do belong to Ro. Thus,it must be a pair (ai,ak) such that both (ai,aj) and (aj,ak) belong to R* atthat point -and therefore also to Ro, since (ai, ak) was the first pair in whichthe two relations differ. But then Ro, by hypothesis a transitive relation, mustalso contain (ai, ak) -a contradiction.
Therefore, the result will be the reflexivetransitive closure of R and the algorithm is correct.But when will the algorithm terminate? The answer is after at most n 2iterations of the while loop. This is because after each successful iteration apair (ai, a k) is added to R* that was not there before, and there are at mostn 2 pairs to be added. Hence the algorithm will terminate after at most n 2iterations.
And since each iteration can be carried out in O(n 3 ) time (all triplesof elements of A need to be searched), the complexity of the new algorithmis O(n 2 x n 3 ) = O(n 5 ) -a polynomial rate of growth, and thus a spectacularimprovement over our exponential first attempt.Figure 1-10Example 1.6.3: Let us see how the new algorithm performs on the graph inFigure 1-10. We start in the first line with the graph plus all self-loops. Suppose36Chapter 1: SETS, RELATIONS, AND LANGUAGESthat the search for triples (ai, aj, ak) that violate transitivity is conducted in the"natural" orderThe first violation thus discovered is (ai, a4, a3), so edge (ai, a3) is added.
Wenext start checking all triples from the beginning -because the introduction of(at, a3) may have caused a violation of transitivity in a triple that was examinedin the previous iteration. Indeed, the next violation discovered is (ai, a3, a2),and so (ai, a2) is added. We start once again from the beginning, this time todiscover a violation for (a4' a3, a2) -edge (a4, a2) is added. In the next iterationwe go through all triples without discovering a violation, and hence we concludethat we have computed the reflexive transitive closure of the graph.OThis example illustrates the source of our algorithm's relative inefficiency,reflected in the steep n 5 growth of its complexity: A triple (ai,aj,ak) must betested again and again for possible violation of transitivity, since a newly insertedpair may create new violations in triples that have been already checked.Can we do better? In particular, is there a way to order the triples so thatnewly added pairs never introduce transitivity violations in the already examinedtriples? Such an ordering would yield an 0(n 3 ) algorithm, because each triplewould then have to be examined once and only once.As it turns out, such an ordering is possible: We order all triples (ai, aj, ak)to be searched in increasing j -the middle index! We first look systematicallyfor violations of transitivity of the form (ai, ai, ak); those that are found arecorrected by adding the appropriate pairs, and the search continues from thepoint it stopped.
Once all triples of the form (ai, ai, ak) have been examined,we look at all triples of the form (ai, a2, ak), then (ai, a3, ak), and so on. Theprecise order in which the triples within each group are examined is immaterial.Once we examine the last group, all triples of the form (ai, an, ak), then we stop,having computed the reflexive transitive closure. The full algorithm is this:Initially R*:= RU {(ai,ai): ai E A}for each j = 1,2, ... , n dofor each i = 1,2, ... ,n and k = 1,2, ...
,n doif (a;,aj), (aj,ak) E R* but (a;,ak) ~ R* then add (ai,ak) to R*.Why does this idea work? Consider a path (aio, ai, , ... , aik_l , aik) fromaio to ai k , where 1 :S i j :S n for all j. Define the rank of the path to be thelargest integer among il, ... ,ik-l; that is, the largest index appearing in anyintermediate node.
Trivial paths, such as edges and self-loops, have rank zero,as they have no intermediate nodes.With this terminology we can argue about the correctness of our latestalgorithm. In particular, we can prove the following statement: For each j =1.6: Closures and Algorithms370, ... , n, immediately after the jth execution of the outer loop, R* contains allpairs (ai, ak) such that there is a path of rank j or less from ai to ak in R.Notice that, since all paths have rank at most n, this implies that in the end allpairs joined by any path will have been added in R*.The proof of this statement is by induction on j. The result is certainlytrue when j = 0 -no iterations yet, and accordingly R* contains only pairsconnected by trivial paths, of rank O.
For the induction hypothesis, supposethat the result holds for j up to some value, say m < n, and consider them + 1st iteration. We must show that the m + 1st iteration adds to R* preciselythose pairs that are connected in R by paths of rank equal to m + 1, that is, inwhich the highest-indexed node is am+l. If two nodes ai and ak are connected bysuch a path, then they must be connected by such a path in which am+l appearsexactly once -if am+l appears more than once, then omit the portion of the pathbetween the first and the last appearance- while all other intermediate nodesare indexed m or less.
And such a path would consist of a path of rank m or lessfrom ai to am+l, followed by a path of rank m or less from am+l to ak. By theinduction hypothesis, both pairs (ai, am+d and (am+l' ak) must be in R* at thispoint. Therefore, the algorithm will discover that (ai,am+l), (am+l,ak) E R*,but (ai, ak) i:. R*, and will add the pair (ai, ak) to R*.
Conversely, the m + 1stiteration will add to R* only pairs (ai, aj) that are connected by a path of rankexactly m + 1. The algorithm is correct.Example 1.6.3 (continued): If we apply this algorithm to the graph in Figure1-10, no edges are added when j = 1 and j = 2.
Then when j = 3 the edge(a4, a2) is added, and when j = 4 the edges (al' a3) and (at. a2) are added. <:)Closure Properties and ClosuresThe transitive closure of a relation is just one instance of an important style ofdefining larger sets (or relations) starting from smaller ones.Definition 1.6.3: Let D be a set, let n ~ 0, and let R ~ D n + l be a (n + 1)ary relation on D. Then a subset B of D is said to be closed under R ifbn + l E B whenever bl , ... , bn E Band (b l , ... , bn , bn + l ) E R. Any property ofthe form "the set B is closed under relations R 1 , R 2 , ... , Rm" is called a closureproperty of B.Example 1.6.4: The set of a person's ancestors is closed under the relation{( a, b) : a and b are persons, and b is a parent of a},since the parent of an ancestor is also an ancestor.<:)38Chapter 1: SETS, RELATIONS, AND LANGUAGESExample 1.6.5: Let A be a fixed set.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
