JCSSI 6-2005 rus (Задания по FPTL), страница 2
Описание файла
Файл "JCSSI 6-2005 rus" внутри архива находится в следующих папках: Задания по FPTL, FPTL Release, Doc. PDF-файл из архива "Задания по FPTL", который расположен в категории "". Всё это находится в предмете "параллельные системы и параллельные вычисления" из 9 семестр (1 семестр магистратуры), которые можно найти в файловом архиве НИУ «МЭИ» . Не смотря на прямую связь этого архива с НИУ «МЭИ» , его также можно найти и в других разделах. Архив можно найти в разделе "остальное", в предмете "параллельные системы и параллельные вычисления" в общих файлах.
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
èË ˝ÚÓÏ Ú·ÛÂÚÒfl Òӄ·ÒÓ‚‡ÌË ‡ÌÓÒÚÂÈ ÚÂÏÓ‚ τ1 Ë τ2 ‰Îfl ÔËÏÂÌflÂÏÓÈ ÓÔ‡ˆËË ÍÓÏÔÓÁˈËË, Í‡Í ˝ÚÓ ·˚ÎÓ Û͇Á‡ÌÓ‚˚¯Â;3) ‰Û„Ëı ÚÂÏÓ‚ ÌÂÚ.ÑÎfl ÒÚÓ„Ëı ·‡ÁËÒÌ˚ı ÙÛÌ͈ËÈ, Ú.Â. Ú‡ÍËı, Á̇˜ÂÌË ÍÓÚÓ˚ı Ì ÓÔ‰ÂÎÂÌÓ, ÂÒÎË Ì ÓÔ‰ÂÎÂÌıÓÚfl ·˚ Ó‰ËÌ ËÁ Ëı ‡„ÛÏÂÌÚÓ‚, ÓÔ‡ˆËË ÍÓÏÔÓÁˈËË ÏÓÌÓÚÓÌÌ˚ ÓÚÌÓÒËÚÂθÌÓ „‡ÙËÍÓ‚ ÙÛÌ͈ËÈ, Í ÍÓÚÓ˚Ï ÓÌË ÔËÏÂÌfl˛ÚÒfl. ÅÓΠÚÓ„Ó,ÓÌË ÌÂÔÂ˚‚Ì˚ [2, 16], ˜ÚÓ ÔÓÁ‚ÓÎflÂÚ Ì‡ËÏÂ̸¯Â ¯ÂÌË ÒËÒÚÂÏ˚ ÙÛÌ͈ËÓ̇θÌ˚ı Û‡‚ÌÂÌËÈ (1.1) ‚˚‡ÁËÚ¸ fl‚ÌÓÒ ÔÛÒÚ˚Ï „‡ÙËÍÓÏ), X i = [ X 1 /Xi|1 = 1, 2, …, n]τi,Á‰ÂÒ¸ [A/X]B – ÂÁÛÎ¸Ú‡Ú Ó‰ÌÓ‚ÂÏÂÌÌÓÈ ÔÓ‰ÒÚ‡Ìӂ͇ A ‚ÏÂÒÚÓ ‚ÒÂı ‚ıÓʉÂÌËÈ X ‚ B.ë‰Â·ÂÏ ‰‚‡ Á‡Ï˜‡ÌËfl, ͇҇˛˘ËÂÒfl ÙÓÏ˚Á‡‰‡ÌËfl ÙÛÌ͈ËÈ ‚ FPTL Ë Â„Ó ‚˚‡ÁËÚÂθÌ˚ı‚ÓÁÏÓÊÌÓÒÚÂÈ.
Ç˚·Ó Û͇Á‡ÌÌ˚ı ÓÔ‡ˆËÈ ÍÓÏÔÓÁˈËË ÙÛÌ͈ËÈ, ÔÓÏËÏÓ Ú·ӂ‡ÌËfl ÛÌË‚Â҇θÌÓÒÚË, ‚ ·Óθ¯ÓÈ ÒÚÂÔÂÌË ·˚Î Ô‰ÓÔ‰ÂÎÂÌ, Í‡Í ·˚ÎÓ ÛÊ Ò͇Á‡ÌÓ, Ó·˘ÂÔËÌflÚÓÈ Ï‡ÚÂχÚ˘ÂÒÍÓÈ Ô‡ÍÚËÍÓÈ ÓÔ‰ÂÎÂÌËfl ÙÛÌ͈ËÈ ‚‚ˉ ÂÍÛÒË‚Ì˚ı ‡‚ÂÌÒÚ‚, ‚ Ô‡‚ÓÈ ˜‡ÒÚË ÍÓÚÓ˚ı ÏÓÊÂÚ ËÒÔÓθÁÓ‚‡Ú¸Òfl ÓÔ‡ˆËfl ‡Á·Ó‡ ÒÎÛ˜‡Â‚ Ë ÔÓ‰ÒÚ‡ÌÓ‚ÍË (ÔÓ‰ÒÚ‡ÌÓ‚ÍË ÙÛÌ͈ËÈ ‚ÏÂÒÚÓÔÂÂÏÂÌÌ˚ı ËÁ‚ÂÒÚÌÓÈ ÙÛÌ͈ËË).133( F * π2 • f 2 ) • f 1 ) ⊕2⊕ ( P2f 3 ) ⊕ ( P3( f 4 * π 2 ) • F ).2á‰ÂÒ¸ π i (m ≥ 0, 0 ≤ i ≤ m) – ÙÛÌ͈ËË ‚˚·Ó‡ ‡m„ÛÏÂÌÚ‡ (·‡ÁËÒÌ˚ ÙÛÌ͈ËË): π i (x1x2…xm) = xi Ëmπ 0 (x1x2…xm) = λ (ÔÛÒÚÓÈ ÍÓÚÂÊ).
ÑÛ„Ë ·‡ÁËÒÌ˚ ÙÛÌ͈ËË fl‚Îfl˛ÚÒfl ÍÓÌÒÚÛÍÚÓ‡ÏË Ë Ó·‡ÚÌ˚ÏË Í ÌËÏ ÙÛÌ͈ËflÏË (‰ÂÒÚÛÍÚÓ‡ÏË), ÍÓÚÓ˚ Ë̉ۈËÛ˛ÚÒfl ÔË ÓÔËÒ‡ÌËË ÚËÔÓ‚ ‰‡ÌÌ˚ı.Ç flÁ˚Í ÂÒÚÂÒÚ‚ÂÌÌ˚Ï Ó·‡ÁÓÏ ÏÓ„Û ·˚Ú¸Ô‰ÒÚ‡‚ÎÂÌ˚ Ú‡Í Ì‡Á˚‚‡ÂÏ˚ ԇ‡ÎÎÂθÌ˚ÂÙÛÌ͈ËË [19], ÔËÏÂÓÏ ÍÓÚÓ˚ı ÒÎÛÊËÚ ËÁ‚ÂÒÚ̇fl ‚ ÚÂÎÂÙÓÌËË ÙÛÌ͈Ëfl „ÓÎÓÒÓ‚‡ÌËfl f(x1, x2, x3).Ö Á̇˜ÂÌË ÓÔ‰ÂÎÂÌÓ, ÂÒÎË ËÁ‚ÂÒÚ̇ ıÓÚfl ·˚Ӊ̇ Ô‡‡  ‡„ÛÏÂÌÚÓ‚ Ë Ëı Á̇˜ÂÌËfl ‡‚Ì˚; ‚˝ÚÓÏ ÒÎÛ˜‡Â Á̇˜ÂÌË ÙÛÌ͈ËË ÂÒÚ¸ Á̇˜ÂÌË ӉÌÓ„Ó ËÁ ‡„ÛÏÂÌÚÓ‚ ˝ÚÓÈ Ô‡˚; Ë̇˜Â Á̇˜ÂÌËÂÙÛÌ͈ËË Ì ÓÔ‰ÂÎÂÌÓ. îë ˝ÚÓÈ ÙÛÌ͈ËË ËÏÂÂÚÔ‰ÒÚ‡‚ÎÂÌËÂ:mf = ( π1 * π2 ) • P=3π1 ⊕ ( π2 * π3 ) • P=333π2 ⊕ ( π1 * π3 ) • P=3333π1 ,3„‰Â P= – ÔÓÔÓÁˈËÓ̇θ̇fl ÙÛÌ͈Ëfl ‡‚ÂÌÒÚ‚‡.ùÚÛ ÙÛÌÍˆË˛ ÌÂθÁfl ÌÂÔÓÒ‰ÒÚ‚ÂÌÌÓ ‚˚‡ÁËÚ¸ Ò‰ÒÚ‚‡ÏË Î˛·Ó„Ó ÔÓÒΉӂ‡ÚÂθÌÓ„Ó flÁ˚͇; ‰Îfl ˝ÚÓ„Ó ÌÂÓ·ıÓ‰ËÏÓ Ó„‡ÌËÁÓ‚‡Ú¸ Í‚‡ÁËÔ‡‡ÎÎÂθÌÓ ‚˚˜ËÒÎÂÌË ‚ÒÂı  ‡„ÛÏÂÌÚÓ‚, ̇ÔËÏÂ, ÔÓ Ò˜ÂÚ˜ËÍÛ ËÎË Ú‡ÈÏÂÛ, ÔÓ‚Âflfl‡‚ÂÌÒÚ‚Ó ÔÓÎÛ˜‡ÂÏ˚ı Á̇˜ÂÌËÈ. 臇ÎÎÂθ̇flÓÔ‡ˆËÓÌ̇fl ÒÂχÌÚË͇ flÁ˚͇ FPTL ÔÓÁ‚ÓÎflÂÚÍÓÂÍÚÌÓ Ì‡ıÓ‰ËÚ¸ Á̇˜ÂÌËfl Ú‡ÍÓ„Ó Ó‰‡ ÙÛÌ͈ËÈ.1.2.
á ‡ ‰ ‡ Ì Ë Â ‰ ‡ Ì Ì ˚ ı. Ç FPTL ÏÓÊÌÓÔ‰ÒÚ‡‚ÎflÚ¸ β·ÓÈ ‡·ÒÚ‡ÍÚÌ˚È ÚËÔ ‰‡ÌÌ˚ı.ÅÓΠÚÓ„Ó, ËÒÔÓθÁÛÂÏ˚ ÔË Â„Ó ÔÓÒÚÓÂÌËËÙÛÌ͈ËË-ÍÓÌÒÚÛÍÚÓ˚ Ë Ó·‡ÚÌ˚ ËÏ ÙÛÌ͈ËˉÂÒÚÛÍÚÓ˚ ‚ÏÂÒÚÂ Ò ÙÛÌ͈ËflÏË ‚˚·Ó‡ ‡„ÛÏÂÌÚ‡ Ó·‡ÁÛ˛Ú ÔÓÎÌ˚È Ì‡·Ó ·‡ÁËÒÌ˚ı ÙÛÌ͈ËÈ ‚ ÚÓÏ ÒÏ˚ÒÎÂ, ˜ÚÓ Î˛·‡fl ‚˚˜ËÒÎËχfl ÙÛÌ͈Ëfl ̇‰ ‰‡ÌÌ˚Ï ‡ÒÒχÚË‚‡ÂÏÓ„Ó ÚËÔ‡ ÏÓÊÂÚ·˚Ú¸ ‚˚‡ÊÂ̇ Ò‰ÒÚ‚‡ÏË flÁ˚͇ FPTL [9, 17].íËÔ˚ ‰‡ÌÌ˚ı, Í‡Í Ë ÙÛÌ͈ËË, ‚ FPTL ÓÔ‰ÂÎfl˛ÚÒfl ˜ÂÂÁ ÒËÒÚÂÏÛ ÂÎflˆËÓÌÌ˚ı Û‡‚ÌÂÌËÈ ÒàáÇÖëíàü êÄç. íÖéêàü à ëàëíÖåõ ìèêÄÇãÖçàü ‹ 6 2005ŇʇÌÓ‚ Ë ‰.134ËÒÔÓθÁÓ‚‡ÌËÂÏ ‚‚‰ÂÌÌ˚ı ‚˚¯Â ÓÔ‡ˆËÈ ÍÓÏÔÓÁˈËË ÙÛÌ͈ËÈ Ë ÍÓÌÒÚÛÍÚÓÓ‚.çËÊ Ô‰ÒÚ‡‚ÎÂÌ ÔÓÒÚÓÈ ÔËÏ Á‡‰‡ÌËfl ̇ÚۇθÌÓ„Ó fl‰‡ ˜ËÒÂÎ ‚ FPTL:Data NAT {Constructors {=> Nat : O;Nat => Nat : succ;}NAT = O ? NAT*succ;}ǂ‰ÂÌÌ˚ Á‰ÂÒ¸ ÍÓÌÒÚÛÍÚÓ˚ Ë ÌÂfl‚ÌÓ Ó‰ÌÓÁ̇˜ÌÓ ÒÓÓÚ‚ÂÚÒÚ‚Û˛˘Ë ËÏ ‰ÂÒÚÛÍÚÓ˚ Ó·‡ÁÛ˛Ú ÔÓÎÌ˚È Ì‡·Ó ·‡ÁËÒÌ˚ı ÙÛÌ͈ËÈ.
ë Ëı ÔÓÏÓ˘¸˛ β·‡fl ÂÍÛÒ˂̇fl ÙÛÌ͈Ëfl ‚˚‡ÁËχ ̇‰ÏÌÓÊÂÒÚ‚ÓÏ ‰‡ÌÌ˚ı NAT.Ç Ô˂‰ÂÌÌÓÏ ÔËÏ ÍÓÌÒÚÛ͈Ëfl NAT • succËÌÚÂÔÂÚËÛÂÚÒfl Í‡Í ÏÌÓÊÂÒÚ‚Ó {succ(x)|x ∈ NAT}.ÑÂÒÚÛÍÚÓ˚ ‚ flÁ˚Í ÌÂfl‚ÌÓ ‚‚Ó‰flÚÒfl ‚ÏÂÒÚ ÒÓÔ‰ÂÎÂÌËÂÏ ÍÓÌÒÚÛÍÚÓÓ‚. ÑÂÒÚÛÍÚÓ˚ O–1 Ësucc–1 ËÌÚÂÔÂÚËÛ˛ÚÒfl: O−1(O) = λ, O–1(succ) = ω;succ–1(succ(x)) = x, succ−1(O) = ω.éÚÏÂÚËÏ ‚‡ÊÌ˚ ԇÍÚ˘ÂÒÍË ÓÒÓ·ÂÌÌÓÒÚËflÁ˚͇ FPTL:ÒıÂÏ̇fl ÙÓχ Á‡‰‡ÌËfl ÙÛÌ͈ËÈ,ÒÚÓ„‡fl ÚËÔËÁ‡ˆËfl,‚ÓÁÏÓÊÌÓÒÚ¸ Á‡‰‡ÌËfl Ô‡‡ÏÂÚËÁÓ‚‡ÌÌ˚ı ÙÛÌ͈ËÈ Ë ‰‡ÌÌ˚ı,ÔÓÎËflÁ˚˜ÌÓÒÚ¸, Á‡Íβ˜‡˛˘‡flÒfl ‚ ‚ÓÁÏÓÊÌÓÒÚË ËÒÔÓθÁÓ‚‡ÌËfl ‚ ÔÓ„‡Ïχı ÙÛÌ͈ËÈ Ë ‰‡ÌÌ˚ı, ÓÔ‰ÂÎflÂÏ˚ı ‚ ‰Û„Ëı flÁ˚͇ı ÔÓ„‡ÏÏËÓ‚‡ÌËfl (C, Pascal Ë ‰.).üÁ˚Í FPTL ËÏÂÂÚ ‰‚ ÒÂχÌÚËÍË: Ó‰ÌÛ ‰ÂÌÓÚ‡ˆËÓÌÌÛ˛, ÓÔËÒ‡ÌÌÛ˛ ‚˚¯Â, Ë Ô‡‡ÎÎÂθÌÛ˛ ÓÔ‡ˆËÓÌÌÛ˛ ÒÂχÌÚËÍÛ, ÍÓÚÓ‡fl ‡ÒÒχÚË‚‡ÂÚÒfl‚ ÒÎÂ‰Û˛˘ÂÏ ‡Á‰ÂÎÂ.1.3.
å Ó ‰  Π¸ Ô ‡ ‡ Î Î Â Î ¸ Ì Ó „ Ó ‚ ˚ ˜ Ë Ò Î Â Ì Ë fl Á Ì ‡ ˜ Â Ì Ë È Ù Û Ì Í ˆ Ë È. åÓ‰Âθ Ô‡‡ÎÎÂθÌÓ„Ó ‚˚˜ËÒÎÂÌËfl Á̇˜ÂÌËÈ ÙÛÌ͈ËÈ Á‡‰‡ÂÚ ÔÓˆÂÒÒ ‚˚˜ËÒÎÂÌËfl Í‡Í ÔÓˆÂÒÒ ÔÂÓ·‡ÁÓ‚‡ÌËfl ‰Â‚¸Â‚ [16]. ç‡ Í‡Ê‰ÓÏ ¯‡„ ÒÓÒÚÓflÌË‚˚˜ËÒÎÂÌËfl Ô‰ÒÚ‡‚ÎflÂÚÒfl ·Ë̇Ì˚Ï ‡ÁϘÂÌÌ˚Ï ‰Â‚ÓÏ, Ú‡ÍËÏ, ˜ÚÓ: ÎËÒÚ¸fl ‰Â‚‡ ÔÓϘÂÌ˚ ÒËÏ‚Ó·ÏË ˝ÎÂÏÂÌÚÓ‚ D ∪ {ω} (D – ÛÌË‚ÂÒÛω‡ÌÌ˚ı, ω – ‚˚˜ËÒÎËÏÓ ÌÂÓÔ‰ÂÎÂÌÌÓ Á̇˜ÂÌËÂ); ‚ÌÛÚÂÌÌË ‚¯ËÌ˚ ‰Â‚‡ ÔÓϘÂÌ˚ ÎË·ÓÒËÏ‚Ó·ÏË ÓÔ‡ˆËÈ •, ∗,, ⊕, ÎË·Ó ÙÛÌ͈ËÓ̇θÌ˚ÏË ÚÂχÏË.ç ӄ‡Ì˘˂‡fl Ó·˘ÌÓÒÚË, ‰ÓÔÛÒÚËÏ, ˜ÚÓ ËÌÚÂÂÒÛ˛˘‡fl Ì‡Ò ÙÛÌ͈Ëfl X1 ÓÔËÒ˚‚‡ÂÚÒfl ÒËÒÚÂÏÓÈ ÂÍÛÒË‚Ì˚ı ÙÛÌ͈ËÓ̇θÌ˚ı Û‡‚ÌÂÌËÈ ÚËÔ‡ (1.1).( min )Ç˚˜ËÒÎÂÌË Á̇˜ÂÌËfl ÙÛÌ͈ËË X 1 , fl‚Îfl˛˘Â„ÓÒfl Ô‚ÓÈ ÍÓÓ‰Ë̇ÚÓÈ Ì‡ËÏÂ̸¯Â„Ó Â¯ÂÌËfl ‰Îfl X1 ÒËÒÚÂÏ˚ (1.1), ‰Îfl ‡„ÛÏÂÌÚ‡ – ÍÓÚÂʇd Ô‰ÒÚ‡‚ÎflÂÚÒfl ‚ ‚ˉ ÍÓ̘ÌÓÈ ËÎË ÌÂÓ„‡Ì˘ÂÌÌÓÈ ÔÓÒΉӂ‡ÚÂθÌÓÒÚË ÒÓÒÚÓflÌËÈ, ̇˜‡Î¸Ì˚È ˝ÎÂÏÂÌÚ ÍÓÚÓÓÈ – ‰ÂÂ‚Ó Ò ‰‚ÛÏfl ‚¯Ë̇ÏË, Ô˘ÂÏ ÍÓÌ‚‡fl ‚¯Ë̇ ÔÓϘÂ̇ ÒËÏ‚ÓÎÓÏ ÙÛÌ͈ËÓ̇θÌÓÈ ÔÂÂÏÂÌÌÓÈ X1, ‡ ÎËÒÚÓ‚‡fl –‡„ÛÏÂÌÚÓÏ d.
ùÚ‡ ÔÓÒΉӂ‡ÚÂθÌÓÒÚ¸ ÒÓ‰ÂÊËÚ‰ËÌÒÚ‚ÂÌÌÓ (ÂÒÎË ÔÓˆÂÒÒ Á‡Í‡Ì˜Ë‚‡ÂÚÒfl ÛÒÔ¯ÌÓ) ÍÓ̘ÌÓ ÒÓÒÚÓflÌËÂ. ÖÒÎË ˝ÚÓ ÒÓÒÚÓflÌË ÂÒÚ¸‰ÂÂ‚Ó ËÁ Ó‰ÌÓÈ ‚¯ËÌ˚, ÔÓϘÂÌÌÓ ÌÂÍÓÚÓ˚Ï ‰‡ÌÌ˚Ï d' ∈ D, ÚÓ „Ó‚ÓËÏ Ó ÂÁÛθڇÚË‚ÌÓÏÓÍÓ̘‡ÌËË ‚˚˜ËÒÎÂÌËfl Á̇˜ÂÌËfl ÙÛÌ͈ËË Ò d'. ÖÒÎË ˝ÚÓ ÍÓ̘ÌÓ ÒÓÒÚÓflÌË ÂÒÚ¸ ω ËÎË ÔÓˆÂÒÒ ‚˚˜ËÒÎÂÌËÈ ÌÂÓ„‡Ì˘ÂÌ, ÚÓ ‰Â·ÂÚÒfl ‚˚‚Ó‰ Ó ·ÂÁÂÁÛθڇÚÌÓÏ Á‡‚¯ÂÌËË ‚˚˜ËÒÎÂÌËfl. èÂÂıÓ‰˚ ËÁ ÒÓÒÚÓflÌËfl ‚ ÒÓÒÚÓflÌË ÔË ÔÓËÒÍ Á̇˜ÂÌËflÙÛÌ͈ËË ÓÔ‰ÂÎfl˛ÚÒfl Ô‡‚Ë·ÏË ÔÂÓ·‡ÁÓ‚‡ÌËfl ‰Â‚¸Â‚, ‡Á‰ÂÎÂÌÌ˚ÏË Ì‡ ‰‚‡ ÔÓ‰ÏÌÓÊÂÒÚ‚‡:Ô‡‚Ë· ‡Á‚ÂÚ˚‚‡ÌËfl Ë Ò‚ÂÚ˚‚‡ÌËfl ‰Â‚¸Â‚.臂Ë· ÔÂÓ·‡ÁÓ‚‡ÌËfl ‰Â‚¸Â‚ Á‡‰‡˛ÚÒfl ‚‚ˉ ÒıÂÏ ËÁÏÂÌÂÌËfl ÒÓÒÚÓflÌËÈ Ë Ó·ÓÁ̇˜‡˛ÚÒflu' ⇒ u'', „‰Â u' Ë u'' – ÒıÂÏ˚ ÒÓÒÚÓflÌËfl.
ëıÂχ ÒÓÒÚÓflÌËfl ÓÚ΢‡ÂÚÒfl ÓÚ ÍÓÌÍÂÚÌÓ„Ó ÒÓÒÚÓflÌËfl ÚÂÏ,˜ÚÓ ‚ ÌÂÈ ‰Îfl ‡ÁÏÂÚÍË ‚¯ËÌ ‰Â‚‡ ÒÓÒÚÓflÌËflÏÓ„ÛÚ ËÒÔÓθÁÓ‚‡Ú¸Òfl ÒÎÂ‰Û˛˘Ë ÏÂÚ‡ÔÂÂÏÂÌÌ˚Â: t – ÔÓËÁ‚ÓθÌ˚È ÙÛÌ͈ËÓ̇θÌ˚È ÚÂÏ(‚ÓÁÏÓÊÌÓ, Ò Ë̉ÂÍÒ‡ÏË), u – ÔÓËÁ‚ÓθÌÓ ‰Â‚Ó-ÒÓÒÚÓflÌËÂ, d – ÔÓËÁ‚ÓθÌ˚È ˝ÎÂÏÂÌÚ D (‚ÓÁÏÓÊÌÓ, Ò Ë̉ÂÍÒ‡ÏË), f – ·‡ÁËÒ̇fl ÙÛÌ͈Ëfl, Xi –ÙÛÌ͈ËÓ̇θ̇fl ÔÂÂÏÂÌ̇fl.êÂÁÛÎ¸Ú‡Ú ÔËÏÂÌÂÌËfl Ô‡‚Ë· u' ⇒ u'' Í ÒÓÒÚÓflÌ˲ u ÂÒÚ¸ ‰Â‚Ó, ÔÓÎÛ˜ÂÌÌÓ ÔÛÚÂÏ Á‡ÏÂÌ˚ ‚ uÌÂÍÓÚÓÓ„Ó Â„Ó ÔÓ‰‰Â‚‡ u' ̇ ‰ÂÂ‚Ó u''.ç‡ ËÒ. 1 ÔÓ͇Á‡Ì˚ Ô‡‚Ë· ‡Á‚ÂÚ˚‚‡ÌËfl, ̇ËÒ.
2 – Ò‚ÂÚ˚‚‡ÌËfl ‰Â‚¸Â‚. ëÔ‡‚‰ÎË‚ÓÒÚ¸Ô‡‚ËÎ 6–9 ‚˚ÚÂ͇ÂÚ ËÁ ÚÓ„Ó, ˜ÚÓ ÓÔ‡ˆËfl ⊕ ÔËÏÂÌflÂÚÒfl ÚÓθÍÓ Í ÓÚÓ„Ó̇θÌ˚Ï ËÎË ÒÓ‚ÏÂÒÚÌ˚Ï ÙÛÌ͈ËflÏ.чÌ̇fl ÏÓ‰Âθ fl‚ÎflÂÚÒfl ̉ÂÚÂÏËÌËÓ‚‡ÌÌÓÈ, ÔÓÒÍÓθÍÛ ‚ Ó·˘ÂÏ ÒÎÛ˜‡Â ‚ÓÁÏÓÊÌÓ ÔËÏÂÌÂÌË ÌÂÒÍÓθÍËı Ô‡‚ËÎ Í ‰Â‚Û-ÒÓÒÚÓflÌ˲ ‚˚˜ËÒÎÂÌËÈ, Ë ÔÓ˝ÚÓÏÛ ‚ Á‡‚ËÒËÏÓÒÚË ÓÚ ËÒÔÓθÁÛÂÏÓ„Ó Ô‡‚Ë· ·Û‰ÛÚ ÔÓÎÛ˜‡Ú¸Òfl ‡Á΢Ì˚ÂÔÓÒΉӂ‡ÚÂθÌÓÒÚË ‚˚˜ËÒÎÂÌËÈ. åÓ‰Âθ Ú‡ÍÊÂÔ‡‡ÎÎÂθ̇, Ú‡Í Í‡Í ‚ÓÁÏÓÊÌÓ Ó‰ÌÓ‚ÂÏÂÌÌÓÂÔËÏÂÌÂÌË ÌÂÒÍÓθÍËı Ô‡‚ËÎ Í ÌÂÒ‚flÁÌ˚Ï ÍÛÒÚ‡Ï ‰Â‚‡ ÒÓÒÚÓflÌËfl. àÒÚÓ˜ÌËÍ Ô‡‡ÎÎÂÎËÁχ –Ò‚ÓÈÒÚ‚‡ ÓÔ‡ˆËÈ ∗,, ⊕. è‡ÍÚ˘ÂÒÍË ˝ÚÓ ÓÁ̇˜‡ÂÚ, ˜ÚÓ ÔÓˆÂÒÒ ‚˚˜ËÒÎÂÌËÈ ‡Á‚Ë‚‡ÂÚÒfl ÌÂÁ‡‚ËÒËÏÓ ÔÓ ‡Á΢Ì˚Ï ‚ÂÚ‚flÏ ‰Â‚‡-ÒÓÒÚÓflÌËfl,˜ÚÓ ‰‡ÎÓ Ô‡‚Ó Ì‡Á‚‡Ú¸ ÏÓ‰Âθ ‚˚˜ËÒÎÂÌËÈ ‚ [16]‡ÒËÌıÓÌÌÓÈ.
LJÊÌÓ ÓÚÏÂÚËÚ¸, ˜ÚÓ Ì ‚ÒflÍËÈ ÔÓfl‰ÓÍ ÔËÏÂÌÂÌËfl Ô‡‚ËÎ ÔÂÓ·‡ÁÓ‚‡ÌËfl ÒÓÒÚÓflÌËÈ ÔË‚Ó‰ËÚ Í ÍÓÂÍÚÌÓÏÛ ‚˚˜ËÒÎÂÌ˲ Á̇˜ÂÌËfl ÙÛÌ͈ËË. ç‡ÔËÏÂ, ÔË ‚˚˜ËÒÎÂÌËË (t1 ⊕ t2)(d)Ò̇˜‡Î‡ ‰Â·ÂÚÒfl ÔÓÔ˚Ú͇ ‚˚˜ËÒÎÂÌËfl t1(d), ÍÓÚÓÓ Ì ÓÔ‰ÂÎÂÌÓ, Ë ÔÓˆÂÒÒ ÔÓ‰ÓÎʇÂÚÒfl ·ÂÒÍÓ̘ÌÓ, ‡ Á̇˜ÂÌË t2(d) ÓÔ‰ÂÎÂÌÓ. í‡ÍËÏ Ó·‡ÁÓÏ, ÛÒÎÓ‚ËÂÏ ÍÓÂÍÚÌÓÒÚË Â‡ÎËÁ‡ˆËË ÏÓ‰ÂÎËàáÇÖëíàü êÄç. íÖéêàü à ëàëíÖåõ ìèêÄÇãÖçàü ‹ 6 2005ëíêìäíìêçõâ ÄçÄãàá à èãÄçàêéÇÄçàÖ èêéñÖëëéÇ1t1∆t22∆t1dt2d∆∈{*, →, ⊕}3t1 × t2Xit2t1d135τi(X1, X2, ...
, Xn)ddddêËÒ. 1. 臂Ë· ‡Á‚ÂÚ˚‚‡ÌËfl ‰Â‚¸Â‚.4f5 tω, ÂÒÎË f(d) = ω⊕ω∆10u13uωu⊕8uω11ωuωd7⊕6ωd', ÂÒÎË f(d) = d'dd∆ωu∆∈{ →,*}du⊕9ωd12d1d*d2d1d2∆∈{→→,*}duuêËÒ. 2. 臂Ë· Ò‚ÂÚ˚‚‡ÌËfl ‰Â‚¸Â‚.fl‚ÎflÂÚÒfl Ô‡‡ÎÎÂθÌÓ (ËÎË Í‚‡ÁËÔ‡‡ÎÎÂθÌÓÂ)‚˚˜ËÒÎÂÌË Á̇˜ÂÌËÈ ÙÛÌ͈ËÈ, ÒÓ‰ËÌflÂÏ˚ı ÓÔ‡ˆËÂÈ ⊕.ç ÏÂÌ ÒÛ˘ÂÒÚ‚ÂÌÌÓ ÛÏÂÌË ÔÂ˚‚‡Ú¸ ÌÂÌÛÊÌ˚ ‚˚˜ËÒÎÂÌËfl. ä‡Í ‚ˉÌÓ ËÁ Ô‡‚ËÎ 6–11,ÔË ÔÓÎÛ˜ÂÌËË Ì‡ Ó‰ÌÓÈ ËÁ ‚ÂÚ‚ÂÈ Á̇˜ÂÌËfl d, ÓÚ΢ÌÓ„Ó ÓÚ ω, ËÎË Á̇˜ÂÌËfl ω ‚˚˜ËÒÎÂÌËfl, Ò‚flÁ‡ÌÌ˚Â Ò ‰Û„ÓÈ ‚ÂÚ‚¸˛, ÌÂÓ·ıÓ‰ËÏÓ Ô‚‡Ú¸.
äÓÏ ˝ÚÓ„Ó, ÏÓ‰Âθ Ô‰ÓÒÚ‡‚ÎflÂÚ ‚ÓÁÏÓÊÌÓÒÚ¸ ÔÓ‚˚¯ÂÌËfl ˝ÙÙÂÍÚË‚ÌÓÒÚË ‚˚˜ËÒÎÂÌËÈ Á‡ Ò˜ÂÚ‚˚˜ËÒÎÂÌËÈ Ò ÛÔÂʉÂÌËÂÏ. ÖÒÎË ËÏÂÂÚÒfl ‰ÓÒÚ‡ÚÓ˜ÌÓ ÍÓ΢ÂÒÚ‚Ó ÂÒÛÒÓ‚, ÚÓ ÔË ÓÔ‰ÂÎÂÌËËt2)(d) ÏÓÊÌÓ t1(d) ‚˚˜ËÒÎflÚ¸ Ó‰Á̇˜ÂÌËfl (t1ÌÓ‚ÂÏÂÌÌÓ Ò t2(d), ÒÚÂÏflÒ¸ χÍÒËχθÌÓ ‡ÒÔ‡‡ÎÎÂÎËÚ¸ ÔÓˆÂÒÒ.ùÚË ÓÒÓ·ÂÌÌÓÒÚË ÏÓ‰ÂÎË fl‚Îfl˛ÚÒfl ÔË̈ËÔˇθÌ˚ÏË ÔË Â ‡ÎËÁ‡ˆËË Ì‡ ‚˚˜ËÒÎËÚÂθÌ˚ıÒËÒÚÂχı Ë ÔË ‡Á‡·ÓÚÍ ˝ÙÙÂÍÚË‚Ì˚ı ‡Î„ÓËÚÏÓ‚ Ô·ÌËÓ‚‡ÌËfl Ô‡‡ÎÎÂθÌÓ„Ó ‚˚ÔÓÎÌÂÌËfl ÙÛÌ͈ËÓ̇θÌ˚ı ÔÓ„‡ÏÏ.1.4. ë Ú Û Í Ú Û Ë Ó ‚ ‡ Ì Ì ˚  î ë. ëÚÛÍÚÛËÓ‚‡ÌÌ˚ îë ÔÓ‰ÏÌÓÊÂÒÚ‚Ó ÏÌÓÊÂÒÚ‚‡ îë,‚ ÔÓÒÚÓÂÌËË ÍÓÚÓ˚ı ‚ÏÂÒÚÓ ‰‚Ûı ÓÔ‡ˆËÈ ÍÓÏÔÓÁˈËË ÙÛÌ͈ËÈ ⊕ ËËÒÔÓθÁÛÂÚÒfl ÚÂ̇τ2, τ3), „‰Â τ1, τ2, τ3 – îë, ڇ̇fl ÓÔ‡ˆËfl (τ1ÍËÂ, ˜ÚÓ ‚ ËÌÚÂÔÂÚ‡ˆËË ϕ îë τ1 ËÏÂÂÚ Á̇˜ÂÌËÂÔÓÔÓÁˈËÓ̇θÌÓÈ ÙÛÌ͈ËË, ‡ τ2, τ3 – ÔÓËÁ‚Óθτ2, τ3) ≡ (ϕ(τ1)Ì˚ ÙÛÌ͈ËË, ÔË ˝ÚÓÏ ϕ(τ1τ2, τ3)(α) = ϕ(τ2)(α), ÂÒÎËϕ(τ2), ϕ(τ3)), ϕ(τ1ϕ(τ1)(α) “ËÒÚËÌÌÓ” Ë ϕ(τ3)(α), ‚ ÔÓÚË‚ÌÓÏ ÒÎÛ˜‡Â.ëÚÛÍÚÛËÓ‚‡ÌÌ˚ îë Ô‰ÒÚ‡‚Îfl˛ÚÒfl „‡Ù˘ÂÒÍË (ËÒ.
3).f3 • F2 * f4,è Ë Ï Â 1. èÛÒÚ¸ F1 = (( f1 * f2) • pf5 * F1) (ËÒ. 4).ɇÙ˘ÂÒÍÓ Ô‰ÒÚ‡‚ÎÂÌË ÒÚÛÍÚÛËÓ‚‡ÌÌ˚ı îë ÔӢ ‰Â‚ӂˉÌÓ„Ó Ô‰ÒÚ‡‚ÎÂÌËfl îëÓ·˘Â„Ó ‚ˉ‡, ‡ „·‚ÌÓÂ, ÓÌÓ ÒÛ˘ÂÒÚ‚ÂÌÌÓ ÛÔÓ˘‡ÂÚ‡ÎËÁ‡ˆË˛ Ô‡‡ÎÎÂθÌ˚ı ‚˚˜ËÒÎÂÌËÈ Á̇˜ÂÌËÈÙÛÌ͈ËÈ. çÂÙÓχθÌÓ, Ô‡‡ÎÎÂθÌÓ ‚˚˜ËÒÎÂÌË Á̇˜ÂÌËÈ ÙÛÌ͈ËÈ, Ëϲ˘Ëı ÒÚÛÍÚÛËÓ‚‡ÌÌ˚ îë, ÏÓÊÂÚ ·˚Ú¸ Ô‰ÒÚ‡‚ÎÂÌ Í‡Í ÔÓˆÂÒÒÓ‰ÌÓ‚ÂÏÂÌÌÓ„Ó ÔÓ‰‚ËÊÂÌËfl ‚˚˜ËÒÎÂÌËÈ ÔÓ‚ÒÂÏ ‚ÂÚ‚flÏ ÒÚÛÍÚÛÌÓ„Ó Ô‰ÒÚ‡‚ÎÂÌËfl îë.èË ˝ÚÓÏ ‰Îfl ‚ÒflÍÓÈ ·‡ÁËÒÌÓÈ ÙÛÌ͈ËË, ÍÓÚÓ‡fl‚ÒÚ˜‡ÂÚÒfl ̇ ËÁ·‡ÌÌÓÈ ‚ÂÚ‚Ë, ÓÒÛ˘ÂÒÚ‚ÎflÂÚÒfl ÔËÏÂÌÂÌËÂ Í ‰‡ÌÌ˚Ï, ‚˚˜ËÒÎÂÌÌ˚Ï Ô‰¯ÂÒÚ‚Û˛˘ËÏË ˝ÎÂÏÂÌÚ‡ÏË „‡Ù˘ÂÒÍÓ„Ó Ô‰ÒÚ‡‚ÎÂÌËfl, ÔÓÒΠ˜Â„Ó ‰‡ÌÌ˚ Ô‰‡˛ÚÒfl ÌÂÔÓÒ‰ÒÚ‚ÂÌÌÓ ÒÎÂ‰Û˛˘ÂÏÛ ˝ÎÂÏÂÌÚÛ ‚ÂÚ‚Ë.