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

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

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

Œ» ¡³¤¥¬ ¤®ª §»¢ ²¼, ·²® ¤«¿ «¾¡®£® 2 (0; 1) ¢§ ¨¬­ ¿¨­´®°¬ ¶¨¿ ±«³· ©­»µ -¯ ° ­¥ ¬ ²¥°¨ «¨§³¥²±¿. „«¿ ½²®£® ­ ¬ ¯®­ ¤®¡¿²±¿ ±«¥¤³¾¹¨¥ ²¥µ­¨·¥±ª¨¥ «¥¬¬».‹¥¬¬ 12. ³±²¼ ¯®±«¥¤®¢ ²¥«¼­®±²¼ z ¯°®±² ®²­®±¨²¥«¼­® x ¨®²­®±¨²¥«¼­® y, ². ¥. K (znjxn) = O(log n) ¨ K (znjyn) = O(log n).

’®£¤ K (zn) I (xn : yn) + O(log n).„®ª § ²¥«¼±²¢®. „«¿ «¾¡»µ xn , yn , zn ¨¬¥¾² ¬¥±²® ±®®²­®¸¥­¨¿K (xn; zn) = K (xn) + K (znjxn) + O(log n);K (xn) K (xnjyn) = I (xn : yn) + O(log n);K (xnjyn) K (xnjzn) + K (znjyn) + O(log n);K (xnjzn) + K (zn) = K (xn; zn ) + O(log n):‘ª« ¤»¢ ¿ ¨µ, ¯®«³· ¥¬K (zn) K (znjxn) + K (znjyn) + I (xn : yn) + O(log n):(4.2)“·¨²»¢ ¿ K (znjxn) = O(log n) ¨ K (znjyn) = O(log n), ¯®«³· ¥¬ K (zn) I (xn : yn) + O(log n). 20 0‹¥¬¬ 13.

³±²¼ ¤ ­» ·¥²»°¥ ¯®±«¥¤®¢ ²¥«¼­®±²¨ x, y, x , y ² ª¨¥,·²® xn ¨ yn ­¥§ ¢¨±¨¬» ®²­®±¨²¥«¼­® x0n ¨ ®²­®±¨²¥«¼­® yn0 :I (xn : ynjx0n) = O(log n); I (xn : ynjyn0 ) = O(log n):’®£¤ ¢±¿ª ¿ ¯®±«¥¤®¢ ²¥«¼­®±²¼ z, ¯°®±² ¿ ®²­®±¨²¥«¼­® x ¨ y(K (znjxn) = O(log n), K (znjyn) = O(log n)), ¯°®±² ² ª¦¥ ¨ ®²­®±¨²¥«¼­® x0 ¨ y0 (K (znjx0n) = O(log n), K (znjyn0 ) = O(log n)).„®ª § ²¥«¼±²¢®. ³±²¼ z ¯°®±² ®²­®±¨²¥«¼­® x ¨ y. ®ª ¦¥¬, ·²®00z ¯°®±² ² ª¦¥ ®²­®±¨²¥«¼­® x ¨ y .  ±±¬®²°¨¬ °¥«¿²¨¢¨§®¢ ­­»©¢ °¨ ­² ­¥° ¢¥­±²¢ (4.2)K (znjx0n) K (znjxn; x0n) + K (znjyn; x0n ) + I (xn : ynjx0n) + O(log n):69Ž±« ¡«¿¿ ¥£®, ¯®«³· ¥¬K (znjx0n) K (znjxn) + K (znjyn) + I (xn : ynjx0n) + O(log n):®±ª®«¼ª³ z ¯°®±² ®²­®±¨²¥«¼­® x ¨ y, ¨ ¯®±«¥¤®¢ ²¥«¼­®±²¨ x ¨ y­¥§ ¢¨±¨¬» ®²­®±¨²¥«¼­® x0 , ¯®«³· ¥¬ K (znjx0n) = O(log n).

€­ «®£¨·­®K (znjyn0 ) = O(log n). 2‘«¥¤³¾¹ ¿ «¥¬¬ ¯®§¢®«¨² ±¢®¤¨²¼ § ¤ ·³ ® ­¥¬ ²¥°¨ «¨§³¥¬®±²¨¢§ ¨¬­®© ¨­´®°¬ ¶¨¨ -¯ °» ª § ¤ ·¥ ® ­¥¬ ²¥°¨ «¨§³¥¬®±²¨ ¢§ ¨¬­®© ¨­´®°¬ ¶¨¨ ­¥ª®²®°®© -¯ °», ¯°¨·¥¬ > .³±²¼ < 1=2, ¨ ¯®±«¥¤®¢ ²¥«¼­®±²¨ x, y ®¡° §³¾² ¯ °³. ’®£¤ ¤«¿ «¾¡®£® , ³¤®¢«¥²¢®°¿¾¹¥£® ­¥° ¢¥­±²¢³‹¥¬¬ 14.p < min f1 1 2; 1=2g;±³¹¥±²¢³¥² ² ª ¿ -¯ ° x0 , y0 , ·²® «¾¡ ¿ ¯®±«¥¤®¢ ²¥«¼­®±²¼ z,¯°®±² ¿ ®²­®±¨²¥«¼­® x ¨ y, ¿¢«¿¥²±¿ ² ª¦¥ ¯°®±²®© ®²­®±¨²¥«¼­®00x ¨ y.®±²°®¨¬ ¯®±«¥¤®¢ ²¥«¼­®±²¨¿¢«¿¾²±¿ ±«³· ©­®© -¯ °®© ¨„®ª § ²¥«¼±²¢®.0,xy0,ª®²®°»¥I (xn : ynjx0n) = O(log n); I (xn : ynjyn0 ) = O(log n):’®£¤ ±®£« ±­® «¥¬¬¥ 13 ¢±¿ª ¿ ¯®±«¥¤®¢ ²¥«¼­®±²¼, ¯°®±² ¿ ®²­®±¨²¥«¼­® x ¨ y, ¡³¤¥² ² ª¦¥ ¯°®±²®© ¨ ®²­®±¨²¥«¼­® x0 ¨ y0 .

®±«¥¤®¢ ²¥«¼­®±²¨ x, y, x0 , y0 ¡³¤³² ®¡° §®¢»¢ ²¼ ·¥²¢¥°ª³ ±«³· ©­³¾ ®²­®±¨²¥«¼­® ­¥ª®²®°®£® ° ±¯°¥¤¥«¥­¨¿ P ±¯¥¶¨ «¼­®£® ¢¨¤ . ±±¬®²°¨¬ ·¥²¢¥°ª³ ¤¢®¨·­»µ ±«³· ©­»µ ¢¥«¨·¨­ '1, '2, '3 ¨ '4 ,¨¬¥¾¹¨µ ±«¥¤³¾¹¥¥ ±®¢¬¥±²­®¥ ° ±¯°¥¤¥«¥­¨¥ P . ‚®-¯¥°¢»µ, ¯®²°¥¡³¥¬, ·²®¡» ±®¢¬¥±²­»¥ ° ±¯°¥¤¥«¥­¨¿ ¯ ° ±«³· ©­»µ ¢¥«¨·¨­ h'1 ; '2i ¨h'3; '4 i ¡»«¨ ² ª¨¬¨, ª ª ¯®ª § ­® ­ °¨±.

4.2. ±¯°¥¤¥«¥­¨¥ '1 ¨ '2  ±¯°¥¤¥«¥­¨¥ '3 ¨ '4''0101''110022221 1 1122221234¨±. 4.2. °®¥ª¶¨¨ ° ±¯°¥¤¥«¥­¨¿70P'3 = 0; '4 = 001'1 t001 t101 '3 = 0; '4 = 101' 022 122'3 = 1; '4 = 001'022 122'3 = 1; '4 = 101't001 1 t101 '2'211'2'21¨±. 4.3.  ±¯°¥¤¥«¥­¨¿1'1 ; '2 ¯°¨ ´¨ª±¨°®¢ ­­»µ §­ ·¥­¨¿µ '3; '4‚®-¢²®°»µ, ³±«®¢­»¥ ° ±¯°¥¤¥«¥­¨¿ ¢¥°®¿²­®±²¥© ¯ °» h'1 ; '2i ¯°¨ ¨§¢¥±²­»µ §­ ·¥­¨¿µ '3 ¨ '4 ¤®«¦­» ¡»²¼ ² ª¨¬¨,pª ª ­ °¨±. 4.3.‚ ª ·¥±²¢¥ §­ ·¥­¨¿ ¯ ° ¬¥²° t ¢®§¼¬¥¬ 1 2 1 2 .

‚»° ¦¥­¨¥ ¤«¿¢¥«¨·¨­» t ¨¬¥¥² ±¬»±« (¯®¤ª®°¥­­®¥ ¢»° ¦¥­¨¥ ­¥®²°¨¶ ²¥«¼­®), ². ª.¯® ³±«®¢¨¾ 1=2.„ ­­®¥ ®¯°¥¤¥«¥­¨¥ ª®°°¥ª²­®, ². ¥. °¨±. 4.2 ¨ 4.3 ¤¥©±²¢¨²¥«¼­® § ¤ ¾² ±®¢¬¥±²­®¥ ° ±¯°¥¤¥«¥­¨¥ ·¥²¢¥°ª¨ ±«³· ©­»µ ¢¥«¨·¨­, ¥±«¨ ¢±¥·¨±« , ±²®¿¹¨¥ ¢ ² ¡«¨¶ µ, ­¥®²°¨¶ ²¥«¼­». ²® ³±«®¢¨¥ ¢»¯®«­¥­®, ¥±«¨ t 0 ¨ 1 t 0. ‹¥£ª® ¯°®¢¥°¨²¼, ·²® ®¡ ­¥° ¢¥­±²¢ ¢»¯®«­¥­»¤«¿ ¢»¡° ­­®£® §­ ·¥­¨¿ ¯ ° ¬¥²° .‚ ± ¬®¬ ¤¥«¥, ¯¥°¢®¥ ­¥° ¢¥­±²¢®p1 2 ¢ ³±«®¢¨¨ «¥¬¬», ¢²®°®¥¢»²¥ª ¥² ¨§ ®£° ­¨·¥­¨¿ 1­¥° ¢¥­±²¢® ¢»¯®«­¥­® ¤«¿ «¾¡»µ ¨ ¨§ ¨­²¥°¢ « (0; 12 ).„®ª ¦¥¬, ·²® ¯°¨ ¢»¡° ­­®¬ §­ ·¥­¨¨ t ±«³· ©­»¥ ¢¥«¨·¨­» '1 ¨'2 ­¥§ ¢¨±¨¬» ®²­®±¨²¥«¼­® '3 ¨ '4, §­ ·¨²I ('1 : '2j'3) = 0; I ('1 : '2j'4) = 0:„®ª § ²¥«¼±²¢ ­¥§ ¢¨±¨¬®±²¨ '1 ¨ '2 ¯°¨ ³±«®¢¨¿µ '3 = 0, '4 = 0,'3 = 1, ¨ '4 = 1 ±®¢¥°¸¥­­® ­ «®£¨·­», ¨ ¬» ° ±±¬®²°¨¬ ²®«¼ª®±«³· © '3 = 0.ˆ² ª, ¤®ª ¦¥¬, ·²® ¯°¨ ³ª § ­­®¬ ¢»¡®°¥ ¯ ° ¬¥²° t ±«³· ©­»¥¢¥«¨·¨­» '1 ¨ '2 ­¥§ ¢¨±¨¬» ¯°¨ ³±«®¢¨¨ '3 = 0.

‹¥£ª® ¢¨¤¥²¼, ·²®±®¢¬¥±²­®¥ ° ±¯°¥¤¥«¥­¨¥ '1 ¨ '2 ¯°¨ ³±«®¢¨¨ '3 = 0 ¡³¤¥² ² ª¨¬, ª ª­ °¨±. 4.4. ¥§ ¢¨±¨¬®±²¼ ¯ °» ¤¢®¨·­»µ ±«³· ©­»µ ¢¥«¨·¨­ ®§­ · ¥², ·²® § ¤ ¾¹ ¿ ° ±¯°¥¤¥«¥­¨¥ ¬ ²°¨¶ ¨§ ·¥²»°¥µ ·¨±¥« ¨¬¥¥² ° ­£®¤¨­. Ž±² ¥²±¿ ­ ©²¨ ² ª®¥ §­ ·¥­¨¥ t, ¯°¨ ª®²®°®¬ ®¯°¥¤¥«¨²¥«¼ ¬ ²°¨¶», § ¤ ­­®© ­ °¨±. 4.4, ° ¢¥­ ­³«¾. Œ» ¯®«³· ¥¬ ª¢ ¤° ²­®¥ ³° ¢71''1 20101 t + 22¨±. 4.4.  ±¯°¥¤¥«¥­¨¥12t + 2'1 ¨ '2 ¯°¨ ³±«®¢¨¨ '3 = 0­¥­¨¥2)(t +)= 0;(1 t +22 p 4®¤­¨¬ ¨§ ª®°­¥© ª®²®°®£® ¨ ¡³¤¥² ·¨±«® 1 2 1 2 .Œ» ¤®ª § «¨, ·²® ±«³· ©­»¥ ¢¥«¨·¨­» '1 ¨ '2 ­¥§ ¢¨±¨¬» ®²­®±¨²¥«¼­® '3 ¨ '4.

‘«¥¤®¢ ²¥«¼­®, ¥±«¨ ¯®±«¥¤®¢ ²¥«¼­®±²¨ ±«®¢ x; y; x0 ; y0®¡° §³¾² P -±«³· ©­³¾ ·¥²¢¥°ª³, ²®I (xn : ynjx0n) = O(log n); I (xn : ynjyn0 ) = O(log n):Š°®¬¥ ²®£®, x ¨ y ®¡° §³¾² -¯ °³, x0 ¨ y0 { -¯ °³.„«¿ ¤®ª § ²¥«¼±²¢ «¥¬¬» ®±² ¥²±¿ § ¬¥²¨²¼, ·²® ¥±«¨ ¤ ­ ¯°®¨§¢®«¼­ ¿ -¯ ° hx; yi, ²® ±®£« ±­® ³²¢¥°¦¤¥­¨¾ 2 ¥¥ ¬®¦­® ° ±¸¨°¨²¼¤® P -±«³· ©­®© ·¥²¢¥°ª¨ hx; y; x0 ; y0 i. 213‘«¥¤±²¢¨¥ 3. ³±²¼8 < < 2 , ¨ x, y { -¯ ° . ’®£¤ ¢±¿ª ¿ ¯®±«¥¤®-¢ ²¥«¼­®±²¼ z, ¯°®±² ¿ ®²­®±¨²¥«¼­® x ¨ y, ¨¬¥¥² «®£ °¨´¬¨·¥±ª³¾±«®¦­®±²¼ (K (zn) = O(log n)).„®ª § ²¥«¼±²¢®. ³±²¼ z { ¯®±«¥¤®¢ ²¥«¼­®±²¼, ¯°®±² ¿ ®²­®±¨p1 2, ².

¥. ¤«¿ ,²¥«¼­® x ¨ y. ¥²°³¤­® ¯°®¢¥°¨²¼, ·²® 12 < 1§ ¤ ­­®£® ¢ ³±«®¢¨¨ «¥¬¬», ¨ = 1=2 ¢»¯®«­¥­® ³±«®¢¨¥ «¥¬¬» 14.‘«¥¤®¢ ²¥«¼­®, z ² ª¦¥ ¿¢«¿¥²±¿ ¯°®±²®© ®²­®±¨²¥«¼­® ­¥ª®²®°»µ x0 ¨000y , ®¡° §³¾¹¨µ ±«³· ©­³¾ 1=2 ¯ °³. ® ¢§ ¨¬­ ¿ ¨­´®°¬ ¶¨¿ xn ¨ yn­¥ ¯°¥¢®±µ®¤¨² O(log n). ˆ§ «¥¬¬» 12 ¯®«³· ¥¬ K (zn) = O(log n). 2³±²¼ ²¥¯¥°¼ { ¯°®¨§¢®«¼­®¥ ·¨±«® ¨§ ¨­²¥°¢ « (0; 1). „«¿ ²®£®·²®¡» ¤®ª § ²¼, ·²® ¤«¿ ¢±¿ª®© -¯ °» ¢§ ¨¬­ ¿ ¨­´®°¬ ¶¨¿ ­¥ ¬ ²¥°¨ «¨§³¥²±¿, ¤®±² ²®·­® ­¥±ª®«¼ª® ° § ¯®¢²®°¨²¼ ¯°¨¥¬ ¨§ ¤®ª § ²¥«¼±²¢ ±«¥¤±²¢¨¿ 3. °®¢¥¤¥¬ ½²® ° ±±³¦¤¥­¨¥ ´®°¬ «¼­®.“²¢¥°¦¤¥­¨¥ 5. ³±²¼ 0 < < 1, x ¨ y { -¯ ° . ’®£¤ ¤«¿ ¢±¿ª®©¯®±«¥¤®¢ ²¥«¼­®±²¨ z, ¯°®±²®© ®²­®±¨²¥«¼­® x ¨ ®²­®±¨²¥«¼­® y,K (zn) = O(log n):72³±²¼ ¯®±«¥¤®¢ ²¥«¼­®±²¼ z ¯°®±² ®²­®±¨²¥«¼­®x ¨ ®²­®±¨²¥«¼­® y.

‘­ · « ®²¬¥²¨¬, ·²® ¥±«¨ x ¨ y ¿¢«¿¾²±¿ -¯ °®©,²®, § ¬¥­¨¢ ¢±¥ ¡¨²» ±«®¢ ¯®±«¥¤®¢ ²¥«¼­®±²¨ y ­ ¯°®²¨¢®¯®«®¦­»¥,¬» ¯®«³·¨¬ ( 12 ) ¯ °³ ± ² ª¨¬¨ ¦¥ ±¢®©±²¢ ¬¨ ¬ ²¥°¨ «¨§³¥¬®±²¨¢§ ¨¬­®© ¨­´®°¬ ¶¨¥©. ®½²®¬³ ¤®±² ²®·­® ° ±±¬®²°¥²¼ 1=2.‘«³· © = 1=2 ²°¨¢¨ «¥­. ‘«®¢ ±«³· ©­®© 1=2 ¯ °» ­¥§ ¢¨±¨¬»,². ¥.

I (xn : yn) = O(log n), ¯® «¥¬¬¥ 12 ±«®¦­®±²¼ ±«®¢ zn ­¥ ¡®«¼¸¥,I (xn : yn) + O(log n). ’ ª¨¬ ®¡° §®¬, ®±² ¥²±¿ ° ±±¬®²°¥²¼ < 1=2.³±²¼ ²¥¯¥°¼ 0 < < 1=2. ‚»¡¥°¥¬ ¯ ° ¬¥²° 1:„®ª § ²¥«¼±²¢®.p1 = min f1 1 2; 1=2g:‘®£« ±­® «¥¬¬¥ 13 ±³¹¥±²¢³¥² ² ª ¿ 1-¯ ° hx1; y1 i, ·²® ¢±¿ª ¿ ¯®±«¥¤®¢ ²¥«¼­®±²¼ z, ¯°®±² ¿ ®²­®±¨²¥«¼­® x ¨ y, ¿¢«¿¥²±¿ ² ª¦¥ ¯°®±²®© ¨ ®²­®±¨²¥«¼­® x1, y1. …±«¨ 1 = 1=2, ²® K (zn) ­¥ ¯°¥¢®±µ®¤¨²I (x1n : yn1 ) + O(log n), ¨ ¢±¥ ¤®ª § ­®. ‚ ¯°®²¨¢­®¬ ±«³· ¥ ±­®¢ ¯°¨¬¥­¨¬ «¥¬¬³ 13, ±®£« ±­® ª®²®°®© ±³¹¥±²¢³¥² ² ª ¿ 2-¯ ° hx2; y2 i,p1 21 ; 1=2g;2 = min f1·²® ¢±¿ª ¿ z, ¯°®±² ¿ ®²­®±¨²¥«¼­® x1 ¨ y1, ¿¢«¿¥²±¿ ¯°®±²®© ¨ ®²­®±¨²¥«¼­® x2, y2 . ®¢²®°¿¿ ¯°¨¬¥­¥­¨¥ «¥¬¬» 13, ¯®«³·¨¬ ¯®±«¥¤®¢ ²¥«¼­®±²¼ ¯ °hx1; y1 i; hx2 ; y2i; : : : ; hxn ; yn i; : : : ;£¤¥ ¤«¿ ª ¦¤®£® n ¯®±«¥¤®¢ ²¥«¼­®±²¨ xn ¨ yn ®¡° §³¾² n-¯ °³,p(4.3)n+1 = min f1 1 2n; 1=2g; n = 1; 2; : : :°¨ ½²®¬ ¢±¿ª ¿ ¯°®±² ¿ ®²­®±¨²¥«¼­® x ¨ y ¯®±«¥¤®¢ ²¥«¼­®±²¼ z ¿¢«¿¥²±¿ ² ª¦¥ ¯°®±²®© ®²­®±¨²¥«¼­® ª ¦¤®© ¨§ ¯®±«¥¤®¢ ²¥«¼­®±²¥© xn ¨ny .

Ž±² ¥²±¿ ¤®ª § ²¼, ·²® ­ ­¥ª®²®°®¬ ¸ £¥ ¡³¤¥² ¯®«³·¥­ 1=2-¯ ° :9N N = 1=2:°¥¤¯®«®¦¨¬ ¯°®²¨¢­®¥. ’®£¤ fng ¿¢«¿¥²±¿ ¡¥±ª®­¥·­®© ±²°®£® ¢®§° ±² ¾¹¥© ¯®±«¥¤®¢ ²¥«¼­®±²¼¾, ¢±¥ ·«¥­» ª®²®°®© ¬¥­¼¸¥ 1=2. ‡­ ·¨² ¯®±«¥¤®¢ ²¥«¼­®±²¼ ¨¬¥¥² ­¥ª®²®°»© ¯°¥¤¥« 1.

®¤±² ¢«¿¿ 1 ¢°¥ª³°°¥­²­®¥ ±®®²­®¸¥­¨¥ (4.3), ¯®«³· ¥¬p1 = 1 1 21 ;73®²ª³¤ 1 = 0. ® ½²® ¯°®²¨¢®°¥·¨² ¢®§° ±² ­¨¾ n. 2“²¢¥°¦¤¥­¨¥ 5 ¯®§¢®«¿¥² ¤®ª §»¢ ²¼ ²¥®°¥¬³ 7 ¤«¿ «¾¡®£® §­ ·¥­¨¿¯ ° ¬¥²° a. „¥©±²¢¨²¥«¼­®, ±®£« ±­® (4.1) ¤«¿ «¾¡®£® a ¨§ ¨­²¥°¢ « (0; 1) ±³¹¥±²¢³¥² ² ª®¥ , ·²® ±() = a; ²®£¤ ¤«¿ -¯ °» x, yK (xn) = n + O(log n); K (yn) = n + O(log n); I (xn : yn) = a n + O(log n):® ±®£« ±­® ³²¢¥°¦¤¥­¨¾ 5 ¤«¿ ¢±¿ª®© -¯ °» ®¡¹ ¿ ¨­´®°¬ ¶¨¿ ­¥¬ ²¥°¨ «¨§³¥²±¿.’¥¯¥°¼ «¥£ª® ¤®ª § ²¼ ²¥®°¥¬³ 8. ³±²¼ ¤ ­ ¯®±«¥¤®¢ ²¥«¼­®±²¼ x² ª ¿, ·²® K (xn ) = n + O(log n). ¥§ ®£° ­¨·¥­¨¿ ®¡¹­®±²¨ ¬®¦­® ±·¨² ²¼, ·²® ±«®¢ xn ¨¬¥¾² ¤«¨­³ n ¨ ±®¤¥°¦ ² ¯® n=2 + O(1) ­³«¥© ¨¥¤¨­¨¶ (±¬.

¯°¨¬¥° 7). ‘®£« ±­® ³²¢¥°¦¤¥­¨¾ 2 ¤«¿ «¾¡®£® 2 (0; 1)¬®¦­® ¯®¤®¡° ²¼ ² ª³¾ ¯®±«¥¤®¢ ²¥«¼­®±²¼ y, ·²® x ¨ y ®¡° §³¾² ¯ °³. Ž±² ¥²±¿ ¯°¨¬¥­¨²¼ ³²¢¥°¦¤¥­¨¥ 5.4.2.  °» ®°²®£®­ «¼­»µ ¯®¤¯°®±²° ­±²¢‚ ½²®¬ ° §¤¥«¥ ¬» ° ±±¬®²°¨¬ ¢²®°³¾ ª®­±²°³ª¶¨¾, ¯®§¢®«¿¾¹³¾ ¯®«³· ²¼ ¯®±«¥¤®¢ ²¥«¼­®±²¨ ±«®¢ x, y ± ­¥¬ ²¥°¨ «¨§³¥¬®© ¢§ ¨¬­®© ¨­´®°¬ ¶¨¥©.

‡ ´¨ª±¨°³¥¬ ¤¢ ¯ ° ¬¥²° { ­ ²³° «¼­»¥ ·¨±« m ¨ k² ª¨¥, ·²® 2k < m. „«¿ ª ¦¤®£® n 2 N ¢»¡¥°¥¬ ­¥ª®²®°®¥ ª®­¥·­®¥¯®«¥ Fn (¯®«¥ Fn ¡³¤¥² ±®¤¥°¦ ²¼ 2(n) ½«¥¬¥­²®¢). Ž¡®§­ ·¨¬ ·¥°¥§ Vn«¨­¥©­®¥ m-¬¥°­®¥ ¯°®±²° ­±²¢® ­ ¤ Fn. ‘·¨² ¥¬, ·²® ¢ Vn ¢»¡° ­ ­¥ª®²®°»© ¡ §¨±. ³¤¥¬ £®¢®°¨²¼, ·²® ¢¥ª²®°» v ¨ w ¨§ Vn ®°²®£®­ «¼­»,¥±«¨ ¢ ´¨ª±¨°®¢ ­­®© ±¨±²¥¬¥ ª®®°¤¨­ ²v = (v1; v2 ; : : : ; vm ); w = (w1; w2; : : : ; wm)¨v 1 w 1 + v 2 w 2 + : : : + v m w m = 0:„ «¥¥, ¡³¤¥¬ ­ §»¢ ²¼ «¨­¥©­»¥ ¯®¤¯°®±²° ­±²¢ A; B Vn ®°²®£®­ «¼­»¬¨, ¥±«¨ «¾¡®© ¢¥ª²®° ¨§ A ®°²®£®­ «¥­ «¾¡®¬³ ¢¥ª²®°³ ¨§ B .‚ ª ·¥±²¢¥ xn ¨ yn ¡³¤¥¬ ¡° ²¼ ¯ °» ®°²®£®­ «¼­»µ k-¬¥°­»µ ¯®¤¯°®±²° ­±²¢ ¨§ Vn. …±«¨ Pn { ·¨±«® ¢±¥µ ¯ ° ®°²®£®­ «¼­»µ k-¬¥°­»µ¯®¤¯°®±²° ­±²¢ ¢ Vn, ²®, ®·¥¢¨¤­®, K (xn; yn) log Pn + O(log n).

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

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