Tiểu luận môn Cơ sở mô phỏng ngẫu nhiên

Phần 1. Mở đầu Trong hoạt động cuộc sống, nghiên cứu và học tập, chúng ta rất cần đến sự ngẫu nhiên của các đại lượng. Như chúng ta đã biết, có nhiều ứng dụng phải sử dụng số ngẫu nhiên. Một trong số đó là trong thuật toán mật mã, với mục đích chính là mã hóa một thông điệp để chỉ có người nhận mới được dùng chúng. Muốn vậy chúng ta phải làm cho thông điệp có vẻ như ngẫu nhiên bằng cách dùng một chuỗi giả ngẫu nhiên để mã hóa và cũng với chuỗi đó người nhận có thể giải mã được. Một lĩnh vực khác cũng được sử dụng rộng rãi các số ngẫu nhiên là mô phỏng. Một mô phỏng đặc trưng bao gồm một chương trình mô tả một số khía cạnh của thế giới thực. Các số ngẫu nhiên lại thích hợp làm dữ liệu nhập cho các chương trình như vậy. Ngay cả khi không cần các số ngẫu nhiên, mô phỏng vẫn cần các số tùy ý dùng làm dữ liệu nhập. Nhiều ứng dụng khi phân tích một số lượng lớn dữ liệu, đôi khi chỉ cần xử lý trên một tập con nhỏ của nó, khi đó chỉ cần lựa chọn theo kiểu thử ngẫu nhiên. Có nhiều phương pháp để sinh số ngẫu nhiên. Tiểu luận này sẽ đưa ra hai phương pháp có bản đó là phương pháp đồng dư tuyến tính và đồng dư cộng. Không thể dùng máy vi tính để sinh được chuỗi số ngẫu nhiên thực sự, chúng ta chỉ hy vọng tạo ra các chuỗi có nhiều thuộc tính giống như chuỗi số ngẫu nhiên. Các số này được gọi là các số giả ngẫu nhiên. Có nhiều phương pháp để kiểm tra xem một chuỗi giả ngẫu nhiên có một số thuộc tính của chuỗi ngẫu nhiên hay không. Tiểu luận sẽ trình bày một phương pháp kiểm tra cơ bản đó là phương pháp khi bình phương. Nội dung tiểu luận gồm ba phần: Phần 1: Đưa ra một số khái niệm về số ngẫu nhiên và số giả ngẫu nhiên. Phần 2: Giới thiệu ra hai phương pháp cơ bản để tạo số ngẫu nhiên: đó là phương pháp đồng dư tuyến tính và phương pháp đồng dư cộng. Phần 3: Trình bày một phương pháp khi bình phương nhằm kiểm tra tính ngẫu nhiên của chuỗi được sinh ra. Tiểu luận nhằm mục đích là giới thiệu các thuật toán và những kỹ thuật để dùng máy vi tính tạo số ngẫu nhiên và kiểm tra tính ngẫu nhiên của số được tạo. Để cài đặt cho những thuật toán trong tiểu luận này, chúng tôi sử dụng ngôn ngữ lập trình Pascal. Phần 2. Nội dung I/ Số ngẫu nhiên và số giả ngẫu nhiên Thông thường người ta dùng thuật ngữ ngẫu nhiên khi muốn nói đến một sự tùy ý. Một người yêu cầu một số ngẫu nhiên, nghĩa là không quan tâm đến giá trị của số đó. Tuy nhiên, số ngẫu nhiên là một khái niệm toán học được định nghĩa là mọi số đều có khả năng xuất hiện tương đương nhau. Để đáp ứng được định nghĩa số ngẫu nhiên trên, chúng ta phải giới hạn các số được dùng vào một phạm vi nhất định. Không thể có một số nguyên ngẫu nhiên mà chỉ có một số nguyên ngẫu nhiên trong một miền xác định nào đó. Trong hầu hết các trường hợp ta không phải chỉ cần một số ngẫu nhiên, mà cần đến dãy số ngẫu nhiên. Khi đó cần phải chứng minh nhiều mặt về các thuộc tính của dãy số ngẫu nhiên. Ví dụ trong một chuỗi dài các số ngẫu nhiên của một phạm vi nhỏ, chúng ta có thể muốn biết số lần xuất hiện của các giá trị trong chuỗi. Không có cách nào để tạo ra các số ngẫu nhiên thực sự từ một máy vi tính. Bởi vì khi ta viết chương trình tạo số ngẫu nhiên thì các số mà chương trình tạo ra chắc chắn có thể suy luận được. Cách tốt nhất mà chúng ta hy vọng là viết các chương trình để tạo ra các chuỗi số có được nhiều thuộc tính giống như các số ngẫu nhiên. Các số này thường được gọi là các số giả ngẫu nhiên. Chúng không thật sự ngẫu nhiên nhưng chúng có thể hữu dụng như sự xấp xỉ của các số ngẫu nhiên. Tiểu luận này trình bày phương pháp tạo số ngẫu nhiên trên máy vi tính nên ở một mức độ nào đó, từ nay ta thống nhất số giả ngẫu nhiên với số ngẫu nhiên. Có nhiều phương pháp để sinh những chuỗi số như vậy. Chẳng hạn phương pháp đồng dư tuyến tính, phương pháp đồng dư cộng, phương pháp đồng dư toàn phương... Các phương pháp này phải đáp ứng được các yêu cầu sau: -Những số được sinh ra phải phân bố đều và độc lập về mặt thống kê. Giá trị của một số trong một chuỗi ngẫu nhiên không liên quan đến giá trị của số kế tiếp. Chuỗi phải không được lặp lại đối với bất kỳ độ dài nào. -Tốc độ sinh số ngẫu nhiên phải nhanh. Bởi vì trong quá trình một mô phỏng thực hiện thường yêu cầu một số lượng lớn các số ngẫu nhiên. Nếu công cụ sinh chậm thì chi phí thực hiện mô phỏng sẽ cao. -Thuật toán để sinh số ngẫu nhiên sử dụng càng ít bộ nhớ càng tốt. Bởi vì chương trình mô phỏng thường yêu cầu bộ nhớ lớn nhưng bộ nhớ thường bị giới hạn. Trong một số trường hợp, một số thuộc tính của các số ngẫu nhiên thì quan trọng trong khi các thuộc tính còn lại thì không cần thiết. Trong trường hợp đó, cần tạo ra các số gần ngẫu nhiên, chúng chắc chắn có các thuộc tính mong muốn nhưng chưa chắc có các thuộc tính khác. Trong một số ứng dụng, các số gần ngẫu nhiên có thể là thích hợp hơn các số giả ngẫu nhiên. Có nhiều phương pháp để kiểm tra xem một chuỗi giả ngẫu nhiên có một số thuộc tính của chuỗi ngẫu nhiên hay không. Chẳng hạn phương pháp kiểm tra số ngẫu nhiên theo luật phân phối đều, phân phối chuẩn, phân phối mũ.. Trong phần tiếp theo ta sẽ xem xét cụ thể hai phương pháp sinh số ngẫu nhiên và một phương pháp kiểm tra tính ngẫu nhiên của chuỗi được sinh. II/ Các phương pháp tạo số ngẫu nhiên Nhiều công trình nghiên cứu nhằm đưa ra các thuật toán sinh chuỗi số giả ngẫu nhiên. Thuật toán không chỉ khó trong kỹ thuật mà còn khó trong tốc độ sinh số ngẫu nhiên, độ dài vòng lặp, và tính chính xác của chương trình. Phần này giới thiệu hai phương pháp thông dụng là phương pháp đồng dư tuyến tính và phương pháp đồng dư cộng. 1/ Phương pháp đồng dư tuyến tính. Phương pháp đồng dư tuyến tính được D. Lehner đề xuất vào năm 1951. Đây là phương pháp nổi tiếng và rất thường được sử dụng để tạo số ngẫu nhiên. Phương pháp này được đặc trưng bởi công thức đệ quy sinh số thứ n+1 dựa trên số thứ n như sau: an+1=(b*an + c) mod m (n³0). Giá trị khởi đầu là hằng số a0, hằng số b là một số nhân, hằng số c là số gia và m là số chia (modulus). Sự lựa chọn những giá trị của những hằng số này có ảnh hưởng đến độ dài chu kỳ của chuỗi số ngẫu nhiên được sinh ra. Ta thấy, trong phương pháp này những số kế tiếp trong chuỗi được sinh ra bởi mối quan hệ đệ quy. Để tạo một số ngẫu nhiên mới, ta dùng số trước đó nhân với b, cộng thêm c, chia cho m và lấy phần dư. Như vậy số nhận được luôn nằm trong đoạn từ 0 đến m-1 Ví dụ 1: Cho b=2, c=3, m=10 và a0=0 thì ta có a0=0 a1=(2*0+3) mod 10=3 a2=(2*3+3) mod 10=9 a3=(2*9+3) mod 10=1 a4=(2*1+3) mod 10=5 a5=(2*5+3) mod 10=3 a6=(2*3+3) mod 10=9 a7=(2*9+3) mod 10=1 a8=(2*1+3) mod 10=5 Ví dụ 2: Cho b=2, c=0, m=10 và a0=1 thì ta có a0=1 a1=(2*1) mod 10=2 a2=(2*2) mod 10=4 a3=(2*4) mod 10=8 a4=(2*8) mod 10=6 a5=(2*6) mod 10=2 a6=(2*2) mod 10=4 a7=(2*4) mod 10=8 a8=(2*8) mod 10=6 Trong ví dụ 2 minh họa trường hợp trong đó c=0. Thuật toán này được gọi là phương pháp đồng dư nhân. Nếu cạ0 thuật toán được gọi là phương pháp đồng dư hỗn hợp. Cả hai ví dụ minh họa khả năng lặp lại của bất kỳ của chuỗi được sinh bởi lược đồ này. Thuật toán trên rất thích hợp khi sử dụng trong máy vi tính để tạo số ngẫu nhiên vì nó dễ cài đặt. Dưới đây là đoạn chương trình tạo ra N số ngẫu nhiên cho mảng A. Program tao_mang_ngau_nhien; type mmc=array[1..1000] of word; Var a:mmc; c,m,i:word; Begin c:=3; m:=10 a[0]:=0; for i:=1 to 100 do a[i]:=(a[i-1]*b+c) mod m; end. Để có được số ngẫu nhiên tốt, phải có cách chọn các hằng số a0, b và m. Nhiều tài liệu đã cung cấp một số hướng dẫn trong việc chọn các hằng số này. Trước hết m nên lớn, vì chu kỳ sẽ luôn luôn nhỏ hơn m nên khi m lớn thì sự lặp lại của các số sẽ ít hơn. m có thể là giá trị tối đa của một kiểu nguyên nhưng cũng không cần phải hoàn toàn lớn như vậy nếu không tiện. Thông thường, chọn m là lũy thừa của 10 hoặc 2 là thuận lợi trong việc tính toán đồng dư. Thứ hai là chọn b và c: Một chuỗi được sinh ra bởi sơ đồ đồng dư tuyến tính có chu kỳ m nếu và chỉ nếu: c là nguyên tố cùng nhau với m. b-1 là bội số của mọi số nguyên tố chia cho m. b-1 là bội của 4 nếu m là bội của 4. Những ràng buộc này dẫn đến những giá trị số nhân có dạng b=zp+1, trong đó z là cơ số được dùng trong biểu diễn số của máy tính, k là số lượng bít tối đa của kiểu nguyên, m=zk và zÊp<k. Như đối với sự lựa chọn của c, b phải thỏa mãn yêu cầu là nguyên tố cùng nhau với m. Theo tài liệu Algorithms, b nên là một hằng số tùy ý, không theo một mẫu riêng nào cả, ngoại trừ nó nên kết thúc bởi ....x21, với x chẵn. b không nên quá lớn hoặc quá nhỏ. Một sự lựa chọn an toàn là dùng một số ít hơn m một chữ số. Điều này giúp tránh được một số sự cố có thể xảy ra mà các phân tích toán học còn để hở. Thứ ba là chọn x0. Nếu chu kỳ của chuỗi là m, sự lựa chọn x0 là không quan trọng, vì toàn bộ chuỗi sẽ được sinh ra. Tuy nhiên cần chú ý khi chọn x0=0 và sử dụng phương pháp đồng dư nhân sẽ dẫn đến một chuỗi thoái hóa. Các quy luật nêu trên được phát triển bởi D. E. Knuth. Knuth chứng minh rằng các sự lựa chọn này làm cho phương pháp đồng dư tuyến tính tạo ra các số ngẫu nhiên tốt, thỏa mãn được nhiều kiểm tra thống kê phức tạp. Một tình huống xấu nhất là chuỗi số được sinh ra có chu kỳ nhỏ so với miền xác định của nó. Ví dụ như với b=19, m=381, a0=0 sẽ tạo ra chuỗi không ngẫu nhiên 0, 1, 20, 0, 1, 20,... trong khoảng từ 0 đến 380. Không phải dễ để nhận ra được các tình huống như trên. Vì vậy tốt nhất nên theo các chỉ dẫn của Knuth đưa ra để tránh được những trường hợp “xấu” mà ông đã tìm được. Khi các giá trị khởi động khác nhau thì tạo thành các chuỗi ngẫu nhiên khác nhau. Thường thì không cần phải lưu trữ cả chuỗi như chương trình nêu trên. Ngược lại, chúng ta chỉ cần lưu lại trong một biến toàn cục a, khởi động với một giá trị nào đó, rồi cập nhật bằng phép tính a:=(a*b+1) mod m. Trong Pascal, chúng ta còn một bước nữa mới có thể thực hiện được, bởi vì chúng ta không được phép bỏ qua tình trạng tràn số. Tràn số là một trường hợp lỗi mà có thể tạo ra các kết quả không dự đoán được. Giả sử máy tính có kiểu nguyên 32 bít và ta chọn m=100000000, b=31415821, a=1234567. Tất cả các giá trị này đều nhỏ hơn giá trị tối đa của kiểu số nguyên, nhưng phép toán nhân đã làm cho nó tràn a*b+1. Kết quả được tạo ra sẽ không có quan hệ với tính toán của chúng ta. Vì ta chỉ quan tâm đến 8 ký số sau cùng nên có một kỹ thuật để loại bỏ sự tràn là phân nhỏ phép nhân ra làm nhiều phần. Để nhân p và q, ta viết p=104p1+p0 q=104q1+q0. Do đó phép nhân được viết: p*q= (104p1+p0)*(104q1+q0)=104p1q1+104(p1q0+p0q1)+p0q0 Chúng ta chỉ muốn 8 ký số cho kết quả, vì thế có thể bỏ qua số hạng đầu tiên (104p1q1) và bỏ qua bốn ký số đầu tiên của số hạng thứ hai 104(p1q0+p0q1). Ta có chương trình như dưới đây Procedure tao_chuoi_ngau_nhien; const m=100000000; m1=10000;b=3141581; var i,a,N:integer; Function nhan(p,q:integer):integer; var p1,p0,q1,q0:integer; Begin p1:=p div m1; p0:=p mod m1; q1:=q div m1; q0:=q mod m1; nhan:=(((p0q1+p1q0) mod m1)*m1+p0q0) mod m; End; Function randomint:integer; Begin a:=(nhan(a,b)+1) mod m; randomint:=a; End; BEGIN readln(N,a); for i:=1 to N do write(random); Readln; END. Hàm nhan() trong chương trình này tính (p*q mod m) không bị tràn khi mà m nhỏ hơn 1/2 giá trị số nguyên tối đa. Khi chạy chương trình với dữ liệu nhập N=10 và q=124567 chương trình sẽ tạo được 10 số như sau: 35884508, 80001069, 63512650, 43635651, 1034472, 87181513, 6917174, 209855, 67115956, 59939877. Trong các số này, có sự không ngẫu nhiên: ví dụ, các ký số hàng đơn vị xoay vòng qua các ký số từ 0 đến 9. Dễ dàng chứng minh được điều này là do từ công thức. Nói chung các ký số bên phải không thật sự ngẫu nhiên. Đây là hạn chế cơ bản của phương pháp đồng dư tuyến tính để tạo số ngẫu nhiên. Để tạo một số nguyên ngẫu nhiên trong giới hạn [0,r-1], ta có thể thay hàm random() ở chương trình trên bởi hàm dưới đây: Function badrandom(r:integer):integer; begin a:=(nhan(b,a)+1) mod m badrandom:= a mod r end; Hàm này được đánh giá là không “tốt” vì các ký số không ngẫu nhiên bên phải là các ký số được sử dụng, nên chuỗi kết quả chỉ có được ít thuộc tính mong muốn. Vấn đề này có thể dễ dàng khắc phục bằng cách dùng các ký số bên trái thay thế. Hàm được viết lại là: Function newrandom(r:integer):integer; begin a:=(nhan(b,a)+1) mod m newrandom:= a*r div m end; Hàm trên cho ta một số nguyên ngẫu nhiên giữa 0 và r-1. Tuy nhiên tình huống tràn vẫn còn có thể xảy ra. Ta cải tiến lại hàm này như sau: Function randomint(r:integer):integer; Begin a:=(nhan(a,b)+1) mod m; randomint:=((a div m1)*r) div m1; End; Để tạo số thực ngẫu nhiên giữa 0 và 1, ta xem các số tạo như trên là phân thập phân với chấm thập phân ở bên trái. Điều này có thể cài được dễ dàng bằng cách trả về giá trị thực a/m thay vì số nguyên a. Hàm tạo số thực ngẫu nhiên giữa 0 và 1 được viết. Function randomreal:real; Begin a:=(nhan(a,b)+1) mod m; randomreal:=a/m; End; Khi đó người sử dụng có thể nhận được một số nguyên trong giới hạn [0,r) bằng cách đơn giản nhân giá trị này với r và cắt lấy phần nguyên của kết quả. Hay có thể nói một số thực ngẫu nhiên giữa 0 và 1 mới chính là số cần thiết. 2/ Phương pháp đồng dư cộng. Một phương pháp khác để tạo các số ngẫu nhiên là dựa trên “các thanh ghi dịch chuyển hồi tiếp tuyến tính” được sử dụng trên các máy mã hóa trước đây. ý tưởng bắt đầu với một thanh ghi chứa một mẫu tùy ý, sau đó chuyển sang phải một bước, bỏ vào các vị trí trống bên trái bằng một bít được xác định bằng cách XOR của hai bít phải nhất của thanh ghi đó. Một thanh ghi dịch chuyển hồi tiếp tuyến tính 4 bít Ví dụ: Nếu thanh ghi được khởi tạo là 1111 thì sau dịch chuyển, nội dung là 0111 (1 XOR 1=0), tiếp theo sẽ là 0011, 0001, 1000, 0100, 0010, 1001, 1100,0110, 1011, 0101, 1010, 1101, 1110, 1111. Khi chúng ta nhận lại mẫu khởi tạo, tiến trình hiển nhiên đã lặp lại. Chú ý rằng tất cả các mẫu bít có thể có đều xuất hiện: giá trị khởi đầu lặp lại sau 15 bước. Tuy nhiên, nếu ta thay đổi các vị trí các bít lấy ra dùng để tính giá trị cho hồi tiếp bên trái thì sẽ được một chuỗi hoàn toàn khác. Ví dụ, ta lấy bít 0 và 2 thay vì 0 và 1 như trên (thứ tự tính từ phải sang trái) thì chúng ta nhận được chuỗi 1111, 0111, 0011, 1001, 1100, 1110, 1111, không phải chu kỳ đầy đủ như trước. Thông thường với thanh ghi n bít, chúng ta có thể sắp xếp để chiều dài vòng lặp là 2n-1. Vì vậy, với giá trị n đủ lớn, các thanh ghi n bít tạo được chuỗi ngẫu nhiên khá tốt. Thông thường, chúng ta thường lấy n=31 hay n=63. Cũng như phương pháp đồng dư tuyến tính, các đặc tính toán học của các thanh ghi này đã được nghiên cứu nhằm đưa ra nhiều phương án lựa chọn vị trí lấy ra các bít để tính giá trị bít bên phải để tạo được tất cả các mẫu. Ví dụ với n=31, các vị trí rút ra có thể là 0 và một trong các vị trí: 4, 7, 8, 14, 19, 25, 26, hay 29. Một cách thực hiện khác là có thể tính toán một lần một một số nguyên thay vì mỗi lần một bít với phương pháp đệ quy như trên. Trong ví dụ trên nếu sử dụng phép toán XOR bit cho hai số kế tiếp, chúng ta tạo được một số sẽ xuất hiện tại ba vị trí sau đó trong danh sách. Điều này giúp ta có được một phương pháp tạo số ngẫu nhiên có thể dễ dàng áp dụng cho máy vi tính. Dùng thanh ghi dịch chuyển hồi tiếp với hai bít lấy ra tính toán là bít thứ b và thứ c, cũng giống như dùng công thức đệ quy sau: a[k]:=(a[k-b]+a[k-c]) mod m Để thích hợp với phương pháp thanh ghi dịch chuyển, phép toán cộng trong công thức này nên được thay thế bằng phép toán XOR trên bít. Tuy nhiên, điều này chứng tỏ rằng có thể tạo được các số ngẫu nhiên tốt ngay cả khi chỉ dùng phép cộng số nguyên thông thường mà thôi. Phương pháp này gọi là đồng dư cộng (additive congruential) Bít phải nhất của các số trong phương pháp này cũng giống như các bít trong thanh ghi dịch chuyển hồi tiếp tương ứng. Do đó số bước đạt được trước khi bắt đầu lặp lại, ít nhất cũng bằng chiều dài của chu kỳ lặp. Với phương pháp này các số ngẫu nhiên được tạo ra vượt qua được các kiểm tra thống kê. Để cài đặt chương trình tạo số ngẫu nhiên theo phương pháp đồng dư cộng, chúng ta cần giữ một bảng gồm c phần tử, luôn chứa c số được tạo ra gần nhất. Việc tính toán được tiếp tục bằng cách thay thế một trong các số trong bảng bằng tổng của hai số khác trong bảng. Khởi đầu, bảng nên gồm các số không lớn quá và cũng không nhỏ quá. Một cách đơn giản là dùng phương pháp đồng dư tuyến tính để sinh ra bảng này. Knuth khuyên nên chọn b=31, c=55. Khi đó chúng ta cần phải giữ lại 55 số được tạo gần nhất. Cấu trúc dữ liệu thích hợp là dùng hàng đợi, nhưng bởi vì kích thước của bảng cố định nên chúng ta chỉ dùng một mảng kích thước đó, với chỉ số xoay vòng như sau: Procedure randominit(s:integer); begin a[0]:=s;j:=0; repeat j:=j+1; a[j]:=(nhan(b,a[j-1])+1) mod m; until j=54; end; Function randomint(r:integer):integer; begin j:=(j+1) mod 55; a[j]:=a[(j+23) mod 55] + a[(j+54) mod 55]) mod m; randomint:=((a[j] div m1)*r) div m1; end; Biến toàn cục a được thay bằng một mảng và một con trỏ chỉ số j trên mảng. Dung lượng lớn của mảng a là một khuyết điểm của phương pháp này trong một số ứng dụng. Nhưng nó cũng chính là một ưu điểm, bởi vì nó làm cho chu kỳ lặp rất dài, ít nhất 255-1 ngay cả khi m nhỏ. Hàm randomint trả về một số nguyên giữa 0 và r-1. Và dĩ nhiên, chúng ta cũng có thể dễ dàng thay đổi như phần trước để trả về một số thực ngẫu nhiên giữa 0 và 1 bằng cách a[j]/m. Hàm randomint() được viết lại randomreal() như sau: Function randomreal:real; begin j:=(j+1) mod 55; a[j]:=a[(j+23) mod 55] + a[(j+54) mod 55]) mod m; randomreal:=a[j]/m; end; Ví dụ: Cho m=10, và mở rộng chuỗi 1, 2, 4, 8, 6 được sinh trong ví dụ trước. a1 = 1 a2 = 2 a3 = 4 a4 = 8 a5 = 6 a6 = (a5 + a1) mod 10 = (6+1) mod 10 =7 a7 = (a6 + a2) mod 10 = (7+2) mod 10 =9 a8 = (a7 + a3) mod 10 = (9+4) mod 10 =3 a9 = (a8 + a4) mod 10 = (3+8) mod 10 =1 a10 = (a9 +a5) mod 10 = (1+6) mod 10 =7 a11 = (a10 + a6) mod 10 = (7+7) mod 10 =4 a12 = (a11 + a7) mod 10 = (4+9) mod 10 =3 a13 = (a12 + a8) mod 10 = (3+3) mod 10 =6 a14 = (a13 + a9) mod 10 = (6+1) mod 10 =7 a15 = (a14 + a10) mod 10 = (7+7) mod 10 =4 a16 = (a15 + a11) mod 10 = (4+4) mod 10 =8 a17 = (a16 + a12) mod 10 = (8+3) mod 10 =1 a18 = (a17 + a13) mod 10 = (1+6) mod 10 =7 a19 = (a18 + a14) mod 10 = (7+7) mod 10 =4 a20 = (a19 + a15) mod 10 = (4+4) mod 10 =8 III/ Kiểm tra tính ngẫu nhiên bằng phương pháp “Khi bình phương”. Thường có thể dễ dàng nhận ra một chuỗi là không ngẫu nhiên, nhưng thật khó chứng minh rằng một chuỗi là ngẫu nhiên. Như đã đề cập trước đây, không có một chuỗi nào được tạo bằng máy vi tính có thể thực sự ngẫu nhiên, nhưng chúng ta có thể có được một chuỗi thể hiện nhiều đặc tính của các số ngẫu nhiên. Thực tế, thường không thể xác định chính xác thuộc tính nào của số ngẫu nhiên là quan trọng đối với một trình ứng dụng đặc biệt. Hơn nữa, lúc nào cũng nên nghĩ đến việc thực hiện một vài kiểu kiểm tra trên phương pháp tạo số ngẫu nhiên, để đảm bảo rằng không có trường hợp suy thoái xảy ra. Các phương pháp tạo số ngẫu nhiên có thể rất tốt nhưng cũng có khi rất xấu. Nhiều kiểm tra được triển khai để xác định một chuỗi có được nhiều thuộc tính của chuỗi ngẫu nhiên thực sự hay không. Hầu hết các kiểm tra này đều có cơ sở trong toán học. Trong số đó kiểm tra “khi-bình phương” là một kiểm tra thống kê cơ bản, dễ cài đặt và hữu dụng trong nhiều ứng dụng. ý tưởng của phương pháp khi bình phương là xem xét các số tạo ra có phân bố một cách hợp lý hay không. Nếu chúng ta tạo ra N số dương có giá trị nhỏ hơn r thì chúng ta mong muốn nhận được khoảng N/r số cho mỗi giá trị. Nhưng số lần xuất hiện của tất cả các giá trị cũng không được bằng nhau, vì nếu số lần xuất hiện của tất cả các giá trị bằng nhau thì không còn là ngẫu nhiên nữa. Điều này dẫn đến việc cần tính toán xem một chuỗi các số có được phân bố giống như một chuỗi ngẫu nhiên hay không bằng cách tính tổng số của bình phương số lần xuất hiện của mỗi giá trị, chia cho tần số mong muốn (N/r), rồi trừ bớt chiều dài chuỗi (N). Ta có chương trình kiểm tra tính ngẫu nhiên của chuỗi được sinh ra như sau: Function khi_binh_phuong(N,r,s:integer):real; var i,t:integer; f:array[0..rmax] of integer; begin raninit(s); for i:=0 to rmax do f[i]:=0; for i:=1 to n do begin t:=randomint(r); f[t]:=f[t]+1; end; t:=0; for i:=0 to r-1 do t:=t+f[i]*f[i]; Khi_binh_phuong:=((r*t/N)-N); end; Giá trị của hàm là giá trị thống kê khi bình phương và cũng có thể biểu diễn kết quả của công thức toán học sau: Với 0<i<r. Nếu giá trị thống kê khi bình phương “gần” với r thì các số đó là ngẫu nhiên, ngược lại, nếu nó “xa” r thì chúng không ngẫu nhiên. Đối với phương pháp kiểm tra đơn giản mà chúng ta đang thực hiện, giá trị thống kê chỉ nên lệch một khoảng 2 so với r. Điều này chỉ đúng nếu N lớn hơn 10r. Để đảm bảo chuỗi tạo ra là ngẫu nhiên, nên thực hiện kiểm tra nhiều lần. Phương pháp kiểm tra này cài đặt đơn giản nên thích hợp cho việc tích hợp nó vào bên trong mỗi chương trình tạo số ngẫu nhiên, nhằm đảm bảo rằng không có điều gì ngoài dự tính có thể gây ra các vấn đề nghiêm trọng. Tất cả các thuật toán “tốt” mà chúng ta đã thảo luận đều vượt qua được kiểm tra này. Sử dụng phương pháp tạo nêu trên cho 1000 số có giá trị nhỏ hơn 100, chúng ta có giá trị thống kê khi bình phương là 100.8 đối với phương pháp đồng dư tuyến tính và 105.4 đối với phương pháp đồng dư cộng. Cả hai phương pháp đều đạt trong vùng lệch 20 so với 100 (tức là trong [80,120]). Phần 3. Kết luận Như chúng ta đã biết, có nhiều phương pháp tạo số ngẫu nhiên. Tiểu luận đã trình bày kỹ thuật tạo số ngẫu nhiên bằng máy vi tính với hai phương pháp thông dụng là phương pháp đồng dư tuyến tính và phương pháp cộng. Có hai cách để lập trình sinh ra chuỗi ngẫu nhiên. Người ta thường tạo một hàm, khởi động nó, rồi gọi lặp lại nhiều lần, mỗi lần trả về một số ngẫu nhiên. Một cách khác là chỉ gọi một lần, và nó tạo ra dãy các số ngẫu nhiên cho trình ứng dụng. Trong cả hai trường hợp trên, người ta đều mong muốn nhận được các chuỗi giống nhau trong các lời gọi kế tiếp (để tìm lỗi hay so sánh các chương trình khác nhau trên cùng dữ liệu nhập) và tạo được một chuỗi tùy ý. Tất cả các điểm nêu trên đòi hỏi phải dùng đến trạng thái được giữ lại giữa các lời gọi của hàm tạo số ngẫu nhiên. Điều này có thể không thuận lợi trong một số môi trường lập trình. Phương pháp cộng bất lợi vì có một trạng thái khá lớn (mảng giữ các số nguyên vừa tạo) nhưng lại có một thuận lợi là có một chu kỳ dài, mà có thể không cần phải khởi tạo. Cho dù công cụ tạo số ngẫu nhiên tốt đến bao nhiêu đi nữa vẫn có thể sinh ra chuỗi không ngẫu nhiên hoặc không có nhiều thuộc tính ngẫu nhiên mong muốn. Vì vậy, cần phải xem xét cẩn thận các công cụ tạo số ngẫu nhiên bằng cách thực hiện nhiều loại kiểm tra thống kê, nếu không thì thì khó đảm bảo một phương pháp tạo số ngẫu nhiên là tốt. Tiểu luận đã trình bày được một phương pháp kiểm tra tính ngẫu nhiên của chuỗi được sinh ra, đó là phương pháp “khi bình phương”. Đây là một phương pháp kiểm tra khá chặt chẽ và dễ cài đặt. Ngoài ra, để có được công cụ tạo số ngẫu nhiên tốt thì cần phải dựa trên các phân tích toán học và nhiều kinh nghiệm thực tế. Một phương pháp được đề xuất nhằm tránh các sai lệch xảy ra trong thao tác tạo số ngẫu nhiên là kết hợp các phương pháp với nhau. Chẳng hạn dùng phương pháp đồng dư tuyến tính để tạo mảng ban đầu cho phương pháp đồng dư cộng. Lời kết: Để hoàn thành được đề tài này, ngoài sự nỗ lực và cố gắng của bản thân, tác giả đã nhận được sự giúp đỡ qúy báu của Quý Thầy, PGS.TS. Trần Lộc Hùng. Là một học viên chuyên ngành Tin học và dù rất tâm đắc với đề tài đang nghiên cứu nhưng với thời gian có hạn và khối lượng kiến thức của bản thân còn ít ỏi nên chắc chắn tiểu luận không tránh khỏi những hạn chế trong việc tiếp cận, nghiên cứu và trình bày. Tác giả xin kính trọng cảm ơn sự giúp đỡ quý báu của Quý Thầy và mong được đón nhận từ Quý Thầy sự góp ý để giúp tác giả có được hiểu biết đúng hơn đối với vấn đề đang nghiên cứu đồng thời mong được sự lượng thứ cho những sơ suất trong tiểu luận này. tài liệu tham khảo [1] Phạm Văn Khánh Lý thuyết mô phỏng đại lượng ngẫu nhiên và quá trình ngẫu nhiên [2] Robert Sedgewick Algorithms Addison-Wesley Publishing 2nd Edition [3] Các tài liệu về sinh số ngẫu nhiên: Generation of random numbers Mục lục Nội dung Trang Mở đầu ......................................................................................................................... .......................... 1 Nội dung ......................................................................................................................... ...................... 2 1-Số ngẫu nhiên và số giả ngẫu nhiên .......................................................................... 2 2-Các phương pháp tạo số ngẫu nhiên .......................................................................... 3 Phương pháp đồng dư tuyến tính ................................................................