1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 3
Текст из файла (страница 3)
For example, suppose that you are asked whetherwe can use tiles from a given finite list of basic shapes to tile the whole plane.If the set of shapes contains a square, or even any triangle, then the answeris obviously "yes." But what if it consists of a few bizarre shapes, or if someof the shapes are mandatory, that is, they must be used at least once for thetiling to qualify? This is surely the kind of complicated question that you wouldlike to have answered by a machine. In Chapter 5 we use the formalism ofTuring machines to prove that this and many other problems cannot be solvedby computers at all.Even when a computational task is amenable to solution by some algorithm,it may be the case that there is no reasonably fast, practically feasible algorithmthat solves it.
In the last two chapters of this book we show how real-life computational problems can be categorized in terms of their complexity: Certainproblems can be solved within reasonable, polynomial time bounds, whereasothers seem to require amounts of time that grow astronomically, exponentially.In Chapter 7 we identify a class of common, practical, and notoriously difficultproblems that are called NP-complete (the traveling salesman problem is onlyone of them). We establish that all these problems are equivalent in that, if oneof them has an efficient algorithm, then all of them do.
It is widely believed thatall NP-complete problems are of inherently exponential complexity; whetherthis conjecture is actually true is the famous P -:j; NP problem, one of the mostimportant and deep problems facing mathematicians and computer scientiststoday.This book is very much about algorithms and their formal foundations.However, as you are perhaps aware, the subject of algorithms, their analysisand their design, is considered in today's computer science curriculum quiteseparate from that of the theory of computation.
In the present edition of thisbook we have tried to restore some of the unity of the subject. As a result,this book also provides a decent, if somewhat specialized and unconventional,introduction to the subject of algorithms. Algorithms and their analysis areintroduced informally in Chapter 1, and are picked up again and again in thecontext of the restricted models of computation studied in Chapters 2 and 3,and of the natural computational problems that they Hpawn. This way, whengeneral models of algorithms are sought later, the reader is in a better positionto appreciate the scope of the quest, and to judge its success. Algorithms playa4I ntrod uctionmajor role in our exposition of complexity as well, because there is no better wayto appreciate a complex problem than to contrast it with another, amenable toan efficient algorithm.
The last chapter culminates in a Hection on coping withNP-completeness, where we present an array of algorithmic techniques thathave been successfully used in attacking NP-complete problems (approximationalgorithms, exhaustive algorithms, local search heuristics, and so on).Computation is eSHential, powerful, beautiful, challenging, ever-expanding-and so is its theory. This book only tells the beginning of an exciting Htory.It is a modest introduction to a few basic and carefully selected topics from thetreasure chest of the theory of computation. We hope that it will motivate itsreaderH to seek out more; the references at the end of each chapter point to goodplaces to start.1Sets, Relations, and La nguages1.1 SETSThey say that mathematics is the language of science - it is certainly the language of the theory of computation, the scientific discipline we shall be studyingin this book.
And the language of mathematics deals with sets, and the complex ways in which they overlap, intersect, and in fact take part themselves informing new sets.A set is a collection of objects. For example, the collection of the four lettersa, b, c, and d is a set, which we may name L; we write L = {a, b, c, d}. Theobjects comprising a set are called its elements or members. For example, bis an element of the set L; in symbols, bEL. Sometimes we simply say that bis in L, or that L contains b. On the other hand, z is not an element of L, andwe write z ~ L.In a set we do not distinguish repetitions of the elements.
Thus the set{red, blue, red} is the same set as {red, blue}. Similarly, the order of the elementsis immaterial; for example, {3, 1, 9}, {9, 3,1}, and {I, 3, 9} are the same set. Tosummarize: Two sets are equal (that is, the same) if and only if they have thesame elements.The elements of a set need not be related in any way (other than happeningto be all members of the same set); for example, {3, red, {d, blue}} is a set withthree clements, one of which is itself a set. A set may have only one element;it is then called a singleton.
For example, {I} is the set with 1 as its onlyelement; thus {1} and 1 are quite different. There is also a set with no elementat all. Naturally, there can be only one such set: it is called the empty set, andis denoted by 0. Any set other than the empty set is said to be nonempty.So far we have specified sets by simply listing all their elements, separatedby commas and included in braces. Some sets cannot be written in this way,56Chapter 1: SETS.
RELATIONS. AND LANGUAGESbecause they are infinite. For example, the set N of natural numbers is infinite;we may suggest its elements by writing N = {D, 1, 2, ... }, using the three dotsand your intuition in place of an infinitely long list. A set that is not infinite isfinite.Another way to specify a set is by referring to other sets and to propertiesthat elements mayor may not have.
Thus if I = {l, 3, 9} and G = {3,9}, Gmay be described as the set of elements of I that are greater than 2. We writethis fact as follows.G = {x : x E I and x is greater than 2}.In general, if a set A has been defined and P is a property that elements of Amayor may not have, then we can define a new setB = {x: x E A and x has propertyPl.As another example, the set of odd natural numbers is0= {x : x E N and x is not divisible by 2}.A set A is a subset of a set B --in symbols, A ~ B- if each element ofA is also an element of B. Thus 0 ~ N, since each odd natural number is anatural number. Note that any set is a subset of itself. If A is a subset of Bbut A is not the same as B, we say that A is a proper subset of B and writeA C B. Also note that the empty set is a subset of every set. For if B is any set,then 0 ~ B, since each element of 0 (of which there are none) is also an elementof B.To prove that two sets A and B are equal, we may prove that A ~ BandB ~ A.
Every element of A must then be an element of B and vice versa, sothat A and B have the same elements and A = B.Two sets can be combined to form a third by various set operations, justas numbers are eombined by arithmetic operations such as addition. One setoperation is union: the union of two sets is that set having as elements theobjects that are elements of at least one of the two given sets, and possibly ofboth. We use the symbol U to denote union, so thatA U B = {x : x E A or x E B}.For example,{l, 3, 9} u {3, 5, 7} = {I, 3, 5, 7, 9}.The intersection of two sets is the eollection of all elements the two setshave in common; that is,An B = {x : x E A and x E B}.1.1: Sets7For example,{I, 3, 9} n {3, 5, 7} = {3},and{1,3,9} n {a,b,c,d} = 0.Finally, the difference of two sets A and B, denoted by A - B, is the set of allelements of A that are not elements of B.A - B = {x: xEA and x~B}.For example,{I, 3, 9} - {3, 5, 7} = {I, 9}.Certain properties of the set operations follow easily from their definitions.For example, if A, B, and C are sets, the following laws hold.AUA=AAnA=AAUB=BUAAnB=BnA(A U B) U C = AU (B U C)(A n B) n C = An (B n C)(A U B) n C = (A n C) U (B n C)(A n B) U C = (A U C) n (B U C)(A U B) nA = A(AnB) UA = AA - (B U C) = (A - B) n (A - C)A - (B n C) = (A - B) U (A - C)IdempotencyCommutativityAssociativityDistributivityAbsorptionDeMorgan's lawsExample 1.1.1: Let us prove the first of De Morgan's laws.
LetL = A - (B U C)andR = (A - B) n (A - C);we are to show that L= R.We do this by showing (a) L~R and (b) R~L.(a) Let x be any element of L; then x E A, but x ~ B and x ~ C. Hencex is an element of both A - B and A - C, and is thus an element of R.Therefore L ~ R.( b) Let x E R; then x is an element of both A - B and A - C, and istherefore in A but in neither B nor C. Hence x E A but x ~ B U C, sox E L.Chapter 1: SETS, RELATIONS, AND LANGUAGES8Therefore R~L, and we have established that L = R.OTwo sets are disjoint if they have no element in common, that is, if theirintersection is empty.It is possible to form intersections and unions of more than two sets. IfS is any collection of sets, we write U S for the set whose elements are theelements of all the sets in S.
For example, if S = {{a, b}, {b, c}, {c, d}} thenUS = {a, b, c, d}; and if S = {{ n} : n EN}, that is, the collection of all thesingleton sets with natural numbers as elements, then US = N. In general,uSimilarly,S= {x : xEP for some set PES}.n= {x : xEP for each set PES}.SThe collection of all subsets of a set A is itself a set, called the power setof A and denoted 2A. For example, the subsets of {c, d} are {c, d} itself, thesingletons {c} and {d} and the empty set 0, so2{c,d}= {{c,d},{c},{d},0}.A partition of a non empty set A is a subset II of 2A such that 0 is not anelement of II and such that each element of A is in one and only one set in II.That is, II is a partition of A if II is a set of subsets of A such that(1) each element of II is nonempty;(2) distinct members of II are disjoint;(3) UII = A.For example, {{a, b}, {c}, {d}} is a partition of {a, b, c, d}, but {{b, c}, {c, d} }is not.
The sets of even and odd natural numbers form a partition of N.Problems for Section 1.11.1.1. Determine whether each of the following is true or false.(a)0~ 0(b) 0 E 0(c) 0 E {0}(d) 0 ~ {0}(e) {a,b} E {a,b,c,{a,b}}(f) {a, b} ~ {a, b, {a, b}}(g) {a,b}~ 2{a,b,{a,b}}(h) {{a, b}} E2{a,b,{a,b}}(i) {a,b,{a,b}}-{a,b}={a,b}1.2: Relations and Functions91.1.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
