Thuật toán Algorithms (Phần 32)

Chia sẻ: Tran Anh Phuong | Ngày: | Loại File: PDF | Số trang:10

0
30
lượt xem
3
download

Thuật toán Algorithms (Phần 32)

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'thuật toán algorithms (phần 32)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:
Lưu

Nội dung Text: Thuật toán Algorithms (Phần 32)

  1. 303 Exercises 1. Decrypt the following message, which was encrypted with a Vigenere cipher using the pattern CAB (repeated as necessary) for the key (on a 27-letter alphabet, with blank preceding A): DOBHBUAASXFZWJQQ 2. What table should be used to decrypt messages that have been encrypted using the table substitution method? 3. Suppose that a Vigenere cipher with a two-character key is used to encrypt a relatively long message. Write a program to infer the key, based on the assumption that the frequency of occurrence of each character in odd positions should be roughly equal to the frequency of occurrence of each character in the even positions. 4. Write matching encryption and decryption procedures which use the “exclusive or” operation between a binary version of the message with a binary stream from one of the linear congruential random number generators of Chapter 3. 5. Write a program to “break” the method given in the previous exercise, assuming that the first 10 characters of the message are known to be blanks. 6. Could one encrypt plaintext by “and”ing it (bit by bit) with the key? Explain why or why not. 7. True or false: Public-key cryptography makes it convenient to send the same message to several different users. Discuss your answer. 8. What is P(S(M)) for the RSA method for public-key cryptography? 9. RSA encoding might involve computing Mn, where M might be a k digit number, represented in an array of k integers, say. About how many operations would be required for this computation? 10. Implement encryption/decryption procedures for the RSA method (as- sume that s, p and N are all given and represented in arrays of integers of size 25).
  2. 304 SOURCES for String Processing The best references for further information on many of the algorithms in this section are the original sources. Knuth, Morris, and Pratt’s 1977 paper and Boyer and Moore’s 1977 paper form the basis for much of the material from Chapter 19. The 1968 paper by Thompson is the basis for the regular- expression pattern matcher of Chapters 20-21. Huffman’s 1952 paper, though it predates many of the algorithmic considerations here, still makes interesting reading. Rivest, Shamir, and Adleman describe fully the implementation and applications of their public-key cryptosystem in their 1978 paper. The book by Standish is a good general reference for many of the topics covered in these chapters, especially Chapters 19, 22, and 23. Parsing and compiling are viewed by many to be the heart of computer science, and there are a large number of standard references available, for example the book by Aho and Ullman. An extensive amount of background information on cryptography may be found in the book by Kahn. A. V. Aho and J. D. Ullman, Principles of Compiler Design, Addison-Wesley, Reading, MA, 1977. R. S. Boyer and J. S. Moore, “A fast string searching algorithm,” Communica- tions of the ACM, 20, 10 (October, 1977). D. A. Huffman, “A method for the construction of minimum-redundancy codes,” Proceedings of the IRE, 40 (1952). D. Kahn, The Codebreakers, Macmillan, New York, 1967. D. E. Knuth, J. H. Morris, and V. R. Pratt, “Fast pattern matching in strings,” SIAM Journal on Computing, 6, 2 (June, 1977). R. L. Rivest, A. Shamir and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Communications of the ACM, 21, 2 (February, 1978). T. A. Standish, Data Structure Techniques, Addison-Wesley, Reading, MA, 1980. K. Thompson, “Regular expression search algorithm,” Communications of the ACM, 11, 6 (June, 1968).
  3. GEOMETRIC ALGORITHMS
  4. 24. Elementary Geometric Methods Computers are being used more and more to solve large-scale problems which are inherently geometric. Geometric objects such as points, lines and polygons are the basis of a broad variety of important applications and give rise to an interesting set of problems and algorithms. Geometric algorithms are important in design and analysis systems for physical objects ranging from buildings and automobiles to very large-scale integrated circuits. A designer working with a physical object has a geometric intuition which is difficult to support in a computer representation. Many other applications directly involve processing geometric data. For example, a political “gerrymandering” scheme to divide a district up into areas which have equal population (and which satisfy other criteria such as putting most of the members of the other party in one area) is a sophisticated geometric algorithm. Other applications abound in mathematics and statistics, where many types of problems arise which can be naturally set in a geometric representation. Most of the algorithms that we’ve studied have involved text and num- bers, which are represented and processed naturally in most programming environments. Indeed, the primitive operations required are implemented in the hardware of most computer systems. For geometric problems, we’ll see that the situation is different: even the most elementary operations on points and lines can be computationally challenging. Geometric problems are easy to visualize, but that can be a liability. Many problems which can be solved instantly by a person looking at a piece of paper (example: is a given point inside a given polygon?) require non- trivial computer programs. For more complicated problems, as in many other applications, the method of solution appropriate for implementation on a computer might be quite different from the method of solution appropriate for a person. 307
  5. CWAPTER 24 One might suspect that geometric algorithms would have a long history because of the constructive nature of ancient geometry and because useful applications are so widespread, but actually much of the work in the field has been quite recent. Of course, it is often the case that the work of an- cient mathematicians has useful application in the development of algorithms for modern computers. The field of geometric algorithms is interesting to study because there is strong historical context, because new fundamental algorithms are still being developed, and because many important large-scale applications require these algorithms. Points, Lines, and Polygons Most of the programs that we’ll study will operate on simple geometric objects defined in a two-dimensional space. (But we will consider a few algorithms which work in higher dimensions.) The fundamental object is a point, which we’ll consider to be a pair of integers -the “coordinates” of the point in the usual Cartesian system. Considering only points with integer coordinates leads to slightly simpler and more efficient algorithms, and is not as severe a restriction as it might seem. A line is a pair of points, which we assume are connected together by a straight line segment. A polygon is a list of points: we assume that successive points are connected by lines and that the first point is connected to the last to make a closed figure. To work with these geometric objects, we need to be decide how to represent them. Most of our programs will use the obvious representations type point = record x,y: integer end; line = record pl, p2: point end; Note that points are restricted to have integer coordinates. A real repre- sentation could also be used. However, it is important to note that restricting the algorithms to process only integers can be a very significant timesaver in many computing environments, because integer calculations are typically much more efficient that “floating-point” calculations. Thus, when we can get by with dealing only with integers without introducing much extra complica- tion, we will do so. More complicated geometric objects will be represented in terms of these basic components. For example, polygons will be represented as arrays of points. Note that using arrays of lines would result in each point on the polygon being included twice (though that still might be the natural repre- sentation for some algorithms). Also, it is useful for some applications to include extra information associated with each point or line. This can clearly be handled by adding an info field to the records.
  6. ELEMENTARY GEOMETRIC METHODS 309 We’ll use the following set of sixteen points to illustrate the operation of several geometric algorithms: ‘N .E ‘L l K ‘ 0 l F *A ‘C ‘I ‘G l J ‘H l D l M l B The points are labeled with single letters for reference in explaining the examples. The programs usually have no reason to refer to points by “name”; they are simply stored in an array and are referred to by index. Of course, the order in which the points appear in the array may be important in some of the programs: indeed, it is the goal of some geometric algorithms to “sort” the points into some particular order. The labels that we use are assigned in the order in which the points are assumed to appear in the input. These points have the following integer coordinates: A B C D E F G H I J K L M N O P x: 3 11 6 4 5 8 1 7 9 14 10 16 15 13 2 12 y: 9 1 8 3 15 11 6 4 7 5 13 14 2 16 12 10 A typical program will maintain an array p [1..N] of points and simply read in N pairs of integers, assigning the first pair to the x and y coordinates of p [I], the second pair to the x and y coordinates of p [2], etc. When p is representing a polygon, it is sometimes convenient to maintain “sentinel” values p[O]=p[N] and p[N+l]=p[l].
  7. 310 CXAPTER 24 At some’ point, we usually want to “draw” our geometric objects. Even if this is not inherent in the application, it is certainly more pleasant to work with pictures than numbers when developing or debugging a new implemen- tation. It is clear that the fundamental operation here is drawing a line. Many types of hardware devices have this capability, but it is reasonable to consider drawing lines using just characters, so that we can print approximations to picture of our objects directly as output to Pascal programs (for example). Our restriction to integer point coordinates helps us here: given a line, we simply want a collection of points that approximates the line. The following recursive program draws a line by drawing the endpoints, then splitting the line in half and drawing the two halves. procedure draw(l: line) ; var dx, dy: integer; t: point; 11,12: line; begin dot(l.pl.x,l.pl.y); dot(l.p2.x,l.p2.y); dx:=J.p2.x-1.pl.x; dy:=l.p2.y-1.pl.y; if (abs(dx)>l) or (abs(dy)>l) then begin t.x:=l.pl .x+dx div 2; t.y:=l.pl .y+dy div 2; Il.pl:=l.pl; H.p2:=t; draw(l1); /2.pl:=t; /2.p2:=l.p2; draw(12); end ; end ; The procedure dot is assumed to “draw” a single point. One way to implement this is to maintain a two-dimensional array of characters with one character per point allowed, initialized to “a”. The dot simply corresponds to storing a different character (say rr*“) in the array position corresponding to the referenced point. The picture is “drawn” by printing out the whole array. For example, when the above procedure is used with such a dot procedure with a 33x33 picture array to “draw” the lines connecting our sample points BG, CD, EO, IL, and PK at a resolution of two characters per unit of measure, we get the following picture:
  8. ELEMENTARY GEOMETRIC METHODS 311 ................................. ................................. ........ ..* ...................... ....... ..* ....................... ...... ..* .................... ...* ..... ..*.......................*. .... ..*.............*.........* .. ... ... ..*...............*.......* .... .. ..*................*......* .................... ..*....* ..... ..*..* ...... ..................... ..*.* ....... ..................... ...................... ..* ........ ..* ......... ..................... .................... ..* .......... ................... ..* ........... ..*.......* ............ .......... ..*......* ............. .......... ......... ..*......* .............. ......... ..* ..................... ..................... ..**.......* ... .***...* ...................... ...................... ..... ..**.* ....... ..* ....................... ....... ..*** ..................... ....... ..*..** ................... ...... ..*.....*** ................ ..** .............. ............... ................. ..* ............. .................. ..** ........... ..* .......... .................... ................................. ................................. Algorithms for converting geometric objects to points in this manner are called scan-conversion algorithms. This example illustrates that it is easy to draw nice-looking diagonal lines like EO and IL, but that it is somewhat harder to make lines of arbitrary slope look nice using a coarse matrix of characters. The recursive method given above has the disadvantages that it is not particularly efficient (some points get plotted several times) and that it doesn’t draw certain lines very well (for example lines which are nearly horizontal and nearly vertical). It has the advantages that it is relatively simple and that it handles all the cases of the various orientation of the endpoints of the line in a uniform way. Many sophisticated scan-conversion algorithms have been developed which are more efficient and more accurate than this recursive one. If the array has a very large number of dots, then the ragged edges of the lines aren’t discernible, but the same types of algorithms are appropriate. However, the very high resolution necessary to make high-quality lines can require very large amounts of memory (or computer time), so sophisticated algorithms are called for, or other technologies might be appropriate. For example, the text of this book was printed on a device capable of printing millions of dots per square inch, but most of the lines in the figures were drawn
  9. 312 CHAPTER 24 with pen and ink. Line Intersection As our first example of an elementary geometric problem, we’ll consider the problem of determining whether or not two given line segments intersect. The following diagram illustrates some of the situations that can arise. E / 0 When line segments actually intersect, as do CD and BG, the situation is quite straightforward except that the endpoint of one line might fall on the other, as in the case of KP and IL. When they don’t intersect, then we extend the line segments and consider the position of the intersection point of these extended lines. This point could fall on one of the segments, as in the case of IL and BG, or it could lie on neither of the segments, as in the case of CD and OE, or the lines could be parallel, as in the case of OE and IL. The straightforward way to solve this problem is to find the intersection point of the lines defined by the line segments, then check whether this intersection point falls between the endpoints of both of the segments. Another easy method uses a tool that we’ll find useful later, so we’ll consider it in more detail: Given a line and oints, we’re often interested in whether the two points fall on the same the line or not. This function is straightforward to compute from the for the lines as follows:
Đồng bộ tài khoản