Оқулық ретінде ұсынған Алматы 2012

Д.Н. Шоқаев 
 
 
16
Қиықтау  әдісінің  идеясын  қолданып,  бірқалыпты  үлес-
тірілген  кездейсоқ  сандарды  тудыратын  алғашқы  алгоритмді 
1946  ж.  Фон  Нейман  мен  Метрополис  ұсынған  болатын.  Бұл 
алгоритм “орта шаршы” деген атқа ие болды, және 
k
2
-орынды 
сандармен жұмыс істейді. Есептеу алгоритмі келесі қадамдардан 
тұрады: 
1-қадам. 
k
n
a
...
a
a
,
z
2
2
1
0

 деп аламыз. 
2-қадам. 
n
z -ді шаршылаймыз: 
k
n
b
...
b
b
,
z
4
2
1
2
0

.
 
3-қадам.  Алынған  шаршының 
k
2   орта  цифрын  алып, 
оларды тізбектің келесі санының разрядтары деп есептейміз: 
k
k
k
n
b
...
b
b
,
z
3
2
1
1
0




. 
Бұл  алгоритм  бізге  бұрыннан  белгілі,  (1.2)  формуласына 
сәйкес келетініне оңай көз жеткізуге болады.  
1.1-мысал, 
1981
0
0
,
z 
 болсын, сонда 
2

k
 болады. Шешуі:  
,
 
,
z
1981
0
0

 
 
 ,
,
z
03924361
0
2
0

 
 ,
,
z
9243
0
1

 
 
 ,
,
z
85433049
0
2
1

 
 
 ,
,
z
4330
0
2

 
 
 ,
,
z
18748900
0
2
2

 
 ,
,
z
7489
0
3

 
 
және т. б. 
Өкінішке  орай,  орта  шаршы  алгоритмі  көп  жағдайларда 
статистикалық  қанағатты  нәтижелер  бермейді.  Осы  алгоритм-
мен  тізбектелген  кездейсоқ  сандардың  арасында  мәні  кішірек, 
яғни  математикалық  үміті 
5
0,
m
z

 
сандар  көбірек  кездеседі. 
Сонымен  қатар,  тізбектің  аяғы  нөлге  айналуын,  яғни  тізбектің 
жұпындалуын жиі байқауға болады. 
ХХ  ғасырдың  50-жылдарының  бас  кезінде  американдық 
ғалым  Дж.  Форсайт  жүргізген  сынақтар  мынандай  нәтижелер 
берді. 16 бастапқы мәндердің 12-сі: 
0,6100
0,8100;
0,4100;
0,2100;
0,6100;
   
циклмен  аяқталатын  тізбекке,  ал  екеуі  тізбектің  жұпындалуына 
алып келді.  
Кейде  орта  шаршы  алгоритммен  жасалған  тізбекте 
кездейсоқ сандар тіпті байқалмайды. 

Компьютермен модельдеу негіздері 
 
 
17
1.2-мысал. [3] 
4500
0
0
,
z 
 тең болсын. 
Шешімі: 
 ,
,
z
4500
0
0

 
 
 ,
,
z
20250000
0
2
0

 
 ,
,
z
2500
0
1

 
 
,
 
,
z
06250000
0
2
1

 
 ,
,
z
2500
0
2

 
 
 ,
,
z
06250000
0
2
2

 
 ,
,
z
2500
0
3

 
 
және т. б. 
Осы  кемшіліктердің  салдарынан  қазіргі  уақытта  орта 
шаршы  алгоритмі  кең  қолданылмайды  және  ол  біз  үшін  тек 
тарихи  көзқарас  түрінде  қалады.  Оның  бұрынғы  кең 
қолданылуы  қарапайымдылығы  мен  қызық  ерекшелігі  арқылы 
түсіндіріледі.  
Дж.  Фон  Нейманның  жолын  қуушылар  бұл  алгоритмнің 
біраз модификациясын ұсынды. Мысалы, жақсы нәтижелерге 






1
2
2
1
10
10
10




n
n
k
k
k
n
n
z
z
D
Ц
z
,
z
Ф
                   (1.3) 
функциясына  негізделген  алгоритммен  жетуге  болады.  Соған 
қарамастан,  қазіргі  кезде  кездейсоқ  сандар  тізбегін  тудыратын 
барлық  қолданбалы  программалар  шегерінділер  мен  қосын-
дылар әдістеріне негізделген.  
 
1.3.  Шегерінділер әдісі (конгруэнттік әдіс) 
 
Бұл  әдісті  1948  ж.  Д.  Леймар  ұсынған  болатын.  Жалпы 
жағдайда  шегерінді  әдісі  мына  түрдегі  сызықты  формулаға 
негізделеді: 
),
m
(mod
C
az
z
*
n
*
n


1
                            
(1.4) 
мұндағы 
c
,
a
,
z
*
0
 және 
m
 – теріс емес бүтін сандар. 
(1.4)  түріндегі  жазу 
*
n
z
1

  саны 
c
az
*
n

1
  өрнегін 
m
-ге 
бөлгендегі  қалдыққа  тең  екенін  көрсетеді,  басқаша  айтқанда, 
*
n
z
1

  –  бұл 
c
az
*
n

1
-ң 
m
  модулі  бойынша  алынған  ең  кіші  оң 
шегеріндісі.  Параметрлері  қандай  да  мәнге  ие  болмасын,  (1.4) 
формуласымен  тек  қана  ақырғы  жиын  құратын  бүтін  кездейсоқ 
сандар  ғана  алуға  болады,  содан  кейін  тізбектегі  сандар 

Д.Н. Шоқаев 
 
 
18
қайталана  бастайды.  Бұл  айқындығы  күмәнсіз 
m
P 
  шекте-
луінен келіп шығады, мұндағы 
P  кездейсоқ тізбектің периоды.  
1.3-мысал. 
9
5
7
0




m
,
z
c
,
a
*
 болсын. 
Сонда 
,
)
(mod
z
*
4
9
5
7
5
1




 
             
,
)
(mod
z
*
6
9
5
7
4
2




   
             
,
)
(mod
z
*
2
9
5
7
6
3




 
             
,
)
(mod
z
*
1
9
5
7
2
4




 
             
,
)
(mod
z
*
3
9
5
7
1
5




 
             
,
)
(mod
z
*
8
9
5
7
3
6




 
             
,
)
(mod
z
*
7
9
5
7
8
7




 
             
,
)
(mod
z
*
0
9
5
7
7
8




 
             
5
9
5
7
0
9




)
(mod
z
*
     және т.б. 
Енді (1.4) өрнегінің 
0

c
 болған жағдайдағы дербес түрін 
қарастырайық: 
 
).
m
(mod
az
z
*
n
*
n

1
  (1.5) 
Бұл формула кездейсоқ тізбектерді біршама тез, бірақ (1.4) 
формуласына қарағанда азырақ периодпен модельдейді. 
1.4-мысал. 
m
 ,
a
, 
*
z
0
 параметрлерінің мәндерін бұрынғыдай 
қалдырамыз.  
Сонда: 
,
)
(mod
z
*
8
9
7
5
1



 
,
)
(mod
z
*
5
9
7
2
3



 
   
,
)
(mod
z
*
2
9
7
8
2



 
.
)
(mod
z
*
8
9
7
5
4



 
1.3-мысал  шегерінділер  әдісінің  бір  артықшылығын  жақсы 
бейнелейді.  Ол  –  (1.4)  өрнегін  қолданғанда,  кездейсоқ  сандар 
тізбегінің  ешқашан  жұпыланбайтындығы.  Сонымен  бірге,  бұл 
мысалдар  (1.4)  және  (1.5)  формулалардағы  параметрлердің 
мәндерін  ойламай  таңдаса,  яғни  олардың  орнына  кез  келген 
цифрларды қоя салса, ешқашан жақсы статистикалық қасиеттері 
бар  кездейсоқ  сандар  тізбектері  алынбайтындығын  көрсетеді. 
Сондықтан, 
m
 
c,
 ,
a
  параметрлерін  және  кездейсоқ  тізбектің 

Компьютермен модельдеу негіздері 
 
 
19
бастапқы санын 
 
*
z
0
 таңдағанда мынадай жағдайлар есте болуы 
керек:  тізбектің  периоды  неғұрлым  үлкен,  тізбекті  генерация-
лаудың  жылдамдығы  жоғары  және  кездейсоқ  сандардың  ара-
сындағы арақатынасы (корреляциясы) неғұрлым кем болғаны жөн. 
Қазіргі кезде компьютерде қолдануға шегерінділер әдісінің 
(1.5) формуласы ыңғайлы екені анықталған [4]. Ол үшін 
b
m
2

 
болуы  қажет.  Мұндағы  b   –  машиналық  сөздегі  екілік  цифрдың 
саны.  Сонда  кездейсоқ  тізбектің 
4
/
m
P 
  тең  максималды 
периодына мына шарттар орындалғанда жетуге болады: 
1) 
*
z
0
  кез келген оң, тақ, бүтін сан; 
2) 
,
t
a
3
8 

 мұндағы  t  – кез келген оң бүтін сан. 
Ал  енді  шегерінділер  әдісінің  (1.4)  формуласына  келсек, 
онымен  кездейсоқ  сандар  тізбегін  модельдегенде  периодтың  ең 
максималды 
m
P 
  мөлшеріне  жетуге  болады.  Бұл  нәтижені 
мына теорема дәлелдейді. 
1.1-теорема.  Конгруэнттік  әдістің  (1.4)  формуласы  бойын-
ша  алынған  кездейсоқ  тізбек  периодының  ұзындығы 
m
-ға  тең 
болу үшін мынадай шарттар орындалуы керек: 
а) 
c
 және 
m
 – өзара жай сандар; 
б) 


1

a
 саны 
r
-ге еселі, егер 
r
 жәй сан және 
m
 санының 
бөлгіші болса; 
в) 


1

a
 саны 4-ке еселі, егер 
m
 саны да төртке еселі болса. 
Бұл теореманың дәлелдемесін [5] табуға болады. 
Кездейсоқ  тізбек  периодының  ұзындығы  дәл 
m
  болған-
дықтан, 0 мен 


1

m
-дің арасындағы әр сан бұл тізбекте бір-ақ 
рет  кездеседі.  Сондықтан 
*
z
0
-ның  мәні  периодтың  ұзындығына 
әсер  етпейді.  Айта  кететін  тағы  бір  жайт,  (1.4)  және  (1.5) 
формулаларымен  алынған  кездейсоқ  тізбектер  мүшелерінің 
мәндері 


m
;
0
  кесіндісіне  бірқалыпты  орналасады,  ал 
 
1
0;
 
аралығындағы  сандарды  алу  үшін  бұл  формулаларды  мына 
өрнекпен толтыру қажет: 
.
 
z
m
z
*
n
n
1
1
1




                             
(1.6) 

Д.Н. Шоқаев 
 
 
20
1.4. Қосындылау әдісі 
 
Ван Вейнгарден ұсынған қосындылау әдісі мына [6] жалпы 
мағыналы сызықтық формуланы қолданады: 
 
...
,
j
),
m
(mod
C
z
a
z
k
i
i
j
i
j
k
2
1
1
0








         (1.7) 
Бұл  әдіспен  алынған  кездейсоқ  тізбектердің  периоды 
шегерінді  әдісі  қолданғандағы  периодтан  едәуір  ұзын  болады. 
Оның  себебі,  бұл  тізбектерде  период  пайда  болуы  үшін 
шегерінді  әдісі  сияқты  оның  екі  ғана  емес,  бірнеше  мүшесі 
сәйкес  келуі  керек.  Сонымен  қатар,  қосындылау  әдісімен 
алынған тізбек сандарының корреляциясы аз.  
Қосындылау  әдісінің  ең  қарапайым  формуласын  алу  үшін 
(1.7) өрнегінің параметрлеріне мынадай мағына беру керек: 
.
a
a
,
a
...
a
a
C
k
1
0
1
0
1
3
2








 
Сонда 
).
m
(mod
z
z
z
j
j
j
1
1




 
Бұл өрнек Фибоначчи формуласы деген атқа ие болды және 
өткен ғасырдың елуінші жылдарының бас кезінде кең қолданыс 
тапты.  Алайда,  Фибоначчи  формуласымен  генерацияланған 
сандар  жеткілікті  кездейсоқ  болған  жоқ.  Тек  қана  Дэвис  деген 
ғалым  осы  формуламен,  оның  бастапқы 
0
z
  және 
1
z
  сандарын 
сәтті  таңдап,  статистикалық  қасиеттері  жақсы  бірқалыпты 
кездейсоқ сандардың тізбегін алды. 
Дэвистің алгоритмі [7]  мына формуланы қолданады: 
),
(mod
z
z
z
j
j
j
4
1
1




 
(1.8) 
мұндағы 
.
,
z
,
z
542101887
0
2
5
42
17
1
0






 
Қазіргі  уақытта  қосындылау  әдісі  алгоритмдерінің  ара-
сында  ең  көп  тарағаны  аддитивті  алгоритмдер  болып  отыр  [8]. 
Ол алгоритмдер мына формуланы қолданады: 
),
m
(mod
z
z
z
k
j
j
j




1
 
мұндағы  k  – үлкен және бүтін сан 


16

k
. 

Компьютермен модельдеу негіздері 
 
 
21
Бастапқы 
k
z
,...,
z
,
z
1
0
  сандарын  ойлағандай  таңдаған  кезде, 
бұл  алгоритмдер  статистикалық  қасиеттері  жақсы  кездейсоқ 
сандардың көзі бола алады.  
 
1.5.  Периодтың және кездейсоқ тізбектердің 
                апериодтылығының ұзындықтарын сынақ 
                арқылы анықтау 
 
Жоғарыда  келтірілген  деректерден  анық  көрінетін  бір 
ерекшелікті  қарастырайық.  Ол  ерекшеліктің  мәні  мынада:  кез-
дейсоқ сандар тудыратын әдістердің бәрі де, оларды компьютерде 
қолданғанда,  периодикалық  тізбек  тудырады.  Шынында,  кез 
келген  компьютердің  кодында 
 
1
;
0
  аралығында  жататын  әртүрлі 
сандардың  тек  шекті  мөлшерін  ғана  жазуға  болады.  Сондықтан 
ерте  ме,  кеш  пе, 
L
z
  санының  мәні  алдындағы  сандардың  мән-
дерінің біреуімен, мысалы 
l
z -мен сәйкес келеді. Онда келесі теңдік 
тура болады: 
 
.
 
2
 
1,
i
,
z
z
i
l
i
L





 
      (1.9) 
L   –  (1.9)  шартын  қанағаттандыратын,  ең  кіші  сан  болсын. 
Сонда 
 
z
 
 ,
z
,
z
1
-
L
1
0

 
сандар жиыны кездейсоқ тізбектің апериодты 
кесіндісі  деп аталады (1.3-сурет).  Ал, 
L
 – апериодтылық кесін-
дісінің  ұзындығы.  (L-l)  мәні  периодқа  тең  екені  1.3-суреттен 
айқын  көрінеді,  яғни  P=L-l.  Сонымен,  тізбек  тек  кездейсоқ 
сандардан тұруы үшін оның ұзындығы апериодтық кесіндінің 
 
 
 
1.3-сурет 
 
ұзындығынан  аспауы  керек.  Сондықтан 
L   мен  P -ң  нақты 
мәндерін  таба  білу  қажет. 
L   мен  P -ң  мәнін  сынақ  арқылы 
анықтаудың бір әдісіне тоқталайық [9, 10]. 

Д.Н. Шоқаев 
 
 
22
}
z
{
i
 
–  жоғарыда  көрсетілген  алгоритмдердің  біреуінің 
көмегімен  алынған  кездейсоқ  сандар  тізбегі  болсын.  Осы 
тізбектің  индексі  L-P  айырымынан  біраз  үлкен 
N
z   мүшесін 
жадымызда  сақтап  қаламыз  (1.4-сурет).  Сонан  соң 
N
z -ді 
,
z
,
z
N
N
2
1


....  сандарының  біреуімен  сәйкес  келгенше  салыс-
тырамыз. Ерте ме, кеш пе, осы салыстырудың нәтижесінде мына 
теңдікке жетеміз: 
.
N)
(k
      
          
z
 
z
k
N


 
 
 
L  
P  
P  
P  
N  
K  
L  
P  
P  
K  
N  
 
 
1.4-сурет 
 
Демек,  k-N=P  тізбек  периодының  ұзындығы.  Содан  соң, 
берілген  алгоритммен  келесі  екі  кездейсоқ  тізбекті  қатар 
генерациялаймыз: 
,...
,
,
,
3
2
1
0
z
z
z
z
                                  
(1.10) 
,...
,
,
,
3
2
1



p
p
p
p
z
z
z
z
                             
(1.11) 
және осы тізбектердің қатар алынған мүшелерін, олар бір біріне 
теңелгенше, яғни мына теңдеу 
*
*
i
p
i
z
z


 
орындалғанша  салыстырамыз.  Сонда  (1.11)  тізбегінің  сәйкес 
келген 
мүшесінің 
нөмірі 
*
i
P
L


 
апериодтылығының 
ұзындығын анықтайды.  Айтылғандарды келесі алгоритм түріне 
келтірейік: 
1-қадам. 
0
1


R
,
i
  деп  аламыз,  мұндағы 
R   тізбек 
периодының ұзындығы әлі табылмағандығының белгісі. 

Компьютермен модельдеу негіздері 
 
 
23
2-қадам. Кездейсоқ тізбектің кезекті 
i
z  мүшесін генерациялау. 
3-қадам. 
1

 i
i
 болсын. 
4-қадам. 
0

R
  шартын  тексеру.  Бұл  шарт  орындалмаса      
7-қадамды орындау керек. 
5-қадам. 
1

 N
i
  шартын  тексеріп,  ол  орындалмаған 
жағдайда 2-қадамға көшу керек. 
6-қадам. 
N
z
Y 
  және 
1

 r
r
  деп  алып,  2-қадамға  көшу 
керек. 
7-қадам. 
Y
z
i

 шартын тексеріп, ол орындалмаған жағдайда 
2-қадамға қайту керек. 
8-қадам.  Периодтың  ұзындығын  мына  өрнектен 
N
i
P


 
анықтап алып, 
i
-ді бірге теңеу керек: 
1

i
. 
9-қадам.  Зерттеліп  отырған  кездейсоқ  тізбектің 
i
z
  және 
1

i
z
 мүшелерінің мәндерін қайтадан табу керек. 
10-қадам. 
P
i
i
z
z


 шартын тексеріп, ол орындалған жағдайда, 
12-қадамға көшу. 
11-қадам. 
1

 i
i
 деп алып, 9-қадамға қайтып бару. 
12-қадам. 
Апериодтық 
кесіндінің 
ұзындығын 
мына 
өрнектен 
i
P
L


айқындау.  
13-қадам. 
P
  мен 
L
-дің  мағынасын  компьютердің 
экранына әлде принтерге шығару. 
 
1.6. Қалыптан ауытқу әдісі 
 
L
  мен 
P
-ның  мәндері  өте  үлкен  бірқалыпты  үлестірілген 
кездейсоқ  сандардың  тізбегін  модельдеу  үшін  украин  ғалымы 
Д.И.  Голенко  ұсынған  қалыптан  ауытқу  әдісін  қолдануға  болады. 
Бұл  әдістің  идеясы  бір  кездейсоқ  тізбекті  модельдеу  үшін 
қатарымен екі алгоритмді пайдалануға негізделген: 












.
M
k
j
егер
),
z
(
,
M
k
j
егер
),
z
(
z
j
j
j

1
 
     (1.12) 

Д.Н. Шоқаев 
 
 
24
M   параметрі 
L
M 
  шартынан  таңдалады  және  қалыптан 
ауытқу периоды деп аталады. 
(1.12) өрнегінен көрініп тұрғандай, жоғарғы 
 
z
Ф
 функциясы 
көмегімен 
1
2
1
0

M
z
,...,
z
,
z
,
z
 тізбегі модельденеді. Ал содан кейін  


L
l
  
z
z
l
L


 
сәйкестелуін  болдырмау  үшін, 
M
z
  кездейсоқ  саны  төмендегі 
 
z

 функциясының көмегімен табылады. Осындай ауытқу одан 
әрі  де,  келесі 
l
M    кездейсоқ  саннан  асқан  сайын,  тізбектің 
берілген ұзындығына жеткенше қайталанып отырады. 
Қалыптан  ауытқу  әдісін  іске  асыратын  алгоритм  7  қадам-
нан тұрады. 
1-қадам. 
1

k
 және 
0

j
 деп аламыз. 
2-қадам. 
M
k
j


  шартын  тексереміз.  Бұл  шарт  орын-
далған жағдайда 4-қадамға көшеміз. 
3-қадам. 
 
j
j
z
Ф
z

1
  рекурренттік  қатынасын  іске  асыру. 
Содан кейін 6-қадамды орындау керек. 
4-қадам. 
 
j
j
z
z


1
 рекурренттік қатынасын орындау және  
К параметрін бір санға көтеру: 
1

 k
k
. 
5-қадам. 
1

 j
j
 деп аламыз. 
6-қадам. 
N
j 
  шартын  тексеру,  мұндағы  N -модель-
денетін  тізбектің  берілген  ұзындығы.  Бұл  шарт  орындалған 
жағдайда 2-қадамға көшеміз. 
7-қадам. Модельдеу нәтижесін баспалау. 
Д.И. Голенко өзі ұсынған қалыптан ауытқу әдісі, кездейсоқ 
сандар тізбегінің ұзындығын  M есе ұзартатынын көрсетті.  
 
 
Бақылау сұрақтары 
1. 
)
m
(mod
C
az
z
*
n
*
n


1
  өрнегі  бойынша  алынған  кез-
дейсоқ сандар тізбегінің периоды  Р=m болу үшін қандай шарттар 
орындалуы тиіс? 

Компьютермен модельдеу негіздері 
 
 
25
2. 
)
m
(mod
az
z
*
n
*
n

1
 
өрнегінің  параметрлерін  таңдау 
қандай шартпен анықталады? 
3.    Д.И.  Голенконың  “ауытқу”  әдісі  қандай  заңдылықты 
модельдеу үшін қолданылады? 
4. 
]]
z
[
D
[
z
n
k
k
k
n
2
2
2
1
10
10
10




  формуласы  қандай аралық-
тағы сандарды модельдеуге қолданылады? 
5. 
).
m
(mod
z
z
z
k
j
j
j




1
 формуласы қандай әдіске жатады? 
6. Базалық кездейсоқ сандар тізбегін модельдейтін бір және 
екі реттілік рекурренттік өрнектерді жазыңыз. 
7.  Периоды  Р  =  512  –  ге  тең  кездейсоқ  сандар  тізбегін 
модельдейтін өрнекті келтіріңіз. 
8.  Мына  тізбектің  периоды  Р  мен  апериодтылығының         
L мәндерін анықтаңыз: 
0.17;  0.31;  0.02;  0.94;  0.45;  0.27;  0.13;  0.78; 0.22;  0.45;  0.27.  
9.  Кездейсоқ  сан 
0
z
=0.221  тең  болсын.  Қиықтау  әдісімен 
1
z
 табыңыз. 
10.  Төмендегі тізбек қай әдіспен модельденген? 
0.15;  0.97;  0.45;  0.36;  0.62........ 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Д.Н. Шоқаев 
 
 
26

жүктеу/скачать 2,94 Mb.

Достарыңызбен бөлісу: