1
1
Các phương pháp tạo số ngẫu
Các phương pháp tạo số ngẫu
nhiên phân bố đều
nhiên phân bố đều
Nhóm 6
Nhóm 6
Phạm Thị Kiều Trang
Phạm Thị Kiều Trang
Vũ Văn Ninh
Vũ Văn Ninh
Phạm Quốc Thịnh
Phạm Quốc Thịnh
Nguyễn Vũ Minh
Nguyễn Vũ Minh
2
Yêu cầu
Yêu cầu

Trình bày các phương pháp tạo số ngẫu nhiên phân bố đều
Trình bày các phương pháp tạo số ngẫu nhiên phân bố đều

Nêu các ví dụ ứng dụng trong thực tiễn
Nêu các ví dụ ứng dụng trong thực tiễn
3
Số ngẫu nhiên phân bố đều
Số ngẫu nhiên phân bố đều

Trong công việc nghiên cứu về tín hiệu, chúng ta không thể không
Trong công việc nghiên cứu về tín hiệu, chúng ta không thể không

Độc lập về thống kê

Có khả năng tái tạo
Có khả năng tái tạo
4
Linear Congruence
Linear Congruence
(Đồng dư tuyến tính)
(Đồng dư tuyến tính)

Đặc trưng bởi hàm số:
Đặc trưng bởi hàm số:
x
x
i+1
i+1
=[ax
=[ax
i
i
+ c]mod(m)
+ c]mod(m)
Trong đó a và c là hằng số, m là module.
Trong đó a và c là hằng số, m là module.
a,c,m đều là số nguyên dương.
a,c,m đều là số nguyên dương.

Hàm này tạo ra một chuỗi số liên tiếp giả ngẫu
Hàm này tạo ra một chuỗi số liên tiếp giả ngẫu
nhiên với khởi đầu là số cho trước x

, ) (mod m)

Additive congruential method: là trường hợp đặc biệt của
Additive congruential method: là trường hợp đặc biệt của
Mixed congruential method khi
Mixed congruential method khi
f(x
f(x
i
i
, x
, x
i-1
i-1
, , x
, , x
i-k
i-k
) = a
) = a
1
1
x
x
i
i
+ a
+ a
2
2

ngẫu nhiên để tạo ra một chuỗi ngẫu nhiên mới
ngẫu nhiên để tạo ra một chuỗi ngẫu nhiên mới
6
Tausworthe generators
Tausworthe generators

Đặc trưng bởi hàm:
Đặc trưng bởi hàm:
x
x
i
i
= (a
= (a
1
1
x
x
i-1
i-1
+ a
+ a
2
2
x
x
i-2
i-2
+ + a
+ + a

n-1
+ x
+ x
n-2
n-2

Bộ tạo số ngẫu nhiên Fibonacci đặc trưng bởi hàm:
Bộ tạo số ngẫu nhiên Fibonacci đặc trưng bởi hàm:
x
x
n
n
= (x
= (x
n-1
n-1
+ x
+ x
n-2
n-2
) mod m
) mod m
8
Tính chất của bộ tạo số ngẫu nhiên
Tính chất của bộ tạo số ngẫu nhiên

Một hàm số đơn giản cũng sẽ cho ta một kết quả ngẫu nhiên thực sự. Mục đích của bộ tạo số
Một hàm số đơn giản cũng sẽ cho ta một kết quả ngẫu nhiên thực sự. Mục đích của bộ tạo số
ngẫu nhiên là tạo ra một chuỗi số mà khó có thể đoán trước được. Việc sử dụng một loạt các bước
ngẫu nhiên là tạo ra một chuỗi số mà khó có thể đoán trước được. Việc sử dụng một loạt các bước

x
n
n
= (9806x
= (9806x
n-1
n-1
+ 1)mod(2
+ 1)mod(2
17
17
- 1)
- 1)
Với giá trị x
Với giá trị x
0
0
=37.911, hàm của chúng ta sẽ bị kẹt và chỉ tạo ra số 37.911 liên tiếp.
=37.911, hàm của chúng ta sẽ bị kẹt và chỉ tạo ra số 37.911 liên tiếp.
Một số bộ tạo còn yêu cầu giá trị khởi tạo thỏa mãn một điều kiện nào đó, hay chu kỳ của chuỗi số
Một số bộ tạo còn yêu cầu giá trị khởi tạo thỏa mãn một điều kiện nào đó, hay chu kỳ của chuỗi số
phụ thuộc giá trị khởi tạo. Cần tránh việc sử dụng chúng do chúng ta sẽ khó trong việc quản lý.
phụ thuộc giá trị khởi tạo. Cần tránh việc sử dụng chúng do chúng ta sẽ khó trong việc quản lý.

Một thiết lập chính xác cho hàm khởi tạo là quan trọng. Tính ngẫu nhiên cũng như chu kỳ của bộ
Một thiết lập chính xác cho hàm khởi tạo là quan trọng. Tính ngẫu nhiên cũng như chu kỳ của bộ
tạo số chỉ được xác định khi ta chọn chính xác hàm tạo số. Nếu xảy ra tràn bộ nhớ hay giá trị của
tạo số chỉ được xác định khi ta chọn chính xác hàm tạo số. Nếu xảy ra tràn bộ nhớ hay giá trị của
chúng ta bị cắt xén, làm tròn, tính ngẫu nhiên và chu kỳ có thể bị thay đổi.
chúng ta bị cắt xén, làm tròn, tính ngẫu nhiên và chu kỳ có thể bị thay đổi.