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

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

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

’ ª, ¢ [1] ¯®ª § ­®, ·²® ±«®¦­®±²¼ ¯ °» ±«®¢ ¢»° ¦ ¥²±¿·¥°¥§ ±«®¦­®±²¼ ¯¥°¢®£® ±«®¢ ¢ ¯ °¥ ¨ ³±«®¢­³¾ ±«®¦­®±²¼ ¢²®°®£®:K (x; y) = K (x) + K (yjx) + O(log(jxj + jyj)):(0.1)‚ ¦­® ®²¬¥²¨²¼, ·²® «®£ °¨´¬¨·¥±ª®¥ ±« £ ¥¬®¥ ¢ ° ¢¥­±²¢¥ (0.1) ­¥«¼§¿ § ¬¥­¨²¼ ­ ·«¥­ ¬¥­¼¸¥£® ¯®°¿¤ª 1.‚§ ¨¬­ ¿ ¨­´®°¬ ¶¨¿ ±«®¢ x ¨ y ®¯°¥¤¥«¿¥²±¿ ª ª ° §­®±²¼ ¬¥¦¤³ ª®«¬®£®°®¢±ª®© ±«®¦­®±²¼¾ ±«®¢ y ¨ ³±«®¢­®© ±«®¦­®±²¼¾ ±«®¢ y®²­®±¨²¥«¼­® ±«®¢ x:I (x : y) := K (y) K (yjx):’ ª¨¬ ®¡° §®¬, ¢§ ¨¬­ ¿ ¨­´®°¬ ¶¨¿ x ¨ y ¯®ª §»¢ ¥², ­ ±ª®«¼ª® §­ ­¨¥ ±«®¢ x ³¯°®¹ ¥² § ¤ ·³ ­ µ®¦¤¥­¨¿ y.

ˆ§ (0.1) ¨ ®¯°¥¤¥«¥­¨¿ ¢§ ¨¬­®© ¨­´®°¬ ¶¨¨ ±«¥¤³¥² ° ¢¥­±²¢®I (x : y) = K (x) + K (y) K (x; y) + O(log(jxj + jyj)):(0.2)ˆ§ (0.2) ¢¨¤­®, ·²® ¢§ ¨¬­ ¿ ¨­´®°¬ ¶¨¿ ¯ °» ±«®¢ ±¨¬¬¥²°¨·­ (±²®·­®c²¼¾ ¤® «®£ °¨´¨·¥±ª®£® ±« £ ¥¬®£®), ². ¥.jI (x : y) I (y : x)j = O(log(jxj + jyj)):(0.3)®«¼¸¨­±²¢® ¤¢®¨·­»µ ±«®¢ ¤«¨­» n ¨¬¥¾² ª®«¬®£®°®¢±ª³¾ ±«®¦­®±²¼, ¡«¨§ª³¾ ª n. ®½²®¬³¯®¯° ¢ª O(log(jxj + jyj)) ¢ (0.1) ­¥¢¥«¨ª .16Š ª ¯®ª § ­® ¢ [1], ¢ ° ¢¥­±²¢ µ (0.2) ¨ (0.3), ª ª ¨ ¢ (0.1), ­¥«¼§¿ ¨§¡ ¢¨²¼±¿ ®² «®£ °¨´¬¨·¥±ª®£® ±« £ ¥¬®£®.

’ ª¦¥ «¨¸¼ ± ²®·­®±²¼¾ ¤®O(log(jxj + jyj)) ¢»¯®«­¥­® ­¥° ¢¥­±²¢®, ¢»° ¦ ¾¹¥¥ ±¢®©±²¢® ±³¡ ¤¤¨²¨¢­®±²¨K (x; y) K (x) + K (y) + O(log(jxj + jyj)):(0.4)Ž²¬¥²¨¬, ·²® ±¢®©±²¢® ¬®­®²®­­®±²¨K (x) K (x; y) + O(1)(0.5)¢»¯®«­¥­® ± ²®·­®±²¾ ¤¤¨²¨¢­®© ª®­±² ­²».’ ª¨¬ ®¡° §®¬, ¬­®£¨¥ ¯°®±²¥©¸¨¥ ¨ ­ ¨¡®«¥¥ ¥±²¥±²¢¥­­»¥ ­¥° ¢¥­±²¢ ¤«¿ ª®«¬®£®°®¢±ª¨µ ±«®¦­®±²¥© ¢»¯®«­¥­» ²®«¼ª® ± ²®·­®c²¼¾ ¤® ¤¤¨²¨¢­®£® «®£ °¨´¬¨·¥±ª®£® ·«¥­ . ‚ ¤ ­­®© ° ¡®²¥ ¬» ¢±¥£¤ ¡³¤¥¬ ° ±±¬ ²°¨¢ ²¼ ±®®²­®¸¥­¨¿ ¬¥¦¤³ ª®«¬®£®°®¢±ª¨¬¨ ±«®¦­®±²¿¬¨±«®¢ ± ²®·­®±²¼¾ ¤® «®£ °¨´¬¨·¥±ª®£® ±« £ ¥¬®£®.Ž²¬¥²¨¬, ·²® ª°®¬¥ ®¯°¥¤¥«¥­­®© ¢»¸¥ ª®«¬®£®°®¢±ª®© ±«®¦­®±²¨ (­ §»¢ ¥¬®© ² ª¦¥ ¯°®±²®© ª®«¬®£®°®¢±ª®© ±«®¦­®±²¼¾), ¨±¯®«¼§³¾²±¿ °®¤±²¢¥­­»¥ ¥© ¯®­¿²¨¿ ¯°¥´¨ª±­®©, ¬®­®²®­­®© ±«®¦­®±²¨,±«®¦­®±²¨ ° §°¥¸¥­¨¿ ¨ ¯°¨®°­®© ½­²°®¯¨¨.

²¨ ¢ °¨ ­²» ±«®¦­®±²¥© ¨¬¥¾² ° §«¨·­»¥ ±¯¥¶¨ «¼­»¥ ±¢®©±²¢ [14]. Ž¤­ ª® ¤«¿ ª ¦¤®£® ±«®¢ x ¢±¥ ¯¥°¥·¨±«¥­­»¥ ¢»¸¥ ¢¨¤» ±«®¦­®±²¥© ¨¬¥¾² §­ ·¥­¨¿,®²«¨· ¾¹¨¥±¿ «¨¸¼ ­ O(log jxj). ®½²®¬³, ¯®±ª®«¼ª³ ¢±¥ ¤ «¼­¥©¸¨¥³²¢¥°¦¤¥­¨¿ ¬» ¡³¤¥¬ ´®°¬³«¨°®¢ ²¼ À± ²®·­®±²¼¾ ¤® «®£ °¨´¬ Á, °¥§³«¼² ²» ¤ ­­®© ° ¡®²¥ ¬®£³² ¡»²¼ ¯¥°¥­¥±¥­» ­ ¢±¥ ¢ °¨ ­²» ª®«¬®£®°®¢±ª®© ±«®¦­®±²¨.Ž¤­ ¨§ ¯¥°¢»µ ° ¡®² Š®«¬®£®°®¢ ¯® «£®°¨²¬¨·¥±ª®© ±«®¦­®±²¨­ §»¢ « ±¼ À’°¨ ¯®¤µ®¤ ª ®¯°¥¤¥«¥­¨¾ ¯®­¿²¨¿ \ª®«¨·¥±²¢® ¨­´®°¬ ¶¨¨"Á. „¢³¬¿ ¨§ ²°¥µ ° ±±¬®²°¥­­»µ ¢ ±² ²¼¥ ¯®¤µ®¤®¢ ¡»«¨ ½­²°®¯¨¿ ˜¥­­®­ ¨ «£®°¨²¬¨·¥±ª ¿ ±«®¦­®±²¼. Š®«¬®£®°®¢ ¯®ª § «, ·²® «£®°¨²¬¨·¥±ª¨© ¯®¤µ®¤ ¿¢«¿¥²±¿ ³²®·­¥­¨¥¬ ¢¥°®¿²­®±²­®£®, ¨ ®¡° ²¨« ¢­¨¬ ­¨¥ ­ ¯ ° ««¥«¨§¬ ±¢®©±²¢ ½­²°®¯¨© ±«³· ©­»µ ¢¥«¨·¨­ ¨ «£®°¨²¬¨·¥±ª®© ±«®¦­®±²¨ ±«®¢. °®±²¥©¸¨¥ ¯°¨¬¥°» ¤ ­­®£® ¯ ° ««¥«¨§¬ { ±®®²­®¸¥­¨¿ (0.1), (0.2), (0.3) ¤«¿ ª®«¬®£®°®¢±ª®© ±«®¦­®±²¨¨ ­ «®£¨·­»¥ ¨¬ ±®®²­®¸¥­¨¿H (; ) = H () + H (j )(0.6)I ( : ) = H () + H ( ) H (; )(0.7)I ( : ) = I ( : )(0.8)7¤«¿ ¸¥­­®­®¢±ª®© ½­²°®¯¨¨.

„«¿ ¸¥­­®­®¢±ª¨µ ½­²°®¯¨© ¢»¯®«­¥­»² ª¦¥ ±¢®©±²¢ ¬®­®²®­­®±²¨H () H (; )(0.9)¨ ±³¡ ¤¤¨²¨¢­®±²¨H (; ) H () + H ( ):(0.10)¥ª®²®°»¥ ¡®«¥¥ ±«®¦­»¥ ­¥° ¢¥­±²¢ ¤«¿ ª®«¬®£®°®¢±ª®© ±«®¦­®±²¨, ² ª¦¥ ¨µ ¯°¨¬¥­¥­¨¿ ° ±±¬ ²°¨¢ «¨±¼ ¢ [10]. Ž²¬¥²¨¬, ·²® ¤«¿¢±¥µ ­¥° ¢¥­±²¢ ¤«¿ ª®«¬®£®°®¢±ª®© ±«®¦­®±²¨, ° ±±¬®²°¥­­»µ ¢ [10],­¥²°³¤­® ¤®ª § ²¼ ¸¥­­®­®¢±ª¨¥ ­ «®£¨ ( ­ «®£¨·­»¥ ­¥° ¢¥­±²¢ ,¢»¯®«­¥­­»¥ ¤«¿ ¸¥­­®­®¢±ª®© ½­²°®¯¨¨).‚ ¤ ­­®© ° ¡®²¥ ¬» ¤®ª ¦¥¬, ·²® ¢±¥ ±¢®©±²¢ , ¢»° §¨¬»¥ ± ¯®¬®¹¼¾ «¨­¥©­»µ ° ¢¥­±²¢ ¨ ­¥° ¢¥­±²¢, ®¤¨­ ª®¢» ¤«¿ ª®«¬®£®°®¢±ª®©±«®¦­®±²¨ ¨ ¸¥­­®­®¢±ª®© ½­²°®¯¨¨, ².

¥. ª« ±±» «¨­¥©­»µ ­¥° ¢¥­±²¢,¢»¯®«­¥­­»µ ¤«¿ ª®«¬®£®°®¢±ª¨µ ±«®¦­®±²¥© ¨ ¤«¿ ¸¥­­®­®¢±ª¨µ ½­²°®¯¨©, ±®¢¯ ¤ ¾². ’ ª¦¥ ¬» ¯®ª ¦¥¬, ·²® ±³¹¥±²¢³¥² «¨­¥©­®¥ ­¥° ¢¥­±²¢® (­¥° ¢¥­±²¢® ˆ­£«¥²®­ ), ¢»¯®«­¥­­®¥ ¤«¿ ° §¬¥°­®±²¥© «¨­¥©­»µ ¯®¤¯°®±²° ­±²¢, ­® ­¥ ¢»¯®«­¥­­®¥ ¤«¿ ¸¥­­®­®¢±ª®© ½­²°®¯¨¨¨ ª®«¬®£®°®¢±ª®© ±«®¦­®±²¨.…¹¥ ®¤­¨¬ ¯°¨¬¥°®¬ ¯ ° ««¥«¨§¬ ¬¥¦¤³ ª« ±±¨·¥±ª®© ¨ «£®°¨²¬¨·¥±ª®© ²¥®°¨¥© ¨­´®°¬ ¶¨¨ ¿¢«¿¥²±¿ ¯®­¿²¨¥ ®¡¹¥© ¨­´®°¬ ¶¨¨.‚ [9] ƒ · ¨ Š¥°­¥° ®¯°¥¤¥«¨«¨ ®¡¹³¾ ¨­´®°¬ ¶¨¾ ¯ °» ±«³· ©­»µ ¢¥«¨·¨­, ² ª¦¥ ¤ «¨ ¢ ²¥°¬¨­ µ ª®«¬®£®°®¢±ª®© ±«®¦­®±²¨ ­¥´®°¬ «¼­®¥®¯°¥¤¥«¥­¨¥ ­ «®£¨·­®£® ¯®­¿²¨¿ ¤«¿ ¯ °» ±«®¢.

ˆ­²³¨²¨¢­® ¢¥«¨·¨­ ®¡¹¥© ¨­´®°¬ ¶¨¨ ¤¢³µ ®¡º¥ª²®¢ (¤¢³µ ±«³· ©­»µ ¢¥«¨·¨­ ¨«¨ ¤¢³µ±«®¢) ¥±²¼ ° §¬¥° ¨µ À®¡¹¥© · ±²¨Á, ². ¥. ¬ ª±¨¬³¬ ¨­´®°¬ ¶¨¨, ª®²®°³¾ ¬®¦­® ¢»¤¥«¨²¼ ®¤­®¢°¥¬¥­­® ¨§ ®¡®¨µ ®¡º¥ª²®¢ (±¬. ² ª¦¥ [6],£¤¥ ¯®­¿²¨¥ ®¡¹¥© ¨­´®°¬ ¶¨¨ ¯ °» ±«³· ©­»µ ¢¥«¨·¨­ ®¡±³¦¤ ¥²±¿± ²®·ª¨ §°¥­¨¿ ²¥®°¨¨ ª®¤¨°®¢ ­¨¿). ‹¥£ª® ¯®ª § ²¼, ·²® ª ª ¢ ¸¥­­®­®¢±ª®¬, ² ª ¨ ¢ ª®«¬®£®°®¢±ª®¬ ±«³· ¥ ¢¥«¨·¨­ ®¡¹¥© ¨­´®°¬ ¶¨¨ ­¥¯°¥¢®±µ®¤¨² ¢§ ¨¬­®© ¨­´®°¬ ¶¨¨ ®¡º¥ª²®¢.

Ž±­®¢­»¬ °¥§³«¼² ²®¬° ¡®²» [9] ¡»«® ¤®ª § ²¥«¼±²¢® ²®£®, ·²® ®¡¹ ¿ ¨­´®°¬ ¶¨¿ ±«³· ©­»µ ¢¥«¨·¨­ ¬®¦¥² ¡»²¼ ­ ¬­®£® ¬¥­¼¸¥ ¢§ ¨¬­®© ¨­´®°¬ ¶¨¨. °¨½²®¬ ƒ · ¨ Š¥°­¥° ³ª § «¨ ½´´¥ª²¨¢­»© ±¯®±®¡ ¢»·¨±«¥­¨¿ ®¡¹¥© ¨­´®°¬ ¶¨¨ ¯ °» ±«³· ©­»µ ¢¥«¨·¨­ ¯® ¨µ ±®¢¬¥±²­®¬³ ° ±¯°¥¤¥«¥­¨¾.’ ª¦¥ ¢ [9] ¡»«® ¯®±²°®¥­® ±¥¬¥©±²¢® ¯°¨¬¥°®¢ ¯ ° ±«®¢, ³ ª®²®°»µ8®¡¹ ¿ ¨­´®°¬ ¶¨¿ ­ ¬­®£® ¬¥­¼¸¥ ¨µ ¢§ ¨¬­®© ¨­´®°¬ ¶¨¨. „®ª § ²¥«¼±²¢® ƒ · ¨ Š¥°­¥° ¨±¯®«¼§®¢ «® ¬¥²®¤» ²¥®°¨¨ ¢¥°®¿²­®±²¥© ¨¡»«® ¤®¢®«¼­® ±«®¦­»¬.€­. €. Œ³·­¨ª [5, 13] ¯°¥¤«®¦¨« ¡®«¥¥ ¯°®±²®¥ ¨ ¨±¯®«¼§³¾¹¥¥ ²®«¼ª® «£®°¨²¬¨·¥±ª¨¥ ¬¥²®¤» ¤®ª § ²¥«¼±²¢® ±³¹¥±²¢®¢ ­¨¿ ¯ ° ±«®¢, ³ª®²®°»µ ®¡¹ ¿ ¨­´®°¬ ¶¨¿ ¬­®£® ¬¥­¼¸¥ ¢§ ¨¬­®©. ‚ [13] ¡»« ¯®±² ¢«¥­ ¢®¯°®±: ¤«¿ ¢±¿ª®£® «¨ ±«®¢ x ±³¹¥±²¢³¥² ² ª®¥ y, ·²® ¢§ ¨¬­ ¿¨­´®°¬ ¶¨¿ x ¨ y ¨¬¥¥² § ¤ ­­³¾ ¢¥«¨·¨­³, ®¡¹ ¿ ¨­´®°¬ ¶¨¿ ­³«¥¢ ¿? ‚ ¤ ­­®© ° ¡®²¥ ¬» ¯®«³·¨¬ ¯®«®¦¨²¥«¼­»© ®²¢¥² ­ ¢®¯°®±Œ³·­¨ª .‚¥°­¥¬±¿ ª ¢®¯°®±³ ® ±²°®£®¬ ®¯°¥¤¥«¥­¨¨ ¯®­¿²¨¿ ®¡¹¥© ¨­´®°¬ ¶¨¨ ¯ °» ±«®¢.

¥´®°¬ «¼­® ¬» £®¢®°¨¬, ·²® x ¨ y ¨¬¥¾² u ¡¨²®¢®¡¹¥© ¨­´®°¬ ¶¨¨, ¥±«¨ ¥±²¼ ±«®¢® z ±«®¦­®±²¨ u, ª®²®°®¥ ¯°®±²® ®²­®±¨²¥«¼­® x ¨ ®²­®±¨²¥«¼­® y. °¨ ¯®¯»²ª¥ ¤ ²¼ ²®·­®¥ ®¯°¥¤¥«¥­¨¥ ¢®§­¨ª ¾² ²¥µ­¨·¥±ª¨¥ ²°³¤­®±²¨. „¥«® ¢ ²®¬, ·²® ¤«¿ ®¯°¥¤¥«¥­¨¿ ®¡¹¥©¨­´®°¬ ¶¨¨ ²°¥¡³¥²±¿ ´®°¬ «¨§®¢ ²¼ ¨­²³¨²¨¢­®¥ ®²­®¸¥­¨¥ À±«®¢®z ¯°®±²® ®²­®±¨²¥«¼­® ±«®¢ xÁ. Ž¤­ ª® ª ¦¥²±¿ ­¥¢®§¬®¦­»¬ ®²¤¥«¨²¼ ±«®¢ À±«®¦­»¥Á ®²­®±¨²¥«¼­® x ®² ±«®¢ À¯°®±²»µÁ ®²­®±¨²¥«¼­®x. —²®¡» ¯°¥®¤®«¥²¼ ½²® § ²°³¤­¥­¨¥, ¢ [15] ¡»«® ¯°¥¤«®¦¥­® ¯¥°¥©²¨®² ° ±±¬®²°¥­¨¿ ¨­¤¨¢¨¤³ «¼­»µ ±«®¢ ª ¡¥±ª®­¥·­»¬ ¯®±«¥¤®¢ ²¥«¼­®±²¿¬ ±«®¢.  ¬­®¦¥±²¢¥ ¯®±«¥¤®¢ ²¥«¼­®±²¥© ±«®¢ ¬®¦­® ®¯°¥¤¥«¨²¼®²­®¸¥­¨¥ À³±«®¢­®© ¯°®±²®²»Á. € ¨¬¥­­®, ° ±±¬®²°¨¬ ¯®±«¥¤®¢ ²¥«¼­®±²¨ ±«®¢ x1; x2; : : : ¨ y1; y2; : : :, ¯°¥¤¯®« £ ¿ jxnj = O(n) ¨ jynj = O(n).³¤¥¬ £®¢®°¨²¼, ·²® ¯®±«¥¤®¢ ²¥«¼­®±²¼ y1; y2; : : : ¯°®±² ®²­®±¨²¥«¼­®¯®±«¥¤®¢ ²¥«¼­®±²¨ x1; x2 ; : : :, ¥±«¨ ±ª®°®±²¼ °®±² ³±«®¢­®© ±«®¦­®±²¨K (ynjxn) ±¨¬¯²®²¨·¥±ª¨ ¬ « ¯® ±° ¢­¥­¨¾ ± n.

‚®§¬®¦­» ° §«¨·­»¥¢ °¨ ­²» ³²®·­¥­¨¿ ¯®­¿²¨¿ ±¨¬¯²®²¨·¥±ª®© ¬ «®±²¨.  ¨¡®«¥¥ ¥±²¥±²¢¥­­»¬ ª ¦¥²±¿ £®¢®°¨²¼, ·²® K (ynjxn) = O(log n). ® ¢®§¬®¦­» ¨¤°³£¨¥ ¢ °¨ ­²» ´®°¬ «¨§ ¶¨¨ ®²­®¸¥­¨¿ ³±«®¢­®© ¯°®±²®²»: ¤«¿ «¾¡®© ´³­ª¶¨¿ f (n) ² ª®©, ·²®f (n) = (log n); f (n) = o(n) ¯°¨ n ! 1;¬®¦­® ®¯°¥¤¥«¨²¼ ¯°®±²®²³ fyng ®²­®±¨²¥«¼­® fxng ³±«®¢¨¥¬K (ynjxn) = O(f (n)):’ ª¨¬ ®¡° §®¬, ¬» ®¯°¥¤¥«¨«¨ ±¥¬¥©±²¢® ®²­®¸¥­¨© · ±²¨·­®£® ¯°¥¤¯®°¿¤ª ­ ¯°®±²° ­±²¢¥ ¯®±«¥¤®¢ ²¥«¼­®±²¥© ±«®¢. ®±«¥ ´ ª²®°¨§ 9¶¨¨ ¯® ±®®²¢¥²±²¢³¾¹¨¬ ®²­®¸¥­¨¿¬ ½ª¢¨¢ «¥­²­®±²¨ ¯®«³· ¥¬ ±¥¬¥©±²¢® · ±²¨·­»µ ¯®°¿¤ª®¢. ‚ ¤ ­­®© ° ¡®²¥ ¬» ¯®ª ¦¥¬, ·²® ¢±¥ ³ª § ­­»¥ · ±²¨·­® ³¯®°¿¤®·¥­­»¥ ¬­®¦¥±²¢ ¿¢«¿¾²±¿ ¢¥°µ­¨¬¨ ¯®«³°¥¸¥²ª ¬¨, ­® ­¥ ¿¢«¿¾²±¿ ­¨¦­¨¬¨ ¯®«³°¥¸¥²ª ¬¨.Ž¯°¥¤¥«¿¥¬®¥ ±¥¬¥©±²¢® ¯®«³°¥¸¥²®ª ¬®¦­® ° ±±¬ ²°¨¢ ²¼ ª ª ´¨­¨²­»© ­ «®£ ²¼¾°¨­£®¢»µ ±²¥¯¥­¥© ­¥° §°¥¸¨¬®±²¨, ¨ ¨§³·¥­¨¥ ¨µ «£¥¡° ¨·¥±ª¨µ ±¢®©±²¢ ª ¦¥²±¿ ¨­²¥°¥±­®© ± ¬®±²®¿²¥«¼­®© § ¤ ·¥©.¥ª®²®°»¥ ±¢®©±²¢ ¤ ­­»µ ¯®«³°¥¸¥²®ª ° ±±¬ ²°¨¢ «¨±¼ ¢ [15].

®¤«¿ ­ ± ½²¨ ¯®«³°¥¸¥²ª¨ ¢ ¦­» ¯°¥¦¤¥ ¢±¥£® ª ª ¨­±²°³¬¥­² ¤«¿ ´®°¬ «¨§ ¶¨¨ ¯®­¿²¨¿ ®¡¹¥© ¨­´®°¬ ¶¨¨. ‡ ´¨ª±¨°®¢ ¢ ®¤¨­ ¨§ ³ª § ­­»µ ¢ °¨ ­²®¢ ®¯°¥¤¥«¥­¨¿ ³±«®¢­®© ¯°®±²®²», ¬®¦­® ®¯°¥¤¥«¨²¼ ®¡¹³¾ ¨­´®°¬ ¶¨¾ ¤«¿ ¯ °» ¯®±«¥¤®¢ ²¥«¼­®±²¥© ±«®¢ ª ª ¨µ ²®·­³¾­¨¦­¾¾ £° ­¼ ®²­®±¨²¥«¼­® ¢¢¥¤¥­­®£® ®²­®¸¥­¨¿ ¯°¥¤¯®°¿¤ª . Œ»¤®ª ¦¥¬ ±³¹¥±²¢®¢ ­¨¥ ¯ ° ¯®±«¥¤®¢ ²¥«¼­®±²¥© ± ¡®«¼¸®© ¢§ ¨¬­®©¨­´®°¬ ¶¨¥© ¨ ­³«¥¢®© ²®·­®© ­¨¦­¥© £° ­¼¾, ·²® ¢ ²¥°¬¨­®«®£¨¨ƒ · ¨ Š¥°­¥° ±®®²¢¥²±²¢³¥² ±³¹¥±²¢®¢ ­¨¾ ¯ ° ±«®¢ ± ¡®«¼¸®© ¢§ ¨¬­®© ¨­´®°¬ ¶¨¥© ¨ ­³«¥¢®© ®¡¹¥© ¨­´®°¬ ¶¨¥©. Œ» ° ±±¬®²°¨¬ ¤¢ ±¥¬¥©±²¢ ¯°¨¬¥°®¢ ¯ °, ¨¬¥¾¹¨µ ¡®«¼¸³¾ ¢§ ¨¬­³¾ ¨ ­³«¥¢³¾ ®¡¹³¾¨­´®°¬ ¶¨¾.

¥°¢®¥ ¨§ ° ±±¬ ²°¨¢ ¥¬»µ ­ ¬¨ ±¥¬¥©±²¢ ¯°¨¬¥°®¢ ¡»«® ¯°¥¤«®¦¥­® ¢ [9]. Œ» ¯°¨¢¥¤¥¬ ¤«¿ ­¥£® ­®¢®¥, ¡®«¥¥ ¯°®±²®¥ ¤®ª § ²¥«¼±²¢® ²®£®, ·²® ¢¥«¨·¨­ ®¡¹¥© ¨­´®°¬ ¶¨¨ ¬­®£® ¬¥­¼¸¥, ·¥¬¢§ ¨¬­ ¿ ¨­´®°¬ ¶¨¿; ¯°¨ ½²®¬ ¬» ¯®«³·¨¬ ¡®«¥¥ ±¨«¼­³¾ ®¶¥­ª³ ­ ¢¥«¨·¨­³ ®¡¹¥© ¨­´®°¬ ¶¨¨. ‚²®°®¥ ±¥¬¥©±²¢® ° ±±¬ ²°¨¢ ¥¬»µ ­ ¬¨¯°¨¬¥°®¢ ¿¢«¿¥²±¿ ®¡®¡¹¥­¨¥¬ ª®­±²°³ª¶¨¨ ¨§ ° ¡®²» [13]. Ž¡ ° ±±¬ ²°¨¢ ¥¬»µ ª« ±± ¯°¨¬¥°®¢ ¯®§¢®«¿² ­ ¬ ¤ ²¼ ¯®«®¦¨²¥«¼­»© ®²¢¥² ­ ¢®¯°®± €­. €. Œ³·­¨ª .„ «¥¥ ¬» ª° ²ª® ®¯¨¸¥¬ ±®¤¥°¦ ­¨¥ £« ¢ 1-4.‚ £« ¢¥ 1 ¬» ¤ ¤¨¬ ­¥±ª®«¼ª® ®¯°¥¤¥«¥­¨© ¨ ¤®ª ¦¥¬ ®±­®¢­»¥ ²¥µ­¨·¥±ª¨¥ ³²¢¥°¦¤¥­¨¿, ­¥®¡µ®¤¨¬»¥ ¤«¿ ¯®«³·¥­¨¿ °¥§³«¼² ²®¢, ±¢¿§»¢ ¾¹¨µ ª®«¬®£®°®¢±ª³¾ ±«®¦­®±²¼ ¨ ½­²°®¯¨¾ ˜¥­­®­ .³±²¼ ±«³· ©­ ¿ ¢¥«¨·¨­ ' ¯°¨­¨¬ ¥² §­ ·¥­¨¿ a1; : : : ; am ± ¢¥°®¿²­®±²¿¬¨ p1; : : : ; pm .  ±±¬®²°¨¬ n ª®¯¨© ±«³· ©­»µ ¢¥«¨·¨­ '. ’®·­¥¥,¯³±²¼ '1; : : : ; 'n ­¥§ ¢¨±¨¬» ¨ ª ¦¤ ¿ ¨§ ­¨µ ° ±¯°¥¤¥«¥­ ª ª '.

³¤¥¬ ¨­²¥°¥±®¢ ²¼±¿ À²¨¯¨·­»¬¨Á §­ ·¥­¨¿¬¨ n-ª¨ ±«³· ©­»µ ¢¥«¨·¨­h'1; : : : ; 'n i. ‡­ ·¥­¨¿¬¨ ¤ ­­®£® ª®°²¥¦ ±«³· ©­»µ ¢¥«¨·¨­ ¿¢«¿¾²±¿±«®¢ ¤«¨­» n ¢ «´ ¢¨²¥ a1 : : : ; am. ® § ª®­³ ¡®«¼¸¨µ ·¨±¥« ± ¡«¨§ª®©ª ¥¤¨­¨¶¥ ¢¥°®¿²­®±²¼¾ ¤®«¨ ¡³ª¢ ai ¢ ½²®¬ ±«®¢¥ ¡³¤³² ¡«¨§ª¨ ª ¢¥°®10¿²­®±²¿¬ pi .

‡ ¬¥²¨¬, ·²® ±®£« ±­® § ª®­³ ¡®«¼¸¨µ ·¨±¥« ±°¥¤¨ §­ ·¥p­¨© 'j ¤®«¿ ¡³ª¢ ai ± ¡®«¼¸®© ¢¥°®¿²­®±²¼¾ ¡³¤¥² ° ¢­® pi n + O( n),². ¥. ³ª«®­¥­¨¥ · ±²®² ®² ¢¥°®¿²­®±²¥© ®¡° ²­® ¯°®¯®°¶¨®­ «¼­® ª®°­¾¨§ n. „«¿ ­ ± ¡³¤³² ¨­²¥°¥±­» ±«®¢ , ¢ ª®²®°»µ · ±²®²» ¡³ª¢ ³ª«®­¿¾²±¿ ®² ¢¥°®¿²­®±²¥© ¬¥­¼¸¥, ·¥¬ ¬®¦­® ®¦¨¤ ²¼ ¢ ±®®²¢¥²±²¢¨¨ ±§ ª®­®¬ ¡®«¼¸¨µ ·¨±¥«. ³¤¥¬ £®¢®°¨²¼, ·²® ±«®¢® ¤«¨­» n ²¨¯¨·­®®²­®±¨²¥«¼­® ° ±¯°¥¤¥«¥­¨¿ ', ¥±«¨ ®­® ±®¤¥°¦¨² pi n + O(1) ¡³ª¢ ai(i = 1; : : : ; m). —²®¡» ¯°¨¤ ²¼ ²®·­»© ±¬»±« ¬ «®¬³ ·«¥­³ O(1), ¬»¤®«¦­» ®¯°¥¤¥«¿²¼ ²¨¯¨·­®±²¼ ­¥ ¤«¿ ¨­¤¨¢¨¤³ «¼­»µ ±«®¢, ¤«¿ ¡¥±ª®­¥·­»µ ¯®±«¥¤®¢ ²¥«¼­®±²¥©.€­ «®£¨·­®¥ ®¯°¥¤¥«¥­¨¥ ¨¬¥¥² ±¬»±« ² ª¦¥ ¨ ¤«¿ ¬­®£®¬¥°­»µ ±«³· ©­»µ ¢¥«¨·¨­ '. „ ¤¨¬ ´®°¬ «¼­®¥ ®¯°¥¤¥«¥­¨¥ ±° §³ ¤«¿ ¬­®£®¬¥°­®£® ±«³· ¿.1 2k ¯°¨­¨¬ ¾²Ž¯°¥¤¥«¥­¨¥.

³±²¼ ±«³· ©­»¥ ¢¥«¨·¨­» ' ; ' ; : : : ; '§­ ·¥­¨¿ ¢ ª®­¥·­»µ «´ ¢¨² µ A1; A2; : : : ; Ak ¨ ¨¬¥¾² ±®¢¬¥±²­®¥° ±¯°¥¤¥«¥­¨¥P (a1; a2; : : : ; ak ) = Prob['1 = a1; '2 = a2; : : : ; 'k = ak ]: §®¢¥¬ ª®°²¥¦ hx1 ; x2; : : : ; xk i, ±®±²®¿¹¨© ¨§ k ¡¥±ª®­¥·­»µ ¯®±«¥¤®¢ ²¥«¼­®±²¥© ±«®¢, P -²¨¯¨·­»¬, ¥±«¨ ª ¦¤®¥ ±«®¢® xin ¨¬¥¥² ¤«¨­³ n, ¨ ¤«¿ «¾¡®£® ­ ¡®° §­ ·¥­¨© ha1; a2; : : : ; ak i ·¨±«® ² ª¨µ ¯®§¨¶¨© i, ·²® ¢ ª ¦¤®¬ ±«®¢¥ xjn ­ i-¬ ¬¥±²¥ ±²®¨² ¡³ª¢ aj , ° ¢­®nP (a1; a2; : : : ; ak ) + O(1).‚ ¦­»¬ ±¢®©±²¢®¬ P -²¨¯¨·­»µ ¯®±«¥¤®¢ ²¥«¼­®±²¥© ¿¢«¿¥²±¿ ±¢¿§¼ª®«¬®£®°®¢±ª®© ±«®¦­®±²¨ ±«®¢ ² ª¨µ ¯®±«¥¤®¢ ²¥«¼­®±²¨ ¨ ¸¥­­®­®¢±ª®© ½­²°®¯¨¨ ° ±¯°¥¤¥«¥­¨¿ P .

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

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