Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008) (1185330), страница 55
Текст из файла (страница 55)
ᇉ‡˜‡ ‚˚fl‚ÎÂÌËfl ӯ˷ÓÍ Â¯‡ÂÚÒfl „Ó‡Á‰Ó ΄˜Â, ˜ÂÏ Á‡‰‡˜‡ËÒÔ‡‚ÎÂÌËfl ӯ˷ÓÍ, Ë ‰Îfl ӷ̇ÛÊÂÌËfl ӯ˷ÓÍ ‚ ÌÓχ ͉ËÚÌ˚ı ͇ډÓÔÓÎÌËÚÂθÌÓ ‚‚Ó‰flÚÒfl Ӊ̇ ËÎË ·ÓΠ"ÍÓÌÚÓθÌ˚ı" ˆËÙ. ëÛ˘ÂÒÚ‚Û˛Ú ‰‚‡ÓÒÌÓ‚Ì˚ı Í·ÒÒ‡ ÍÓ‰Ó‚ Ò ËÒÔ‡‚ÎÂÌËÂÏ Ó¯Ë·ÓÍ: ·ÎÓÍÓ‚˚ ÍÓ‰˚ Ë Ò‚ÂÚÓ˜Ì˚ ÍÓ‰˚.ÅÎÓÍÓ‚˚È ÍÓ‰ (ËÎË ‡‚ÌÓÏÂÌ˚È ÍÓ‰) ‰ÎËÌ˚ n ̇‰ ‡ÎÙ‡‚ËÚÓÏ , Ó·˚˜ÌÓ̇‰ ÍÓ̘Ì˚Ï ÔÓÎÂÏ q = {0,..., q – 1}, fl‚ÎflÂÚÒfl ÔÓ‰ÏÌÓÊÂÒÚ‚ÓÏ C ⊂ n; ͇ʉ˚È‚ÂÍÚÓ x ∈ C ̇Á˚‚‡ÂÚÒfl ÍÓ‰Ó‚˚Ï ÒÎÓ‚ÓÏ, M = | C | ̇Á˚‚‡ÂÚÒfl ‡ÁÏÂÓÏ ÍÓ‰‡; ‰Îfl‰‡ÌÌÓÈ ÏÂÚËÍË d ̇ qn (Ó·˚˜ÌÓ ı˝ÏÏËÌ„Ó‚ÓÈ ÏÂÚËÍË d H) Á̇˜ÂÌË d* = d* (C) == minx,y ∈ C, x ≠ yd(x, y) ̇Á˚‚‡ÂÚÒfl ÏËÌËχθÌ˚Ï ‡ÒÒÚÓflÌËÂÏ ÍÓ‰‡ ë.
ÇÂÒ w(x)ÍÓ‰Ó‚Ó„Ó ÒÎÓ‚‡ x ∈ C ÓÔ‰ÂÎflÂÚÒfl Í‡Í w(x) = d(x, 0). (n, M, d* )-ÍÓ‰ ÂÒÚ¸ q-Á̇˜Ì˚È·ÎÓÍÓ‚˚È ÍÓ‰ ‰ÎËÌ˚ n, ‡Áχ å Ë Ò ÏËÌËχθÌ˚Ï ‡ÒÒÚÓflÌËÂÏ d*. ÅË̇Ì˚ÏÍÓ‰ÓÏ Ì‡Á˚‚‡ÂÚÒfl ÍÓ‰ ̇‰ 2.äÓ„‰‡ ÍÓ‰Ó‚˚ ÒÎÓ‚‡ ‚˚·Ë‡˛ÚÒfl Ú‡ÍËÏ Ó·‡ÁÓÏ, ˜ÚÓ·˚ ‡ÒÒÚÓflÌË ÏÂʉÛÌËÏË ·˚ÎÓ Ï‡ÍÒËχθÌ˚Ï, ÍÓ‰ ̇Á˚‚‡ÂÚÒfl ÍÓ‰ÓÏ Ò ËÒÔ‡‚ÎÂÌËÂÏ Ó¯Ë·ÓÍ, ÔÓÒÍÓθÍÛ ÌÂÁ̇˜ËÚÂθÌÓ ËÒ͇ÊÂÌÌ˚ ‚ÂÍÚÓ˚ ÏÓ„ÛÚ ·˚Ú¸ ‚ÓÒÒÚ‡ÌÓ‚ÎÂÌ˚ ÔÛÚÂÏ‚˚·Ó‡ ·ÎËÊ‡È¯Â„Ó ÍÓ‰Ó‚Ó„Ó ÒÎÓ‚‡. äÓ‰ ë fl‚ÎflÂÚÒfl ÍÓ‰ÓÏ Ò ËÒÔ‡‚ÎÂÌËÂÏ tӯ˷ÓÍ (Ë ÍÓ‰ÓÏ Ò Ó·Ì‡ÛÊÂÌËÂÏ 2t ӯ˷ÓÍ), ÂÒÎË d* (C) ≥ 2t + 1.
Ç ˝ÚÓÏ ÒÎÛ˜‡Â͇ʉ‡fl ÓÍÂÒÚÌÓÒÚ¸ Ut(x) = {y ∈ C: d(x, y) ≤ t} ÚÓ˜ÍË x ∈ C Ì ÔÂÂÒÂ͇ÂÚÒfl Ò Ut(y)‰Îfl β·ÓÈ ÚÓ˜ÍË y ∈ C, y ≠ x. ëӂ¯ÂÌÌ˚È ÍÓ‰ – ˝ÚÓ q-Á̇˜Ì˚È (n, M, 2t + 1)-ÍÓ‰,É·‚‡ 16. ê‡ÒÒÚÓflÌËfl ‚ ÚÂÓËË ÍÓ‰ËÓ‚‡ÌËfl245‰Îfl ÍÓÚÓÓ„Ó å ÒÙ U t(x) Ò ‡‰ËÛÒÓÏ t Ë ˆÂÌÚ‡ÏË ‚ ÍÓ‰Ó‚˚ı ÒÎÓ‚‡ı Á‡ÔÓÎÌfl˛ÚÔÓÎÌÓÒÚ¸˛ ‚Ò ÔÓÒÚ‡ÌÒÚ‚Ó Fqn ·ÂÁ ÔÂÂÒ˜ÂÌËÈ.ÅÎÓÍÓ‚˚È ÍÓ‰ C ⊂ Fqn ̇Á˚‚‡ÂÚÒfl ÎËÌÂÈÌ˚Ï, ÂÒÎË ë fl‚ÎflÂÚÒfl ‚ÂÍÚÓÌ˚Ï ÔÓ‰ÔÓÒÚ‡ÌÒÚ‚ÓÏ ÔÓÒÚ‡ÌÒÚ‚‡ Fqn .
[n, k]-ÍÓ‰ ÂÒÚ¸ k-ÏÂÌ˚È ÎËÌÂÈÌ˚È ÍÓ‰ C ⊂ Fqn(Ò ÏËÌËχθÌ˚Ï ‡ÒÒÚÓflÌËÂÏ d* ); ÓÌ ËÏÂÂÚ ‡ÁÏ qk, Ú.Â. fl‚ÎflÂÚÒfl (n, qk, d* )-ÍÓ‰ÓÏ. qr − 1 qr − 1,äÓ‰ÓÏ ï˝ÏÏËÌ„‡ ̇Á˚‚‡ÂÚÒfl ÎËÌÂÈÌ˚È Òӂ¯ÂÌÌ˚È − r, 3 -ÍÓ‰ Ò11q−q−ËÒÔ‡‚ÎÂÌËÂÏ Ó‰ÌÓÈ Ó¯Ë·ÍË.k × n å‡Úˈ‡ G ÒÓ ÒÚÓ͇ÏË, fl‚Îfl˛˘ËÏËÒfl ·‡ÁËÒÌ˚ÏË ‚ÂÍÚÓ‡ÏË ‰Îfl ÎËÌÂÈÌÓ„Ó [n, k]-ÍÓ‰‡ ë, ̇Á˚‚‡ÂÚÒfl ÔÓÓʉ‡˛˘ÂÈ Ï‡ÚˈÂÈ ÍÓ‰‡ C . Ç Òڇ̉‡ÚÌÓςˉ Â ÏÓÊÌÓ Á‡ÔËÒ‡Ú¸ Í‡Í (1k|A), „‰Â 1k ÂÒÚ¸ k × k ‰ËÌ˘̇fl χÚˈ‡. ä‡Ê‰ÓÂÒÓÓ·˘ÂÌË (ËÎË ËÌÙÓχˆËÓÌÌ˚È ÒËÏ‚ÓÎ, ÒËÏ‚ÓÎ ËÒÚÓ˜ÌË͇) u = (u1 ,..., uk ) ∈ FqnÏÓÊÂÚ ·˚Ú¸ Á‡ÍÓ‰ËÓ‚‡Ì ÔÛÚÂÏ ÛÏÌÓÊÂÌËfl Â„Ó (ÒÔ‡‚‡) ̇ ÔÓÓʉ‡˛˘Û˛ χÚˈÛ:uG ∈ C.
å‡Úˈ‡ H = (–AT|1n–k) ̇Á˚‚‡ÂÚÒfl χÚˈÂÈ ÔÓ‚ÂÍË Ì‡ ÔÓ˜ÌÓÒÚ¸ ÍÓ‰‡ë. óËÒÎÓ r = n – k ÒÓÓÚ‚ÂÚÒÚ‚ÛÂÚ ÍÓ΢ÂÒÚ‚Û ˆËÙ ÔÓ‚ÂÍË Ì‡ ˜ÂÚÌÓÒÚ¸ ‚ ÍӉ Ë̇Á˚‚‡ÂÚÒfl ËÁ·˚ÚÓ˜ÌÓÒÚ¸˛ ÍÓ‰‡ ë. àÌÙÓχˆËÓÌ̇fl ÒÍÓÓÒÚ¸ (ËÎË ÍÓ‰Ó‚‡fllog 2 MkÒÍÓÓÒÚ¸) ÍÓ‰‡ ë – ˝ÚÓ ˜ËÒÎÓ R =. ÑÎfl q-Á̇˜ÌÓ„Ó [n, k]-ÍÓ‰‡ R = log 2 q;nnk‰Îfl ·Ë̇ÌÓ„Ó [n, k]-ÍÓ‰‡ R = .në‚ÂÚÓ˜Ì˚È ÍÓ‰ – Ú‡ÍÓÈ ÚËÔ ÍÓ‰‡ Ò ËÒÔ‡‚ÎÂÌËÂÏ Ó¯Ë·ÓÍ, ‚ ÍÓÚÓÓÏ ÔÓ‰ÎÂʇ˘ËÈ ÍÓ‰ËÓ‚‡Ì˲ k-·ËÚÓ‚ ËÌÙÓχˆËÓÌÌ˚È ÒËÏ‚ÓÎ ÔÂÓ·‡ÁÛÂÚÒfl ‚ n-·ËÚÓ‚ÓÂkÍÓ‰Ó‚Ó ÒÎÓ‚Ó, „‰Â R = – ÍÓ‰Ó‚‡fl ÒÍÓÓÒÚ¸ (n ≥ k), ‡ ÔÂÓ·‡ÁÓ‚‡ÌË fl‚ÎflÂÚÒflnÙÛÌ͈ËÂÈ ÔÓÒΉÌËı m ËÌÙÓχˆËÓÌÌ˚ı ÒËÏ‚ÓÎÓ‚, „‰Â m – ‰ÎË̇ ÍÓ‰Ó‚Ó„Ó Ó„‡Ì˘ÂÌËfl.
ë‚ÂÚÓ˜Ì˚ ÍÓ‰˚ ˜‡ÒÚÓ ËÒÔÓθÁÛ˛ÚÒfl ‰Îfl ÔÓ‚˚¯ÂÌËfl ͇˜ÂÒÚ‚‡ ‡‰ËÓ ËÒÔÛÚÌËÍÓ‚˚ı ÎËÌËÈ Ò‚flÁË. äÓ‰ ÔÂÂÏÂÌÌÓÈ ‰ÎËÌ˚ – ÍÓ‰ Ò ÍÓ‰Ó‚˚ÏË ÒÎÓ‚‡ÏˇÁ΢ÌÓÈ ‰ÎËÌ˚.Ç ÓÚ΢ˠÓÚ ÍÓ‰Ó‚ Ò ‡‚ÚÓχÚ˘ÂÒÍËÏ ËÒÔ‡‚ÎÂÌËÂÏ Ó¯Ë·ÓÍ, ÍÓÚÓ˚ Ô‰̇Á̇˜ÂÌ˚ ÚÓθÍÓ ‰Îfl ÔÓ‚˚¯ÂÌËfl ̇‰ÂÊÌÓÒÚË Ô‰‡˜Ë ‰‡ÌÌ˚ı, ÍËÔÚÓ„‡Ù˘ÂÒÍËÂÍÓ‰˚ Ô‰̇Á̇˜ÂÌ˚ ‰Îfl ÔÓ‚˚¯ÂÌËfl Á‡˘Ë˘ÂÌÌÓÒÚË ÎËÌËÈ Ò‚flÁË. Ç ÍËÔÚÓ„‡ÙËËÓÚÔ‡‚ËÚÂθ ËÒÔÓθÁÛÂÚ Íβ˜ ‰Îfl ¯ËÙÓ‚‡ÌËfl ÒÓÓ·˘ÂÌËfl ‰Ó Â„Ó Ô‰‡˜Ë ÔÓÌÂÁ‡˘Ë˘ÂÌÌ˚Ï Í‡Ì‡Î‡Ï Ò‚flÁË, ‡ ‡‚ÚÓËÁÓ‚‡ÌÌ˚È ÔÓÎÛ˜‡ÚÂθ ̇ ‰Û„ÓÏ ÍÓ̈ÂËÒÔÓθÁÛÂÚ Íβ˜ ‰Îfl ‡Ò¯ËÙÓ‚ÍË ÔÓÎÛ˜ÂÌÌÓ„Ó ÒÓÓ·˘ÂÌËfl.
ó‡˘Â ‚ÒÂ„Ó ‡Î„ÓËÚÏ˚ ÒʇÚËfl Ë ÍÓ‰˚ Ò ËÒÔ‡‚ÎÂÌËÂÏ Ó¯Ë·ÓÍ ËÒÔÓθÁÛ˛ÚÒfl ÒÓ‚ÏÂÒÚÌÓ Ò ÍËÔÚÓ„‡Ù˘ÂÒÍËÏË ÍÓ‰‡ÏË, ˜ÚÓ Ó·ÂÒÔ˜˂‡ÂÚ Ó‰ÌÓ‚ÂÏÂÌÌÓ ˝ÙÙÂÍÚË‚ÌÛ˛ Ë Ì‡‰ÂÊÌÛ˛Ò‚flÁ¸ ·ÂÁ ӯ˷ÓÍ Ô‰‡˜Ë ‰‡ÌÌ˚ı Ë Á‡˘ËÚÛ ‰‡ÌÌ˚ı ÓÚ ÌÂÒ‡Ì͈ËÓÌËÓ‚‡ÌÌÓ„Ó‰ÓÒÚÛÔ‡. ᇯËÙÓ‚‡ÌÌ˚ ÒÓÓ·˘ÂÌËfl, ÍÓÚÓ˚Â, ·ÓΠÚÓ„Ó, ÏÓ„ÛÚ ·˚Ú¸ ÒÍ˚Ú˚ ‚ÚÂÍÒÚÂ, ËÁÓ·‡ÊÂÌËË Ë Ú.Ô., ̇Á˚‚‡˛ÚÒfl ÒÚ„‡ÌÓ„‡Ù˘ÂÒÍËÏË ÒÓÓ·˘ÂÌËflÏË.16.1.
åàçàåÄãúçéÖ êÄëëíéüçàÖ à ÖÉé ÄçÄãéÉàåËÌËχθÌÓ ‡ÒÒÚÓflÌËÂÑÎfl ÍÓ‰‡ ë ⊂ V, „‰Â V – n-ÏÂÌÓ ‚ÂÍÚÓÌÓ ÔÓÒÚ‡ÌÒÚ‚Ó, Ò̇·ÊÂÌÌÓ ÏÂÚËÍÓÈd, ÏËÌËχθÌÓ ‡ÒÒÚÓflÌË d* = d* (C) ÍÓ‰‡ ë ÓÔ‰ÂÎflÂÚÒfl ͇Ímin d ( x, y).x , y ∈C , x ≠ y246ó‡ÒÚ¸ IV. ê‡ÒÒÚÓflÌËfl ‚ ÔËÍ·‰ÌÓÈ Ï‡ÚÂχÚËÍÂåÂÚË͇ d Á‡‚ËÒËÚ ÓÚ ÔËÓ‰˚ ÔÓ‰ÎÂʇ˘Ëı ËÒÔ‡‚ÎÂÌ˲ ӯ˷ÓÍ ‚ÒÓÓÚ‚ÂÚÒÚ‚ËË Ò Ô‰̇Á̇˜ÂÌËÂÏ ÍÓ‰‡. ÑÎfl Ó·ÂÒÔ˜ÂÌËfl Ú·ÛÂÏ˚ı ı‡‡ÍÚÂËÒÚËÍÔÓ ÍÓÂÍÚËÓ‚Í ÌÂÓ·ıÓ‰ËÏÓ ÔËÏÂÌflÚ¸ ÍÓ‰˚ Ò Ï‡ÍÒËχθÌ˚Ï ÍÓ΢ÂÒÚ‚ÓÏÍÓ‰Ó‚˚ı ÒÎÓ‚. ç‡Ë·ÓΠ¯ËÓÍÓ ËÒÒΉӂ‡ÌÌ˚ÏË ‚ ˝ÚÓÏ Ô·Ì ÍÓ‰‡ÏË fl‚Îfl˛ÚÒflq-Á̇˜Ì˚ ·ÎÓÍÓ‚˚ ÍÓ‰˚ ‚ ı˝ÏÏËÌ„Ó‚ÓÈ ÏÂÚËÍ d H ( x, y) =| {i : xi ≠ yi , i = 1,..., n} | .ÑÎfl ÎËÌÂÈÌ˚ı ÍÓ‰Ó‚ ë ÏËÌËχθÌÓ ‡ÒÒÚÓflÌË d* (C) = w (C), „‰Â w (C) == min{w(x): x ∈ C}, ̇Á˚‚‡ÂÚÒfl ÏËÌËχθÌ˚Ï ‚ÂÒÓÏ ÍÓ‰‡ C. èÓÒÍÓθÍÛ Ï‡Úˈ‡ HχÚˈ‡ ÔÓ‚ÂÂ̇ ˜ÂÒÚÌÓÒÚ¸ [n, k]-ÍÓ‰‡ ë ËÏÂÂÚ rank(H ) ≤ n – k ÌÂÁ‡‚ËÒËÏ˚ıÒÚÓηˆÓ‚, ÚÓ d* (C) ≤ n – k + 1 (‚ÂıÌflfl „‡Ìˈ‡ ëËÌ„ÎÚÓ̇).Ñ‚ÓÈÒÚ‚ÂÌÌÓ ‡ÒÒÚÓflÌËÂÑ‚ÓÈÒÚ‚ÂÌÌÓ ‡ÒÒÚÓflÌË d⊥ ÎËÌÂÈÌÓ„Ó [n, k]-ÍÓ‰‡ C ⊂ qn fl‚ÎflÂÚÒfl ÏËÌËχθÌ˚Ï ‡ÒÒÚÓflÌËÂÏ ‰‚ÓÈÒÚ‚ÂÌÌÓ„Ó ÍÓ‰‡ C⊥ ‰Îfl ë.Ñ‚ÓÈÒÚ‚ÂÌÌ˚È ÍÓ‰ C⊥ ‰Îfl ÍÓ‰‡ ë ÓÔ‰ÂÎflÂÚÒfl Í‡Í ÏÌÓÊÂÒÚ‚Ó ‚ÒÂı ‚ÂÍÚÓÓ‚nq , ÓÚÓ„Ó̇θÌ˚ı ͇ʉÓÏÛ ÍÓ‰Ó‚ÓÏÛ ÒÎÓ‚Û ËÁ ë: C ⊥ = {v ∈qn : 〈 v, u 〉 = 0 ‰Îflβ·Ó„Ó u ∈ C}.
äÓ‰ C ⊥ fl‚ÎflÂÚÒfl ÎËÌÂÈÌ˚Ï [n, n – k]-ÍÓ‰ÓÏ. (n – k) × n ÔÓÓʉ‡˛˘‡flχÚˈ‡ ‰Îfl C ⊥ fl‚ÎflÂÚÒfl χÚˈÂÈ ÔÓ‚ÂÍË Ì‡ ˜ÂÚÌÓÒÚ¸ ‰Îfl ë.ê‡ÒÒÚÓflÌË ‚ar-ÔÓËÁ‚‰ÂÌËflÑÎfl ÎËÌÂÈÌ˚ı ÍÓ‰Ó‚ ë1 Ë ë2 , Ëϲ˘Ëı ‰ÎËÌÛ n Ò C 2 ⊂ C1 , Ëı bar-ÔÓËÁ‚‰ÂÌËÂC 1 |C 2 ÂÒÚ¸ ÎËÌÂÈÌ˚È ÍÓ‰ ‰ÎËÌ˚ 2n, ÓÔ‰ÂÎÂÌÌ˚È Í‡Í C1 | C2 = {x | x + y : x ∈ C1 ,y ∈ C2}.ê‡ÒÒÚÓflÌË bar-ÔÓËÁ‚‰ÂÌËfl – ÏËÌËχθÌÓ ‡ÒÒÚÓflÌË d * (C 1 |C 2 ) bar-ÔÓËÁ‚‰ÂÌËfl C1 | C2 .ê‡ÒÒÚÓflÌË ‰ËÁ‡È̇ãËÌÂÈÌ˚È ÍÓ‰ ̇Á˚‚‡ÂÚÒfl ˆËÍ΢ÂÒÍËÏ ÍÓ‰ÓÏ, ÂÒÎË ‚Ò ˆËÍ΢ÂÒÍË ҉‚Ë„ËÍÓ‰Ó‚Ó„Ó ÒÎÓ‚‡ Ú‡ÍÊ ÔË̇‰ÎÂÊ‡Ú ë, Ú.Â.
ÂÒÎË ‰Îfl β·Ó„Ó (a0 ,...., an–1 ) ∈ C ‚ÂÍÚÓ(an– 1 , a0 ,..., an– 2 ) ∈ C . ì‰Ó·ÌÓ ÓÚÓʉÂÒÚ‚ÎflÚ¸ ÍÓ‰Ó‚Ó ÒÎÓ‚Ó (a 0 ,..., an– 1 ) ÒÏÌÓ„Ó˜ÎÂÌÓÏ c( x ) = a0 + a1 x + ... + an −1 x n −1 , ÚÓ„‰‡ ͇ʉ˚È ˆËÍ΢ÂÒÍËÈ [n, k]-ÍÓ‰ÏÓÊÂÚ ·˚Ú¸ Ô‰ÒÚ‡‚ÎÂÌ Í‡Í „·‚Ì˚È Ë‰Â‡Î 〈 g( x )〉 = {r ( x )g( x ) : r ( x ) ∈ Rn} ÍÓθˆ‡Rn = q ( x ) /( x n − 1), ÔÓÓʉÂÌÌ˚È ÏÌÓ„Ó˜ÎÂÌÓÏ g( x ) = g0 + g1 x + ...
+ x n − k , ̇Á˚‚‡ÂÏ˚Ï ÔÓÓʉ‡˛˘ËÏ ÏÌÓ„Ó˜ÎÂÌÓÏ ÍÓ‰‡ ë.ÑÎfl ˝ÎÂÏÂÌÚ‡ α ÔÓfl‰Í‡ n ‚ ÍÓ̘ÌÓÏ ÔÓΠq s [n, k]-ÍÓ‰ ÅÓÁ–óÓ‰ıÛË–ïÓÍ‚ÂÌ„Âχ, Ëϲ˘ËÈ ‡ÒÒÚÓflÌË ‰ËÁ‡È̇ d, fl‚ÎflÂÚÒfl ˆËÍ΢ÂÒÍËÏ ÍÓ‰ÓÏ ‰ÎËÌ˚ n,ÔÓÓʉÂÌÌ˚Ï ÏÌÓ„Ó˜ÎÂÌÓÏ g(x) ‚ q ( x ) ÒÚÂÔÂÌË n – k, Ëϲ˘ËÏ ÍÓÌËα , α2,..., αd–1. åËÌËχθÌÓ ‡ÒÒÚÓflÌË d* ÍÓ‰‡ ÅÓÁ–óÓ‰ıÛË–ïÓÍ‚ÂÌ„Âχ Ò̘ÂÚÌ˚Ï ‡ÒÒÚÓflÌËÂÏ ‰ËÁ‡È̇ d ·Óθ¯Â ËÎË ‡‚ÌÓ d.äÓ‰ êˉ‡–ëÓÎÓÏÓ̇ – ˝ÚÓ ÍÓ‰ ÅÓÁ–óÓ‰ıÛË–ïÓÍ‚ÂÌ„Âχ Ò s = 1. èÓÓʉ‡˛˘ËÏ ÏÌÓ„Ó˜ÎÂÌÓÏ ÍÓ‰‡ êˉ‡–ëÓÎÓÏÓ̇ Ò ‡ÒÒÚÓflÌËÂÏ ‰ËÁ‡È̇ d fl‚ÎflÂÚÒflÏÌÓ„Ó˜ÎÂÌ g( x ) = ( x − α )...( x − α d −1 ) ÒÚÂÔÂÌË n – k = d – 1, Ú.Â. ‰Îfl ÍÓ‰‡ êˉ‡–ëÓÎÓÏÓ̇ ‡ÒÒÚÓflÌË ‰ËÁ‡È̇ d = n – k + 1 Ë ÏËÌËχθÌÓ ‡ÒÒÚÓflÌË d* ≥ d .èÓÒÍÓθÍÛ ‰Îfl ÎËÌÂÈÌÓ„Ó [n, k]-ÍÓ‰‡ ÏËÌËχθÌÓ ‡ÒÒÚÓflÌË d * ≤ n – k + 1(‚ÂıÌflfl „‡Ìˈ‡ ëËÌ„ÎÚÓ̇), ÍÓ‰ êˉ‡–ëÓÎÓÏÓ̇ ӷ·‰‡ÂÚ ÏËÌËχθÌ˚χÒÒÚÓflÌËÂÏ d* = n – k + 1 Ë ‰ÓÒÚË„‡ÂÚ ‚ÂıÌÂÈ „‡Ìˈ˚ ëËÌ„ÎÚÓ̇.
Ç ÔÓË„˚‚‡ÚÂÎflı ÍÓÏÔ‡ÍÚ-‰ËÒÍÓ‚ ÔÂËÏÛ˘ÂÒÚ‚ÂÌÌÓ ËÒÔÓθÁÛÂÚÒfl ÒËÒÚÂχ ‰‚ÓÈÌÓÈ ÍÓÂ͈ËË Ó¯Ë·ÓÍ (255, 251,5) ÍÓ‰‡ êˉ‡–ëÓÎÓÏÓ̇ ̇‰ ÔÓÎÂÏ 256 .É·‚‡ 16. ê‡ÒÒÚÓflÌËfl ‚ ÚÂÓËË ÍÓ‰ËÓ‚‡ÌËfl247ê‡Ò˜ÂÚÌÓ ÏËÌËχθÌÓ ‡ÒÒÚÓflÌË ÉÓÔÔ˚ê‡Ò˜ÂÚÌÓ ÏËÌËχθÌÓ ‡ÒÒÚÓflÌË ÉÓÔÔ˚ ([Gopp71]) – ÌËÊÌflfl „‡Ìˈ‡ d* (m)‰Îfl ÏËÌËχθÌÓ„Ó ‡ÒÒÚÓflÌËfl Ó‰ÌÓÚӘ˜Ì˚ı „ÂÓÏÂÚ˘ÂÒÍËı ÍÓ‰Ó‚ ÉÓÔÔ˚ (ËÎËÍÓ‰Ó‚ ‡Î„·‡Ë˜ÂÒÍÓÈ „ÂÓÏÂÚËË) G(m ). ÑÎfl ÍÓ‰‡ G(m), ‡ÒÒÓˆËËÓ‚‡ÌÌÓ„Ó Ò‰ÂÎËÚÂÎflÏË D Ë mP, m ∈ „·‰ÍÓÈ ÔÓÂÍÚË‚ÌÓÈ ‡·ÒÓβÚÌÓ ÌÂÔË‚Ó‰ËÏÓȇ΄·‡Ë˜ÂÒÍÓÈ ÍË‚ÓÈ Ó‰‡ g > 0 ̇‰ ÍÓ̘Ì˚Ï ÔÓÎÂÏ q , Ï˚ ËÏÂÂÏ ‡‚ÂÌÒÚ‚Ód* (m) = m + 2 – 2g, ÂÒÎË 2g – 2 < m < n.ÑÎfl ÍÓ‰‡ ÉÓÔÔ˚ ë(m) ÒÚÛÍÚÛ‡ ÔÓÒΉӂ‡ÚÂθÌÓÒÚË ÔÓÔÛÒÍÓ‚ ‚ ê ÏÓÊÂÚÔÓÁ‚ÓÎËÚ¸ ÔÓÎÛ˜ËÚ¸ ·ÓΠÚÓ˜ÌÛ˛ ÌËÊÌ˛˛ „‡ÌËˆÛ ÏËÌËχθÌÓ„Ó ‡ÒÒÚÓflÌËfl(ÒÏ. ‡ÒÒÚÓflÌË îÂÌ„‡-ê‡Ó).ê‡ÒÒÚÓflÌË îÂÌ„‡–ê‡Óê‡ÒÒÚÓflÌË îÂÌ„‡-ê‡Ó δ FR (m) – ÌËÊÌflfl „‡Ìˈ‡ ‰Îfl ÏËÌËχθÌÓ„Ó ‡ÒÒÚÓflÌËflÓ‰ÌÓÚӘ˜Ì˚ı „ÂÓÏÂÚ˘ÂÒÍËı ÍÓ‰Ó‚ ÉÓÔÔ˚ G(m), ÍÓÚÓÓ ÎÛ˜¯Â ‡Ò˜ÂÚÌÓ„ÓÏËÌËχθÌÓ„Ó ‡ÒÒÚÓflÌËfl ÉÓÔÔ˚.
àÒÔÓθÁÛÂÏ˚È ÏÂÚÓ‰ ÍÓ‰ËÓ‚‡ÌËfl îÂÌ„‡–ê‡Ó‰Îfl ÍÓ‰‡ ë(m) ‰ÂÍÓ‰ËÛÂÚ Ó¯Ë·ÍË ‰Ó ÔÓÎÓ‚ËÌ˚ ‡ÒÒÚÓflÌËfl îÂÌ„‡–ê‡Ó δFR(m) ËÛ‚Â΢˂‡ÂÚ ‚ÓÁÏÓÊÌÓÒÚË ÔÓ ËÒÔ‡‚ÎÂÌ˲ ӯ˷ÓÍ ‰Îfl Ó‰ÌÓÚӘ˜Ì˚ı „ÂÓÏÂÚ˘ÂÒÍËı ÍÓ‰Ó‚ ÉÓÔÔ˚.îÓχθÌÓ ‡ÒÒÚÓflÌË îÂÌ„‡–ê‡Ó ÓÔ‰ÂÎflÂÚÒfl ÒÎÂ‰Û˛˘ËÏ Ó·‡ÁÓÏ. èÛÒÚ¸ S·Û‰ÂÚ ˜ËÒÎÓ‚‡fl ÔÓÎÛ„ÛÔÔ‡, Ú.Â. ÔÓ‰ÔÓÎÛ„ÛÔÔ‡ S ÔÓÎÛ„ÛÔÔ˚ ∪ {0}, ڇ͇fl ˜ÚÓÓ‰ g =| ∪ {0} \ S | ÔÓÎÛ„ÛÔÔ˚ S fl‚ÎflÂÚÒfl ÍÓ̘Ì˚Ï, Ë 0 ∈ S. ê‡ÒÒÚÓflÌË îÂÌ„‡–ê‡Ó ̇ S ÂÒÚ¸ ÙÛÌ͈Ëfl δ FR : S → ∪ {0}, ڇ͇fl ˜ÚÓ δ FR ( m) = min{ν(r ) : r ≥ m, r ∈ S},„‰Â ν(r ) =| {( a, b) ∈ S 2 : a + b = r} | .
é·Ó·˘ÂÌÌÓ r- ‡ÒÒÚÓflÌË îÂÌ„‡–ê‡Ó ̇ S ÓÔ‰ÂÎflÂÚÒfl Í‡Í δ rFR ( m) = min{ν[ m1 ,..., mr ] : m ≤ m1 < ... < mr , mi ∈ S}, „‰Â ν[ m1 ,..., mr ] == | {a ∈ S : mi − a ∈ S ‰Îfl ÌÂÍÓÚÓÓ„Ó i = 1,..., r}|. íÓ„‰‡ ËÏÂÂÏ δ FR ( m) = δ1FR ( m)(ÒÏ., ̇ÔËÏÂ, [FaMu03]).ë‚Ó·Ó‰ÌÓ ‡ÒÒÚÓflÌËÂë‚Ó·Ó‰ÌÓ ‡ÒÒÚÓflÌË – ÏËÌËχθÌ˚È ÌÂÌÛ΂ÓÈ ‚ÂÒ ï˝ÏÏËÌ„‡ β·Ó„Ó ÍÓ‰Ó‚Ó„Ó ÒÎÓ‚‡ ‚ Ò‚ÂÚÓ˜ÌÓÏ ÍӉ ËÎË ÍӉ ÔÂÂÏÂÌÌÓÈ ‰ÎËÌ˚.îÓχθÌÓ, k- ÏËÌËχθÌÓ ‡ÒÒÚÓflÌË dk∗ Ò‚ÂÚÓ˜ÌÓ„Ó ÍÓ‰‡ ËÎË ÍÓ‰‡ ÔÂÂÏÂÌÌÓÈ ‰ÎËÌ˚ ÂÒÚ¸ ̇ËÏÂ̸¯Â ı˝ÏÏËÌ„Ó‚Ó ‡ÒÒÚÓflÌË ÏÂÊ‰Û Ì‡˜‡Î¸Ì˚ÏË ÓÚÂÁ͇ÏË ‰ÎËÌ˚ k β·˚ı ‰‚Ûı ÍÓ‰Ó‚˚ı ÒÎÓ‚, ÍÓÚÓ˚ ‡Á΢‡˛ÚÒfl ̇ ‰‡ÌÌ˚ı̇˜‡Î¸Ì˚ı ÓÚÂÁ͇ı.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
