JCSSI 6-2005 rus (Задания по FPTL), страница 3
Описание файла
Файл "JCSSI 6-2005 rus" внутри архива находится в следующих папках: Задания по FPTL, FPTL Release, Doc. PDF-файл из архива "Задания по FPTL", который расположен в категории "". Всё это находится в предмете "параллельные системы и параллельные вычисления" из 9 семестр (1 семестр магистратуры), которые можно найти в файловом архиве НИУ «МЭИ» . Не смотря на прямую связь этого архива с НИУ «МЭИ» , его также можно найти и в других разделах. Архив можно найти в разделе "остальное", в предмете "параллельные системы и параллельные вычисления" в общих файлах.
Просмотр PDF-файла онлайн
Текст 3 страницы из PDF
ÖÒÎË ˝ÎÂÏÂÌÚÓÏ ‚ÂÚ‚Ë, ‡ÒÒχÚË‚‡ÂÏÓ„Ó ‚ ͇˜ÂÒڂ Ә‰ÌÓ„ÓàáÇÖëíàü êÄç. íÖéêàü à ëàëíÖåõ ìèêÄÇãÖçàü ‹ 6 2005ŇʇÌÓ‚ Ë ‰.136τ1ττ2‡·τ1τ2**τ1→τ2→τ3‚„êËÒ. 3. ɇÙ˘ÂÒÍÓ Ô‰ÒÚ‡‚ÎÂÌË ÒÚÛÍÚÛËÓ‚‡ÌÌ˚ı îë: ‡ – ·‡ÁËÒ̇fl ÙÛÌ͈Ëfl ËÎË ÙÛÌ͈ËÓ̇θ̇fl ÔÂÂÏÂÌ̇fl,· – τ ≡ τ1 • τ2, ‚ – τ ≡ τ1 * τ2, „ – τ ≡ (τ1τ2, τ3).f2F2**f4f1→*→p*f2f5**F1êËÒ. 4. èËÏ „‡Ù˘ÂÒÍÓ„Ó Ô‰ÒÚ‡‚ÎÂÌËfl îë.͇̉ˉ‡Ú‡ ‚˚˜ËÒÎÂÌËÈ, fl‚ÎflÂÚÒfl ÙÛÌ͈ËÓ̇θ̇flÔÂÂÏÂÌ̇fl, ÚÓ ‚ÏÂÒÚÓ Ì ÔÓ‰ÒÚ‡‚ÎflÂÚÒfl  ÒÚÛÍÚÛÌÓ Ô‰ÒÚ‡‚ÎÂÌËÂ. Ç Ô˂‰ÂÌÌÓÏ ‚˚¯Â ÔËÏ ÔË ÔÓÔ˚ÚÍ ‚˚˜ËÒÎÂÌËfl Á̇˜ÂÌËfl F1 ̇ Ò‡ÏÓÈ ÌËÊÌÂÈ ‚ÂÚ‚Ë ÌÂÓ·ıÓ‰ËÏÓ Ò̇˜‡Î‡ ÔÓ‰ÒÚ‡‚ËÚ¸ ‚ÏÂÒÚÓ F1  ÒÚÛÍÚÛÌÓ Ô‰ÒÚ‡‚ÎÂÌËÂ, ‡Á‡ÚÂÏ ÔÓ‰ÓÎÊËÚ¸ ‚˚˜ËÒÎÂÌËfl, ÔÓ‰‚Ë„‡flÒ¸ ‚Ô‰ ÔÓ ˝ÚÓÏÛ Ô‰ÒÚ‡‚ÎÂÌ˲.è‡Ì˚Â-ÛÁÎ˚ ‚ ÒÚÛÍÚÛÌÓÏ Ô‰ÒÚ‡‚ÎÂÌËË Ó„‡Ì˘˂‡˛Ú ÚË ‚ÂÚ‚Ë, Ò‰Ìflfl ËÁ ÍÓÚÓ˚ı‡ÒÒÓˆËËÓ‚‡Ì‡ Ò ÌÂÓ·ıÓ‰ËÏ˚Ï ‚˚˜ËÒÎÂÌËÂÏ ÛÒÎÓ‚Ëfl ‚ ÛÒÎÓ‚ÌÓÈ ÍÓÌÒÚÛ͈ËË îë (ÒÏ.
Ô‡‚Ë·„‡Ù˘ÂÒÍÓ„Ó Ô‰ÒÚ‡‚ÎÂÌËfl ÒÚÛÍÚÛËÓ‚‡ÌÌ˚ıîë), ‡ ‰‚ ‰Û„Ë – ‚ÂıÌflfl Ë ÌËÊÌflfl – ˝ÚÓ ÛÔÂʉ‡˛˘Ë ‚˚˜ËÒÎÂÌËfl, ËÒÔÓθÁÓ‚‡ÌË ÂÁÛθڇڇÍÓÚÓ˚ı Á‡‚ËÒËÚ ÓÚ ÚÓ„Ó, fl‚ÎflÂÚÒfl ÎË ËÒÚËÌÌ˚ÏËÎË ÎÓÊÌ˚Ï Á̇˜ÂÌËÂ, ÓÔ‰ÂÎflÂÏÓ ÔË Â‡ÎËÁ‡ˆËË Ò‰ÌÂÈ ‚ÂÚ‚Ë. èÓ˝ÚÓÏÛ ÔÓÒÚÓ ÏÓ„ÛÚ ·˚Ú¸ÔÓÒÚÓÂÌ˚ ‰‚ ÒÚ‡Ú„ËË ‚˚˜ËÒÎÂÌËÈ (ÒÏ. ‡Á‰. 3):Ò ÛÔÂʉÂÌËÂÏ ËÎË ·ÂÁ ‚ Á‡‚ËÒËÏÓÒÚË ÓÚ ÚÓ„Ó, ‡Á¯‡ÂÚÒfl ËÎË ÌÂÚ ‚˚˜ËÒÎÂÌË ÔÓ ‚ÂıÌÂÈ Ë ÌËÊÌÂÈ ‚ÂÚ‚flÏ ÛÒÎÓ‚Ì˚ı ÍÓÌÒÚÛ͈ËÈ ‚ „‡Ù˘ÂÒÍÓÏ Ô‰ÒÚ‡‚ÎÂÌËË îë ‰Ó Á‡‚¯ÂÌËfl ‚˚˜ËÒÎÂ-ÌËfl ÛÒÎÓ‚Ëfl.
é˜Â‚ˉÌÓ, ˜ÚÓ Ô‡Ì˚ *-ÛÁÎ˚ÙËÍÒËÛ˛Ú ‰‚ ԇ‡ÎÎÂθÌÓ ‚˚ÔÓÎÌflÂÏ˚ı ‚ÂÚ‚Ë,ÔÓfl‰ÓÍ ÔÓ‰‚ËÊÂÌËfl ‚˚˜ËÒÎÂÌËÈ ÔÓ ÍÓÚÓ˚ÏÏÓÊÂÚ ·˚Ú¸ ÔÓËÁ‚ÓθÌ˚Ï.2. ëÚÛÍÚÛÌ˚È ‡Ì‡ÎËÁ îë. àÁ‚ÂÒÚÌ˚ ‡Á΢Ì˚ ÔÓ‰ıÓ‰˚ Ë ÏÂÚËÍË, ̇ԇ‚ÎÂÌÌ˚ ̇ ÓˆÂÌË‚‡ÌË ӄ‡ÌËÁ‡ˆËÓÌÌÓÈ ÒÎÓÊÌÓÒÚË ÔÓ„‡ÏÏ. ç‡ÔËÏÂ Û ïÓÎÒÚ‰‡ ‚ ͇˜ÂÒÚ‚Â Ô‡‡ÏÂÚÓ‚, ÓÔ‰ÂÎfl˛˘Ëı ÒÎÓÊÌÓÒÚ¸ Ó„‡ÌËÁ‡ˆËË ÔÓ„‡ÏÏ˚,ËÒÔÓθÁÛÂÚÒfl ÍÓ΢ÂÒÚ‚Ó ‚ ÌÂÈ ‡Á‚ÂÚ‚ÎÂÌËÈ, ˜ËÒÎÓ ‡Á΢Ì˚ı ·‡ÁÓ‚˚ı ÍÓÌÒÚÛ͈ËÈ flÁ˚͇ (Ú‡Í̇Á˚‚‡ÂÏ˚È ÒÎÓ‚‡¸ ÔÓ„‡ÏÏ˚) Ë Ú.Ô. é‰Ì‡ÍÓβ·ÓÏÛ ÔÓ„‡ÏÏËÒÚÛ ËÁ‚ÂÒÚÌÓ, ˜ÚÓ ÒÎÓÊÌÓÒÚ¸‡Ì‡ÎËÁ‡ ÔÓ„‡ÏÏ˚, Ú‡Í ÊÂ, Í‡Í Ë Â ‚˚˜ËÒÎËÚÂθ̇fl ÚÛ‰ÓÂÏÍÓÒÚ¸, ‚ ·Óθ¯ÓÈ ÒÚÂÔÂÌË Á‡‚ËÒflÚ ÓÚ ÍÓ΢ÂÒÚ‚‡ Ë ÔËÓ‰˚ ˆËÍ΢ÂÒÍËı Ë ÂÍÛÒË‚Ì˚ı ÍÓÌÒÚÛ͈ËÈ ‚ ÌÂÈ.
á‡ÏÂÚËÏ, ˜ÚÓ ˝ÚÓÁ‡Ï˜‡ÌË ÓÚÌÓÒËÚÒfl Í ‡Ì‡ÎËÁÛ Ì ÚÓθÍÓ ÔÓ„‡ÏÏ, ÌÓ Ë „‡ÏχÚËÍ flÁ˚ÍÓ‚ ÔÓ„‡ÏÏËÓ‚‡ÌËfl,ÚÂÍÒÚÓ‚ ̇ ÂÒÚÂÒÚ‚ÂÌÌ˚ı flÁ˚͇ı (ıÓÓ¯Ó ËÁ‚ÂÒÚ̇ÌÂÚ˂ˇθ̇fl Á‡‰‡˜‡ ‡Ì‡ÎËÁ‡ ÒËÌÚ‡ÍÒ˘ÂÒÍÓ„Ó“ÛÒÚÓÈÒÚ‚‡” ÔÓËÁ‚‰ÂÌËÈ íÓÎÒÚÓ„Ó, ÑÓÒÚÓ‚ÒÍÓ„Ó Ë ‰.).àáÇÖëíàü êÄç. íÖéêàü à ëàëíÖåõ ìèêÄÇãÖçàü ‹ 6 2005ëíêìäíìêçõâ ÄçÄãàá à èãÄçàêéÇÄçàÖ èêéñÖëëéÇçËÊ ͇ÚÍÓ ËÁÎÓÊÂÌ˚ ÓÒÌÓ‚Ì˚ ÂÁÛθڇÚ˚‡Á‡·ÓÚ‡ÌÌÓ„Ó Ì‡ÏË ÔÓ‰ıÓ‰‡ Í ‡Ì‡ÎËÁÛ ÒÚÛÍÚÛÌÓÈ ÒÎÓÊÌÓÒÚË ÙÛÌ͈ËÓ̇θÌ˚ı ÔÓ„‡ÏÏ ÔÓËı ÙÛÌ͈ËÓ̇θÌ˚Ï ÒıÂÏ‡Ï [19]. ÅÛ‰ÂÏ Ô‰ÔÓ·„‡Ú¸, ˜ÚÓ îë ‡Ì‡ÎËÁËÛÂÏÓÈ ÔÓ„‡ÏÏ˚ Ô‰ÒÚ‡‚ÎÂ̇ ‚ ‚ˉ ÒËÒÚÂÏ˚ ÙÛÌ͈ËÓ̇θÌ˚ı Û‡‚ÌÂÌËÈ (ÒÏ.
‡Á‰. 1.1)X i = τi ,i = 1, 2, …, k,(2.1)„‰Â Xi – ÙÛÌ͈ËÓ̇θÌ˚ ÔÂÂÏÂÌÌ˚Â, ‡ τi – ÚÂÏ˚, ÔÓÒÚÓÂÌÌ˚ ÔÛÚÂÏ ÔËÏÂÌÂÌËfl ÍÓ̘ÌÓ„Ó˜ËÒ· ÓÔ‡ˆËÈ ÍÓÏÔÓÁˈËË Í ‚‚‰ÂÌÌ˚Ï ÏÌÓÊÂÒÚ‚‡Ï ÙÛÌ͈ËÓ̇θÌ˚ı ÔÂÂÏÂÌÌ˚ı Ë ·‡ÁËÒÌ˚ıÙÛÌ͈ËÈ, ÔËÓ‰‡ ÍÓÚÓ˚ı Ì ËÏÂÂÚ Á̇˜ÂÌËfl ‚ÍÓÌÚÂÍÒÚ ‰‡Î¸ÌÂÈ¯Â„Ó ËÁÎÓÊÂÌËfl.èÂÂÏÂÌ̇fl Xi ÌÂÔÓÒ‰ÒÚ‚ÂÌÌÓ Á‡‚ËÒËÚ ÓÚ Xj ‚(2.1), ÂÒÎË Xj ‚ıÓ‰ËÚ ‚ ÚÂÏ τi. éÚÌÓ¯ÂÌË ÌÂÔÓÒ‰ÒÚ‚ÂÌÌÓÈ Á‡‚ËÒËÏÓÒÚË ÏÂÊ‰Û Xi Ë Xj Ó·ÓÁ̇Xj, ‡ ÏÌÓÊÂÒÚ‚Ó ÔÂÂÏÂÌÌ˚ı, ÔË̇‰˜ËÏ XiÎÂʇ˘Ëı Ú‡ÌÁËÚË‚ÌÓÏÛ Á‡Ï˚͇Ì˲ ÌÂÔÓÒ‰ÒÚ‚ÂÌÌÓÈ Á‡‚ËÒËÏÓÒÚË ‰Îfl Xi ·Û‰ÂÏ ‚˚‰ÂÎflÚ¸ Í‡Í [Xi]Ë Ì‡Á˚‚‡Ú¸ [Xi]-ÏÌÓÊÂÒÚ‚ÓÏ ËÎË Í·ÒÒÓÏ Ú‡ÌÁËÚË‚ÌÓÒÚË Xi. ÑÎfl ÔÛÒÚÓ„Ó ÏÌÓÊÂÒÚ‚‡ ‚‚‰ÂÏ ÒËÏ‚ÓÎΩ.
üÒÌÓ, ˜ÚÓ ÂÒÎË [Xi] = Ω, ÚÓ τi – ÚÂÏ-ÍÓÏÔÓÁˈËflÚÓθÍÓ ·‡ÁËÒÌ˚ı ÙÛÌ͈ËÈ.îÛÌ͈Ëfl Xi ÓÔ‰ÂÎÂ̇ ÂÍÛÒË‚ÌÓ, ÂÒÎË Xi ∈ [Xi].êÂÍÛÒË‚ÌÓ ÓÔ‰ÂÎÂÌË Xi fl‚ÎflÂÚÒfl ÔÓÒÚ˚Ï,ÂÒÎË Xi ÂÍÛÒË‚ÌÓ Ë ∀Xj ((Xj ∈ [Xi] ∧ Xi ≠ Xj ⊃ Xi ∉∉ [Xj]) ∧ Xj ∉ [Xj]).
èÓÒÚÓ ÂÍÛÒË‚ÌÓ ÓÔ‰ÂÎÂÌË Xi ̇ÁÓ‚ÂÏ ÔÓÒÚ˚Ï ˆËÍ΢ÂÒÍËÏ ÓÔ‰ÂÎÂÌËÂÏ, ÂÒÎË τi ‚ (2.1) ÏÓÊÂÚ ·˚Ú¸ Ô˂‰ÂÌÓ ‚ ˝Í‚Ë‚‡ÎÂÌÚÌÓÈ ÙÓÏÂ: τ 'i • Xi ⊕ τ ''i , „‰Â ÚÂÏ˚ τ 'i Ëτ ''i Ì ÒÓ‰ÂÊ‡Ú ‚ıÓʉÂÌËÈ ÂÍÛÒË‚ÌÓ ÓÔ‰ÂÎÂÌÌ˚ı ÙÛÌ͈ËÈ. ùÚÓÚ ‚ˉ ÓÔ‰ÂÎÂÌËfl Xi Ú‡ÍÊÂ̇Á˚‚‡˛Ú Ô‡‚ÓÒÚÓÓÌÌÂÈ ÂÍÛÒËÂÈ ËÎË ËÚ‡ÚË‚Ì˚Ï ÓÔ‰ÂÎÂÌËÂÏ. Ç ˝ÚÓÏ ÒÎÛ˜‡Â ÏÓÊÌÓ ÏËÌËχθÌÓ ¯ÂÌË ۇ‚ÌÂÌËfl ‚ˉ‡ X = τ' • Xi ⊕ τ''Ô‰ÒÚ‡‚ËÚ¸ fl‚ÌÓ, ÂÒÎË ‚ flÁ˚Í ÂÒÚ¸ ÓÔ‡ˆËfl ÍÓÏÔÓÁˈËË ÙÛÌ͈ËÈ + , ̇Á‚‡Ì̇fl ËÚ‡ˆËÂÈ [2]:τ1 + τ2 = τ2 ⊕ τ1 • τ2 ⊕ τ1 • τ1 • τ2 ⊕ … ⊕ τ 1 • τ2 ⊕ …,„‰Â τ1 ≡ τ, τk + 1 ≡ τk • τ . àÚ‡ÚË‚ÌÓ ÓÔ‰ÂÎÂÌ˽͂˂‡ÎÂÌÚÌÓ ÔÓÌflÚ˲ ˆËÍ· ‚ flÁ˚͇ı ÔÓ„‡ÏÏËÓ‚‡ÌËfl.éÔ‰ÂÎÂÌË Xi – ÔÓÒÚÓÂ, ÂÒÎË Xi Ì fl‚ÎflÂÚÒflÂÍÛÒË‚Ì˚Ï Ë [Xi] Ì ÒÓ‰ÂÊËÚ ÂÍÛÒË‚Ì˚ı ÓÔ‰ÂÎÂÌËÈ. éÔ‰ÂÎÂÌËfl Xi Ë Xj ‚Á‡ËÏÌÓ ÂÍÛÒË‚Ì˚, ÂÒÎË Xi ∈ [Xj] Ë Xj ∈ [Xi]. ã„ÍÓ ÔÓ͇Á‡Ú¸,˜ÚÓ ‚ ˝ÚÓÏ ÒÎÛ˜‡Â [Xi] ≡ [Xj].
ç‡ÁÓ‚ÂÏ Í·ÒÒÓÏ ‚Á‡ËÏÌÓÈ ÂÍÛÒË‚ÌÓÒÚË ‰Îfl Xi ÏÌÓÊÂÒÚ‚Ó ‚ÒÂı ‚Á‡ËÏÌÓ ÂÍÛÒË‚Ì˚ı Ò Xi ÓÔ‰ÂÎÂÌËÈ. ÅÛ‰ÂÏ Ó·ÓÁ̇˜‡Ú¸ Í·ÒÒ ‚Á‡ËÏÌÓÈ ÂÍÛÒË‚ÌÓÒÚË ‰Îfl Xi ˜ÂÂÁ 〈Xi〉. é˜Â‚ˉÌÓ, ˜ÚÓ ‰Îfl ‚Á‡ËÏÌÓ ÂÍÛÒË‚Ì˚ıÓÔ‰ÂÎÂÌËÈ Í·ÒÒ˚ ‚Á‡ËÏÌÓÈ ÂÍÛÒË‚ÌÓÒÚË ·Û‰ÛÚ ˝Í‚Ë‚‡ÎÂÌÚÌ˚. ã„ÍÓ ÔÓ͇Á‡Ú¸, ˜ÚÓ Ì½͂˂‡ÎÂÌÚÌ˚ Í·ÒÒ˚ ‚Á‡ËÏÌÓÈ ÂÍÛÒË‚ÌÓÒÚË Ì ÔÂÂÒÂ͇˛ÚÒfl.k137éÔ‰ÂÎÂÌË Xi ‚ÎÓÊÂÌÓ ‚ Xj, ÂÒÎË Xi ∈ [Xj], XiÒÚÓ„Ó ‚ÎÓÊÂÌÓ ‚ Xj, ÂÒÎË Xi ∈ [Xj] Ë Xj ∉ [Xi]. é˜Â‚ˉÌÓ, ‚Á‡ËÏÌÓ ÂÍÛÒË‚Ì˚ ÓÔ‰ÂÎÂÌËfl ÒÚÓ„Ó‚ÎÓÊÂÌ˚ ‰Û„ ‚ ‰Û„‡.
äÓÏ ÚÓ„Ó, ÂÒÎË 〈Xi〉 ‚ÎÓÊÂÌÓ ‚ Xj, ÚÓ Í‡Ê‰˚È ˝ÎÂÏÂÌÚ Xk ∈ 〈Xi〉 Ú‡ÍÊ ‚ÎÓÊÂÌ‚ Xj. ÖÒÎË ÓÔ‰ÂÎÂÌË Xi – ˆËÍ΢ÂÒÍÓ ÓÔ‰ÂÎÂÌË (ÔÓÒÚÓ ˆËÍ΢ÂÒÍÓ ÓÔ‰ÂÎÂÌËÂ), ÚÓ ·Û‰ÂÏÚ‡ÍÊ „Ó‚ÓËÚ¸, ˜ÚÓ Xi – ˆËÍ΢ÂÒÍÓ ‚ÎÓÊÂÌË ‚ ÓÔ‰ÂÎÂÌË Xj (ÔÓÒÚÓ ˆËÍ΢ÂÒÍÓ ‚ÎÓÊÂÌË ‚ Xj).ǂ‰ÂÏ ÓÚÌÓ¯ÂÌË ÒÚÓ„Ó„Ó ‚Íβ˜ÂÌËfl (⊂)ÏÂÊ‰Û Í·ÒÒ‡ÏË [[Xi]] ≡ [Xi] ∪ {Xi}, i = 1, 2, …, k, ÍÓÚÓÓ ÔÓÁ‚ÓÎflÂÚ Ò‡‚ÌË‚‡Ú¸ ÒÚÛÍÚÛÌÛ˛ ÒÎÓÊÌÓÒÚ¸ ÓÔ‰ÂÎÂÌËÈ ÙÛÌ͈ËÈ Xi, i = 1, 2, …, k ‚ (2.1).èË ˝ÚÓÏ ËÌÚÛËÚË‚ÌÓ flÒÌÓ, ˜ÚÓ ÂÒÎË [[Xi]] ⊂ [[Xj]],ÚÓ ÒÓ ÒÚÛÍÚÛÌÓÈ Ë ‚˚˜ËÒÎËÚÂθÌÓÈ ÚÓ˜ÂÍ ÁÂÌËfl Xi Ì ÒÎÓÊÌ Xj.ÑÎfl 〈Xi〉 = {Xi1, Xi2, …, Xin}, „‰Â Xij ∈ {X1, X2, …, Xk},[[Xi1]] = [[Xi2]] = … = [[Xin]], Ú.Â.
ÏÓÊÌÓ ÔËÌflÚ¸,˜ÚÓ ÒÚÛÍÚÛ̇fl Ë ‚˚˜ËÒÎËÚÂθ̇fl ÒÎÓÊÌÓÒÚ¸ Xi1,Xi2, … Xin ‡‚Ì˚.ç‡ÁÓ‚ÂÏ Xi Ë Xj ‚ (2.1) ÌÂÁ‡‚ËÒËÏ˚ÏË, ÂÒÎË[[Xi]] ∩ [[Xj]] = Ω.èË [[Xi]] ∩ [[Xj]] ≠ Ω ÓÔ‰ÂÎÂÌËfl Xi Ë Xj ‚ (2.1)·Û‰ÂÏ ÔÓ·„‡Ú¸ ˜‡ÒÚ˘ÌÓ Á‡‚ËÒËÏ˚ÏË ÔÓ ÔÂÂÏÂÌÌ˚Ï, ‚ıÓ‰fl˘ËÏ ‚ ÔÂÂÒ˜ÂÌË [[Xi]] ∩ [[Xj]].ǂ‰ÂÌÌÓ ÓÚÌÓ¯ÂÌË ‚Íβ˜ÂÌËfl, ‡ Ú‡ÍÊ ÓÚÌÓ¯ÂÌËfl ‡‚ÂÌÒÚ‚‡ Ë ÔÂÂÒ˜ÂÌËfl ÏÂÊ‰Û ÏÌÓÊÂÒÚ‚‡ÏË [[Xi]], i = 1, 2, …, k, ÔÓÁ‚ÓÎfl˛Ú Ò‡‚ÌË‚‡Ú¸ÔÓ ÒÚÛÍÚÛÌÓÈ Ë ‚˚˜ËÒÎËÚÂθÌÓÈ ÒÎÓÊÌÓÒÚˇÁ΢Ì˚ ÓÔ‰ÂÎÂÌËfl ÙÛÌ͈ËÈ Xi ‚ (2.1).
äÓÏÂÚÓ„Ó, ÂÍÛÒË‚Ì˚ ÓÔ‰ÂÎÂÌËfl Á‡‰‡˛Ú ÌÂÍÓÚÓ˚È ·ÓΠ‚˚ÒÓÍËÈ ÛÓ‚Â̸ ÒÚÛÍÚÛÌÓÈ Ë ‚˚˜ËÒÎËÚÂθÌÓÈ ÒÎÓÊÌÓÒÚË ÙÛÌ͈ËÈ ÔÓ Ò‡‚ÌÂÌ˲ ÒÔÓÒÚ˚ÏË ÓÔ‰ÂÎÂÌËflÏË. ùÚÓÚ Ù‡ÍÚ ËÒÔÓθÁÛÂÚÒfl ‚ ‡Á‡·ÓÚ‡ÌÌÓÏ ‡Î„ÓËÚÏ Ô·ÌËÓ‚‡ÌËfl Ô‡‡ÎÎÂθÌÓ„Ó ‚˚ÔÓÎÌÂÌËfl ÙÛÌ͈ËÓ̇θÌ˚ı ÔÓ„‡ÏÏ Ì‡ Çë (ÒÏ. ‡Á‰.
3), ‚ ÍÓÚÓÓÏ ‡Á¯ÂÌÓÚÓθÍÓ ÂÍÛÒË‚ÌÓ ÓÔ‰ÂÎÂÌÌ˚ ÙÛÌ͈ËË Ì‡Á̇˜‡Ú¸ ̇ ‡Á΢Ì˚ ÍÓÏÔ¸˛ÚÂ˚ Çë, Û‚Â΢˂‡fl Ú‡ÍËÏ Ó·‡ÁÓÏ “ÁÂÌËÒÚÓÒÚ¸” ‡ÒÔ‡‡ÎÎÂÎË‚‡ÌËfl Ë ÛÏÂ̸¯‡fl ËÌÚÂÌÒË‚ÌÓÒÚ¸ ÏÂÊÍÓÏÔ¸˛ÚÂÌ˚ıÓ·ÏÂÌÓ‚ ‚ ÔÓˆÂÒÒ ԇ‡ÎÎÂθÌÓ„Ó ‚˚ÔÓÎÌÂÌËflÙÛÌ͈ËÓ̇θÌÓÈ ÔÓ„‡ÏÏ˚.
àÁÎÓÊÂÌÌ˚È ÔÓ‰ıÓ‰ Í ‡Ì‡ÎËÁÛ ÒÚÛÍÚÛÌÓÈ ÒÎÓÊÌÓÒÚË ÙÛÌ͈ËÓ̇θÌ˚ı ÔÓ„‡ÏÏ ÔÓ Ëı îë ÏÓÊÌÓ ‡Ò¯ËËÚ¸‰Îfl ÚÓ„Ó, ˜ÚÓ·˚ ËÏÂÚ¸ ‚ÓÁÏÓÊÌÓÒÚ¸ ·ÓΠÚÓ˜ÌÓȉËÙÙÂÂ̈ˇˆËË ÔÓ ÒÎÓÊÌÓÒÚË ÓÔ‰ÂÎflÂÏ˚ı ‚ÔÓ„‡ÏÏ ÙÛÌ͈ËË.ç‡ÁÓ‚ÂÏ ÒÚÂÔÂ̸˛ ÂÍÛÒË‚ÌÓÒÚË Xi ‚ (2.1)ÒÛÏχÌÓ ÍÓ΢ÂÒÚ‚Ó ÂÍÛÒË‚Ì˚ı ÓÔ‰ÂÎÂÌËÈ‚ [[Xi]], ÔÓÎÓÊË‚  ‡‚ÌÓÈ 0, ÂÒÎË Ú‡ÍËı ÓÔ‰ÂÎÂÌËÈ ÌÂÚ.ÉÎÛ·ËÌÓÈ ÂÍÛÒË‚ÌÓÒÚË Xi Ó·ÓÁ̇˜ËÏ Ï‡ÍÒËχθÌÓ ÍÓ΢ÂÒÚ‚Ó ‚ÎÓÊÂÌÌ˚ı ‰Û„ ‚ ‰Û„‡ ÂÍÛÒË‚Ì˚ı ÓÔ‰ÂÎÂÌËÈ, ‚ıÓ‰fl˘Ëı ‚ [[Xi]].åÓÊÌÓ ÔËÌflÚ¸, ˜ÚÓ ÓÔ‰ÂÎÂÌËfl ÙÛÌ͈ËÈ,Ëϲ˘Ë ·Óθ¯Û˛ ÒÚÂÔÂ̸ ÂÍÛÒË‚ÌÓÒÚË ËÎË(Ë) „ÎÛ·ËÌ˚ ÂÍÛÒË‚ÌÓÒÚË ËϲÚ, Í‡Í Ô‡‚ËÎÓ,àáÇÖëíàü êÄç.
íÖéêàü à ëàëíÖåõ ìèêÄÇãÖçàü ‹ 6 2005ŇʇÌÓ‚ Ë ‰.138X12X2X7X3X52X42X8X9X62êËÒ. 5. ɇ٠ÌÂÔÓÒ‰ÒÚ‚ÂÌÌÓÈ Á‡‚ËÒËÏÓÒÚË.X1X7<X2><X8>X6êËÒ. 6. ɇ٠‚ÎÓÊÂÌÌÓÒÚË îë.XX<X>‡·‚êËÒ. 7. é·ÓÁ̇˜ÂÌËfl ‚¯ËÌ ‡ˆËÍ΢ÂÒÍÓ„Ó „‡Ù‡: ‡– ÌÂÂÍÛÒË‚ÌÓ ÓÔ‰ÂÎÂÌË X, · – ˆËÍ΢ÂÒÍÓÂÓÔ‰ÂÎÂÌË X, ‚ – Í·ÒÒ ‚Á‡ËÏÌÓÈ ÂÍÛÒË‚ÌÓÒÚË 〈X〉.·Óθ¯Û˛ ÒÚÛÍÚÛÌÛ˛ Ë ‚˚˜ËÒÎËÚÂθÌÛ˛ ÒÎÓÊÌÓÒÚ¸. Ä̇ÎËÁ ÒÚÛÍÚÛÌÓÈ ÒÎÓÊÌÓÒÚË ÙÛÌ͈ËÓ̇θÌ˚ı ÔÓ„‡ÏÏ ÏÓÊÌÓ Ú‡ÍÊ ‰ÓÔÓÎÌËÚ¸ ÓˆÂÌ͇ÏË ÒÚÂÔÂÌË Ëı ‡Á‚ÂÚ‚ÎÂÌÌÓÒÚË, ̇ÔËÏÂ, ÓÔ‰ÂÎflfl ÔÓ ÒÚÛÍÚÛÌÓÏÛ Ô‰ÒÚ‡‚ÎÂÌ˲ XiÓÚÌÓ¯ÂÌË ÍÓ΢ÂÒÚ‚‡ ‚ ÌÂÏ ÛÒÎÓ‚Ì˚ı ‚ÂÚ‚ÂÈ,ÍÓÚÓ˚ ÏÓ„ÛÚ ‚˚˜ËÒÎflÚ¸Òfl Ò ÛÔÂʉÂÌËÂÏ, Í Ó·˘ÂÏÛ ÍÓ΢ÂÒÚ‚Û ‚ÂÚ‚ÂÈ.
ùÚ‡ ÓˆÂÌ͇ ÔÓÁ‚ÓÎflÂÚÓˆÂÌËÚ¸ ̇ ͇˜ÂÒÚ‚ÂÌÌÓÏ ÛÓ‚Ì ‰Óβ ‚ÓÁÏÓÊÌ˚ı ÛÔÂʉ‡˛˘Ëı ‚˚˜ËÒÎÂÌËÈ ÔË Ô‡‡ÎÎÂθÌÓÏ ‚˚ÔÓÎÌÂÌËË ÔÓ„‡ÏÏ˚.Ç [19] ‡Á‡·Óڇ̇ ÔÓ„‡ÏÏ̇fl ÒËÒÚÂχ ‰Îfl‡Ì‡ÎËÁ‡ ÒÚÛÍÚÛÌÓÈ ÒÎÓÊÌÓÒÚË ÙÛÌ͈ËÓ̇θÌ˚ı ÔÓ„‡ÏÏ, „‰Â Ô‰ÛÒÏÓÚÂ̇ ‚ÓÁÏÓÊÌÓÒڸ̇„Îfl‰ÌÓ„Ó „‡Ù˘ÂÒÍÓ„Ó ÓÚÓ·‡ÊÂÌËfl ÂÁÛθڇÚÓ‚ ˝ÚÓ„Ó ‡Ì‡ÎËÁ‡. èËÏÂ, ÌËÊ fl‚ÎflÂÚÒfl ÌÂÍÓÚÓÓÈ ËÎβÒÚ‡ˆËÂÈ ‡·ÓÚ˚ ˝ÚÓÈ ÒËÒÚÂÏ˚.è Ë Ï Â 2.
èÛÒÚ¸ Á‡‰‡Ì‡ îëX1 = …X2…X7…X2;X2 = …X3…;X3 = …X4…X6…X6;X4 = …X8…X5…X8;X5 = …X2… ;X6 = …X6…;X7 = …X8…;X8 = …X8…X9…;X9 = …X8…X8.á‰ÂÒ¸ Ô‡‚˚ ˜‡ÒÚË ÓÔ‰ÂÎÂÌËfl ÙÛÌ͈ËÈX1, …, X9 Ô‰ÒÚ‡‚ÎÂÌ˚ ÚÓθÍÓ ‚ıÓʉÂÌËflÏË ‚ÌËı ÔÂÂÏÂÌÌ˚ı, ÓÚ ÍÓÚÓ˚ı ÓÌË ÌÂÔÓÒ‰ÒÚ‚ÂÌÌÓ Á‡‚ËÒflÚ. ç‡ ËÒ. 5 Ô˂‰ÂÌ „‡Ù, Óڇʇ˛˘ËÈÓÚÌÓ¯ÂÌË ÌÂÔÓÒ‰ÒÚ‚ÂÌÌÓÈ Á‡‚ËÒËÏÓÒÚË Ì‡ÏÌÓÊÂÒÚ‚Â {X1, …, X9}, Ô˘ÂÏ ÂÒÎË Xi ÌÂÔÓÒ‰ÒÚ‚ÂÌÌÓ Á‡‚ËÒËÚ ÓÚ Xj, ÚÓ Ì‡ „‡Ù ÏÂÊ‰Û ‚¯Ë̇ÏË, Ô‰ÒÚ‡‚Îfl˛˘ËÏË Xi Ë Xj, Û͇Á‡Ì‡ ̇ԇ‚Îfl˛˘‡fl Ò‚flÁ¸, ‡ ̇ Ò‚flÁË – ÍÓ΢ÂÒÚ‚Ó ‚ıÓʉÂÌËÈÒÓÓÚ‚ÂÚÒÚ‚Û˛˘ÂÈ ÔÂÂÏÂÌÌÓÈ ‚ Ô‡‚Û˛ ˜‡ÒÚ¸ ÂÂÓÔ‰ÂÎÂÌËfl (ÂÒÎË ‚ıÓʉÂÌË ‡‚ÌÓ Â‰ËÌˈÂ, ÚÓ˝ÚÓÚ Û͇Á‡ÚÂθ ÓÔÛÒ͇ÂÚÒfl).“ëÚfl„Ë‚‡ÌË” ‚ Ó‰ÌÓ ÒÓÒÚÓflÌË ‚Á‡ËÏÌÓ ÂÍÛÒË‚Ì˚ı ÓÔ‰ÂÎÂÌËÈ Ë ÔËÏÂÌÂÌË ÓÚÌÓ¯ÂÌËfl‚ÎÓÊÂÌÌÓÒÚË ÔË‚Ó‰ËÚ Í ‰Û„ÓÈ „‡Ù˘ÂÒÍÓÈ ÙÓÏÂ, Óڇʇ˛˘ÂÈ ÓÚÌÓ¯ÂÌË ‚ÎÓÊÂÌÌÓÒÚË ÏÂʉÛÓÔ‰ÂÎÂÌËflÏË ÙÛÌ͈ËÓ̇θÌÓÈ ÒıÂÏ˚ (2.1).Ç ‡ÒÒÏÓÚÂÌÌÓÈ ÒıÂÏ ËϲÚÒfl ÒÎÂ‰Û˛˘ËÂÍ·ÒÒ˚ ‚Á‡ËÏÌÓÈ ÂÍÛÒË‚ÌÓÒÚË:〈X2〉 = {X2, X3, X4, X5};〈X8〉 = {X8, X9}.ç‡ ËÒ.
6 Ô‰ÒÚ‡‚ÎÂÌ ‡ˆËÍ΢ÂÒÍËÈ „‡Ù, Óڇʇ˛˘ËÈ ÓÚÌÓ¯ÂÌËfl ‚ÎÓÊÂÌÌÓÒÚË ‰Îfl Ô‰˚‰Û˘Â„Ó ÔËχ. é·ÓÁ̇˜ÂÌËfl ‚¯ËÌ, ËÒÔÓθÁÛÂÏ˚ ÔË ˝ÚÓÏ, ÔÓ͇Á‡Ì˚ ̇ ËÒ. 7.Ç [2] ‡ÒÒχÚË‚‡Î‡Ò¸ ÔÓ·ÎÂχ ÓˆÂÌË‚‡ÌËflÒÎÓÊÌÓÒÚË Ô‡‡ÎÎÂθÌÓ„Ó ‚˚˜ËÒÎÂÌËfl ÙÛÌ͈ËÓ̇θÌ˚ı ÔÓ„‡ÏÏ ÔÓ Ëı îë, „‰Â, ‚ ˜‡ÒÚÌÓÒÚË, ÔÓÁ‡‰‡ÌÌÓÈ ‚˚˜ËÒÎËÚÂθÌÓÈ ÒÎÓÊÌÓÒÚË ·‡ÁËÒÌ˚ıÙÛÌ͈ËÈ Ë ‚ÂÓflÚÌÓÒÚË ËÒÚËÌÌÓÒÚË Ô‰Ë͇ÚÓ‚ ‚ÛÒÎÓ‚Ì˚ı ÍÓÌÒÚÛ͈Ëflı ÏÓÊÌÓ ÓÔ‰ÂÎËÚ¸ ÒÂ‰Ì˛˛ ÒÎÓÊÌÓÒÚ¸ ‚˚˜ËÒÎÂÌËfl ÙÛÌ͈ËÈ Xi, i = 1, …, k,‚ (2.1). Ç Â‡ÎËÁ‡ˆËË FPTL ̇ Í·ÒÚ‡ı ‚‚‰Â̇ÒÔˆˇθ̇fl ÔÓ‰ÒËÒÚÂχ ‚ Ò‰ ‡Á‡·ÓÚÍË ÙÛÌ͈ËÓ̇θÌ˚ı ÔÓ„‡ÏÏ, ÍÓÚÓ‡fl ÔÓÁ‚ÓÎflÂÚ ÓˆÂÌË‚‡Ú¸ ÒÚÛÍÚÛÌÛ˛ Ë ‚˚˜ËÒÎËÚÂθÌÛ˛ ÒÎÓÊÌÓÒÚ¸ÙÛÌ͈ËÓ̇θÌ˚ı ÔÓ„‡ÏÏ, ‚ ÚÓÏ ˜ËÒΠ‚ ÔÓˆÂÒÒ Ëı ‡Á‡·ÓÚÍË.3. é·˘‡fl ÒıÂχ Ó„‡ÌËÁ‡ˆËË Ë Ô·ÌËÓ‚‡ÌËflÔÓˆÂÒÒÓ‚ ‚˚ÔÓÎÌÂÌËfl ÙÛÌ͈ËÓ̇θÌ˚ı ÔÓ-àáÇÖëíàü êÄç. íÖéêàü à ëàëíÖåõ ìèêÄÇãÖçàü ‹ 6 2005ëíêìäíìêçõâ ÄçÄãàá à èãÄçàêéÇÄçàÖ èêéñÖëëéÇ„‡ÏÏ Ì‡ Çë. чΠ‡ÒÒχÚË‚‡ÂÏ ÔÓ·ÎÂÏÛ Ó„‡ÌËÁ‡ˆËË Ë Ô·ÌËÓ‚‡ÌËfl ÔÓˆÂÒÒÓ‚ Ô‡‡ÎÎÂθÌÓ„Ó ‚˚ÔÓÎÌÂÌËfl ÒÚÛÍÚÛËÓ‚‡ÌÌ˚ı ÙÛÌ͈ËÓ̇θÌ˚ı ÔÓ„‡ÏÏ (îè) ̇ Çë, ÍÓÚÓ‡fl ËÏÂÂÚ·ÓΠÔÓÒÚÓ ¯ÂÌËÂ.