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

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

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

³¤¥¬ ±·¨² ²¼, ·²® ¯¥°¢»¥ k ³° ¢­¥­¨© ¯¥°¢®© ±¨±²¥¬» ±®®²¢¥²±²¢³¾² ®°²®£®­ «¼­®±²¨ y0 ¯®¤¯°®±²° ­±²¢³ x0, ¯¥°¢»¥ k³° ¢­¥­¨© ¢²®°®© ±¨±²¥¬» { ®°²®£®­ «¼­®±²¨ yr ¯®¤¯°®±²° ­±²¢³ xr .„®ª § ²¥«¼±²¢®.84Š°®¬¥ ²®£®, ¬®¦­® ±·¨² ²¼, ·²® ¯¥°¢»¥ lr ³° ¢­¥­¨© ®¡¥¨µ ±¨±²¥¬ ±®¢¯ ¤ ¾² (¨ ±®®²¢¥²±²¢³¾² ®°²®£®­ «¼­®±²¨ ®¡®¨µ ¯®¤¯°®±²° ­±²¢ y0,yr ¯®¤¯°®±²° ­±²¢³ x0 \ xr ). Ž¡º¥¤¨­¨¬ ¤¢¥ ¤ ­­»¥ ±¨±²¥¬» ³° ¢­¥­¨©.°®±²° ­±²¢® °¥¸¥­¨© ­®¢®© ±¨±²¥¬» (¨§ 2(n k) lr ³° ¢­¥­¨©) ¥±²¼¯¥°¥±¥·¥­¨¥ y0 ¨ yr .

 ± ¨­²¥°¥±³¥² ¢¥°®¿²­®±²¼ ²®£®, ·²® ¥£® ° §¬¥°­®±²¼ ° ¢­ lr 1. Ž·¥¢¨¤­®, ½² ¢¥°®¿²­®±²¼ ®¯°¥¤¥«¿¥²±¿ §­ ·¥­¨¿¬¨ n,k ¨ r, ­® ­¥ § ¢¨±¨² ®² ¢»¡®° ª®­ª°¥²­®£® xr .  ¬ ­¥ ²°¥¡³¥²±¿ §­ ·¥­¨¥ ¤ ­­®© ¢¥°®¿²­®±²¨. ‚ ¦­® «¨¸¼, ·²® ®­® ®¤­®§­ ·­® ®¯°¥¤¥«¿¥²±¿­®¬¥°®¬ r (¯°¨ ¤ ­­®¬ n) ¨ ­¥ § ¢¨±¨² ®² ¢»¡®° xr 2 Ar . 2‡ ª®­·¨¬ ¤®ª § ²¥«¼±²¢® ³²¢¥°¦¤¥­¨¿ 6.  ±±¬®²°¨¬ ¬­®¦¥±²¢® X r¶¥¯®·¥ª ¯®¤¯°®±²° ­±²¢ (4.13) ¤«¨­» r. ‘®£« ±­® «¥¬¬¥ 17 ¢±¥ ² ª¨¥ ¶¥¯®·ª¨ § ¨±ª«¾·¥­¨¥¬ ½ª±¯®­¥­¶¨ «¼­® ¬ «®© ¤®«¨ ¿¢«¿¾²±¿ ¯° ¢¨«¼­»¬¨, §­ ·¨², r¨µ ¯° ¢»¥ ª®­¶» «¥¦ ² ¢ Ar .

„ «¥¥, ¯® «¥¬¬¥ 16 ¯®jX j ¶¥¯®·¥ª ¨¬¥¾² ¯° ¢»¥ ª®­¶», ¯°®±²»¥ ®²­®±¨²¥«¼ª° ©­¥© ¬¥°¥ poly(n)­® z (². ¥. ¨µ ±«®¦­®±²¼®²­®±¨²¥«¼­® z ­¥ ¯°¥¢®±µ®¤¨² D). ‡­ ·¨² ­¥rjjX¬¥­¥¥ ·¥¬ poly(n) ¶¥¯®·¥ª ®¤­®¢°¥¬¥­­® ¿¢«¿¾²±¿ ¯° ¢¨«¼­»¬¨ ¨ ¨¬¥¾² ¯° ¢»© ª®­¥¶ ±«®¦­®±²¨ ­¥ ¡®«¥¥ D ®²­®±¨²¥«¼­® z . ® ¢ ±¨«³ ®¤­®°®¤­®±²¨ («¥¬¬ 18) ¢±¥ ¯®¤¯°®±²° ­±²¢ ¨§ Ar ¿¢«¿¾²±¿ ¯° ¢»¬¨ª®­¶ ¬¨ ®¤¨­ ª®¢®£®·¨±« ¯° ¢¨«¼­»µ ¶¥¯®·¥ª.

‘«¥¤®¢ ²¥«¼­®, ­¥ ¬¥rjjA­¥¥ ·¥¬ poly(n) ½«¥¬¥­²®¢ ¬­®¦¥±²¢ Ar ¨¬¥¾² ±«®¦­®±²¼ ­¥ ¡®«¼¸¥ D®²­®±¨²¥«¼­® z .‚»¡¥°¥¬ ¬¨­¨¬ «¼­®¥ r, ¤«¿ ª®²®°®£® lr = 0. ’®£¤ Ar ±®±²®¨² ¨§¢±¥µ k-¬¥°­»µ ¯®¤¯°®±²° ­±²¢, ¨¬¥¾¹¨µ ­³«¥¢®¥ ¯¥°¥±¥·¥­¨¥ ± x. ‚½²®¬ ±«³· ¥ ¢±¥ k-¬¥°­»¥ ¯®¤¯°®±²° ­±²¢ ¨§ Vn ª°®¬¥ ½ª±¯®­¥­¶¨ «¼­® ¬ «®© ¤®«¨ «¥¦ ² ¢ Ar . „¥©±²¢¨²¥«¼­®, ¯®¤¯°®±²° ­±²¢® x ¢ Vn § ¤ ¥²±¿ ±¨±²¥¬®© (m k) «¨­¥©­»µ ³° ¢­¥­¨©. ‚»¡¥°¥¬ ±«³· ©­® ¥¹¥(m k) «¨­¥©­® ­¥§ ¢¨±¨¬»µ ³° ¢­¥­¨© (§ ¤ ¾¹¨µ ­¥ª®²®°®¥ k-¬¥°­®¥¯®¤¯°®±²° ­±²¢® ¢ Vn).

Ž¡º¥¤¨­¨¬ ¤¢¥ ¤ ­­»¥ ±¨±²¥¬» ³° ¢­¥­¨©. ®¢ ¿ ±¨±²¥¬ ±®¤¥°¦¨² 2(m k) ³° ¢­¥­¨©. ®±ª®«¼ª³ 2k < m, ± ½ª±¯®­¥­¶¨ «¼­® ¡«¨§ª®© ª 1 ¢¥°®¿²­®±²¼¾ ° ­£ ¤ ­­®© ±¨±²¥¬» ° ¢¥­ m(±³¡«¥¬¬ 1), ¨ ®­ ­¥ ¨¬¥¥² ­¥²°¨¢¨ «¼­»µ °¥¸¥­¨©. ²® §­ ·¨², ·²®±«³· ©­® ¢»¡° ­­®¥ ¯®¤¯°®±²° ­±²¢® ¢ Vn ± ½ª±¯®­¥­¶¨ «¼­® ¡«¨§ª®© ª1 ¢¥°®¿²­®±²¼¾ ¨¬¥¥² ­³«¥¢®¥ ¯¥°¥±¥·¥­¨¥ ± x.ˆ² ª, Ar ±®¤¥°¦¨² ¢±¥ k-¬¥°­»¥ ¯®¤¯°®±²° ­±²¢ ¨§ Vn ª°®¬¥ ½ª±¯®­¥­¶¨ «¼­® ¬ «®© ¤®«¨. Œ» §­ ¥¬, ·²® ­¥ ¬¥­¥¥ ·¥¬ ¯®«¨­®¬¨ «¼­ ¿¤®«¿ ¢±¥µ ¯®¤¯°®±²° ­±²¢ ¨§ Ar ¨¬¥¥² ±«®¦­®±²¼ ­¥ ¡®«¥¥ Dn ®²­®±¨²¥«¼­® z . ‘«¥¤®¢ ²¥«¼­®, ¨ ±°¥¤¨ ¢±¥µ k-¬¥°­»µ ¯®¤¯°®±²° ­±²¢ Vn ¯®85ª° ©­¥© ¬¥°¥ ¯®«¨­®¬¨ «¼­ ¿ ¤®«¿ ¨¬¥¥² ±«®¦­®±²¼ ­¥ ¡®«¥¥ D ®²­®±¨²¥«¼­® z . ’ ª¨¬ ®¡° §®¬, ¥±«¨ Qn { ·¨±«® ¢±¥µ k-¬¥°­»µ ¯®¤¯°®±²° ­±²¢¢ Vn, ²®Qn :2D poly(n) ¯®¬­¨¬, ·²® K (x) = log Qn + O(log n). „ «¥¥, D = K (xjz )+ O(log n) =K (x) K (z ) + O(log n).

‘«¥¤®¢ ²¥«¼­®,K (x) K (z ) K (x) O(log n):’ ª¨¬ ®¡° §®¬, K (z ) = O(log n). 286‹¨²¥° ²³° [1] ‡¢®­ª¨­ €.Š., ‹¥¢¨­ ‹.€. ‘«®¦­®±²¼ ª®­¥·­»µ ®¡º¥ª²®¢ ¨ ®¡®±­®¢ ­¨¥ ¯®­¿²¨© ¨­´®°¬ ¶¨¨ ¨ ±«³· ©­®±²¨ ± ¯®¬®¹¼¾ ²¥®°¨¨ «£®°¨²¬®¢. // “Œ. 1970. ’. 25, Â6, ‘. 85-127.[2] Š®«¬®£®°®¢ €.. ’°¨ ¯®¤µ®¤ ª ®¯°¥¤¥«¥­¨¾ ¯®­¿²¨¿ Àª®«¨·¥±²¢®¨­´®°¬ ¶¨¨Á. // °®¡«¥¬» ¯¥°¥¤ ·¨ ¨­´®°¬ ¶¨¨, 1965. ’. 1, Â1,‘.

3-11.[3] Š®«¬®£®°®¢ €.. Š «®£¨·¥±ª¨¬ ®±­®¢ ¬ ²¥®°¨¨ ¨­´®°¬ ¶¨¨ ¨ ²¥®°¨¨ ¢¥°®¿²­®±²¥©. // °®¡«¥¬» ¯¥°¥¤ ·¨ ¨­´®°¬ ¶¨¨. 1969. ’. 5,Â3, ‘. 3-7.[4] Š®«¬®£®°®¢ €.. Š®¬¡¨­ ²®°­»¥ ®±­®¢ ­¨¿ ²¥®°¨¨ ¨­´®°¨ ¶¨¨ ¨¨±·¨±«¥­¨¿ ¢¥°®¿²­®±²¥©. // “Œ. 1983. ’. 38, Â4, ‘. 27-36.[5] Œ³·­¨ª €­.€. Ž ¢»¤¥«¥­¨¨ ®¡¹¥© ¨­´®°¬ ¶¨¨ ¤¢³µ ±«®¢. // ’¥§.¤®ª«. ¥°¢®£® ‚±¥¬¨°­®£® Š®­£°¥±± Ž¡¹-¢ ¬ ²¥¬. ±² ²¨±². ¨ ²¥®°¨¨ ¢¥°®¿²­®±²¥© ¨¬. ¥°­³««¨. Œ.:  ³ª . 1986.

‘. 453.[6] —¨± ° ˆ., Š¥°­¥° Ÿ. ’¥®°¨¿ ¨­´®°¬ ¶¨¨. ’¥®°¥¬» ª®¤¨°®¢ ­¨¿ ¤«¿¤¨±ª°¥²­»µ ±¨±²¥¬ ¡¥§ ¯ ¬¿²¨. // Œ.: Œ¨°. 1985.[7] ˜¥­´¨«¤ „¦. ‘²¥¯¥­¨ ­¥° §°¥¸¨¬®±²¨. // Œ.:  ³ª . 1977.[8] ˜¨°¿¥¢ €.. ‚¥°®¿²­®±²¼. // Œ.:  ³ª . 1989.[9] Gacs P., Korner J. Common Information is Far Less Then MutualInformation. // Probl. of Control and Inform. Theory. 1973. V. 2, Â2,P.

149-162.[10] Hammer D., Shen A. A Strange Application of Kolmogorov Complexity.// Theory of Computing Systems. 1998. V. 31, P. 1-4.[11] Hammer D. Complexity inequalities. Wissenschaft & Technik Verlag,Berlin, ISBN 3{89685{479{8, 1998. 143 pp.87[12] Ingleton A.W. Representation of matroids. In: Welsh D.J.A., editor.Combinatorial Mathematics and its applications. Academic Press (London), 1971. P. 149-167.[13] Muchnik An.A. On Common Information. // Theoretical ComputerScience. 1998. V. 207, P. 319-328[14] Uspensky V.A., Shen A.

Relations between varieties of Kolmogorov complexities. // Mathematical system theory. 1996. V. 29, Â3, P. 271-292.[15] Muchnik An.A., Shen A., Romashchenko A., Vereshchagin N.K. Uppersemi-lattice of binary strings with the relation x is simple conditional toy. // Preprint DIMACS TR 97-74, Rutgers University, 1997[16] Hammer D., Romashchenko A., Shen A., Vereshchagin N.

Inequalitiesfor Shannon Entropy and Kolmogorov Complexity. // Journal of Computer and System Sciences. 2000. V. 60, P. 442-464.[17] ®¬ ¹¥­ª® €.….  °» ±«®¢ ± ­¥¬ ²¥°¨ «¨§³¥¬®© ®¡¹¥© ¨­´®°¬ ¶¨¥©. °®¡«¥¬» ¯¥°¥¤ ·¨ ¨­´®°¬ ¶¨¨. 2000. ’. 36, ‚»¯. 1, ‘. 3-20.[18] ®¬ ¹¥­ª® €.….

®«³°¥¸¥²ª ¯®±«¥¤®¢ ²¥«¼­®±²¨ ±«®¢ ± ®²­®¸¥­¨¥¬ ³±«®¢­®© ¯°®±²®²». // ‚¥±²­¨ª Œ®±ª®¢±ª®£® “­¨¢¥°±¨²¥² ,2000. °¨­¿²® ¢ ¯¥· ²¼.88.

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

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