<> "The repository administrator has not yet configured an RDF license."^^ . <> . . . "Algorithms and Complexity"^^ . "An algorithm is a method for solving a class of problems on a computer. The complexity of an algorithm\r\nis the cost, measured in running time, or storage, or whatever units are relevant, of using the algorithm to\r\nsolve one of those problems.\r\nThis book is about algorithms and complexity, and so it is about methods for solving problems on\r\ncomputers and the costs (usually the running time) of using those methods.\r\nComputing takes time. Some problems take a very long time, others can be done quickly. Some problems\r\nseem to take a long time, and then someone discovers a faster way to do them (a ‘faster algorithm’). The\r\nstudy of the amount of computational effort that is needed in order to perform certain kinds of computations\r\nis the study of computational complexity.\r\nNaturally, we would expect that a computing problem for which millions of bits of input data are\r\nrequired would probably take longer than another problem that needs only a few items of input. So the time\r\ncomplexity of a calculation is measured by expressing the running time of the calculation as a function of\r\nsome measure of the amount of data that is needed to describe the problem to the computer.\r\nFor instance, think about this statement: ‘I just bought a matrix inversion program, and it can invert\r\nan n × n matrix in just 1.2n3 minutes.’ We see here a typical description of the complexity of a certain\r\nalgorithm. The running time of the program is being given as a function of the size of the input matrix.\r\nA faster program for the same job might run in 0.8n3 minutes for an n × n matrix. If someone were\r\nto make a really important discovery (see section 2.4), then maybe we could actually lower the exponent,\r\ninstead of merely shaving the multiplicative constant. Thus, a program that would invert an n × n matrix\r\nin only 7n2.8 minutes would represent a striking improvement of the state of the art.\r\nFor the purposes of this book, a computation that is guaranteed to take at most cn3 time for input of\r\nsize n will be thought of as an ‘easy’ computation. One that needs at most n10 time is also easy. If a certain\r\ncalculation on an n × n matrix were to require 2n minutes, then that would be a ‘hard’ problem. Naturally\r\nsome of the computations that we are calling ‘easy’ may take a very long time to run, but still, from our\r\npresent point of view the important distinction to maintain will be the polynomial time guarantee or lack of\r\nit.\r\nThe general rule is that if the running time is at most a polynomial function of the amount of input\r\ndata, then the calculation is an easy one, otherwise it’s hard.\r\nMany problems in computer science are known to be easy. To convince someone that a problem is easy,\r\nit is enough to describe a fast method for solving that problem. To convince someone that a problem is\r\nhard is hard, because you will have to prove to them that it is impossible to find a fast way of doing the\r\ncalculation. It will not be enough to point to a particular algorithm and to lament its slowness. After all,\r\nthat algorithm may be slow, but maybe there’s a faster way.\r\nMatrix inversion is easy. The familiar Gaussian elimination method can invert an n ×n matrix in time\r\nat most cn3.\r\nTo give an example of a hard computational problem we have to go far afield. One interesting one is\r\ncalled the ‘tiling problem.’ Suppose* we are given infinitely many identical floor tiles, each shaped like a\r\nregular hexagon. Then we can tile the whole plane with them, i.e., we can cover the plane with no empty\r\nspaces left over. This can also be done if the tiles are identical rectangles, but not if they are regular\r\npentagons.\r\nIn Fig. 0.1 we show a tiling of the plane by identical rectangles, and in Fig. 0.2 is a tiling by regular\r\nhexagons.\r\nThat raises a number of theoretical and computational questions. One computational question is this.\r\nSuppose we are given a certain polygon, not necessarily regular and not necessarily convex, and suppose we\r\nhave infinitely many identical tiles in that shape. Can we or can we not succeed in tiling the whole plane?\r\nThat elegant question has been proved* to be computationally unsolvable. In other words, not only do\r\nwe not know of any fast way to solve that problem on a computer, it has been proved that there isn’t any"^^ . "2008-03-06" . . . "Internet Edition, Summer, 1994"^^ . . . . . . . . "Wilf"^^ . "Herbert S."^^ . "Wilf Herbert S."^^ . . . . . . "Algorithms and Complexity (Text)"^^ . . . "AlgoComp.pdf"^^ . . . "Algorithms and Complexity (Other)"^^ . . . . . . "lightbox.jpg"^^ . . . "Algorithms and Complexity (Other)"^^ . . . . . . "preview.jpg"^^ . . . "Algorithms and Complexity (Other)"^^ . . . . . . "medium.jpg"^^ . . . "Algorithms and Complexity (Other)"^^ . . . . . . "small.jpg"^^ . . . "Algorithms and Complexity (Other)"^^ . . . . . . "indexcodes.txt"^^ . . "HTML Summary of #7046 \n\nAlgorithms and Complexity\n\n" . "text/html" . . . "Algoritma E-book" . .