Диссертация (1104114), страница 12

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

‘«¥¤®¢ ²¥«¼­®, ¤«¿ ­¥ª®²®°®© ª®­±² ­²»61C ¢»¯®«­¥­® ­¥° ¢¥­±²¢® K (unjzn) Cf (n): ‚ ±¨«³ ¢»¡®° u ¤ ­­ ¿ª®­±² ­² C ¿¢«¿¥²±¿ ³­¨¢¥°± «¼­®©, ². ¥. ¤«¿ «¾¡®£® ­®¬¥° n ¨ ¤«¿«¾¡®£® ¡«®ª tn (j ) ¨§ yn K (tn(j )jzn) Cf (n): 2’ ª¨¬ ®¡° §®¬, ¯°¨¬¥­¿¿ ª ±«®¢³ zn ¯°®£° ¬¬» ¤«¨­» ­¥ ¡®«¥¥ C f (n), ¬®¦­® ¯®«³·¨²¼ ¢±¥ ¡«®ª¨ tn (j ) ¨§ ±«®¢ yn.„ «¥¥ ¬» ¤®ª ¦¥¬ ¤¢¥ «¥¬¬», ­ «®£¨·­»¥ «¥¬¬ ¬ 7 ¨ 8 ¨§ ¤®ª § ²¥«¼±²¢ ²¥®°¥¬» 4.‘³¹¥±²¢³¥² ² ª ¿ ª®­±² ­² C , ·²® ¤«¿ «¾¡®£® (n; j )¡«®ª ~tn(j ), ª®²®°»© ®²«¨· ¥²±¿ ®² tn(j ) ­¥ ¬¥­¥¥, ·¥¬ ¢ f (n)=10 ¡³ª¢ µ, ¢»¯®«­¥­® ­¥° ¢¥­±²¢®K (t~n(j )jyn)) f (n)g(n)=10 C f (n):‹¥¬¬ 10.³±²¼ ~tn(j ) { ­¥ª®²®°»© (n; j )-¡«®ª, ®²«¨· ¾¹¨©±¿ ®² tn(j ) ­¥ ¬¥­¥¥ ·¥¬ ¢ f (n)=10 ¡³ª¢ µ.

’®£¤ ±«®¢® xn ¬®¦­®¯®«³·¨²¼ ¨§ yn ¢ 4 ½² ¯ : ³±² ­®¢¨¬, ¨§ ª ª®© ¯®«®¢¨­» ±«®¢ xn ¢§¿² ª ¦¤ ¿ ¡³ª¢ ±«®¢ yn (¤«¿ ½²®£® ²°¥¡³¥²±¿ kn ¡¨²®¢); ¯®±«¥ ¢»¯®«­¥­¨¿ ½²®£® ½² ¯ ¡³¤³² ¨§¢¥±²­» kn ¡³ª¢ ¢ ±«®¢¥ xn; ¯®±²°®¨¬ ¡«®ª t~n (j ); ³ª ¦¥¬ f (n)=10 ¡³ª¢ ¢ ±«®¢¥ t~n(j ), ª®²®°»¥ ®²«¨· ¾²±¿ ®² ±®®²¢¥²±²¢³¾¹¨µ ¡³ª¢ ¢ ¡«®ª¥ tn(j ); ¯°¨ ½²®¬ ¬» ¯®«³·¨¬ ¥¹¥ f (n)=10¡³ª¢ ±«®¢ xn; ¯®«³·¨¬ ®±² ¢¸¨¥±¿ (kn f (n)=10) ¡³ª¢ ±«®¢ xn (¤«¿ ½²®£® ²°¥¡³¥²±¿ ­¥ ¡®«¥¥ (kn f (n)=10)g(n) ¡¨²®¢).’ ª¨¬ ®¡° §®¬,K (xnjyn) kn + K (t~n(j )jyn) + (kn f (n)=10)g(n) + O(f (n)):„®ª § ²¥«¼±²¢® «¥¬¬».®±ª®«¼ª³ K (yn) kn g(n) + O(log n), ¯®«³· ¥¬K (xn; yn) = K (xnjyn) + K (yn) + O(log n) 2kn g(n) f (n)g(n)=10 + kn + K (b(n)jyn) + O(f (n)):“·¨²»¢ ¿ (3.4), ¯®«³· ¥¬ ³²¢¥°¦¤¥­¨¥ «¥¬¬».

262‘³¹¥±²¢³¥² ² ª ¿ ª®­±² ­² C , ·²® ¥±«¨ (n; j )-¡«®ª~tn(j ) ®²«¨· ¥²±¿ ®² tn(j ) ­¥ ¬¥­¥¥, ·¥¬ ¢ f (n)=10 ¡³ª¢ µ, ²®K (t~n(j )jzn)) f (n)g(n)=10 C f (n):„®ª § ²¥«¼±²¢® «¥¬¬». ®±ª®«¼ª³ ¯®±«¥¤®¢ ²¥«¼­®±²¼ z f -¯°®±² ®²­®±¨²¥«¼­® y,K (t~n(j )jyn) K (t~n(j )jzn) + K (znjyn) + O(log n) = K (t~n(j )jzn) + O(f (n)):Ž±² ¥²±¿ ¯°¨¬¥­¨²¼ «¥¬¬³ 10. 2‘®£« ±­® «¥¬¬¥ 9 ¤«¿ ¤®±² ²®·­® ¡®«¼¸¨µ n ¢±¥ ¡«®ª¨ tn(j ) ¨¬¥¾²±«®¦­®±²¼ ­ ¬­®£® ¬¥­¼¸¥ f (n)g(n)=20 ®²­®±¨²¥«¼­® zn . ‚ ²® ¦¥ ¢°¥¬¿,±®£« ±­® «¥¬¬¥ 11 ¤«¿ ¤®±² ²®·­® ¡®«¼¸¨µ n ¢±¥ (n; j )-¡«®ª¨ t~n(j ), ®²«¨· ¾¹¨¥±¿ ®² ±®®²¢¥²±²¢³¾¹¥£® tn(j ) ­¥ ¬¥­¥¥ ·¥¬ ¢ f (n)=10 ¡³ª¢ µ,¨¬¥¾² ±«®¦­®±²¼ ¬­®£® ¡®«¼¸¥ f (n)g(n)=20 ®²­®±¨²¥«¼­® zn.

‘«¥¤®¢ ²¥«¼­®, ¥±«¨ ¯°¨¬¥­¿²¼ ª zn ¯°®£° ¬¬» ¤«¨­» ­¥ ¡®«¥¥ f (n)g(n)=20, ²®¬®¦­® ¯®«³·¨²¼ ¢±¥ ¡«®ª¨ tn (j ), ­® ­¥«¼§¿ ¯®«³·¨²¼ ­¨ ®¤­®£® (n; j )¡«®ª , ®²«¨· ¾¹¨¥±¿ ®² ±®®²¢¥²±²¢³¾¹¥£® tn(j ) ¡®«¥¥ ·¥¬ ¢ f (n)=10¡³ª¢ µ. ³±²¼ ln(j ) { ·¨±«® ¢±¥µ (n; j )-¡«®ª®¢, ¨¬¥¾¹¨µ ±«®¦­®±²¼ ­¥¡®«¥¥ f (n)g(n)=20 ®²­®±¨²¥«¼­® zn.

Ž·¥¢¨¤­®,‹¥¬¬ 11.0 + C 1 + C 2 + : : : + C f(n)=10 :ln(j ) Cf(n)f(n)f(n)f(n)Ž¶¥­¨¬ ¯®«³·¥­­³¾ ±³¬¬³ ±¢¥°µ³.  ±±¬®²°¨¬ ±«³· ©­³¾ ¢¥«¨·¨­³ ,° ¢­³¾ ±³¬¬¥ s = f (n) ­¥§ ¢¨±¨¬»µ ®¤¨­ ª®¢® ° ±¯°¥¤¥«¥­­»µ ±«³· ©­»µ ¢¥«¨·¨­, ª ¦¤ ¿ ¨§ ª®²®°»µ ¯°¨­¨¬ ¥² §­ ·¥­¨¿ 0 ¨ 1 ± ¢¥°®¿²­®±²¼¾ 1=2. ’®£¤ Prob[ s=10] = (Cs0 + Cs1 + : : : + Css=10)=2s :°¨ ½²®¬ ¬ ²¥¬ ²¨·¥±ª®¥ ®¦¨¤ ­¨¥ ° ¢­® s=2. ‚®±¯®«¼§³¥¬±¿ ®¶¥­ª®©¥°­¸²¥©­ ¤«¿ ³ª«®­¥­¨¿ ®² ±°¥¤­¥£® §­ ·¥­¨¿ (±¬.

[8], ­¥° ¢¥­±²¢®(43)):14Prob 2e ( ) s :s 2 10Ž£°³¡«¿¿ ®¶¥­ª³, ¯®«³· ¥¬14Cs0 + Cs1 + : : : + Css=10 = 2s Prob s 2 10 2 s:‘«¥¤®¢ ²¥«¼­®, ln(j ) 29=10f(n).4 21091063’¥¯¥°¼ ®¶¥­¨¬ ±«®¦­®±²¼ ±«®¢ yn ®²­®±¨²¥«¼­® xn . °¥¦¤¥ ¢±¥£®¨§ ±«®¢ xn ±® ±«®¦­®±²¼¾ O(f (n)) ¬®¦­® ¯®«³·¨²¼ zn.

„ «¥¥, ¡³¤¥¬¯°¨¬¥­¿²¼ ª ±«®¢³ zn ¢±¥ ¯°®£° ¬¬» ¤«¨­» ­¥ ¡®«¥¥ f (n)g(n)=20 ¨ ¢»¯¨±»¢ ²¼ ¢±¥ ¯®«³· ¥¬»¥ ¢ °¥§³«¼² ²¥ (n; j )-¡«®ª¨.  ­® ¨«¨ ¯®§¤­® ¢±¥¡«®ª¨ tn(j ), ¢µ®¤¿¹¨¥ ¢ yn, ¡³¤³² ¯®«³·¥­». „«¿ ²®£®, ·²®¡» ¢»¡° ²¼ ¨§±¯¨±ª ¢±¥µ ¯®«³· ¥¬»µ (n; j )-¡«®ª®¢ ±®®²¢¥²±²¢³¾¹¨¥ ±«®¢³ yn ¡«®ª¨tn(j ), ¯®²°¥¡³¥²±¿ ¤®¯®«­¨²¥«¼­ ¿ ¨­´®°¬ ¶¨¿, ­¥ ¯°¥¢®±µ®¤¿¹ ¿mn [maxlog ln(j )] (kn =f (n)) 9=10f (n) = 9=10kn :j‡­ ¿ xn ¨ ¢±¥ ¡«®ª¨ tn (j ), ¬» ¬®¦¥¬ ¢®±±² ­®¢¨²¼ yn. ’ ª¨¬ ®¡° §®¬,¯®«³· ¥¬ K (ynjxn) 9=10kn + O(f (n)): ®±ª®«¼ª³ K (xn) 2g(n)kn +O(f (n)), ¨¬¥¥¬K (xn; yn) = K (xn) + K (ynjxn) + O(log n) 2g(n)kn + 9=10kn + O(f (n));·²® ¯°®²¨¢®°¥·¨² (3.4). ’ ª¨¬ ®¡° §®¬, ¬» ¯®«³·¨«¨ ¯°®²¨¢®°¥·¨¥ ±¯°¥¤¯®«®¦¥­¨¥¬ ® ±³¹¥±²¢®¢ ­¨¨ ²®·­®© ­¨¦­¥© £° ­¨ ³ ¯®±«¥¤®¢ ²¥«¼­®±²¥© x ¨ y.

264ƒ« ¢ 4. °» ± ­¥¬ ²¥°¨ «¨§³¥¬®©¢§ ¨¬­®© ¨­´®°¬ ¶¨¥©‚ [9] ° ±±¬ ²°¨¢ «±¿ ¢®¯°®±: ¢±¥£¤ «¨ ¤«¿ ¤¢³µ ±«®¢ ¬®¦­® ­ ©²¨ ²°¥²¼¥, ª®²®°®¥ ¬ ²¥°¨ «¨§®¢ «® ¡» ¨µ ¢§ ¨¬­³¾ ¨­´®°¬ ¶¨¾? ‘«®¢® z ,¬ ²¥°¨ «¨§³¾¹¥¥ ¢§ ¨¬­³¾ ¨­´®°¬ ¶¨¾ x ¨ y, ¤®«¦­® «¥£ª® ¢»·¨±«¿²¼±¿ ¯® ª ¦¤®¬³ ¨§ ­¨µ. ’ ª¨¬ ®¡° §®¬, ¬» ¨­²¥°¥±³¥¬±¿, ¢±¥£¤ «¨¥±²¼ ² ª®¥ ±«®¢®, ª®²®°®¥ ¨¬¥¥² ¬ «³¾ ±«®¦­®±²¼ ®²­®±¨²¥«¼­® ª ¦¤®£® ¨§ ¤¢³µ ¤ ­­»µ, ¨ ±«®¦­®±²¼ ª®²®°®£® ° ¢­ ¨µ ¢§ ¨¬­®© ¨­´®°¬ ¶¨¨.ƒ · ¨ Š¥°­¥° ¤ «¨ ¢ [9] ®²°¨¶ ²¥«¼­»© ®²¢¥² ­ ¤ ­­»© ¢®¯°®±. Ž¤­ ª® ·²®¡» ±´®°¬³«¨°®¢ ²¼ ²®·­®¥ ³²¢¥°¦¤¥­¨¥, ­¥®¡µ®¤¨¬® ¯®¿±­¨²¼,·²® §­ ·¨², ·²® ­¥ª®²®°®¥ ±«®¢® z «¥£ª® ¯®«³·¨²¼ ¯® ±«®¢³ x ¨ ¯® ±«®¢³ y.¥°¥©¤¥¬ ®² ¨­¤¨¢¨¤³ «¼­»µ ±«®¢ ª ¡¥±ª®­¥·­»¬ ¯®±«¥¤®¢ ²¥«¼­®±²¿¬±«®¢ ¨ ¡³¤¥¬ ° ±±¬ ²°¨¢ ²¼ ±¨¬¯²®²¨·¥±ª¨¥ ±¢®©±²¢ ¨µ ±«®¦­®±²¥©.‚ ² ª¨µ ²¥°¬¨­ µ ¬®¦­® ±´®°¬³«¨°®¢ ²¼ °¥§³«¼² ² ƒ · ¨ Š¥°­¥° .’¥®°¥¬ 6.·²®[9] ‘³¹¥±²¢³¾² ² ª¨¥ ¯®±«¥¤®¢ ²¥«¼­®±²¨ ±«®¢ x, y,K (xn) = n + o(n); K (yn) = n + o(n) I (xn : yn) = an + o(n);(a { ¯®«®¦¨²¥«¼­ ¿ ª®­±² ­² ), ¨ ¤«¿ «¾¡®© ¯®±«¥¤®¢ ²¥«¼­®±²¨±«®¢ z, ³¤®¢«¥²¢®°¿¾¹¥© ³±«®¢¨¾K (znjxn) = o(n); K (znjyn) = o(n);¢»¯®«­¥­® K (zn) = o(n).ˆ­ ·¥ £®¢®°¿, ±³¹¥±²¢³¾² xn ¨ yn ² ª¨¥, ·²® ¥±«¨ ±«®¦­®±²¼ zn ¬ « ®²­®±¨²¥«¼­® xn ¨ ®²­®±¨²¥«¼­® yn, ²® ¨ ±«®¦­®±²¼ ± ¬®£® zn ¬ « .

°¨65½²®¬ ¢§ ¨¬­ ¿ ¨­´®°¬ ¶¨¿ ±«®¢ xn ¨ yn ° ±²¥² «¨­¥©­® ¯® n. ’ ª¨¬®¡° §®¬, ±³¹¥±²¢³¾² ¯®±«¥¤®¢ ²¥«¼­®±²¨ ±«®¢, ³ ª®²®°»µ ­¥«¼§¿ ¬ ²¥°¨ «¨§®¢ ²¼ ¢§ ¨¬­³¾ ¨­´®°¬ ¶¨¾. ®«¥¥ ²®£®, ²¥®°¥¬ 6 ³²¢¥°¦¤ ¥²,·²® ­¥«¼§¿ ¬ ²¥°¨ «¨§®¢ ²¼ ¤ ¦¥ · ±²¼ ¢§ ¨¬­®© ¨­´®°¬ ¶¨¨ xn ¨ yn.’®·­¥¥, ¢¥«¨·¨­ ¬ ²¥°¨ «¨§³¥¬®© ¢§ ¨¬­®© ¨­´®°¬ ¶¨¨ ¡¥±ª®­¥·­®¬ « ¯® ±° ¢­¥­¨¾ ± n.‚ ° ¡®²¥ [9] ³ª §»¢ ¥²±¿ ±¥¬¥©±²¢® ¯°¨¬¥°®¢ ¯ ° hxn; yni, ³¤®¢«¥²¢®°¿¾¹¨¥ ²°¥¡®¢ ­¨¾ ²¥®°¥¬» 6. °¨ ½²®¬ ª®­±²°³ª¶¨¿ ¯®§¢®«¿¥² ±²°®¨²¼ ² ª¨¥ ¯®±«¥¤®¢ ²¥«¼­®±²¨ xn, yn ¤«¿ «¾¡»µ §­ ·¥­¨© ¯ ° ¬¥²° a(0 < a < 1). ’.

¥. ¬®¦­® ³ª § ²¼ ² ª¨¥ xn ¨ yn, ¢§ ¨¬­ ¿ ¨­´®°¬ ¶¨¿ª®²®°»µ ®·¥­¼ ¢¥«¨ª (a ¡«¨§ª® ª ¥¤¨­¨¶¥), ­® ¤ ¦¥ ¥¥ ¬ « ¿ · ±²¼ ­¥¬®¦¥² ¡»²¼ ¬ ²¥°¨ «¨§®¢ ­ .‚ ° ¡®²¥ ƒ · ¨ Š¥°­¥° ­¥ ®¶¥­¨¢ ¾²±¿ ®±² ²®·­»¥ ·«¥­». ® ­ «¨§¨°³¿ ¤®ª § ²¥«¼±²¢® ¢ [9], ¬®¦­® ¯°®¢¥°¨²¼, ·²® ²¥®°¥¬ 6p®±² ­¥²±¿ ¢¥°­®©, ¥±«¨ ¢ ´®°¬³«¨°®¢ª¥ § ¬¥­¨²¼ ·«¥­» o(n) ­ pO( n) (¨«¨­ O(f (n)), £¤¥ f (n) { «¾¡ ¿ ´³­ª¶¨¿, ° ±²³¹ ¿¡»±²°¥¥ n, ­® ¬¥¤p«¥­­¥¥ «¨­¥©­®©: f (n) = o(n); f (n) = ( n)). Ž¤­ ª® ¢ ³²¢¥°¦¤¥­¨¿µ® ª®«¬®£®°®¢±ª®© ±«®¦­®±²¨ ¥±²¥±²¢¥­­® ´®°¬³«¨°®¢ ²¼ ° ¢¥­±²¢ ±²®·­®±²¼¾ ¤® «®£ °¨´¬¨·¥±ª®£® ·«¥­ .

®½²®¬³ ª ¦¥²±¿ ¨­²¥°¥±­»¬° ±±¬®²°¥²¼ ³±¨«¥­¨¥ ²¥®°¥¬» 6, ¨¬¥­­®, ¤®ª § ²¼ ¥¥, § ¬¥­¨¢ ¢ ´®°¬³«¨°®¢ª¥ ·«¥­» o(n) ­ O(log n). ’ ª¨¬ ®¡° §®¬, ¥±²¥±²¢¥­­»¬ ³±¨«¥­¨¥¬ ²¥®°¥¬» ƒ · ¨ Š¥°­¥° ¿¢«¿¥²±¿ ±«¥¤³¾¹ ¿ ²¥®°¥¬ .[5, 13] „«¿ «¾¡®© ´³­ª¶¨¨ f (n) ² ª®©, ·²® f (n) = o(n)¨ f (n) = (log n), c³¹¥±²¢³¾² ² ª¨¥ ¯®±«¥¤®¢ ²¥«¼­®±²¨ ±«®¢ x, y,·²®’¥®°¥¬ 7.K (xn ) = n + O(f (n)); K (yn) = n + O(f (n)); I (xn : yn) = an + O(f (n))(a { ­¥ª®²®° ¿ ¯®«®¦¨²¥«¼­ ¿ ª®­±² ­² ), ¨ ¤«¿ «¾¡®© ¯®±«¥¤®¢ ²¥«¼­®±²¨ ±«®¢ z, ª®²®° ¿ f -¯°®±² ®²­®±¨²¥«¼­® x ¨ ®²­®±¨²¥«¼­®y, ¢»¯®«­¥­® K (zn ) = O (f (n)).‚ ° ¡®² µ [5, 13] ¡»«® ¯®«³·¥­® ¤®ª § ²¥«¼±²¢® ²¥®°¥¬» 7 ¤«¿ ¯°®¨§¢®«¼­®£® §­ ·¥­¨¿ ¯ ° ¬¥²° a (0 < a < 1).

„°³£¨¥ ¤®ª § ²¥«¼±²¢ ²¥®°¥¬» 7 ¤«¿ ­¥ª®²®°»µ ±¯¥¶¨ «¼­»µ §­ ·¥­¨© a ¯°¨¢®¤¨«¨±¼ ² ª¦¥¢ [15, 16].’ ª¨¬ ®¡° §®¬, ¤«¿ «¾¡®£® ¯®«®¦¨²¥«¼­®£® a < 1 ¬®¦­® ­ ©²¨ ² ª¨¥xn ¨ yn, ·²® ±«®¦­®±²¨ ¤ ­­»µ ±«®¢ ¯°¨¬¥°­® ° ¢­» n, ¢§ ¨¬­ ¿ ¨­´®°66¬ ¶¨¿ ¯°¨¬¥°­® ° ¢­ an, ¨ ¨µ ¢§ ¨¬­³¾ ¨­´®°¬ ¶¨¾ ­¥«¼§¿ ¬ ²¥°¨ «¨§®¢ ²¼. €­. €. Œ³·­¨ª®¬ ¡»« ¯®±² ¢«¥­ ¢®¯°®±: ¯°¨ ª ª¨µ §­ ·¥­¨¿µ¯ ° ¬¥²° a ¤«¿ ª ¦¤®£® xn ±«®¦­®±²¨ n ¬®¦­® ¯®¤®¡° ²¼ yn ±«®¦­®±²¨ n ² ª®¥, ·²® ¢§ ¨¬­ ¿ ¨­´®°¬ ¶¨¿ I (xn : yn) ¯°¨¬¥°­® ° ¢­ an, ­®¥¥ ­¥«¼§¿ ¬ ²¥°¨ «¨§®¢ ²¼? ®«¥¥ ²®·­®, ¤«¿ ª ª¨µ §­ ·¥­¨© ¯ ° ¬¥²° a ¨¬¥¥² ¬¥±²® ±«¥¤³¾¹¥¥ ³±¨«¥­¨¥ ²¥®°¥¬» 7.’¥®°¥¬ 8.

³±²¼ f (n) { ² ª ¿ ´³­ª¶¨¿, ·²® f (n) = o(n) ¨ f (n) =(log n), ¨ x { ² ª ¿ ¯®±«¥¤®¢ ²¥«¼­®±²¼, ·²® K (xn) = n + O(f (n)).’®£¤ ±³¹¥±²¢³¥² ¯®±«¥¤®¢ ²¥«¼­®±²¼ y ² ª ¿, ·²®K (yn) = n + O(f (n)); I (xn : yn) = an + O(f (n));¨ ¤«¿ «¾¡®© ¯®±«¥¤®¢ ²¥«¼­®±²¨ ±«®¢ z, ª®²®° ¿ f -¯°®±² ®²­®±¨²¥«¼­® x ¨ ®²­®±¨²¥«¼­® y, ¢»¯®«­¥­® K (zn) = O(f (n)).„«¿ a = 1=2 ¤ ­­ ¿ ²¥®°¥¬ ¡»« ¤®ª § ­ ¢ [13].‚ ¤ ­­®© ° ¡®²¥ ° ±±¬ ²°¨¢ ¾²±¿ ¤¢ ° ±±³¦¤¥­¨¿, ¯®§¢®«¿¾¹¨¥¤®ª §»¢ ²¼ ²¥®°¥¬³ 8 ¤«¿ ±ª®«¼ ³£®¤­® ¡«¨§ª¨µ ª ¥¤¨­¨¶¥ §­ ·¥­¨©¯ ° ¬¥²° a. ‚ ¯¥°¢®¬ ¨§ ­¨µ ¨±¯®«¼§³¾²±¿ ¯ °» ±«®¢, ±«³· ©­»¥ ®²­®±¨²¥«¼­® ° ±¯°¥¤¥«¥­¨¿ ®±®¡®£® ¢¨¤ .

²® ±¥¬¥©±²¢® ¯ ° ¿¢«¿¥²±¿· ±²­»¬ ±«³· ¥¬ ª« ±± ¯°¨¬¥°®¢, ¯°¥¤«®¦¥­­»µ ¢ [9]. ®¢»© ¬¥²®¤¤®ª § ²¥«¼±²¢ ¯®§¢®«¿¥² ³«³·¸¨²¼ ®¶¥­ª³ ­ ¢¥«¨·¨­³ ¬ ²¥°¨ «¨§³¥¬®© ®¡¹¥© ¨­´®°¬ ¶¨¨ (¨, ²¥¬ ± ¬»¬, ¤ ²¼ ¤®ª § ²¼ ²¥®°¥¬» 7 ¨ 8).‚²®°®¥ ° ±±³¦¤¥­¨¥ ®±­®¢ ­® ­ ­®¢®© «£¥¡° ¨·¥±ª®© ª®­±²°³ª¶¨¨,®¡®¡¹ ¾¹¥© ¬¥²®¤, ¨±¯®«¼§®¢ ­­»© ¢ [13].‡ ¬¥· ­¨¥ 3. „«¿ ¯°®±²®²» ¡³¤¥¬ ¤®ª §»¢ ²¼ ²¥®°¥¬³ 8 ²®«¼ª® ¤«¿f (n) = log n.

 ±«³· © ¯°®¨§¢®«¼­®© f (n) ¢±¥ ° ±±³¦¤¥­¨¿ ¯¥°¥­®±¿²±¿¤®±«®¢­®.4.1. ‘²®µ ±²¨·¥±ª¨¥ ¯ °» ±±¬®²°¨¬ ±®¢¬¥±²­®¥ ° ±¯°¥¤¥«¥­¨¥ ¯ °» ±«³· ©­»µ ¢¥«¨·¨­ h'; i±® ±«¥¤³¾¹¨¬¨ ±¢®©±²¢ ¬¨: ®¡¥ ¢¥«¨·¨­» ', ¯°¨­¨¬ ¾² §­ ·¥­¨¿ 0 ¨1 ± ¢¥°®¿²­®±²¼¾ 1=2 (². ¥. ¿¢«¿¾²±¿ ¤¢®¨·­»¬¨ ° ¢­®¬¥°­® ° ±¯°¥¤¥«¥­­»¬¨); ¯°¨ ½²®¬ ' ¨ ¯°¨­¨¬ ¾² ° §­»¥ §­ ·¥­¨¿ ± ¢¥°®¿²­®±²¼¾ (¨, ±®®²¢¥²±²¢¥­­®, ±®¢¯ ¤ ¾² ± ¢¥°®¿²­®±²¼¾ (1 )). ’ ª¨¬ ®¡° §®¬,Prob[' = 0; = 0] = Prob[' = 1; = 1] = 1 2 ;Prob[' = 1; = 0] = Prob[' = 0; = 1] = 2 :67„ ­­®¥ ° ±¯°¥¤¥«¥­¨¥ § ¤ ¥²±¿ ² ¡«¨¶¥© ­ °¨±. 4.1.'01¨±. 4.1.

 ±¯°¥¤¥«¥­¨¥01 22P121 2¯ °» ±«³· ©­»µ ¢¥«¨·¨­'; §®¢¥¬ ¯®±«¥¤®¢ ²¥«¼­®±²¨ ±«®¢ x, y -¯ °®©, ¥±«¨ ®­¨ ¿¢«¿¾²±¿ P -±«³· ©­®© ¯ °®© ®²­®±¨²¥«¼­® ° ±¯°¥¤¥«¥­¨¿ P ,§ ¤ ­­®£® ­ °¨±.4.1.Ž¯°¥¤¥«¥­¨¥ 11. ¯®¬­¨¬, ·²® ¤«¿ «¾¡®£® ° ±¯°¥¤¥«¥­¨¿ P ±³¹¥±²¢³¾² P -±«³· ©­»¥ ª®°²¥¦¨.³±²¼ ±«³· ©­»¥ ¢¥«¨·¨­» ' ¨ ¨¬¥¾² ±®¢¬¥±²­®¥ ° ±¯°¥¤¥«¥­¨¥ P ,³ª § ­­®¥ ­ 4.1, ¯®±«¥¤®¢ ²¥«¼­®±²¨ x ¨ y ®¡° §³¾² -¯ °³.

’®£¤ xn, yn ¿¢«¿¾²±¿ ±«³· ©­»¬¨ ±«®¢ ¬¨ ¤«¨­» n, ¨ ®²«¨· ¾²±¿ ¤°³£ ®²¤°³£ ¢ n + O(1) ¡¨²®¢.„ «¥¥, ­¥²°³¤­® ¢»·¨±«¨²¼ ¸¥­­®­®¢±ª¨¥ ½­²°®¯¨¨ ±«³· ©­»µ ¢¥«¨·¨­ ' ¨ , ² ª¦¥ ½­²°®¯¨¾ ¯ °» h'; iH (') = H ( ) = 1;H ('; ) = 1 ( log + (1 ) log(1 )):®«³· ¥¬ ¢§ ¨¬­³¾ ¨­´®°¬ ¶¨¾ ¤ ­­»µ ±«³· ©­»µ ¢¥«¨·¨­I (' : ) = 1 + ( log + (1 ) log(1 )):Ž¡®§­ ·¨¬ ¢¥«¨·¨­³ ¢§ ¨¬­®© ¨­´®°¬ ¶¨¨c() = 1 + ( log + (1 ) log(1 )):(4.1)Ž·¥¢¨¤­®, c() > 0 ¯°¨ 6= 1=2.…±«¨ x ¨ y ®¡° §³¾² -¯ °³, ²®K (xn) = n + O(log n);K (yn) = n + O(log n);I (xn; yn) = c()n + O(log n):’ ª¨¬ ®¡° §®¬, ¯°¨ 6= 1=2 ¢§ ¨¬­ ¿ ¨­´®°¬ ¶¨¿ xn ¨ yn ° ±²¥² «¨­¥©­® ¯® n.68‘«¥¤³¥² ¢»¤¥«¨²¼ ±«³· © = 1=2.

®±ª®«¼ª³ c(1=2) = 0, ¢§ ¨¬­ ¿¨­´®°¬ ¶¨¿ ±«®¢ xn ¨ yn ° ¢­ O(log n). ²® ±®®²¢¥²±²¢³¥² ¨­²³¨¶¨¨:¥±«¨ ¤¢ ±«®¢ ¢»¡° ­» ±«³· ©­® ¨ ­¥§ ¢¨±¨¬®, ²® ®­¨ ®²«¨· ¾²±¿ ¯°¨¬¥°­® ¢ ¯®«®¢¨­¥ ¡¨²®¢. ® ±®£« ±­® ®¯°¥¤¥«¥­¨¾ 1=2-¯ °» ±«®¢ xn ¨ ynª ª ° § ¨ ¤®«¦­» ¡»²¼ ¯ °®© ±«³· ©­»µ ±«®¢, ®²«¨· ¾¹¨µ±¿ ¯°¨¬¥°­®¢ ¯®«®¢¨­¥ ¡¨²®¢.ˆ¬¥­­® -¯ °» ®ª §»¢ ¾²±¿ ¯°¨¬¥° ¬¨ ±«®¢, ³¤®¢«¥²¢®°¿¾¹¨µ ²¥®°¥¬¥ 7.

Характеристики

Список файлов диссертации