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

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

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

’®£¤ ±«®¢ xn, yn ¨¬¥¾² ¤«¨­³ n, ¯°¨·¥¬ ª ¦¤®¥¨§ ­¨µ ±®¤¥°¦¨² ¯® n=2 + O(1) ­³«¥© ¨ ¥¤¨­¨¶. Š°®¬¥ ²®£®, xn ¨ yn®²«¨· ¾²±¿ ¤°³£ ®² ¤°³£ ¢ n + O(1) ¡¨²®¢.Ž²¬¥²¨¬, ·²® ¥±«¨ ¯ ° hx; yi ²¨¯¨·­ ®²­®±¨²¥«¼­® ±®¢¬¥±²­®£®° ±¯°¥¤¥«¥­¨¿ ¯ °» ±«³· ©­»µ ¢¥«¨·¨­ h'; i, ²® ¯®±«¥¤®¢ ²¥«¼­®±²¼ x²¨¯¨·­ ®²­®±¨²¥«¼­® ° ±¯°¥¤¥«¥­¨¿ ±«³· ©­®© ¢¥«¨·¨­» ', ¯®±«¥¤®¢ ²¥«¼­®±²¼ y ²¨¯¨·­ ®²­®±¨²¥«¼­® ° ±¯°¥¤¥«¥­¨¿ .…±«¨ ±«³· ©­»¥ ¢¥«¨·¨­» '1 ; '2; : : : ; 'k ¨¬¥¾² ­¥ª®²®°®¥ ±®¢¬¥±²­®¥ ° ±¯°¥¤¥«¥­¨¥ P , ²® ¤«¿ «¾¡»µ P -²¨¯¨·­»µ ¯®±«¥¤®¢ ²¥«¼­®±²¥© x1 ; x2; : : : ; xk , «¾¡®£® ­¥¯³±²®£® ­ ¡®° ¨­¤¥ª±®¢V f1; 2; : : : ; kg ¨ «¾¡®£® (¡»²¼ ¬®¦¥² ¯³±²®£®) ­ ¡®° ¨­¤¥ª±®¢W f1; 2; : : : ; kg ¢»¯®«­¥­® ­¥° ¢¥­±²¢®“²¢¥°¦¤¥­¨¥ 1.K (xVn jxWn ) nH ('V j'W ) + O(log n)(1.4)(‚ ±«³· ¥, ª®£¤ ­ ¡®° ¨­¤¥ª±®¢ W ¯³±², ³±«®¢­ ¿ ª®«¬®£®°®¢±ª ¿±«®¦­®±²¼ ¨ ³±«®¢­ ¿ ¸¥­­®­®¢±ª ¿ ½­²°®¯¨¿ ¢ ° ¢¥­±²¢¥ (1.4) ®¡° ¹ ¾²±¿ ¢ ¡¥§³±«®¢­»¥.)„®ª § ²¥«¼±²¢®.

‘­ · « ° ±±¬®²°¨¬ ±«³· ©, ª®£¤ ­ ¡®° ¨­¤¥ª±®¢ W ¯³±². ’°¥¡³¥²±¿ ¤®ª § ²¼, ·²® ¤«¿ «¾¡®£® V ¢»¯®«­¥­® ° ¢¥­±²¢®K (xVn ) nH ('V )+ O(log n). …±«¨ V ±®¤¥°¦¨² °®¢­® ®¤¨­ ¨­¤¥ª±, ²® ¬»¬®¦¥¬ ±®±« ²¼±¿ ­ ¢»¢®¤ ( ) ¨§ ¯°¨¬¥° 2.³±²¼ ²¥¯¥°¼ V ±®¤¥°¦¨² l > 1 ¨­¤¥ª±®¢. Œ» § ª®¤¨°³¥¬ ª®°²¥¦¨Vxn ¯®±«¥¤®¢ ²¥«¼­®±²¼¾ ±«®¢ yn ¨ ±¢¥¤¥¬ l-¬¥°­»© ±«³· © ª ³¦¥ ° ±±¬®²°¥­­®¬³ ®¤­®¬¥°­®¬³. „«¿ ½²®£® ­ ¬ ¯®²°¥¡³¥²±¿ ¢¢¥±²¨ ­¥±ª®«¼ª®­®¢»µ ®¡®§­ ·¥­¨©.Ž¡®§­ ·¨¬ l-¬¥°­³¾ ±«³· ©­³¾ ¢¥«¨·¨­³ 'V ·¥°¥§ . ³±²¼ ª®­¥·­®¥ ¬­®¦¥±²¢® A { ®¡« ±²¼ §­ ·¥­¨© (§­ ·¥­¨¿¬¨ ¿¢«¿¾²±¿ ª®°²¥¦¨ ¤«¨­» l, § ¤ ¾¹¨¥ ­ ¡®° §­ ·¥­¨© 'V , ². ¥. A ¥±²¼ ¤¥ª °²®¢®¯°®¨§¢¥¤¥­¨¥ ®¡« ±²¥© §­ ·¥­¨© ´³­ª¶¨© ¨§ ª®°²¥¦ 'V ).

 §³¬¥¥²±¿,H () = H ('V ).32„ «¥¥, ®¯°¥¤¥«¨¬ ¯®±«¥¤®¢ ²¥«¼­®±²¼ ±«®¢ y. ‘«®¢ yn ¡³¤³² ±®±²®¿²¼ ¨§ n ¡³ª¢ «´ ¢¨² A. °¨ ½²®¬ ±«®¢ yn ¡³¤³² ª®¤¨°®¢ ²¼ ª®°²¥¦¨±«®¢ xVn ¢ ±«¥¤³¾¹¥¬ ±¬»±«¥: ¡³ª¢ ­ i-®¬ ¬¥±²¥ ¢ ±«®¢¥ yn ¡³¤¥² ±®®²¢¥²±²¢®¢ ²¼ ­ ¡®°³ ¡³ª¢, ±²®¿¹¨µ ­ i-»µ ¬¥±² µ ¢ ±«®¢ µ ª®°²¥¦ xVn .Ž·¥¢¨¤­®, K (yn) = K (xVn ) + O(1).®±ª®«¼ª³ ª®°²¥¦ xV ²¨¯¨·¥­ ®²­®±¨²¥«¼­® ° ±¯°¥¤¥«¥­¨¿ 'V , ¯®±²°®¥­­ ¿ ¯®±«¥¤®¢ ²¥«¼­®±²¼ y ²¨¯¨·­ ®²­®±¨²¥«¼­® ° ±¯°¥¤¥«¥­¨¿. Š ¯®±«¥¤®¢ ²¥«¼­®±²¨ y ¨ ±«³· ©­®© ¢¥«¨·¨­¥ ¯°¨¬¥­¨¬ ¢»¢®¤ ( )¨§ ¯°¨¬¥° 2. ’ ª¨¬ ®¡° §®¬, K (yn) nH () + O(log n). € §­ ·¨²,K (xVn ) nH ('V ) + O(log n):¥°¥©¤¥¬ ª ° ±±¬®²°¥­¨¾ ®±­®¢­®£® ±«³· ¿.

³±²¼ ­ ¡®° ¨­¤¥ª±®¢W ­¥¯³±². ³±²¼ V 0 = V n W . Ž·¥¢¨¤­®, H ('V j'W ) = H ('V j'W ) ¨K (xVn jxWn ) = K (xVn jxWn ) + O(1). ‘«¥¤®¢ ²¥«¼­®, ­¥ ®£° ­¨·¨¢ ¿ ®¡¹­®±²¨, ¬®¦­® ±·¨² ²¼, ·²® ­ ¡®°» ¨­¤¥ª±®¢ V ¨ W ­¥ ¯¥°¥±¥ª ¾²±¿. ±±¬®²°¨¬ ±«³· ©­»¥ ¢¥«¨·¨­» = 'V ¨ = 'W . Ž­¨ ¯°¨­¨¬ ¾² §­ ·¥­¨¿ ¢ ­¥ª®²®°»µ ª®­¥·­»µ «´ ¢¨² µ A ¨ B (¬­®¦¥±²¢® A ¿¢«¿¥²±¿ ¤¥ª °²®¢»¬ ¯°®¨§¢¥¤¥­¨¥¬ ¬­®¦¥±²¢ §­ ·¥­¨© ±«³· ©­»µ ¢¥«¨·¨­ 'V , B, ±®®²¢¥²±²¢¥­­®, ¤¥ª °²®¢»¬ ¯°®¨§¢¥¤¥­¨¥¬ ¬­®¦¥±²¢ §­ ·¥­¨© ¢¥«¨·¨­ 'W ). ³¤¥¬ ±·¨² ²¼, ·²® A = fa1; a2; : : : ; asg ¨B = fb1; b2; : : : ; br g.Ž¯°¥¤¥«¨¬ ­®¢»¥ ¯®±«¥¤®¢ ²¥«¼­®±²¨ ±«®¢ v ¨ w. ‘«®¢ vn ¡³¤³² ±®±²®¿²¼ ¨§ ¡³ª¢ «´ ¢¨² A, ±«®¢ wn { ¨§ ¡³ª¢ «´ ¢¨² B.

‘«®¢® vn¡³¤¥² ¨¬¥²¼ ¤«¨­³ n, ¨ ª ¦¤ ¿ ¥£® ¡³ª¢ ®¯°¥¤¥«¿¥²±¿ ¡³ª¢ ¬¨, ±²®¿¹¨¬¨ ¢ ±®®²¢¥²±²¢³¾¹¥© ¯®§¨¶¨¨ ¢ ±«®¢ µ ª®°²¥¦ xVn . €­ «®£¨·­®,wn ² ª¦¥ ¡³¤¥² ¨¬¥²¼ ¤«¨­³ n, ¨ ª ¦¤ ¿ ¡³ª¢ ¢ ±«®¢¥ wn ®¯°¥¤¥«¿¥²±¿ ¡³ª¢ ¬¨, ±²®¿¹¨¬¨ ¢ ±®®²¢¥²±²¢³¾¹¥© ¯®§¨¶¨¨ ¢ ±«®¢ µ ª®°²¥¦ xWn . ’ ª¨¬ ®¡° §®¬, vn ¨ wn ª®¤¨°³¾² ª®°²¥¦¨ xVn ¨ xWn . Ž·¥¢¨¤­®, ·²®K (vnjwn) = K (xVn jxWn ) + O(1). °¨ ½²®¬ ¯ ° hv; wi ¿¢«¿¥²±¿ ²¨¯¨·­®©®²­®±¨²¥«¼­® ° ±¯°¥¤¥«¥­¨¿ h; i.Ž±² «®±¼ ¤®ª § ²¼, ·²® ¥±«¨ ¯ ° ¯®±«¥¤®¢ ²¥«¼­®±²¥© hv; wi ²¨¯¨·­ ®²­®±¨²¥«¼­® ° ±¯°¥¤¥«¥­¨¿ ¯ °» ±«³· ©­»µ ¢¥«¨·¨­ h; i, ²®K (vn jwn) nH (j ) + O(log n):‡ ´¨ª±¨°³¥¬ ­¥ª®²®°»© ­®¬¥° n. Ž¡®§­ ·¨¬ mij ·¨±«® ² ª¨µ ¯®§¨¶¨©, ¢ ª®²®°»µ ¢ ±«®¢¥ vn ±²®¨² ¡³ª¢ ai, ¢ ±«®¢¥ wn { ¡³ª¢ bj .

®±ª®«¼ª³ ¯ ° hv; wi ²¨¯¨·­ ®²­®±¨²¥«¼­® ° ±¯°¥¤¥«¥­¨¿ h; i,mij = Prob[ = ai ; = bj ] n + O(1):(1.5)0033„ «¥¥, ¯®±«¥¤®¢ ²¥«¼­®±²¼ w ²¨¯¨·­ ®²­®±¨²¥«¼­® ° ±¯°¥¤¥«¥­¨¿ .²® §­ ·¨², ·²® ¤«¿ ª ¦¤®£® j = 1; : : : ; r ±«®¢® wn ±®¤¥°¦¨²mj = Prob[ = bj ] n + O(1)¡³ª¢ bj . ‡ ¬¥²¨¬, ·²®Xmj = mij :(1.6)i°¥¤¯®«®¦¨¬, ·²® ±«®¢® wn ¨§¢¥±²­® ¨ ²°¥¡³¥²±¿ ­ ©²¨ vn. ‘«®¦­®±²¼ ­ µ®¦¤¥­¨¿ ¢±¥µ ·¨±¥« mij ¥±²¼ O(log n) (ª®­±² ­² ¯¥°¥¤ «®£ °¨´¬®¬ § ¢¨±¨² ®² ° §¬¥°®¢ «´ ¢¨²®¢ A ¨ B, ­® ­¥ § ¢¨±¨² ®² n).³±²¼ ¢¥«¨·¨­» mij ³¦¥ ­ ©¤¥­». ’®£¤ ¤«¿ ¯®«³·¥­¨¿ ±«®¢ vn ¤®±² ²®·­® ¤«¿ ª ¦¤®£® j = 1; 2 : : : ; r ³ª § ²¼ ° §¡¨¥­¨¥ ²¥µ mj ¯®§¨¶¨©, ¢ ª®²®°»µ ¢ ±«®¢¥ wn ±²®¨² ¡³ª¢ bj , ­ s ª« ±±®¢ (±®¤¥°¦ ¹¨µ m1j ; : : : ; msj¯®§¨¶¨©), ¢ ª®²®°»µ ¢ ±«®¢¥ vn ±²®¿² ¡³ª¢» a1; : : : ; as ±®®²¢¥²±²¢¥­­®.„«¿ ª ¦¤®£® j ¨¬¥¥²±¿mj !m1j !m2j ! : : : msj !±¯®±®¡®¢ ° §¡¨²¼ mj ¯®§¨¶¨© ­ ­¥¯¥°¥±¥ª ¾¹¨¥±¿ ¯®¤¬­®¦¥±²¢ ° §¬¥° m1j ; : : : ; msj .

‘«¥¤®¢ ²¥«¼­®,Xmj!K (vnjwn) log m !m ! : : : m ! + O(log n):(1.7)1j2jsjjŽ¶¥­¨¢ ¿ ´ ª²®°¨ «» ± ¯®¬®¹¼¾ ´®°¬³«» ‘²¨°«¨­£ , ­¥²°³¤­® ¯°¥®¡° §®¢ ²¼ ¯° ¢³¾ · ±²¼ (1.7) ¢ ¢»° ¦¥­¨¥X mijnlog mij + O(log n):mji;j nˆ§ (1.5) ¨ (1.6) ±«¥¤³¥², ·²® mnij = Prob[ = ai; = bj ] + O(1=n) ¨ mmijj =Prob[ = ai j = bj ] + O(1=n). ‡­ ·¨² ¯° ¢ ¿ · ±²¼ ­¥° ¢¥­±²¢ (1.7)° ¢­ nXijProb[ = ai; = bj ] log Prob[ = aij = bj ] + O(log n) == n H (j ) + O(log n):234³¤¥¬ ­ §»¢ ²¼ P -²¨¯¨·­»© ª®°²¥¦ ¯®±«¥¤®¢ ²¥«¼­®±²¥© ±«®¢ hx1; x2 ; : : : ; xk i P -±«³· ©­»¬, ¥±«¨ ¤«¿ «¾¡®£® ­¥¯³±²®£® ­ ¡®° ¨­¤¥ª±®¢ V f1; 2 : : : ; kg ¨ «¾¡®£® (¡»²¼ ¬®¦¥² ¯³±²®£®) ­ ¡®° ¨­¤¥ª±®¢ W f1; 2 : : : ; kg ¢»¯®«­¥­® ° ¢¥­±²¢®K (xVn jxWn ) = nH ('V j'W ) + O(log n):(1.8)(‚ ±«³· ¥, ª®£¤ ­ ¡®° ¨­¤¥ª±®¢ W ¯³±², ³±«®¢­ ¿ ª®«¬®£®°®¢±ª ¿±«®¦­®±²¼ ¨ ³±«®¢­ ¿ ¸¥­­®­®¢±ª ¿ ½­²°®¯¨¿ ¢ ° ¢¥­±²¢¥ (1.8) ®¡° ¹ ¾²±¿ ¢ ¡¥§³±«®¢­»¥.)¨¦¥ ¬» ¤®ª ¦¥¬, ·²® ¤«¿ «¾¡®£® ° ±¯°¥¤¥«¥­¨¿ P ±³¹¥±²¢³¥² P ±«³· ©­»© ª®°²¥¦.°¨¬¥° 4.

³±²¼ { ±«³· ©­ ¿ ¢¥«¨·¨­ , ° ¢­ ¿ ­³«¾ ± ¢¥°®¿²­®±²¼¾1, ±«®¢ xn ±®±²®¿² ¨§ n ­³«¥©. ’®£¤ H () = 0 ¨ K (xn ) = O(log n).°¨ ½²®¬ ¯®±«¥¤®¢ ²¥«¼­®±²¼ x ±«³· ©­ ®²­®±¨²¥«¼­® ° ±¯°¥¤¥«¥­¨¿¢¥«¨·¨­» .°¨¬¥° 5.  ±±¬®²°¨¬ ±«¥¤³¾¹¥¥ ° ±¯°¥¤¥«¥­¨¥ P ±«³· ©­®© ¢¥«¨·¨­» :Prob[ = 0] = 1=2; Prob[ = 1] = 1=2:¥²°³¤­® ¯°®¢¥°¨²¼, ·²® H () = 1.Ž¯¨¸¥¬ ±®®²¢¥²±²¢³¾¹¨¥ ¤ ­­®¬³ ° ±¯°¥¤¥«¥­¨¾ P -±«³· ©­»¥ ¯®±«¥¤®¢ ²¥«¼­®±²¨ x. °¥¦¤¥ ¢±¥£® ®­¨ ¤®«¦­» ¡»²¼ P -²¨¯¨·­»¬¨, ². ¥.ª ¦¤®¥ ±«®¢® xn ¤®«¦­® ¤®«¦­® ¨¬¥²¼ ¤«¨­³ n ¨ ±®±²®¿²¼ ¨§ n=2+ O(1)­³«¥© ¨ n=2 + O(1) ¥¤¨­¨¶.„ «¥¥, P -±«³· ©­®±²¼ ¯®±«¥¤®¢ ²¥«¼­®±²¨ §­ ·¨², ·²®K (xn) = nH () + O(log n) = n + O(log n):’ ª¨¬ ®¡° §®¬, P -±«³· ©­»¬¨ ¡³¤³² ¯®±«¥¤®¢ ²¥«¼­®±²¨ ±«®¢, ±®¤¥°¦ ¹¨µ ¯°¨¬¥°­® ° ¢­®¥ ·¨±«® ­³«¥© ¨ ¥¤¨­¨¶ ¨ ¨¬¥¾¹¨µ ±«®¦­®±²¼¡«¨§ª³¾ ª ¬ ª±¨¬ «¼­®© (±°¥¤¨ ¢±¥µ ¤¢®¨·­»µ ±«®¢ ¤ ­­®© ¤«¨­»).‡ ¬¥· ­¨¥ 1.

“ P -±«³· ©­»µ ¯®±«¥¤®¢ ²¥«¼­®±²¥© ±«®¢ ­¥ ²®«¼ª®³±«®¢­»¥ ¨ ¡¥§³±«®¢­»¥ ª®«¬®£®°®¢±ª¨¥ ±«®¦­®±²¨, ­® ¨ ¢¥«¨·¨­» ¢§ ¨¬­®© ¨­´®°¬ ¶¨¨ ¯°®¯®°¶¨®­ «¼­» ±®®²¢¥²±²¢³¾¹¨¬ ¸¥­­®­®¢±ª¨¬¢¥«¨·¨­ ¬. ³±²¼, ­ ¯°¨¬¥°, ¯ ° ¯®±«¥¤®¢ ²¥«¼­®±²¥© hx; yi ±«³· ©­ ®²­®±¨²¥«¼­® ° ±¯°¥¤¥«¥­¨¿ P ¯ °» ±«³· ©­»µ ¢¥«¨·¨­ h'; i. ‘®£« ±­® ®¯°¥¤¥«¥­¨¾ P -±«³· ©­®±²¨ ¢¥«¨·¨­» K (xn), K (yn) ¨ K (xn; yn)Ž¯°¥¤¥«¥­¨¥ 2.35° ¢­» (± ²®·­®±²¼¾ ¤® «®£ °¨´¬¨·¥±ª®£® ±« £ ¥¬®£®) nH ('), nH ( ) ¨nH ('; ) ±®®²¢¥²±²¢¥­­®. ’®£¤ ­ «®£¨·­®¥ ° ¢¥­±²¢® ¢»¯®«­¿¥²±¿ ¨¤«¿ ¢§ ¨¬­®© ¨­´®°¬ ¶¨¨.

‚ ± ¬®¬ ¤¥«¥, ±° ¢­¨¢ ¿ ° ¢¥­±²¢ I (' : ) = H (') + H ( ) H ('; )¨I (xn : yn) = K (xn) + K (yn) K (xn; yn) + O(log n)¯®«³· ¥¬I (xn : yn) = nI (' : ) + O(log n):‹¥¬¬ 2. ³±²¼ ª®°²¥¦ ¯®±«¥¤®¢ ²¥«¼­®±²¥© hx1 ; x2 ; : : : ; xk i ²¨¯¨·¥­ ®²­®±¨²¥«¼­® ±®¢¬¥±²­®£® ° ±¯°¥¤¥«¥­¨¿ P ±«³· ©­»µ ¢¥«¨·¨­h'1; '2 ; : : : ; 'k i, ¨ K (xn; : : : ; xk ) = nH ('1; '2 ; : : : ; 'k ) + O(log n): ’®£¤ ¤ ­­»© ª®°²¥¦ ¯®±«¥¤®¢ ²¥«¼­®±²¥© P -±«³· ¥­.„®ª § ²¥«¼±²¢®. ³±²¼ V { ¯°®¨§¢®«¼­»© ­ ¡®° ¨­¤¥ª±®¢.

‘­ · « ° ±±¬®²°¨¬ ±«³· © W = ; ¨ ¤®ª ¦¥¬, ·²® K (xVn ) = nH ('V ): ‘®£« ±­®«¥¬¬¥ 1 ¢»¯®«­¥­® ­¥° ¢¥­±²¢® K (xVn ) nH ('V ) + O(log n). „®ª ¦¥¬®¡° ²­®¥ ­¥° ¢¥­±²¢®.Ž¡®§­ ·¨¬ U = f1; 2; : : : ; kg ­ ¡®° ¢±¥µ ¨­¤¥ª±®¢. ³±²¼ V 0 = U n V .ˆ§ «¥¬¬» 1 ±«¥¤³¥² ­¥° ¢¥­±²¢®K (xVn jxVn ) nH ('V j'V ) + O(log n):‘ª« ¤»¢ ¿ ¥£® ± ° ¢¥­±²¢ ¬¨K (xUn ) = K (xVn ) + K (xVn jxVn ) + O(log n);nH ('U ) = K (xUn ) + O(log n);nH ('V j'V ) + nH ('V ) = nH ('U );¯®«³· ¥¬ K (xVn ) nH ('V )+O(log n).

’ ª¨¬ ®¡° §®¬, ¤«¿ «¾¡®£® ­ ¡®° ¨­¤¥ª±®¢ V ¢»¯®«­¥­® ° ¢¥­±²¢®K (xVn ) = nH ('V ) + O(log n):’¥¯¥°¼ ¯³±²¼ W { ¯°®¨§¢®«¼­»© ­ ¡®° ¨­¤¥ª±®¢; ®¡®§­ ·¨¬ U~ = V [W . ‚»·¨² ¿ ¨§ ° ¢¥­±²¢ K (xUn~ ) = nH ('U~ ) + O(log n)° ¢¥­±²¢®K (xWn ) = nH ('W ) + O(log n);000036¯®«³· ¥¬K (xVn jxWn ) = nH ('V j'W ) + O(log n):2‚ ¤ «¼­¥©¸¥¬ ­ ¬ ¯®²°¥¡³¥²±¿ ª®­±²°³ª¶¨¿, ¯®§¢®«¿¾¹ ¿ ° ±¸¨°¿²¼ P -±«³· ©­»¥ ª®°²¥¦¨.

€ ¨¬¥­­®, ¯³±²¼ s; r { ­¥®²°¨¶ ²¥«¼­»¥ ¶¥«»¥ ·¨±« , ¨ s < r. ³¤¥¬ ±·¨² ²¼, ·²® ±«³· ©­»¥ ¢¥«¨·¨­»'1; '2; : : : ; 'r ¨¬¥¾² ±®¢¬¥±²­®¥ ° ±¯°¥¤¥«¥­¨¥ P . Ž¡®§­ ·¨¬ ·¥°¥§ P 0¯°®¥ª¶¨¾ ° ±¯°¥¤¥«¥­¨¿ P ­ ¯¥°¢»¥ s ª®®°¤¨­ ², ². ¥. ±®¢¬¥±²­®¥ ° ±¯°¥¤¥«¥­¨¥ ¢¥«¨·¨­ '1; '2 ; : : : ; 's . ’®£¤ «¾¡®© P 0-±«³· ©­»© ª®°²¥¦¬®¦­® ¤®¯®«­¨²¼ ¤® P -±«³· ©­®£®.

®«¥¥ ²®·­®, ¢»¯®«­¥­ ±«¥¤³¾¹ ¿«¥¬¬ .³±²¼ P { ±®¢¬¥±²­®¥ ° ±¯°¥¤¥«¥­¨¥ r ±«³· ©­»µ¢¥«¨·¨­, { ¯°®¥ª¶¨¿ ° ±¯°¥¤¥«¥­¨¿ P ­ ¯¥°¢»¥ s ª®®°¤¨­ ², ¨ ª®°²¥¦ hx1 ; x2 ; : : : ; xs i ¿¢«¿¥²±¿ P 0 -±«³· ©­»¬. ’®£¤ ±³¹¥±²¢³¾² ² ª¨¥ ¯®±«¥¤®¢ ²¥«¼­®±²¨ xs+1 ; xs+2 ; : : : ; xr , ·²® ª®°²¥¦ hx1 ; x2; : : : ; xr i¿¢«¿¥²±¿ P -±«³· ©­»¬.“²¢¥°¦¤¥­¨¥ 2.P0Š ª ¨ ¢ ¤®ª § ²¥«¼±²¢¥ «¥¬¬» 1, ¬» ¡³¤¥¬ § ¬¥­¿²¼ ¬­®£®¬¥°­»¥ ° ±¯°¥¤¥«¥­¨¿ ®¤­®¬¥°­»¬¨ ¨ ª®¤¨°®¢ ²¼ ª®°²¥¦¨ ±«®¢ ®¤­¨¬ ±«®¢®¬. € ¨¬¥­­®, ¬» ¡³¤¥¬ ° ±±¬ ²°¨¢ ²¼ ±«³· ©­»¥¢¥«¨·¨­» = h'1 : : : ; 's i ¨ = h's+1 ; : : : ; 'r i, ª®°²¥¦¨ hx1n : : : ; xsn ir¨ hxs+1n ; : : : ; xn i § ¬¥­¨¬ ­ ¯ °³ ±«®¢ vn , wn.

Ž¡®§­ ·¨¬ ¬­®¦¥±²¢ ,¢ ª®²®°»µ ¨ ¯°¨­¨¬ ¾² §­ ·¥­¨¿, ·¥°¥§ A = fa1; a2; : : : ; ak g ¨B = fb1; b2; : : : ; bl g ±®®²¢¥²±²¢¥­­® (A ¥±²¼ ¤¥ª °²®¢® ¯°®¨§¢¥¤¥­¨¥ ®¡« ±²¥© §­ ·¥­¨© ±«³· ©­»µ ¢¥«¨·¨­ '1; : : : ; 's , ¨ B ¥±²¼ ¤¥ª °²®¢® ¯°®¨§¢¥¤¥­¨¥ ®¡« ±²¥© §­ ·¥­¨© 's+1 ; : : : ; 'r ). ‘«®¢ vn ¡³¤³² ±®±²®¿²¼ ¨§ n¡³ª¢ «´ ¢¨² A, ±«®¢ wn { ¨§ n ¡³ª¢ «´ ¢¨² B.°¥®¡° §³¥¬ § ¤ ­­»¥ ¢ ³±«®¢¨¨ «¥¬¬» ª®°²¥¦¨ hx1n : : : ; xsni ¢ ±«®¢ vn. ³ª¢ ±«®¢ vn ¢ ¯®§¨¶¨¨ i ¡³¤¥² ±®®²¢¥²±²¢®¢ ²¼ ­ ¡®°³ ¡³ª¢,±²®¿¹¨µ ¢ i-»µ ¯®§¨¶¨¿µ ¢ ±«®¢ µ ª®°²¥¦ hx1n; : : : ; xsn i (i = 1; : : : ; n). ®±ª®«¼ª³ ¨±µ®¤­»© ª®°²¥¦ P 0-±«³· ¥­, ¯®±²°®¥­­ ¿ ¯®±«¥¤®¢ ²¥«¼­®±²¼v ±«³· ©­ ®²­®±¨²¥«¼­® ° ±¯°¥¤¥«¥­¨¿ .‘«¥¤³¥² ®²¤¥«¼­® ° ±±¬®²°¥²¼ ±«³· ©, ª®£¤ s = 0. ’®£¤ ¡³¤¥¬ ±·¨² ²¼, ·²® A = f0g (k = 1), ±«³· ©­ ¿ ¢¥«¨·¨­ ° ¢­ ­³«¾ ± ¢¥°®¿²­®±²¼¾ 1, ¢ ª ·¥±²¢¥ vn ¬» ¡³¤¥¬ ¡° ²¼ ±«®¢ , ±®±²®¿¹¨¥ ¨§ n ­³«¥©(±¬. ¯°¨¬¥° 4).„®ª § ²¥«¼±²¢®.37Œ» ¤®ª ¦¥¬, ·²® ¤«¿ ª ¦¤®© ±«³· ©­®© ®²­®±¨²¥«¼­® ¯®±«¥¤®¢ ²¥«¼­®±²¨ v ­ ©¤¥²±¿ ² ª ¿ ¯®±«¥¤®¢ ²¥«¼­®±²¼ w (¢ «´ ¢¨²¥ B), ·²®¯ ° hv; wi ¿¢«¿¥²±¿ ±«³· ©­®© ®²­®±¨²¥«¼­® ±®¢¬¥±²­®£® ° ±¯°¥¤¥«¥­¨¿ h; i.® ­ ©¤¥­­®© ¯®±«¥¤®¢ ²¥«¼­®±²¨ w ¬®¦­® ¡³¤¥² ¯®±²°®¨²¼ ª®°²¥¦hxs+1 ; : : : ; xr i: ¡³ª¢» ¢ ±«®¢¥ wn ª®¤¨°³¾² ­ ¡®° ¡³ª¢, ±²®¿¹¨µ ¢ ±®r®²¢¥²±²¢³¾¹¨µ ¯®§¨¶¨¿µ ¢ ±«®¢ µ ª®°²¥¦ hxs+1n ; : : : ; xn i.

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

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