JCSSI 6-2005 rus (Задания по FPTL)
Описание файла
Файл "JCSSI 6-2005 rus" внутри архива находится в следующих папках: Задания по FPTL, FPTL Release, Doc. PDF-файл из архива "Задания по FPTL", который расположен в категории "". Всё это находится в предмете "параллельные системы и параллельные вычисления" из 9 семестр (1 семестр магистратуры), которые можно найти в файловом архиве НИУ «МЭИ» . Не смотря на прямую связь этого архива с НИУ «МЭИ» , его также можно найти и в других разделах. Архив можно найти в разделе "остальное", в предмете "параллельные системы и параллельные вычисления" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
àáÇÖëíàü êÄç. íÖéêàü à ëàëíÖåõ ìèêÄÇãÖçàü, 2005, ‹ 6, Ò. 131–146ÍÓÏÔ¸˛ÚÂÌ˚ÂÏÂÚÓ‰˚ìÑä 681.51ëíêìäíìêçõâ ÄçÄãàá à èãÄçàêéÇÄçàÖ èêéñÖëëéÇèÄêÄããÖãúçéÉé ÇõèéãçÖçàüîìçäñàéçÄãúçõï èêéÉêÄåå*© 2005 „. ë. Ö. ŇʇÌÓ‚, Ç. è. äÛÚÂÔÓ‚, Ñ. Ä. òÂÒÚ‡ÍÓ‚åÓÒÍ‚‡, åùà (ÚÂıÌ˘ÂÒÍËÈ ÛÌ-Ú)èÓÒÚÛÔË· ‚ ‰‡ÍˆË˛ 07.06.05 „.éÔËÒ‡Ì˚ ÓË„Ë̇θÌ˚ ‡Î„ÓËÚÏ˚ Ô·ÌËÓ‚‡ÌËfl ÔÓˆÂÒÒÓ‚ Ô‡‡ÎÎÂθÌÓ„Ó ‚˚ÔÓÎÌÂÌËfl ÙÛÌ͈ËÓ̇θÌ˚ı ÔÓ„‡ÏÏ. ùÚË ‡Î„ÓËÚÏ˚ ÓÒÌÓ‚‡Ì˚ ̇ Ô‰‚‡ËÚÂθÌÓÏ ÒÚÛÍÚÛÌÓÏ ‡Ì‡ÎËÁ ÒıÂÏ ÔÓ„‡ÏÏ, ÔÓÁ‚ÓÎfl˛˘ÂÏ ‰ËÙÙÂÂ̈ËÓ‚‡Ú¸ ÔÓ ÒÎÓÊÌÓÒÚË ËÒÔÓθÁÛÂÏ˚ ÔË Ëı ÔÓÒÚÓÂÌËË ÙÛÌ͈ËËÔÛÚÂÏ ‡Ì‡ÎËÁ‡ Ëı ÂÍÛÒË‚Ì˚ı ÓÔ‰ÂÎÂÌËÈ Ë, Í‡Í ÒΉÒÚ‚ËÂ, ‰ÓÒÚ‡ÚÓ˜ÌÓ ˝ÙÙÂÍÚË‚ÌÓ Ô·ÌËÓ‚‡Ú¸ÔÓˆÂÒÒ˚ Ô‡‡ÎÎÂθÌÓ„Ó ‚˚˜ËÒÎÂÌËfl Ëı Á̇˜ÂÌËÈ.*ǂ‰ÂÌËÂ. ê‡ÒÒÏÓÚËÏ ÔÓ·ÎÂÏÛ Ô·ÌËÓ‚‡ÌËfl ÔÓˆÂÒÒÓ‚ Ô‡‡ÎÎÂθÌÓ„Ó ‚˚ÔÓÎÌÂÌËfl ÙÛÌ͈ËÓ̇θÌ˚ı ÔÓ„‡ÏÏ Ì‡ ‚˚˜ËÒÎËÚÂθÌ˚ı ÒËÒÚÂχı.
éË„Ë̇θ̇fl ÒÚÓÓ̇ ËÁ·„‡ÂÏ˚ı ÂÁÛθڇÚÓ‚ – Ô˂ΘÂÌË ÏÂÚÓ‰Ó‚ ÒÚÛÍÚÛÌӄӇ̇ÎËÁ‡ ÙÛÌ͈ËÓ̇θÌ˚ı ÔÓ„‡ÏÏ, ÓÒÛ˘ÂÒÚ‚ÎflÂÏÓ„Ó ÔÓ Ëı ÒıÂχÏ, ‰Îfl ‚˚fl‚ÎÂÌËfl ÓÒÓ·ÂÌÌÓÒÚÂÈËÒÔÓθÁÛÂÏ˚ı ‚ Ëı Á‡‰‡ÌËË ÂÍÛÒË‚Ì˚ı ÓÔ‰ÂÎÂÌËÈ Ë ÔÓÒÚÓÂÌË ̇ ˝ÚÓÈ ÓÒÌÓ‚Â ˝ÙÙÂÍÚË‚Ì˚ı‡Î„ÓËÚÏÓ‚ Ô·ÌËÓ‚‡ÌËfl Ô‡‡ÎÎÂθÌÓ„Ó ‚˚ÔÓÎÌÂÌËfl ÙÛÌ͈ËÓ̇θÌ˚ı ÔÓ„‡ÏÏ.àÁ‚ÂÒÚÌÓ, ˜ÚÓ ÔÓ·ÎÂχ ÛÔ‡‚ÎÂÌËfl Ô‡‡ÎÎÂθÌ˚ÏË ÔÓˆÂÒÒ‡ÏË Ì‡ ‚˚˜ËÒÎËÚÂθÌ˚ı ÒËÒÚÂχı, ÍÓÚÓ‡fl ·‡ÁËÛÂÚÒfl ̇ ‡Î„ÓËÚχı ÛÔ‡‚ÎÂÌËfl Á‡„ÛÊÂÌÌÓÒÚ¸˛ Ëı ÍÓÏÔÓÌÂÌÚÓ‚ Ë Ô·ÌËÓ‚‡ÌËfl Ô‡‡ÎÎÂθÌ˚ı ÔÓˆÂÒÒÓ‚, ‚ ̇ÒÚÓfl˘Â‚ÂÏfl ‰‡ÎÂ͇ ÓÚ ÒÍÓθ-ÌË·Û‰¸ Á̇˜ËÏÓ„Ó Ô‡ÍÚ˘ÂÒÍÓ„Ó Â¯ÂÌËfl [1–7]. ùÚÓ ÒÛ˘ÂÒÚ‚ÂÌÌÓ ӄ‡Ì˘ÂÌË ̇ ÔÛÚË ˝ÙÙÂÍÚË‚ÌÓ„Ó ËÒÔÓθÁÓ‚‡ÌËfl·Óθ¯Ëı ÍÓÏÔ¸˛ÚÂÌ˚ı ÒËÒÚÂÏ [1]. çÂÒÏÓÚfl ̇¯ËÓÍÓ ‚̉ÂÌË Í·ÒÚÂÌ˚ı ÒËÒÚÂÏ, ÓÒÛ˘ÂÒÚ‚ÎflÂÏÓ ‚ ̇ÒÚÓfl˘Â ‚ÂÏfl, ‚Ò ÓÚ˜ÂÚÎ˂ ÒÚ‡ÌÓ‚ËÚÒfl ÌÂÓ·ıÓ‰ËÏÓÒÚ¸ ¯ÂÌËfl Ë ‰Û„ÓÈ ÔÓ·ÎÂÏ˚, Ò‚flÁ‡ÌÌÓÈ Ò Ëı ˝ÙÙÂÍÚË‚Ì˚Ï ÔËÏÂÌÂÌËÂÏ, – ÒÓÁ‰‡ÌË ‚˚ÒÓÍÓÛÓ‚Ì‚˚ı flÁ˚ÍÓ‚ Ë ÒËÒÚÂÏÔ‡‡ÎÎÂθÌÓ„Ó ÔÓ„‡ÏÏËÓ‚‡ÌËfl, ÍÓÚÓ˚ ‚Íβ˜‡˛Ú Ì ÚÓθÍÓ ‡Á‚ËÚ˚ Ò‰ÒÚ‚‡ ÓÔËÒ‡ÌËfl Ô‡‡ÎÎÂÎËÁχ, ÌÓ Ú‡ÍÊ ËÌÒÚÛÏÂÌڇθÌ˚ Ò‰˚ ÔÓÂÍÚËÓ‚‡ÌËfl, ÓÚ·‰ÍË, ÍÓÌÚÓÎfl Ô‡‚ËθÌÓÒÚË ËÓˆÂÌË‚‡ÌËfl ‚˚˜ËÒÎËÚÂθÌÓÈ ÒÎÓÊÌÓÒÚË Ô‡‡ÎÎÂθÌ˚ı ÔÓ„‡ÏÏ [1, 2, 8, 9].ëÔ‡‚‰ÎË‚ÓÒÚË ‡‰Ë ÒΉÛÂÚ ÔÓ‰˜ÂÍÌÛÚ¸‚ÔÓÎÌ ӷ˙ÂÍÚË‚Ì˚ Ô˘ËÌ˚ Ú‡ÍÓ„Ó ÒÓÒÚÓflÌËfl.ÑÓ ÒËı ÔÓ Ô‚‡ÎËÛÂÚ ÚӘ͇ ÁÂÌËfl, ˜ÚÓ ‰Îfl ÒÓÁ‰‡ÌËfl Ô‡‡ÎÎÂθÌ˚ı ÔÓ„‡ÏÏ ‰ÓÒÚ‡ÚÓ˜ÌÓ ‡ÒÔ‡‡ÎÎÂÎË‚‡ÌËfl ÔÓ„‡ÏÏ, Á‡‰‡ÌÌ˚ı ̇ ÔÓÒΉÓ-* ꇷÓÚ‡ ‚˚ÔÓÎÌÂ̇ ÔË ÙË̇ÌÒÓ‚ÓÈ ÔÓ‰‰ÂÊÍ êîîà(ÔÓÂÍÚ ‹03-01-00588)‚‡ÚÂθÌ˚ı flÁ˚͇ı.
èË ˝ÚÓÏ ÛÔÛÒ͇ÂÚÒfl ËÁ ‚ˉÛ,˜ÚÓ ‡ÒÔ‡‡ÎÎÂÎË‚‡ÌË ÔÓ Ò‚ÓÂÈ ÒÛÚË ÂÒÚ¸ Ú‡ÌÒÎflˆËfl ÔÓÒΉӂ‡ÚÂθÌÓÈ ÔÓ„‡ÏÏ˚ ̇ flÁ˚Í ÂÂÔ‡‡ÎÎÂθÌÓ„Ó Ô‰ÒÚ‡‚ÎÂÌËfl, ‡, Í‡Í ËÁ‚ÂÒÚÌÓ,ÔÓÒÚÓÂÌË ͇˜ÂÒÚ‚ÂÌÌÓÈ Ô‡‡ÎÎÂθÌÓÈ ÔÓ„‡ÏÏ˚, Ô‰ÒÚ‡‚ÎÂÌË ‚ÒÂı ‚ÓÁÏÓÊÌÓÒÚÂÈ Ô‡‡ÎÎÂÎËÁχ  ‚˚ÔÓÎÌÂÌËfl, ÓÔ‰ÂÎÂÌÌÓ„Ó ÏÂÚÓ‰ÓϯÂÌËfl Á‡‰‡˜Ë, Ú·ÛÂÚ ÒÓÓÚ‚ÂÚÒÚ‚Û˛˘Ëı flÁ˚ÍÓ‚˚ı Ò‰ÒÚ‚. ïÓÚfl Ò‰ÒÚ‚‡ MPI, PVM Ë ‰. [10]Ó„‡ÌËÁ‡ˆËË ‚˚ÔÓÎÌÂÌËfl Ë ÓÔËÒ‡ÌËfl Ô‡‡ÎÎÂθÌ˚ı ÔÓˆÂÒÒÓ‚, Ô‰̇Á̇˜ÂÌÌ˚ ‰Îfl ËÒÔÓθÁÓ‚‡ÌËfl ̇ Í·ÒÚ‡ı, – ÓÔ‡‚‰‡ÌÌ˚È ¯‡„ ̇ ÔÛÚË Ëı·˚ÒÚÓ„Ó Ë ¯ËÓÍÓ„Ó Ô‡ÍÚ˘ÂÒÍÓ„Ó ÔËÏÂÌÂÌËfl, ÚÂÏ Ì ÏÂÌÂÂ, ÓÌË ‚ÂҸχ ÔËÏËÚË‚Ì˚ Í‡Í ÒÚÓ˜ÍË ÁÂÌËfl Ô‰ÒÚ‡‚ÎÂÌËfl ‡Á΢Ì˚ı ÙÓÏ Ô‡‡ÎÎÂÎËÁχ [1, 2], Ú‡Í Ë Ò ÔÓÁˈËË ÛÔ‡‚ÎÂÌËfl ËÔ·ÌËÓ‚‡ÌËfl Ô‡‡ÎÎÂθÌ˚ı ÔÓˆÂÒÒÓ‚.èÓ ÒÛÚË, Ò„ӉÌfl ÔÓ„‡ÏÏËÒÚ ÓÒÛ˘ÂÒÚ‚ÎflÂÚÔÓ‰„ÓÌÍÛ Ò‚ÓÂÈ ÔÓ„‡ÏÏ˚ ÔÓ‰ ÍÓÌÍÂÚÌÛ˛ ‚˚˜ËÒÎËÚÂθÌÛ˛ ÒËÒÚÂÏÛ (Çë) (Ú.Â.
‚˚ÔÓÎÌflÂÚ ÒËÒÚÂÏÌÓ-Á‡‚ËÒËÏÓ ÔÓ„‡ÏÏËÓ‚‡ÌËÂ), Ò‡Ï ÒÚ‡Ú˘ÂÒÍË ‡ÒÔ‰ÂÎflÂÚ Ù‡„ÏÂÌÚ˚ Ô‡‡ÎÎÂθÌÓÈÔÓ„‡ÏÏ˚ ̇ ÍÓÏÔ¸˛ÚÂ˚ (ÔÓˆÂÒÒÓ˚) Çë.äÓÏ ÚÓ„Ó, ˜‡ÒÚ˚ ӷÏÂÌÌ˚ ‚Á‡ËÏÓ‰ÂÈÒÚ‚ËflÍÓÏÔ¸˛ÚÂÓ‚ ÔË ‚˚ÔÓÎÌÂÌËË Ô‡‡ÎÎÂθÌ˚ıÔÓ„‡ÏÏ ‰‡Ê ÔË Ó˜Â̸ ·˚ÒÚ˚ı ͇̇·ı ÏÂÊÍÓÏÔ¸˛ÚÂÌÓ„Ó Ó·ÏÂ̇ ÒÛ˘ÂÒÚ‚ÂÌÌÓ ÒÌËʇ˛Ú˝ÙÙÂÍÚË‚ÌÓÒÚ¸ Ô‡‡ÎÎÂθÌÓÈ ‡·ÓÚ˚ Çë Ë Á‡ÒÚ‡‚Îfl˛Ú ÔÓ„‡ÏÏËÒÚ‡ ‡Á‡·‡Ú˚‚‡Ú¸ ÍÛÔÌÓ·ÎÓ˜Ì˚ ԇ‡ÎÎÂθÌ˚ ÔÓ„‡ÏÏ˚ [7]. èÓ˝ÚÓÏÛÒ Ú‡ÍËÏ ÚÛ‰ÓÏ ‚̉flÂÚÒfl ‚˚ÒÓÍÓÛÓ‚Ì‚ÓÂÙÛÌ͈ËÓ̇θÌÓÂ Ë Îӄ˘ÂÒÍÓ ÔÓ„‡ÏÏËÓ‚‡ÌËÂ, ÍÓÚÓÓ ÔÓ Ò‚ÓÂÈ ÔËӉ fl‚ÎflÂÚÒfl “ÏÂÎÍÓÁÂÌËÒÚ˚Ï” Ë Ú·ÛÂÚ ÔËÏÂÌÂÌËfl ‰Ë̇Ï˘ÂÒÍËıÒıÂÏ ÛÔ‡‚ÎÂÌËfl Ô‡‡ÎÎÂθÌ˚ÏË ÔÓˆÂÒÒ‡ÏË ÔËÂ„Ó Â‡ÎËÁ‡ˆËË Ì‡ Çë [11, 12].Ç Òڇڸ ‡ÒÒχÚË‚‡ÂÚÒfl ÔÓ·ÎÂχ Ó„‡ÌËÁ‡ˆËË Ë Ô·ÌËÓ‚‡ÌËfl ÔÓˆÂÒÒÓ‚ Ô‡‡ÎÎÂθÌÓ„Ó‚˚ÔÓÎÌÂÌËfl ÙÛÌ͈ËÓ̇θÌ˚ı ÔÓ„‡ÏÏ ÔËÏÂ-131132ŇʇÌÓ‚ Ë ‰.ÌËÚÂθÌÓ Í ÒÓÁ‰‡ÌÌÓÈ ÒËÒÚÂÏ ÙÛÌ͈ËÓ̇θÌÓ„ÓÔ‡‡ÎÎÂθÌÓ„Ó ÔÓ„‡ÏÏËÓ‚‡ÌËfl ‰Îfl Í·ÒÚÂÓ‚.Ö ˆÂÌڇθÌ˚È ˝ÎÂÏÂÌÚ – ÓË„Ë̇θÌ˚È flÁ˚ÍÍÓÏÔÓÁˈËÓÌÌÓ„Ó ÙÛÌ͈ËÓ̇θÌÓ„Ó Ô‡‡ÎÎÂθÌÓ„Ó ÔÓ„‡ÏÏËÓ‚‡ÌËfl FPTL (Functional ParallelTypified Language) [9].1.
íÂÓÂÚ˘ÂÒ͇fl ·‡Á‡ flÁ˚͇ ÙÛÌ͈ËÓ̇θÌÓ„Ó Ô‡‡ÎÎÂθÌÓ„Ó ÔÓ„‡ÏÏËÓ‚‡ÌËfl FPTL. 1.1.á ‡ ‰ ‡ Ì Ë Â Ù Û Ì Í ˆ Ë È. éÒÌÓ‚Ì˚ÏË ÒÂχÌÚ˘ÂÒÍËÏË Ó·˙ÂÍÚ‡ÏË ‚ flÁ˚Í FPTL ‚˚ÒÚÛÔ‡˛Ú ‰‡ÌÌ˚ÂË ÓÔ‰ÂÎflÂÏ˚ ̇ ÌËı ‚ Ó·˘ÂÏ ÒÎÛ˜‡Â ˜‡ÒÚ˘Ì˚ ÙÛÌ͈ËË. îÛÌ͈ËË, ÒΉÛfl [9, 13–17], ‡ÒÒχÚË‚‡˛ÚÒfl Í‡Í (m, n)-‡Ì˚Â, m ≥ 0, n ≥ 0, ÚËÔËÁËÓ‚‡ÌÌ˚ ÒÓÓÚ‚ÂÚÒÚ‚Ëfl ÏÂÊ‰Û ÏÌÓÊÂÒÚ‚‡ÏË ‰‡ÌÌ˚ı; (m, n)-‡Ì‡fl ÙÛÌ͈Ëfl f (m, n) – Ó‰ÌÓÁ̇˜ÌÓ˜‡ÒÚ˘ÌÓ ‚ Ó·˘ÂÏ ÒÎÛ˜‡Â ÓÚÓ·‡ÊÂÌË ËÁ D1 ×× D2 × …Dm ‚ D '1 × D '2 × … D 'n ÚËÔ‡ t1 × t2 × …tmt 1' × t 2' × … t n' , „‰Â ti Ë t 'j , i = 1, 2, …, m, j = 1, 2,…, n – ÚËÔ˚, Á̇˜ÂÌËflÏË ÍÓÚÓ˚ı ÒÎÛÊ‡Ú ÌÂÔÛÒÚ˚ ÏÌÓÊÂÒÚ‚‡ Di Ë D 'j ÒÓÓÚ‚ÂÚÒÚ‚ÂÌÌÓ.
èË ˝ÚÓÏÔ‰ÔÓ·„‡ÂÚÒfl, ˜ÚÓ Di Ë D 'j ÒÓ‰ÂÊ‡Ú ‚˚˜ËÒÎflÂÏÓ ÌÂÓÔ‰ÂÎÂÌÌÓ Á̇˜ÂÌËÂ, Ó·ÓÁ̇˜‡ÂÏÓÂω. í‡ÍËÏ Ó·‡ÁÓÏ, ‡„ÛÏÂÌÚ‡ÏË Ë Á̇˜ÂÌËflÏË(m, n)-‡ÌÓÈ ÙÛÌ͈ËË fl‚Îfl˛ÚÒfl ÍÓÚÂÊË ‰‡ÌÌ˚ı‰ÎËÌ˚ m Ë n, ÔË ˝ÚÓÏ ‚˚ÔÓÎÌflÂÚÒfl ÛÒÎÓ‚Ë αλ == λα = α ‰Îfl β·Ó„Ó ÍÓÚÂʇ α, „‰Â λ – ÍÓÚÂÊ ÌÛ΂ÓÈ ‰ÎËÌ˚. îÛÌÍˆË˛ f (m, n) Ó‰ÌÓÁ̇˜ÌÓ Ô‰ÒÚ‡‚ÎflÂÚ Â „‡ÙËÍ: {(α, β)|f (m, n)(α) = β}, „‰Â α Ë β – ÍÓÚÂÊË ‰‡ÌÌ˚ı. чΠÍÓÚÂÊË Ô‰ÒÚ‡‚Îfl˛ÚÒfl ͇ÍÍÓÌ͇ÚÂ̇ˆËfl Ëı ˝ÎÂÏÂÌÚÓ‚ ·ÂÁ ‡Á‰ÂÎËÚÂθÌ˚ıÁ̇ÍÓ‚; α, β, γ, … – Ó·ÓÁ̇˜ÂÌË ÔÓËÁ‚ÓθÌ˚ıÍÓÚÂÊÂÈ.чÌÌ˚Â Ë ÙÛÌ͈ËË ‚ FPTL ÓÔ‰ÂÎfl˛ÚÒfl ‚ Ó·˘ÂÏ ÒÎÛ˜‡Â ÔÓÒ‰ÒÚ‚ÓÏ ÒËÒÚÂÏ ÙÛÌ͈ËÓ̇θÌ˚ıËÎË ÂÎflˆËÓÌÌ˚ı Û‡‚ÌÂÌËÈ ‚ Á‡‰‡ÌÌ˚ı Ò˄̇ÚÛ‡ı, ÍÓÚÓ˚ ڇÍÚÛ˛ÚÒfl Í‡Í ÓÔ‡ÚÓ˚ ̇ËÏÂ̸¯ÂÈ ÙËÍÒËÓ‚‡ÌÌÓÈ ÚÓ˜ÍË ËÎË Ì‡ËÏÂ̸¯Â„Ó¯ÂÌËfl ‡ÒÒχÚË‚‡ÂÏ˚ı ÒËÒÚÂÏ Û‡‚ÌÂÌËÈ. 臇ÏÂÚËÁÓ‚‡ÌÌ˚ ÙÛÌ͈ËË Ë ÚËÔ˚ ‰‡ÌÌ˚ı ̇Á˚‚‡˛ÚÒfl ÙÛÌ͈ËÓ̇·ÏË Ë ÂÎflˆËÓ̇·ÏË ÒÓÓÚ‚ÂÚÒÚ‚ÂÌÌÓ.
íÂÓÂÚ˘ÂÒÍË ÏÌÓÊÂÒÚ‚Ó ÙÛÌ͈ËÈ ‚ flÁ˚ÍÂFPTL Ô‰ÒÚ‡‚ÎflÂÚ Ë̉ÛÍÚË‚Ì˚È Í·ÒÒ ÙÛÌ͈ËÈ,ÔÓÎÛ˜ÂÌÌ˚ı Á‡Ï˚͇ÌËÂÏ ÏÌÓÊÂÒÚ‚‡ ÓÔ‡ˆËÈÍÓÏÔÓÁˈËË ÙÛÌ͈ËÈ O ̇‰ Á‡‰‡ÌÌ˚Ï ÏÌÓÊÂÒÚ‚ÓÏ ·‡ÁËÒÌ˚ı ÙÛÌ͈ËÈ F. 臇 〈O, F〉 ÏÓÊÂÚ ‡ÒÒχÚË‚‡Ú¸Òfl Í‡Í Ò‚Ó·Ó‰Ì‡fl ÙÛÌ͈ËÓ̇θ̇fl ‡Î„·‡.Ç FPTL ËÒÔÓθÁÛ˛ÚÒfl ˜ÂÚ˚ ÔÓÒÚ˚ ÓÔ‡ˆËË ÍÓÏÔÓÁˈËË ÙÛÌ͈ËÈ, fl‚Îfl˛˘ËÂÒfl ‚ ÌÂÍÓÚÓÓÏ ÒÏ˚ÒΠ‰Û͈ËÂÈ Ó·˘ÂÔËÌflÚ˚ı ‚ χÚÂχÚ˘ÂÒÍÓÈ Ô‡ÍÚËÍ ÒÔÓÒÓ·Ó‚ Á‡‰‡ÌËfl ÙÛÌ͈ËÈ ÔÛÚÂχÁ·Ó‡ ÒÎÛ˜‡Â‚, ÔÓ‰ÒÚ‡ÌÓ‚ÍË ‚ÏÂÒÚÓ ‡„ÛÏÂÌÚÓ‚ËÁ‚ÂÒÚÌÓÈ ÙÛÌ͈ËË ‰Û„Ëı ÙÛÌ͈ËÈ. åÓ‰Âθ ù·‡Ì‡-ɉÂÎfl ÓÔ‰ÂÎÂÌËfl ‚˚˜ËÒÎËÏ˚ı ÙÛÌ͈ËÈ,flÁ˚Í ÂÍÛÒË‚Ì˚ı ÙÛÌ͈ËÈ [18] – ÔÓÓ·‡Á˚ ËÒÔÓθÁÛÂÏÓ„Ó Ì‡ÏË ÔÓ‰ıÓ‰‡ Í Á‡‰‡Ì˲ ‚˚˜ËÒÎË-Ï˚ı ÙÛÌ͈ËÈ. èË̈ËÔˇθÌÓ ÓÚ΢ˠÁ‡Íβ˜‡ÂÚÒfl ‚ ÚÓÏ, ˜ÚÓ ‚ÏÂÒÚÓ ÛÌËÙˈËÓ‚‡ÌÌÓÈ ÒÚÛÍÚÛ˚ ‰‡ÌÌ˚ı – ̇ÚۇθÌÓ„Ó fl‰‡ Ë Á‡‰‡ÌÌÓÈ Ì‡ÌÂÏ ÏÓ‰ÂÎË ‚˚˜ËÒÎËÏ˚ı ÙÛÌ͈ËÈ ‚ FPTL Ô‰·„‡ÂÚÒfl Ó·˘ËÈ ÒÔÓÒÓ· ÔÓÒÚÓÂÌËfl ÔÓËÁ‚ÓθÌÓÈ‚˚˜ËÒÎËÏÓÈ ÙÛÌ͈ËË Ì‡‰ ‡·ÒÚ‡ÍÚÌ˚ÏË ÚËÔ‡Ïˉ‡ÌÌ˚ı.
óÂÚ˚ ‡ÒÒχÚË‚‡ÂÏ˚ı ‰‡Î ÓÔ‡ˆËË ÍÓÏÔÓÁˈËË ÙÛÌ͈ËÈ, ÓÔ‡ÚÓ Á‡‰‡ÌËflÙÛÌ͈ËÈ ÔÓÒ‰ÒÚ‚ÓÏ ÒËÒÚÂÏ ÙÛÌ͈ËÓ̇θÌ˚ıÛ‡‚ÌÂÌËÈ Ë “ËÁ‚ÎÂ͇ÂÏÓ” ËÁ ÓÔ‰ÂÎÂÌËfl ‡·ÒÚ‡ÍÚÌÓ„Ó ÚËÔ‡ ‰‡ÌÌ˚ı ÏÌÓÊÂÒÚ‚Ó ÙÛÌ͈ËÈ-ÍÓÌÒÚÛÍÚÓÓ‚ Ë Ó·‡ÚÌ˚ı ËÏ ÙÛÌ͈ËÈ-‰ÂÒÚÛÍÚÓÓ‚ Ó·‡ÁÛ˛Ú ÛÌË‚Â҇θÌÛ˛ Ò˄̇ÚÛÛ, ÔÓÁ‚ÓÎfl˛˘Û˛ ‚˚‡ÁËÚ¸ β·Û˛ ‚˚˜ËÒÎËÏÛ˛ ÙÛÌÍˆË˛Ì‡‰ ‡ÒÒχÚË‚‡ÂÏ˚Ï ÚËÔÓÏ ‰‡ÌÌ˚ı [9, 17].èË ÓÔËÒ‡ÌËË ÓÔ‡ˆËÈ ÍÓÏÔÓÁˈËË ËÒÔÓθÁÛ˛ÚÒfl ÒÎÂ‰Û˛˘Ë ӷÓÁ̇˜ÂÌËfl: f (m, n) – (m, n)-‡Ì‡flÙÛÌ͈Ëfl, f (m, n)(a) – ÂÁÛÎ¸Ú‡Ú Â ÔËÏÂÌÂÌËfl Í ÍÓÚÂÊÛ a, f1 Ë f2 – ËÁ‚ÂÒÚÌ˚ ÙÛÌ͈ËË, f – ÓÔ‰ÂÎflÂχfl ÙÛÌ͈Ëfl, = – ÁÌ‡Í ‡‚ÂÌÒÚ‚‡ ÔÓ ÓÔ‰ÂÎÂÌ˲.1. éÔ‡ˆËfl ÔÓÒΉӂ‡ÚÂθÌÓÈ ÍÓÏÔÓÁˈËË (•)f( m, n )( m, k )= (f1( m, k )f1= { ( α, β ) ∃γ ( α, γ ) ∈( m, n )f( k, m )• f2( k, n )(α) = f 2) =( k, n )∧ (γ, β) ∈ f 2( m, k )(f1};( α ) ).2.
éÔ‡ˆËfl ÍÓÌ͇ÚÂ̇ˆËË (∗)f( m, n 1 + n 2 )( m, n 1 )= (f1( m, n 2 )* f2( m, n 1 )= { ( α, β 1 β 2 ) ( α, β 1 ) ∈ f 1f( m, n 1 + n 2 )( m, n 1 )(α) = f 1) =( m, n 2 )∧ ( α, β 2 ) ∈ f 2( m, n 2 )(α) f 2( α ).3. éÔ‡ˆËfl ÛÒÎÓ‚ÌÓÈ ÍÓÏÔÓÁˈËË (f( m, n )( m, n 1 )= (f1( m, n )= { ( α , β ) ( α, β ) ∈ f 2( m, n )f (m, n)(α) = f 2( m, n )f2};)) =∧ ∃γ ( ( α, γ ) ∈ f 1( m, n )(α), ÂÒÎË Á̇˜ÂÌË f 1( m, n 1 )) };(α) ÓÔÂ-( m, n )f 1 (α)‰ÂÎÂÌÓ; ÂÒÎËËÎË ÔÓˆÂÒÒ Â„Ó ‚˚˜ËÒÎÂÌËfl ‰ÎËÚÒfl ÌÂÓ„‡Ì˘ÂÌÌÓ, ÚÓ f (m, n)(α) Ò˜ËÚ‡ÂÚÒflÌÂÓÔ‰ÂÎÂÌÌ˚Ï.
óÚÓ·˚ Òӄ·ÒÓ‚‡Ú¸ ˝ÚÛ ÛÒÎÓ‚( m, n )ÌÛ˛ ÍÓÌÒÚÛÍˆË˛ Ò Ó·˘ÂÔËÌflÚÓÈ, ÍÓ„‰‡ f 1–ÔÓÔÓÁˈËÓ̇θ̇fl ÙÛÌ͈Ëfl, ÔËÌËχ˛˘‡fl ‰‚‡Á̇˜ÂÌËfl: “ËÒÚË̇” Ë “ÎÓʸ”, ÔÓÎÓÊËÏ, ˜ÚÓ Á̇˜ÂÌË “ÎÓʸ” ÚÓʉÂÒÚ‚ÂÌÌÓ ω.4. éÔ‡ˆËfl Ó·˙‰ËÌÂÌËfl „‡ÙËÍÓ‚ ÙÛÌ͈ËÈ( m, n )( m, n )⊕ f 2 ).(⊕): f (m, n) = ( f 1ÑÎfl ÒÓı‡ÌÂÌËfl Ò‚ÓÈÒÚ‚‡ ÙÛÌ͈ËÓ̇θÌÓÒÚË( m, n )( m, n )Ë f2·˚ÎË ÒÓ‚ÏÂf (m, n) Ú·ÛÂÚÒfl, ˜ÚÓ·˚ f 1( m, n )ÒÚÌ˚: ‰Îfl ‚ÒflÍÓ„Ó ÍÓÚÂʇ α, ÂÒÎË f 1(α) ËàáÇÖëíàü êÄç.
íÖéêàü à ëàëíÖåõ ìèêÄÇãÖçàü ‹ 6 2005ëíêìäíìêçõâ ÄçÄãàá à èãÄçàêéÇÄçàÖ èêéñÖëëéÇ( m, n )f 2 (α) ÓÔ‰ÂÎÂÌ˚, ÓÌË ‰ÓÎÊÌ˚ ·˚Ú¸ ‡‚Ì˚. éÚÓ„Ó̇θÌ˚ ÙÛÌ͈ËË, „‡ÙËÍË ÍÓÚÓ˚ı Ì ÔÂÂÒÂ͇˛ÚÒfl, fl‚Îfl˛ÚÒfl ÒÓ‚ÏÂÒÚÌ˚ÏË. èÓ˝ÚÓÏÛ f (m, n)(α)( m, n )( m, n )‡‚ÌÓ Ó‰ÌÓÏÛ ËÁ Á̇˜ÂÌËÈ f 1 (α) ËÎË f 2 (α), ÍÓÚÓÓ ÓÔ‰ÂÎÂÌÓ, ‚ ˜‡ÒÚÌÓÒÚË ‚˚˜ËÒÎÂÌÓ Ô‚˚Ï.ÇÒ ÓÔ‡ˆËË ÍÓÏÔÓÁˈËË ‡ÒÒӈˇÚË‚Ì˚; ÓÔ‡ˆËfl ⊕ Ú‡ÍÊ ÍÓÏÏÛÚ‡Ú˂̇. ëÎÂ‰Û˛˘ËÈ ÔÓfl‰ÓÍ ÒÚ‡¯ËÌÒÚ‚‡ ÓÔ‡ˆËÈ ÍÓÏÔÓÁˈËË •, ∗,, ⊕,ÔÓÁ‚ÓÎflÂÚ ÓÔÛÒ͇ڸ fl‰ ÒÍÓ·ÓÍ ‚ Á‡ÔËÒË ÙÛÌ͈ËÈ.5.
é·˘‡fl ÙÓχ ÓÔ‰ÂÎÂÌËfl ÙÛÌ͈ËÈ ‚ FPTL –˝ÚÓ ÒËÒÚÂÏ˚ ÙÛÌ͈ËÓ̇θÌ˚ı Û‡‚ÌÂÌËÈ ‚ˉ‡X i = τi ,i = 1, 2, …, n,( min )Xi(0)„‰Â X i=∪Xk≥0(k)i ,i = 1, 2, …, n,= ∅ (∅ – ÌË„‰Â Ì ÓÔ‰ÂÎÂÌ̇fl ÙÛÌ͈Ëfl(k)(k)ê‡ÒÒÏÓÚËÏ ÔËÏ ÂÍÛÒË‚ÌÓ„Ó ÓÔ‰ÂÎÂÌËfl ÙÛÌ͈ËË ÂÒÎË P 1 ( x, y ), ÚÓ f 1 ( F ( x, y ), f 2 ( y ) ),F ( x, y ) = ÂÒÎË P 2 ( x, y ), ÚÓ f 3 ( x, y ), ÂÒÎË P 3 ( x, y ), ÚÓ F ( f 4 ( x, y ), y ).îÛÌ͈ËÓ̇θ̇fl ÒıÂχ (îë) ÙÛÌ͈ËË F(x, y)·Û‰ÂÚ ËÏÂÚ¸ ÒÎÂ‰Û˛˘Û˛ ÙÓÏÛ Ô‰ÒÚ‡‚ÎÂÌËfl(Û͇Á‡ÌËfl ‡ÌÓÒÚË ÙÛÌ͈ËÈ ÓÔÛ˘ÂÌ˚):F ( P1(1.1)„‰Â Xi – ÓÔ‰ÂÎflÂχfl ÙÛÌ͈Ëfl, ‡ τi – ÚÂÏ ÚÓÈ Ê‡ÌÓÒÚË Ë ÚÓ„Ó Ê ÚËÔ‡, ˜ÚÓ Ë Xi, ÍÓÚÓ˚È Á‡‰‡Ì ̇ÏÌÓÊÂÒÚ‚‡ı ÙÛÌ͈ËÓ̇θÌ˚ı ÔÂÂÏÂÌÌ˚ı {X1, X2,…, Xn} Ë ·‡ÁËÒÌ˚ı ÙÛÌ͈ËÈ {f1, f2, …}.åÌÓÊÂÒÚ‚Ó ÚÂÏÓ‚ ÒÚÓËÚÒfl Ë̉ÛÍÚË‚ÌÓ:1) ÙÛÌ͈ËÓ̇θ̇fl ÔÂÂÏÂÌ̇fl ËÎË ·‡ÁËÒ̇flÙÛÌ͈Ëfl ÂÒÚ¸ ÚÂÏ ÚÓÈ Ê ‡ÌÓÒÚË Ë ÚÓ„Ó Ê ÚËÔ‡,˜ÚÓ Ë ÙÛÌ͈ËÓ̇θ̇fl ÔÂÂÏÂÌ̇fl ËÎË ·‡ÁËÒ̇flÙÛÌ͈Ëfl;2) ÂÒÎË τ1 Ë τ2 – ÚÂÏ˚, ÚÓ (τ1∆τ2) – Ú‡ÍÊ ÚÂÏ˚, „‰Â ∆ ∈ {•, ∗,, ⊕}.