| Home / lib / TU Wien Scripta / Informatik / Algorithmen / | ||
|
|
Size 1.1Mb Date Sep 15, 2004 |
Chapter 0: What This Book Is About but also, no one has proved the impossibility of doing so. It should be added that the entire area is vigorously being researched because of the attractiveness and the importance of the many unanswered questions that remain. Thus, even though we just don’t know many things that we’d like to know in this field , it isn’t for lack of trying!...
Chapter 1: Mathematical Preliminaries sharper because not only does it tell us that the function is bounded when x is large, we learn that the function actually approaches 0 as x → ∞. This is typical of the relationship between O and o. It often happens that a ‘O’ result is sufficient for an application. However, that may not be the case, and we may need the more precise ‘o’ estimate. The third symbol of the language of asymptotics is the ‘Θ.’ Definition. We say that f (x) = Θ(g(x)) if there are constants c1 = 0, c2 = 0, x0 such that for all x > x0 it is true that c1 g(x) < f (x) < c2 g(x). We might then say that f and g are of the same rate of growth, only the multiplicative constants are uncertain. Some examples of the ‘Θ’ at work are (x + 1)2 = Θ(3x2 ) (x2 + 5x + 7)/(5x3 + 7x + 2) = Θ(1/x) 3 √ 1 + 2x = Θ(x 4 ) (1 + 3/x)x = Θ(1). The ‘Θ’ is much more precise than either the ‘O’ or the ‘o.’ If we know that f (x) = Θ(x2 ), then we know that f (x)/x2 stays between two nonzero constants for all sufficiently large values of x. The rate of growth of f is established: it grows quadratically with x. The most precise of the symbols of asymptotics is the ‘∼.’ It tells us that not only do f and g grow at the same rate, but that in fact f /g approaches 1 as x → ∞. Definition. We say that f (x) ∼ g(x) if limx→∞ f (x)/g(x) = 1. Here are some examples. x2 + x ∼ x2 (3x + 1)4 ∼ 81x4 sin 1/x ∼ 1/x (2x3 + 5x + 7)/(x2 + 4) ∼ 2x 2x + 7 log x + cos x ∼ 2x Observe the importance of getting the multiplicative constants exactly right when the ‘∼’ symbol is used. While it is true that 2x2 = Θ(x2 ), it is not true that 2x2 ∼ x2 . It is, by the way, also true that 2x2 = Θ(17x2 ), but to make such an assertion is to use bad style since no more information is conveyed with the ‘17’ than without it. The last symbol in the asymptotic set that we will need is the ‘Ω.’ In a nutshell, ‘Ω’ is the negation of ‘o.’ That is to say, f (x) = Ω(g(x)) means that it is not true that f (x) = o(g(x)). In the study of algorithms for computers, the ‘Ω’ is used when we want to express the thought that a certain calculation takes at least so-and-so long to do. For instance, we can multiply together two n × n matrices in time O(n3 ). Later on in this book we will see how to multiply two matrices even faster, in time O(n2.81 ). People know of even faster ways to do that job, but one thing that we can be sure of is this: nobody will ever be able to write a matrix multiplication program that will multiply pairs n × n matrices with fewer than n2 computational steps, because whatever program we write will have to look at the input data, and there are 2n2 entries in the input matrices. Thus, a computing time of cn2 is certainly a lower bound on the speed of any possible general matrix multiplication program. We might say, therefore, that the problem of multiplying two n × n matrices requires Ω(n2 ) time. The exact definition of the ‘Ω’ that was given above is actually rather delicate. We stated it as the negation of something. Can we rephrase it as a positive assertion? Yes, with a bit of work (see exercises 6 and 7 below). Since ‘f = o(g)’ means that f /g → 0, the symbol f = Ω(g) means that f /g does not approach zero. If we assume that g takes positive values only, which is usually the case in practice, then to say that f /g does not approach 0 is to say that ∃ > 0 and an infinite sequence of values of x, tending to ∞, along which |f |/g > . So we don’t have to show that |f |/g > for al l large x, but only for infinitely many large x. 6...
This is rather a good estimate of the growth of n!, since the right member is only about ne times as large as the left member (why?), when n is large. By the use of slightly more precise machinery one can prove a better estimate of the size of n! that is called Stirling’s formula, which is the statement that x√ x! ∼ ( )x 2xπ . e (1.1.10)...
1.2 Positional number systems The octal system is popular because it provides a good way to remember and deal with the long bit strings that the binary system creates. According to the theorem, in the octal system the digits that we need are 0, 1, . . . , 7. For instance, (735)8 = (477)10. The captivating feature of the octal system is the ease with which we can convert between octal and binary. If we are given the bit string of an integer n, then to convert it to octal, all we have to do is to group the bits together in groups of three, starting with the least significant bit, then convert each group of three bits, independently of the others, into a single octal digit. Conversely, if the octal form of n is given, then the binary form is obtainable by converting each octal digit independently into the three bits that represent it in the binary system. For example, given (1101100101)2. To convert this binary number to octal, we group the bits in threes, (1)(101)(100)(101) starting from the right, and then we convert each triple into a single octal digit, thereby getting (1101100101)2 = (1545)8 . If you’re a working programmer it’s very handy to use the shorter octal strings to remember, or to write down, the longer binary strings, because of the space saving, coupled with the ease of conversion back and forth. The hexadecimal system (base 16) is like octal, only more so. The conversion back and forth to binary now uses groups of four bits, rather than three. In hexadecimal we will need, according to the theorem above, 16 digits. We have handy names for the first 10 of these, but what shall we call the ‘digits 10 through 15’ ? The names that are conventionally used for them are ‘A,’ ‘B,’...,‘F.’ We have, for example, (A52C )16 = 10(4096) + 5(256) + 2(16) + 12 = (42284)10 = (1010)2 (0101)2 (0010)2 (1100)2 = (1010010100101100)2 = (1)(010)(010)(100)(101)(100) = (122454)8....
Observe that we are looking at the right side of (1.3.1) with x = 3. Therefore the answer is (310 − 1)/2. Try to get used to the idea that a series in powers of x becomes a number if x is replaced by a number, and if we know a formula for the sum of the series then we know the number that it becomes. Here are some more series to keep in your zoo. A parenthetical remark like ‘(|x| < 1)’ shows the set of values of x for which the series converges. k∞
=0 ∞ m =0...
define a new unknown sequence y1 , y2 , . . . Now substitute for xn in (1.4.5), getting b1 b2 · · · bn+1 yn+1 = bn+1 b1 b2 · · · bn yn + cn+1 . We notice that the coefficients of yn+1 and of yn are the same, and so we divide both sides by that coefficient. The result is the equation yn+1 = yn + dn+1 (n ≥ 0; y0 given) (1.4.7) where we have written dn+1 = cn+1 /(b1 · · · bn+1 ). Notice that the d’s are known. We haven’t yet solved the recurrence relation. We have only changed to a new unknown function that satisfies a simpler recurrence (1.4.7). Now the solution of (1.4.7) is quite simple, because it says that each y is obtained from its predecessor by adding the next one of the d’s. It follows that yn = y0 + jn
=1...
| © 2007 eKnigu | ||
| много! Шикарное предложение: Тюнинг porshe cayenne ну или тюнинг acura mdx вдвое доступнее. Удобно.. бурение артезианских скважин |