tailieunhanh - Thuật toán Algorithms (Phần 5)

Tham khảo tài liệu 'thuật toán algorithms (phần 5)', 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ả | 3. Random Numbers Our next set of algorithms will be methods for using a computer to generate random numbers. We will find many uses for random numbers later on let s begin by trying to get a better idea of exactly what they are. Often in conversation people use the term random when they really mean arbitrary. When one asks for an arbitrary number one is saying that one doesn t really care what number one gets almost any number will do. By contrast a random number is a precisely defined mathematical concept every number should be equally likely to occur. A random number will satisfy someone who needs an arbitrary number but not the other way around. For every number to be equally likely to occur to make sense we must restrict the numbers to be used to some finite domain. You can t have a random integer only a random integer in some range you can t have a random real number only a random fraction in some range to some fixed precision. It is almost always the case that not just one random number but a sequence of random numbers is needed otherwise an arbitrary number might do . Here s where the mathematics comes in it s possible to prove many facts about properties of sequences of random numbers. For example we can expect to see each value about the same number of times in a very long sequence of random numbers from a small domain. Random sequences model many natural situations and a great deal is known about their properties. To be consistent with current usage we ll refer to numbers from random sequences as random numbers. There s no way to produce true random numbers on a computer or any deterministic device . Once the program is written the numbers that it will produce can be deduced so how could they be random The best we can hope to do is to write programs which produce of numbers having many of the same properties as random numbers. Such numbers are commonly called pseudo-random numbers they re not really random but they can be useful 33 34 CHAF TER 3 as .