Программная реализация алгоритма выделения структурных особенностей

Гармашов Константин Сергеевич

Программная реализация алгоритма выделения структурных особенностей

Выпускная квалификационная работа посвящена программной реализации на базе клиент-серверных технологий алгоритма выделения структурных особенностей, которые необходимы для повышения эффективности численных методов решения задачи Коши. Актуальность продиктована необходимостью в решении задачи приведения систем к канонический форме структурно разделённых систем дифференциальных уравнений.

Общественные науки в целом

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36425f1be77c40d58ad4

UUID: 333b8215-0f7c-4fde-b45f-3976127b912e

Язык: Русский

Опубликовано: больше 7 лет назад

Просмотры: 5

Гармашов Константин Сергеевич

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 516275 bytes

Поделиться работой

Ñàíêò-Ïåòåðáóðãñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò Ôàêóëüòåò ïðèêëàäíîé ìàòåìàòèêè ïðîöåññîâ óïðàâëåíèÿ Êàôåäðà Èíôîðìàöèîííûõ ñèñòåì Ãàðìàøîâ Êîíñòàíòèí Ñåðãååâè÷ Âûïóñêíàÿ êâàëèôèêàöèîííàÿ ðàáîòà áàêàëàâðà Ïðîãðàììíàÿ ðåàëèçàöèÿ àëãîðèòìà âûäåëåíèÿ ñòðóêòóðíûõ îñîáåííîñòåé Ïðèêëàäíàÿ ìàòåìàòèêà è èíôîðìàòèêà 010400 Ïðèêëàäíàÿ ìàòåìàòèêà, ôóíäàìåíòàëüíàÿ èíôîðìàòèêà è ïðîãðàììèðîâàíèå Çàâåäóþùèé êàôåäðîé, äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð Îëåìñêîé È.Â. Íàó÷íûé ðóêîâîäèòåëü, äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð Îëåìñêîé È.Â. Ðåöåíçåíò, êàíäèäàò ôèç.-ìàò. íàóê, äîöåíò Õèòðîâ Ã.Ì. Ñàíêò-Ïåòåðáóðã 2016

Ñîäåðæàíèå Ââåäåíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Ïîñòàíîâêà çàäà÷è . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Îñíîâíûå îïðåäåëåíèÿ 6 . . . . . . . . . . . . . . . . . . . . . . . . . . Àëãîðèòì ðåøåíèÿ çàäà÷ 1,2 . . . . . . . . . . . . . . . . . . . . . . . 10 Ïñåâäîêîä . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Ïðèìåð ïðèìåíåíèÿ àëãîðèòìà . . . . . . . . . . . . . . . . . . . . . . 22 Èñïîëüçóåìûå òåõíîëîãèè . . . . . . . . . . . . . . . . . . . . . . . . . 25 C# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 ASP.NET Web-API . . . . . . . . . . . . . . . . . . . . . . . . . . 25 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 HTML JavaScript . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 CSS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 jQuery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 AJAX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 REST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Êîìïîíåíòíî-îðèåíòèðîâàííîå ïðîãðàììèðîâàíèå . . . . . . . . . . . 28 Îïèñàíèå ñåðâåðíîé ÷àñòè 30 . . . . . . . . . . . . . . . . . . . . . . . . Îáùàÿ ñõåìà ñåðâåðíîé ÷àñòè . . . . . . . . . . . . . . . . . . . . . . 31 Îïèñàíèå êëèåíòñêîé ÷àñòè . . . . . . . . . . . . . . . . . . . . . . . . 32 Îáùàÿ ñõåìà êëèåíòñêîé ÷àñòè . . . . . . . . . . . . . . . . . . . . . . 33 Çàêëþ÷åíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Ñïèñîê ëèòåðàòóðû . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Ïðèëîæåíèå SMethodComp.cs . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 Permutation.cs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 Set.cs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 ApplyPermsComponent.cs . . . . . . . . . . . . . . . . . . . . . . . 50 SMController.cs 50 Pair.cs . . . . . . . . . . . . . . . . . . . . . . . . . . . . ApplyPermsController.cs . . . . . . . . . . . . . . . . . . . . . . . 52 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 queries.js . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 index.html main.css main.js 2

Ââåäåíèå Íà ñåãîäíÿøíåé äåíü Èíòåðíåò ÿâëÿåòñÿ ÷àñòüþ íàøåé ïîâñåäíåâíîé æèçíè. Èíòåðíåò-òåõíîëîãèè âñ¼ áîëüøå çàïîëíÿþò å¼. Òàêèì îáðàçîì, îí ðàçâèâàåòñÿ â ñòîðîíó îáëåã÷åíèÿ êëèåíòñêîé ÷àñòè è óòÿæåëåíèÿ ñåðâåðíîé. Â ñâÿçè ñ ýòèì ïîÿâëÿåòñÿ âñ¼ áîëüøå âåá-ñåðâèñîâ, ïðåäëàãàþùèõ ñâîè âû÷èñëèòåëüíûå ìîùíîñòè ïîä êëèåíòñêèå íóæäû. Êîíå÷íî, â ýòîì ðåøåíèè åñòü íåäîñòàòêè. Ñðåäè íèõ: ×òî äåëàòü, åñëè íåò äîñòóïà ê Èíòåðíåòó?. Íî ñåãîäíÿ óæå äàæå ê ÷àéíèêàì ïîäêëþ÷àþò èíòåðíåò! ×èñëåííûå ìåòîäû òîæå íå èñêëþ÷åíèå. Çà÷åì çàãðóæàòü ãèãàáàéòû ïðîãðàìì, òðàòèòü âðåìÿ íà óñòàíîâêó è ò.ä, òîëüêî äëÿ òîãî, ÷òîáû ïîñ÷èòàòü îäíî óðàâíåíèå? Òàêèì îáðàçîì, îò ïîëüçîâàòåëÿ òðåáóåòñÿ òîëüêî çàéòè íà ñàéò âåáñåðâèñà è ââåñòè äàííûå äëÿ ðàñ÷¼òîâ. À äëÿ òåõ, êòî õî÷åò èñïîëüçîâàòü ôóíêöèîíàë ñåðâèñà, ïðåäîñòàâëÿåòñÿ ñîîòâåòñòâóþùèé API. 3

Ïîñòàíîâêà çàäà÷è Ñòðóêòóðíûé ìåòîä èíòåãðèðîâàíèÿ ñèñòåìû m îáûêíîâåííûõ äèôôåðåíöèàëüíûõ óðàâíåíèé ñàìîãî îáùåãî âèäà zk0 = ϕk (x, z1 , . . . , zm ), k = 1, . . . , m, (1) ïðåäïîëàãàåò, ÷òî ñóùåñòâóåò ïðåîáðàçîâàíèå, ïðèâîäÿùåå ñèñòåìó (1) ê âèäó dy0 = f0 (x, y0 , y1 , . . . , yn ), dx (2) dyi = fi (x, y0 , . . . , yi−1 , yl+1 , . . . , yn ), i = 1, . . . , l, dx (3) dyj = fj (x, y0 , . . . , yj−1 ), j = l + 1, . . . , n, dx (4) x ∈ [X0 , Xk ] ⊂ R, ys : [X0 , Xk ] −→ Rrs , s = 0, . . . , n, f0 : [X0 , Xk ] × Rm −→ Rr0 , fi : [X0 , Xk ] × R m− fj : [X0 , Xk ] × R n X rs = m. Pl m− s=i rs Pl s=j −→ Rri , i = 1, . . . , l, rs −→ Rrj , j = l + 1, . . . , n, s=0 Â êà÷åñòâå ïðåîáðàçîâàíèÿ, ïðèâîäÿùåãî ñèñòåìó (1) ê âèäó (2)(4), âûáèðàåì ïåðåñòàíîâêó(ïåðåîáîçíà÷åíèå) óðàâåíåíèé ñèñòåìû (1). Çàäà÷à ñîñòîèò â òîì, ÷òîáû óêàçàòü òàêîé ïîðÿäîê ñëåäîâàíèÿ óðàâíåíèé è íóìåðàöèè ïåðåìåííûõ èñõîäíîé ñèñòåìû (1), ïðè êîòîðîì äëÿ ïðåîáðàçîâàííîé ñèñòåìû πz 0 = πφ(x, πz) (5) ñ âûäåëåííûìè îñîáåííîñòÿìè (2)(4), ýôôåêò îò ïðèìåíåíèÿ ñòðóêòóðíîãî ïîäîõîäà áóäåò ìàêñèìàëüíûì, ò.å. ìàêñèìàëüíî îòíîøåíèå m X ωπ(s) / s=r0 +1 m X s=1 4 ωπ(s) . (6)

πz = (zπ(1) , . . . , zπ(n) )T , πφ = (φπ(1) , . . . , φπ(m) )T , π = ïåðåñòàíîâêà ýëåìåíòîâ ìíîæåñòâà Im = 1, 2, . . . , m, Çäåñü è â äàëüíåéøåì (π(1), . . . , π(m)) îïðåäåëÿþùàÿ ïîðÿäîê ñëåäîâàíèÿ óðàâíåíèé ñèñòåìû 1. Ïðè÷¼ì çäåñü (äëÿ íàãëÿäíîñòè èçëîæåíèÿ àëãîðèòìà è ïîñòàíîâêè çàäà÷è) ðàâåíñòâî π(i) = j îçíà÷àåò, ÷òî j-å óðàâíåíèå ñèñòåìû (1) áóäåò çàíèìàòü i-å ìåñòî â ñèñòåìå (5). Ñ ó÷¼òîì ýòîãî ìîæíî óñòàíîâèòü ñâÿçü ìåæäó óðàâíåíèÿìè èñõîäíîé ñèñòåìû (1) è ñèñòåìû (2)(4): ys = (zπ(Ps−1 rν +1) , zπ(Ps−1 rν +2) , . . . , zπ(Psν=0 rν ) )T , ν=0 ν=0 fs = (φπ(Ps−1 rν +1) , φπ(Ps−1 rν +2) , . . . , φπ(Psν=0 rν ) )T , s = 0, . . . , n. ν=0 Äàëåå ωs ν=0 âåñîâûå êîýôôèöèåíòû, ëèáî çàäàâàåìûå ïîëüçîâàòåëåì, ëèáî âû÷èñëÿåìûå êàê îòíîñèòåëüíûå äîëè çàòðàò( ÷èñëî àðèôìåòè÷åñêèõ φs îò îáùåãî ÷èñëà âû÷èñëåíèé âñåõ êîìïîíåíò âåêòîð-ôóíêöèè φ = (φ1 , φ2 , . . . , φm ), s = {1, . . . , m}. Îáîçíà÷èì ÷åðåç P = {π} ìíîæåñòâî âñåõ ïåðåñòàíîâîê èç m ýëåìåíòîâ Im = {1, 2, . . . , m}. îïåðàöèé, âðåìÿ) âû÷èñëåíèÿ ïðàâîé ÷àñòè ×àñòíûé ñëó÷àé ðåøåíèÿ ýòîé çàäà÷è àëãîðèòì ïðèâåäåíèÿ ê âè- ω 1 = ω 2 = · · · = ωm . íåðàâíîïðàâíûõ ÷àñòåé ωt 6= äó (2)(4) â ïðåäïîëîæåíèè âûïîëíåíèÿ ðàâåíñòâ: Ïðèâåä¼ì îáîáùåíèå àëãîðèòìà íà ñëó÷àé ωd , ∀t, d ∈ Im , t 6= d. 5

Îñíîâíûå îïðåäåëåíèÿ Àááðåâèàòóðà 1 ÑÎÄÓ Ñèñòåìà Îáûêíîâåííûõ Äèôôåðåíöèàëüíûõ Óðàâíåíèé. Îïðåäëåíèå 1 Ìàòðèöó A = {a áóäåì íàçûâàòü ñòðóêòóðíîé ìàòðèöåé ñèñòåìû îáûêíîâåííûõ äèôôåðåíöèàëüíûõ óðàâíåíèé (1) è îáîçíà÷àòü A(φ), åñëè å¼ ýëåìåíòû ( 0, åñëè φi íå çàâèñèò îò zj , aij = 1, åñëè φi çàâèñèò îò zj . m i, j }i, j=1 Òàê, ñòðóêòóðíàÿ ìàòðèöà ñèñòåìû (2)(4) èìååò âèä ∗ ∗  ∗ Or1 ×r1  . . . ...  ∗ A(f ) =   ∗  ∗ ∗  . . . ... ∗ ∗  ... ∗ ∗ ∗ ∗ . . . Or1 ×rl ∗ ∗ ∗   ... ... ... ... ...   ∗ Orl ×rl ∗ ∗ ∗   ∗ ∗ Orl+1 ×rl+1 . . . Orl+1 ×rn   ... ... ... ... ...  ∗ ∗ ∗ ∗ Orn ×rn  Çäåñü è â äàëüíåéøåì Ori ×rj íóëåâàÿ ìàòðèöà ðàçìåðíîñòè ri × rj . Ñèìâîëîì ¾*¿ îáîçíà÷åíû áëîêè, êîòîðûå ìîãóò áûòü è íå íóëåâûìè. Îïðåäëåíèå 2 Ìíîæåñòâî, ýëåìåíòû êîòîðîãî ÿâëÿþòñÿ íîìåðà êîì- ïîíåíò èñêîìîé âåêòîð-ôóíêöèè z = {z1 , . . . , zm }, îò êîòîðûõ íå çàâèñèò ïðàâàÿ ÷àñòü i-ãî óðàâíåíèÿ ÑÎÄÓ (1), áóäåì íàçûâàòü i-ì ãîðèçîíòàëüíûì ñòðóêòóðíûì ìíîæåñòâîì ÑÎÄÓ (1) è îáîçíà÷àòü Ei (φ), ò.å Ei (φ) = {j ∈ Im : aij = 0, A(φ) = {aν,µ }m ν,µ=1 }. Îïðåäëåíèå 3 Ìíîæåñòâî, ýëåìåíòàìè êîòîðîãî ÿâëÿþòñÿ íîìåðà óðàâ- íåíèé ÑÎÄÓ (1) ñ ïðàâûìè ÷àñòÿìè, íå çàâèñÿùèìè îò j-é êîìïîíåíòû âåêòîð-ôóíêöèè z = {z1 , . . . , zm }, áóäåì íàçûâàòü j-ì âåðòèêàëüíûì ñòðóêòóðíûì ìíîæåñòâîì ÑÎÄÓ (1) è îáîçíà÷àòü Hj (φ), ò.å Hj (φ) = {i ∈ Im : aij = 0, A(φ) = {aν,µ }m ν,µ=1 }. Ïóñòü r = (r0 , r1 , . . . , rn ) ∈ ({0} ∪ N ) × N n . δ(r, k) = k−1 X Ââåä¼ì â ðàññìîòðåíèå ri , δ(r, 0) = 0, δ(r, n + 1) = m. i=0 6

Îïðåäëåíèå 4 Áóäåì ãîâîðèòü, ÷òî ÑÎÄÓ (1) èìååò íóëü-ñòðóêòóðó ñ ïàðàìåòðàìè l ∈ {0} ∪ N, n ∈ N, l < n, r = (r0 , r1 , . . . , rn ) ∈ ({0} ∪ N ) × N n , δ(r, n + 1) = m è îáîçíà÷àòü ZSφm [l, n, r], åñëè äëÿ ãîðèçîíòàëüíûõ ìíîæåñò ñïðàâåäëèâû âêëþ÷åíèÿ: {δ(r, i) + 1, . . . , δ(r, l + 1)} ⊂ Eδ(r,i)+µ(i) (φ), i = 1, . . . , l, n > l > 0, {δ(r, j) + 1, . . . , δ(r, n + 1)} ⊂ Eδ(r,j)+µ(j) (φ), i = l + 1, . . . , n, n > l ≥ 0, ãäå µ(s) = 1, . . . , rs , s = 1, . . . , n. Ëåììà 1 Ýëåìåíò j ∈ Ei (πφ), (i ∈ Hj (πφ)), òîãäà è òîëüêî òîãäà, êîãäà π(j) ∈ Eπ(φ) (φ), (π(i) ∈ Hπ(j) (φ), äëÿ π ∈ P , i, j ∈ Im . Îïðåäëåíèå 5 Áóäåì ãîâîðèòü,÷òî íóëü-ñòðóêòóðà ZS ÑÎÄÓ (1) ïðåäåëüíàÿ è îáîçíà÷àòü å¼ ZSφm [l, n, r], åñëè ñïðàâåäëèâû íåâêëþ÷åíèÿ: m φ [l, n, r] {δ(r, 1), . . . , δ(r, l + 1)} 6⊂ Eδ(r,1) (φ), l > 0, {δ(r, l + 1), . . . , δ(r, n + 1)} 6⊂ Eδ(r,l+1) (φ), l ≥ 0. Îïðåäëåíèå 6 Ïîä îáú¼ìîì P íóëü-ñòðóêòóðû ZS äåì ïîíèìàòü âåëè÷èíó âåñîâûå êîýôôèöèåíòû. m ν=r0 +1 ων è îáîçíà÷àòü m φ [l, n, r] ÑÎÄÓ (1) áóå¼ |ZSφm [l, n, r]|, ãäå ων Â ñîîòâåòñâèè ñ îïðåäåëåíèåì ïðåäåëüíîé íóëü-ñòðóêòóðû ñïðàâåäëèâî íåðàâåíñòâî m [l, n, r]| > |ZS m [b b, rb]|, π ∈ P . |ZSπφ πφ l, n Çàäà÷à 1 Íàéòè ïåðåñòàíîâêó π∗ ∈ P , äëÿ êîòîðîé ñïðàâåäëèâî íåðàâåíñòâî m [0, n, r]| ≥ |ZS m [0, n b, rb|, ∀π ∈ P. |ZSπ∗φ πφ Çàäà÷à 2 Íàéòè ïåðåñòàíîâêó π∗ ∈ P , äëÿ êîòîðîé ñïðàâåäëèâî íåðàâåíñòâî m [l, n, r]| ≥ |ZS m [b b, rb|, ∀π ∈ P. |ZSπ∗φ πφ l, n Îïðåäëåíèå 7 Ìíîæåñòâî B = Bφ (ω1 , ω2 , . . . , ωd ) ⊂ Im áóäåì íàçûíóëü-ñòðóêòóðíûì îñíîâàíèåì ÑÎÄÓ (1), åñëè φ âàòü ýëåìåíòíûì äëÿ Bφ = d [ ωs , ωq ∩ ωs = ∅, q 6= s, s=1 ñïðàâåäëèâû âêëþ÷åíèÿ d [ ωs ⊂ Ek , ∀k ∈ ωj , j = 1, . . . , d. s=j 7

Îïðåäëåíèå 8 Äëÿ ëþáîãî ìíîæåñòâà G ⊂ I âåëè÷èíó íàçûâàòü âåñîì ìíîæåñòâà G è îáîçíà÷àòü V [G]: X V [G] = ωi . m P i∈G ωi áóäåì i∈G Ëåììà 2 Äëÿ òîãî, ÷òîáû ìíîæåñòâî W áûëî ïîäìíîæåñòâîì j-ãî ãî- ðèçîíòàëüíîãî ñòðóêòóðíîãî ìíîæåñòâà ÑÎÄÓ (1), äëÿ ëþáîãî j, ïðèíàäëåæàùåãî ìíîæåñòâó V, íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû ìíîæåñòâî V áûëî ïîäìíîæåñòâîì k-ãî âåðòèêàëüíîãî ñòðóêòóðíîãî ìíîæåñòâà ÑÎÄÓ (1) äëÿ ëþáîãî k èç ìíîæåñòâà W: W ⊂ Ej (φ), ∀j ∈ V ⇔ V ⊂ Hk (φ), ∀k ∈ W, V, W ⊂ Ip . Ëåììà 3 Îáúåäèíåíèå d + 1 − j ìíîæåñòâ ω , ω ÿâëÿåòñÿ ïîäìíîæåñòâîì i-ãî ãîðèçîíòàëüíîãî ñòðóêòóðíîãî ìíîæåñòâà ÑÎÄÓ (1) äëÿ ëþáîãî i èç ìíîæåñòâà ωj òîãäà è òîëüêî òîãäà, êîãäà îáúåäèíåíèå j ìíîæåñòâ ω1 , ω2 , . . . , ωj ÿâëÿåòñÿ ïîäìíîæåñòâîì i-ãî âåðòèêàëüíîãî ñòðóêòóðíîãî ìíîæåñòâà ÑÎÄÓ (1) äëÿ ëþáîãî i èç ìíîæåñòâà ωj : j d [ ν=j ων ⊂ Ei (φ) ⇔ j [ j+1 , . . . , ωd ων ⊂ Hi (φ), ∀i ∈ ωj , j = 1, . . . , d. ν=1 Òåîðåìà 1 Äëÿ òîãî, ÷òîáû ìíîæåñòâî W = {i1 , i2 , . . . , iq } áûëî ýëåìåíòíûì íóëü-ñòðóêòóðíûì îñíîâàíèåì Wφ (ω1 , . . . , ωd ), |ωs | = rs , s = 1, . . . , d, ÑÎÄÓ (1), íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû {ig , ig+1 , . . . , ih(r,d)+1−g } ⊂ Eig (φ) ∩ Hih(r,d)+1−g (φ), h(r, d) g = 1, . . . , h(r, d) − , 2 (7) è {ih(r,s−1)+1 , ih(r,s−1)+2 , . . . , ih(r,s−1)+k } ⊂ Eih(r,s−1)+k (φ), k = 1, . . . , rs , s = 1, . . . , d, (8) ãäå [a] öåëàÿ ÷àñòü ÷èñëà a ∈ R. Òåîðåìà 2 Äëÿ òîãî, ÷òîáû íà ìíîæåñòâå ïåðåñòàíîâîê P ñóùåñòâîâà- m ëà òàêàÿ π∗ ∈ P , ÷òî ÑÎÄÓ (5) èìåëà áû íóëü-ñòðóêòóðó ZSπ∗φ [0, n, r], íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû ñóùåñòâîâàëî ýëåìåíòíîå íóëü-ñòðóêòóðíîå îñíîâàíèå Wφ (ω1 , . . . , ωn ), äëÿ êîòîðîãî ω0 = Im \Wφ (ω1 , . . . , ωn ), à |ωs | = rs , s = 0, . . . , d. Ñëåäóåò îòìåòèòü, ÷òî m |ZSπ∗φ [l, n, r]| = V [Wφ1 ] + V [Wφ2 ]. 8

Òåîðåìà 3 Äëÿ òîãî, ÷òîáû íà ìíîæåñòâå ïåðåñòàíîâîê P ñóùåñòâîâàëà òàêàÿ ïåðåñòàíîâêà π∗ ∈ P , ÷òî ÑÎÄÓ (5) èìåëà áû íóëü-ñòðóêòóðà m ZSπ∗φ [l, n, r], íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû ñóùåñòâîâàëè äâà âçàèìíî íåïåðåñêàþùèåñÿ ìíîæåñòâà ýëåìåíòíûå íóëü-ñòðóêòóðíûå îñíîâàíèÿ Wφ1 (ω1 , . . . , ωl ), Wφ2 (ωl+1 , . . . , ωn ), äëÿ êîòîðûõ ω0 = Ip \[Wφ1 (ω1 , . . . , ωl ) ∪ Wφ2 (ωl+1 , . . . , ωn )], |ωs | = rs , s = 0, . . . , n. 9

Àëãîðèòì ðåøåíèÿ çàäà÷ 1,2 Ω(1,0) = {i ∈ Im : i ∈ Ei (φ)}. Åñëè ìíîæåñòâî m [l, n, r]| = 0. Ýòî çíà÷èò, ÷òî íèêàêîå èçìåíå∀π ∈ P, |ZSπφ Ñòðîèì ìíîæåñòâà Ω(1,0) = ∅, òî íèå ïîðÿäêà ñëåäîâàíèÿ óðàâíåíèé èñõîäíîé ñèñòåìû íå ìîæåò îáåñïå÷èòü âûäåëåíèÿ ãðóïï óðàâíåíèé,èìåþùèõ ñòðóêòóðíûå îñîáåííîñòè. Ïðåäñòàâëÿåò èíòåðåñ ñëó÷àé,êîãäà Ω(1,0) 6= ∅. I. Ïîëàãàåì çíà÷åíèå óðîâíÿ äåðåâà ïåðåáîðà b1 µ = 0 è ââîäèì â ðàññìîò- b2 B := ∅ è B := ∅. Äëÿ îïðåäåë¼ííîñòè áóäåì èìåíîâàòü èõ ðåêîðäíûìè. Â íèõ áóäóò õðàíèòüñÿ ëó÷øèå ïî ñóììàð- ðåíèå ïàðó ìíîæåñòâ íîìó âåñó íà ìîìåíò ïðîõîæäåíèÿ ïî äåðåâó ïåðåáîðà óïîðÿäî÷åííûå ìíîæåñòâà, ïîñòðîåííûå â ðåçóëüòàòå ðàáîòû àëãîðèòìà. II. Ïðè ñôîðìèðîâàííîì ìíîæåñòâå Ω(1,µ) íåîáõîäèìî ðàññìàòðèâàòü äâà ñëó÷àÿ. A. Åñëè ìíîæåñòâî Ω(1,µ) 6= ∅, òî ñòðîèì (1,µ) D(i,j) (φ) = Ei (φ) ∩ Hj (φ) ∩ Ω(1,µ) , i ∈ Ω(1,µ) , j ∈ Ω(1,µ) , è ìíîæåñòâî âîçìîæíûõ ïðîäîëæåíèé S (1,µ) = {γ = (i, j) ∈ Ω(1,µ) × Ω(1,µ) , i 6= j : {i, j} ⊂ Dγ(1,µ) }. Íà êàæäîì óðîâíå äåðåâà ïåðåáîðà ââîäèì â ðàññìîòðåíèå ïàðó âñïîìîãàòåëüíûõ ìíîæåñòâ 1. Ïðè Ω(1,µ) \F (1,µ) = ∅ Åñëè æå íà ðîëü F (1,µ) := ∅ Q(1,µ) := ∅. ïåðåõîäèì íà ïï.II(A)1a àëãîðèòìà. Ω(1,µ) \F (1,µ) 6= ∅, òî èùåì öåíòðàëüíîãî ýëåìåíòà: ωi∗ = Ïðè÷¼ì, åñëè è ïðåòåíäåíòà max i∗ ∈Ω(1,µ) \F (1,µ) S (1,µ) = Q(1,µ) , i∗ ∈ Ω(1,µ) \F (1,µ) ωi . òî ïåðåõîäèì íà ïï.II(A)1b. S (1,µ) \Q(1,µ) 6= ∅ èùåì î÷åðåäíîãî ïðåβ ∗ = (β1∗ , β2∗ ) ∈ S (1,µ) \Q(1,µ) íà ðîëü óçëîâîãî ýëåìåíòà Â ïðîòèâíîì ñëó÷àå ïðè òåíäåíòà íà µ-ì óðîâíå: h i h i (1,µ) (1,µ) V Dβ ∗ ≥ V Dβ , ∀β ∈ S (1,µ) \Q(1,µ) . Äàëåå ñðàâíèâàåì âåñà ïðåòåíäåíòîâ íà ðîëü óçëîâîãî è öåíòðàëüíîãî ýëåìåíòîâ 10

V h (1,µ) Dβ ∗ i > ωi∗ . (9) Åñëè íåðàâåíñòâî (9) íå âûïîëíÿåòñÿ, òî ïåðåõîäèì íà ïï.II(A)1b. Â ïðîòèâíîì ñëó÷àå ïðè âûïîëíåíèè íåðàâåíñòâà (9) ýëåìåíò ñòàíîâèòñÿ óçëîâûì β (µ) = β ∗ íà β∗ µ-ì óðîâíå ïåðåáîðà, íî òîëüêî ïðè âûïîëíåíèè íåðàâåíñòâà   µ−1 [ V ξ=0 i 1 h i h h i (1,µ) 1 b b2 ,  > {β1 , β2 } + V Dβ ∗ V B +V B 2 (10) èíà÷å ãîâîðÿ, óñïåøíîé ïðîâåðêå íà öåëåñîîáðàçíîñòü äàëüíå- β (0) , β (1) , . . . , β (µ−1) , β ∗ . Ýëåìåíò β ∗ , âûáðàííûé â êà÷åñòâå óçëîâîãî íà µ-ì óðîâíå, çàïîìèíàåì êàê (1,µ) èñïîëüçîâàííûé Q := Q(1,µ) ∪ {β (1,µ) }. Ôîðìèðóåì ìíîæå(1,µ) (1,µ) (1,µ) (1,µ+1) ñòâî Ω = Dβ (1,µ) \{β1 , β2 } è, óâåëè÷èâàÿ íîìåð óðîâíÿ µ := µ + 1, ïåðåõîäèì ïï.II íà àëãîðèòìà. øåãî ïðîäâèæåíèÿ ïî âåòâè Â ñëó÷àå, åñëè íåðàâåíñòâî (10) íå âûïîëíÿåòñÿ , òî ïåðåõîäèì íà ïï.II(A)1a a. Åñëè óðîâåíü äåðåâà ïåðåáîðà íåëåâîé(µ = 0), òî ïåðåõîäèì íà ïï.V àëãîðèòìà(ïåðåáîðíàÿ ÷àñòü àëãîðèòìà çàêîí÷åíà). Ðåêîðäíûå óïîðÿäî÷åííûå ìíîæåñòâà b1 B è b 2, B îïðåäåë¼ííûå íà ýòîò ìîìåíò, è ÿâëÿþòñÿ èñêîìûìè. Â ïðàòèâíîì ñëó÷àå(ïðè (1,µ) b. µ > 0) î÷èùàåì ðàáî÷èå ìíîæåñòâà (1,µ) Ω := ∅, F := ∅ è ,ïîíèæàÿ óðîâåíü µ := µ − 1, ïåðåõîäèì íà ïï.II(A)1. ∗ Ýëåìåíò i ñòàíîâèòñÿ öåíòðàëüíûì íà µ-ì äåðåâà ïåðåáîðà óðîâíå ïåðåáîðà òîëüêî ïðè âûïîëíåíèè íåðàâåíñòâà  ωi∗ + V   µ−1 [ (ξ) (ξ) {β1 , β2 } ξ=0 h i 1 h b 1i b2 V B +V B > 2 Â ñëó÷àå, åñëè ñïðàâåäëèâî (11), ýëåìåíò i∗ âêëþ÷àåì â ñïè- ñîê èñïîëüçîâàííûõ â êà÷åñòâå öåíòðàëüíûõ íà F (1,µ) := F (1,µ) ∗ ∪ {i }, (11) µ-ì óðîâíå à çàòåì ñòðîèì óïîðÿäî÷åííîå ìíîæå11

B 1 . Êîëè÷åñòâî ýëåìåíòîâ ìíîæåñòâà B 1 = {i1 , i2 , . . . , ik } íå÷¼òíî (k = 2µ + 1) è ñôîðìèðîâàíî ïî ïðàâèëó ñòâî (ξ) (ξ) iξ+1 = β1 , ik−ξ = β2 , ξ = 0, 1, . . . , µ − 1, iµ+1 = i∗ Ïîñëå ïîñòðîåíèÿ ìíîæåñòâà (12) B 1 ïîäíèìàåìñÿ ââåðõ ïî äåðåâó ïåðåáîðà äëÿ ïîñòðîåíèÿ âòîðîãî óïîðÿäî÷åííîãî ìíîæåñòâà B 2, ïåðåõîäÿ íà ïï.III àëãîðèòìà. Â ñëó÷àå áåñïåðñïåêòèâíî- ñòè ïðîäâèæåíèÿ ïî ýòîé âåòâè (íåðàâåíñòâî(11) íå âûïîëíÿåòñÿ) ïåðåõîäèì íà ïï.II(A)1a. Ω(1,µ) = ∅, µ > 0, òî ïîñòðîåíèå âîçìîæíîãî 1 âàðèàíòà óïîðÿäî÷åííîãî ìíîæåñòâà B = {i1 , . . . , ik } çàêîí÷åíî. Îíî áóäåò ñîäåðæàòü k = 2µ ýëåìåíòîâ, êîòîðûå îïðåäåëÿþòñÿ ïî (ξ) (ξ) ïðàâèëó: iξ+1 = β1 , ik−ξ = β2 , ξ = 0, 1, . . . , µ − 1. Äëÿ ïîñòðî2 åíèÿ âòîðîãî óïîðÿäî÷åííîãî ìíîæåñòâà B ïåðåõîäèì íà ïï.III B. Åñëè ìíîæåñòâî ïðè ðàññìàòðèâàåìîãî àëãîðèòìà. Åñëè ìíîæåñòâî Ω(1,µ) = ∅, ïðè µ = 0, òî â ðàìêàõ ðàññìàòðè- âàåìûõ ïðåîáðàçîâàíèé íå ñóùåñòâóåò ïåðåñòàíîâêè, ïðèâîäÿùåé ñèñòåìó ê íóæíîìó âèäó. III. Ïåðåáîð ïðè ðåøåíèè çàäà÷è 1 íà÷èíàåòñÿ ñ ýòîãî ïóíêòà àëãîðèòìà. Ïðè÷¼ì ïîëàãàåì èìåííî â ýòîì ñëó÷àå b 1 := ∅, B b 2 := ∅. B 1 := ∅, B çàäà÷è 1,2 ñòðîèì ìíîæåñòâî Ω(2,0) = Ω(1,0) \B 1 ïðè ñôîð1 ìèðîâàííîì óïîðÿäî÷åííîì ìíîæåñòâå B . Ââîäèì âñïîìîãàòåëüíîå (2,0) ìíîæåñòâî Q = ∅. Çíà÷åíèå íîìåðà óðîâíÿ íà âòîðîì äåðåâå ïåðåáîðà ïîëàãàåì ν = 0. Äëÿ ðåøåíèÿ IV. Ïðè ñôîðìèðîâàííîì ìíîæåñòâå Ω(2,ν) íåîáõîäèìî ðàññìàòðèâàòü äâà ñëó÷àÿ. A. Åñëè ìíîæåñòâî Ω(2,ν) 6= ∅, òî ñòðîèì ìíîæåñòâà (2,ν) D(i,j) (φ) = Ei (φ) ∩ Hj (φ) ∩ Ω(2,ν) , i ∈ Ω(2,ν) , j ∈ Ω(2,ν) , S (2,ν) íà ν -ì øàãå àëãîðèòìà α(0) , α(1) , . . . , α(ν−1) : è ìíîæåñòâî âîçìîæíûõ ïðîäîëæåíèé ïðè âûáðàííûõ óçëîâûõ ýëìåíòàõ S (2,ν) = {γ = (i, j) ∈ Ω(2,ν) × Ω(2,ν) , i 6= j : {i, j} ⊂ Dγ(2,ν) }. Ω(2,ν) íàõîäèì ωj ∗ = maxi∈Ω(2,ν) ωi . Ïðè÷¼ì íà êàæäîì óðîâíå ïðè îáíîâëåíèè äåíòà j ∗ íà ðîëü öåíòðàëüíîãî 12 ïðåòåí-

1. Ïðè ðàññìîòðåíèè ïîñòðîåííîãî ìíîæåñòâà S (2,ν) íåîáõîäèì ðàñ- ñìàòðèâàòü äâà ñëó÷àÿ. S (2,ν) \Q(2,ν) = ∅, òî ïåðåõîäèì íà ïï.IV(A)1c. Â ïðîòèâ(2,ν) íîì ñëó÷àå, ïðè S \Q(2,ν) 6= ∅ èùåì ïðåòåíäåíòà íà ðîëü óç(2,ν) ëîîãî ýëåìåíòà α ∈ S \Q(2,ν) . Ñðåäè íå ðàññìàòðèâàâøèõñÿ ðàíåå â êà÷åñòâå óçëîâûõ íà ν -ì øàãå åìó îòâå÷àåò ìíîæåñòâî Dα∗ , èìåþùåå íàèáîëüøèé âåñ: a. Åñëè V [Dα∗ ] = max α∈S (2,ν) \Q(2,ν) V [Dα ] . Äàëåå ïðîâîäèì ñðàâíåíèå âåñîâ: V [Dα∗ ] > ωj ∗ . Åñëè íåðàâåíñòâî (13) íå (13) âûïîëíÿåòñÿ, òî ïåðåõîäèì íà ïï.IV(A)1c. Â ïðîòèâíîì ñëó÷àå, íåîáõîäèìî ïðîâåñòè ïðîâåðêó íà öåëåñîîáðàçíîñòü (0) äàëüíåéøåãî (1) (ν−1) ïðîäâèæåíèÿ ïî âåòâè ∗ α ,α ,...,α , α . Åñëè íåðàâåíñòâî   ν−1 h i 1 h i h i [ 1 (ξ) (ξ)  (2,ν) 1 b b2  V B +V {α1 , α2 } +V Dα∗ > V B +V B 2 ξ=0 (14) íå âûïîëíÿåòñÿ, òî ïåðåõîäèì íà ïï.IV(A)1b. Ïðè âûïîëíåíèè íåðàâåíñòâ (14) ýëåìåíò âûì: α (ν) =α ∗ íà ν -ì α∗ ñòàíîâèòñÿ óçëî- óðîâíå àëãîðèòìà. Äëÿ ïåðåõîäà íà ñëåäóþùèé âåðõíèé óðîâåíü äåðåâà ïåðåáîðà äîïîëíÿåì ìíîæåñòâî èñïîëüçîâàííûõ â êà÷åñòâå óçëî- Q(2,ν) := Q(2,ν) ∪ {α(ν) }, ôîðìèðóåì ìíîæåñòâî (2,ν) (ν) (ν) Ω(2,ν+1) = Dα(ν) \{α1 , α2 }. Çàòåì, óâåëè÷èâàÿ íîìåð óðîâíÿ (2,ν) (ν := ν+1) è ââîäÿ ìíîæåñòâî Q := ∅, ïåðåõîäèì íà ïï.IV. Ïðè ν > 0 íåîáõîäèìî âåðíóòüñÿ íà ïðåäûäóùèé (íèæíèé) (2,ν) óðîâåíü. Äëÿ ýòîãî î÷èùàåì ìíîæåñòâî Q := ∅, óìåíüøàåì íîìåð óðîâíÿ âòîðîãî äåðåâà ïåðåáîðà íà åäèíèöó (ν := ν − 1) è ïåðåõîäèì ïï.IV(A)1 äàííîãî àëãîðèòìà. âûõ ýëåìåíòîâ b. Åñëè æå ν = 0, òî ðàáîòà àëãîðèòìà ïî ïîèñêó íàèëó÷øåãî óïîðÿäî÷åííîãî ìíîæåñòâà 13 B2 ïðè ôèêñèðîâàííîì B1 çàêîí-

÷åíà. Ïðè ðåøåíèè çàäà÷è 1 íàéäåííîå ðåêîðäíîå ìíîæåñòâî b2 B è åñòü èñêîìîå. Äëÿ ïðîäîëæåíèÿ ðåøåíèÿ ýòîé çàäà÷è òðåáóåòñÿ ïåðåéòè íà ïï.V àëãîðèòìà. Ïðè ðåøåíèè çàäà÷è 2 íåîáõîäèìî ïåðåéòè íà ïï.II(A)1 äëÿ ïîñòðîåíèÿ íîâîãî óïîðÿäî÷åííîãî ìíîæåñòâà c. Ýëåìåíò j∗ ñòàíîâèòñÿ öåíòðàëüíûì íà ν -ì b 1. B óðîâíå ïåðåáîðà òîëüêî ïðè âûïîëíåíèè íåðàâåíñòâà  V B 1 + ωj ∗ + V  ν−1 [  (ξ) (ξ) {α1 , α2 } h i h i 1 b b2 >V B +V B (15) ξ=0 Â ýòîì ñëó÷àå íåîáõîäèìî ñôîðìèðîâàòü óïîðÿäî÷åííîå ìíî- B 2 = {i1 , i2 , . . . , ik }. Êîëè÷åñòâî åãî ýëåìåíòîâ íå÷¼òíî (k = 2ν + 1) è îïðåäåëÿåòñÿ ïî ïðàâèëó æåñòâî (ξ) (ξ) iξ+1 = α1 , ik−ξ = α2 , ξ = 0, 1, . . . , ν − 1; iν+1 = j ∗ . Ïðè ñôîðìèðîâàííîì B2 íåîáõîäèìî ïåðåéòè íà ïï.IV(B)1A. Åñëè æå íåðàâåíñòâî (15) íå âûïîëíÿåòñÿ, òî ïåðåõîäèì íà ïï.IV(A)1b. B. Åñëè ìíîæåñòâî Ω(2,ν) = ∅, òî âîçìîæíû äâà ñëó÷àÿ. ν 6= 0 ïðîõîä B = {i1 , i2 , . . . , ik } áóäåò 1. Ïðè ïî 2 ýòîé ñîäåðæàòü îïðåäåëÿþòñÿ ïî ïðàâèëó iξ+1 = âåòâè çàêîí÷åí. Ïðè÷¼ì k = 2ν ýëåìåíòîâ,êîòîðûå (ξ) = α2 , ξ = 0, 1, . . . , (ξ) α1 , ik−ξ ν − 1. A. Ñëåäóåò ïðîâåñòè çàìåíó ðåêîðäíûõ óïîðÿäî÷åííûõ ìíîæåñòâ b 1 := B 1 B è b 2 := B 2 . Ïðè÷¼ì, åñëè ñïðàâåäëèâî B h i h i h i 1 2 (1,0) b b V B +V B =V Ω , ðàâåíñòâî (16) òî ïåðåáîð çàêîí÷åí, òàê êàê ñóììà âåñîâ íàéäåííûõ óïîðÿäî÷åííûõ ìíîæåñòâ èìååò ìàêñèìàëüíî âîçìîæíûé âåñ. Â ýòîì ñëó÷àå íåîáõîäèìî ïðèñòóïèòü ê âûïîëíåíèþ ñëåäóþùåãî ýòàïà àëãîðèòìà - ïï.V. Åñëè ðàâåíñòâî (16) íå âûïîëíÿåòñÿ, òî ñëåäóåò ïðîäîëæèòü ïåðåáîð. Äëÿ ýòîãî íàäî ïåðåéòè íà ïï.IV(A)1b. 2. Ïðè ν =0 íà ìíîæåñòâå Im \B 1 14 íå ñóùåñòâóåò óïîðÿäî÷åííîãî

B 2 ñ çàäàííûìè ñâîéñòâàìè. Ïðè B 1 6= ∅ b 1 = B 1 , B 2 = ∅.Ïîñëå ýòîãî ïåðåõîäèì ðåêîðäíûìè ñòàíîâÿòñÿ B íåïóñòîãî ìíîæåñòâà íà ïï.V. Çàìå÷àíèå 1 Ýëåìåíòû ëþáîãî óïîðÿäî÷åííîãî ìíîæåñòâà B s = {i1 , i2 , . . . , ik }, s = 1, 2, ïîñòðîåííîãî ïî ïï.I-IV äàííîãî àëãîðèòìà, óäîâëåòâîðÿþò óñëîâèþ (7) òåîðåìû 1. Çàìå÷àíèå 2 Äëÿ ëþáîãî óïîðÿäî÷åííîãî ìíîæåñòâî B s = {i1 , i2 , . . . , ik }, s = 1, 2, ïîñòðîåííîãî ïî ïï.I-IV, ìîæíî ïðîâåñòè ðàçáèåíèå íà êëàññû. i1 ∈ ω1 . Ýëåìåíò i2 áóäåò ïðèàäëåæàòü ìíîæåñòâó ω1 , åñëè i1 ∈ Ei2 (φ). Åñëè æå i1 ∈ / Ei2 (φ), òî ω1 = {i1 } è i2 ∈ ω2 . Äëÿ ýòîãî ïîëàãàåì, ÷òî {i1 , i2 } ⊂ ω1 . Òîãäà, åñëè {i1 , i2 } ⊂ Ei3 (φ), {i1 , i2 } 6⊂ Ei3 (φ)) i3 ∈ ω2 . Ïðåäïîëîæèì, ÷òî ω1 , èíà÷å (åñëè V. Ðóêîâîäñòâóÿñü ïðàâèëîì çàìå÷àíèÿ 2 òî i3 ∈ ïðîâåä¼ì ïîî÷åð¼äíî ðàçáèå- íèå ðåêîðäíûõ ìíîæåñòâ íà êëàññû. Ñíà÷àëà ñäåëàåì ýòî óïîðÿäî÷åí- b2 ≡ B b 1 (ωl+1 , ωl+2 , . . . , ωn ). B íîãî ìíîæåñòâà b 2 (ω1 , ω2 , . . . , ωl ), B à çàòåì äëÿ b1 B ≡ Çàìå÷àíèå 3 Ðåçóëüòàòîì ðàáîòû àëãîðèòìà ÿâëÿåòñÿ ïîñòðîå- íèå äâóõ âçàèìíî íåïåðåñåêàþùèõñÿ ýëåìåíòíûõ íóëü-ñòðóêòóðíûõ b 1, B b 2 ïàðû, èìåþùåé ìàêñèìàëüíûé ñóììàðíûé âåñ. îñíîâàíèé B Çàìå÷àíèå 4 Ðóêîâîäñòâóÿñü óòâåðæäåíèÿìè òåîðåìû 2 (äëÿ ðå- øåíèÿ çàäà÷è 1) è òåîðåìû 3 (äëÿ ðåøåíèÿ çàäà÷è 2), äëÿ ëþáîé ïàðû Bφ1 (ωl+1 , ωl+2 , . . . , ωn ) è Bφ2 = (ω1 , ω2 , . . . , ωl ) ýëåìåíòíûõ íóëüñòðóêòóðíûõ îñíîâàíèé (ïîëó÷åííîé â ðåçóëüòàòå ðàáîòû ïï.I-IV àëãîðèòìà) ìîæíî ïîñòðîèòü ïåðåñòàíîâêó π ∈ P , íà êîòîðîé ÑÎm ÄÓ (5) èìååò íóëü-ñòðóêòóðó ZSπφ [l, n, r], l ∈ N . Äëÿ ýòîãî íåîáõîäèìî ïåðåíóìåðîâàòü ýëåìåíòû êëàññîâ ωs = gδ(r,s) , . . . , gδ(r,s)+rs , rs = |ωs |, s = 1, . . . , n, ýëåìåíòíûõ íóëü-ñòðóêòóðûõ îñíîâàíèé (ω1 , ω2 , . . . , ωl ) Bφ1 (ωl+1 , ωl+2 , . . . , ωn ) è ìíîæåñòâà ω0 = Im \(B 1 ∪ B 2 ) = {g1 , . . . , gr0 }, ãäå r0 = |ω0 |. Ïîñëå ýòîãî èñêîìàÿ ïåðåñòàíîâêà èìååò âèä 15 è Bφ2 =

1 2 . . . r0 r0 + 1 . . . g1 g2 . . . gr0 gδ(r,1)+1 . . . . . . δ(r, l + 1) δ(r, l + 1) + 1 . . . m . . . . hδ(r,l+1) gδ(r,l+1)+1 . . . gδ(r,n+1) π= Ïîêàæåì, ÷òî íèé 1 B ,B 2 m ZSπφ [l, n, r] äëÿ ëþáîé ïàðû íóëü-ñòðóêòóðíûõ îñíîâà- , ñôîðìèðîâàííîé ïï.I-IV àëãîðèòìà, ÿâëÿåòñÿ ïðåäåëüíîé. çàìå÷àíèåì 4, íà áàçå ðåêîðäíûõ ýëåìåíòíûõ íóëüb 1, B b 2 ñòðîèì èñêîìóþ ïåðåñòàíîâêó π ∗ , êîñòðóêòóðíûõ îñíîâàíèé B òîðàÿ ÿâëÿåòñÿ ðåøåíèåì çàäà÷ 1 èëè 2. VI. Ðóêîâîäñòâóÿñü Îòäåëüíî ñëåäóåò îòìåòèòü,÷òî äëÿ èñïîëüçîâàíèÿ àëãîðèòìà ïðè ðåøåíèè çàäà÷ 1 íåîáõîäèìî ñ÷èòàòü ïîñòîÿííî B1 = ∅ è b 1 = ∅. B Íà- ÷àòü ðàáîòó àëãîðèòìà ñëåäóåò ñ ïï.III è îãðàíè÷èòü òîëüêî ïåðåáîðîì ïî âåðõíåìó äåðåâó, ò.å òðåáîâàíèå ñïóñòèòüñÿ ïî äåðåâó ïåðåáîðà íà ïîèñê íîâîãî óïîðÿäî÷åííîãî ìíîæåñòâà äà÷ 1) B 1 îçíà÷àåò(ïðè ðåøåíèè çà- îêîí÷àíèå ïåðåáîðà ñ ïåðåõîäîì íà ïï.V. 16

Ïñåâäîêîä Ω(1,0) = i ∈ Im : i ∈ Ei (φ) F (1,0) ← ∅ Q(1,0) ← ∅ b1 ← ∅ B b2 ← ∅ B µ←0 A1() function A1 if Ω 6= ∅ then () (1,µ) (1,µ) D(i,j) ← Ei (φ) ∩ Hj (φ) ∩ Ω(1,µ) , i, j ∈ Ω(1,µ) (1,µ) S (1,µ) ← {γ = (i, j) ∈ Ω(1,µ) , i 6= j : {i, j} ⊂ Dγ B1() (φ)} else if µ = 0 then else Êîíåö ïåðåáîðà k ← 2µ B 1 = {i1 , . . . , ik } m = 0, 1, . . . , µ − 1 (m) im+1 ← β1 (m) ik−m ← β2 for do end for µ←µ−1 L1() end if end if end function function B1 if F 6= Ω then ω = max ω : i , i ∈ Ω if S 6= Q then () (1,µ) (1,µ) ∗ i (1,µ) i∗ (1,µ) (1,µ) (1,µ) (1,µ) V [Dβ ∗ ] = max V [Dβ if V [D ] > ω then if V [D ] + V [S (1,µ) β∗ (1,µ) β∗ (1,µ) Q \F (1,µ) ]; β ∗ , β ∈ S (1,µ) \Q(1,µ) i∗ (m) (m) µ−1 m=0 {β1 , β2 }] (1,µ) ∗ ←Q ∪ {β } 17 b 1 ] + V [B b 2 ])/2 > (V [B then

β (µ) ← β ∗ = (β1∗ , β2∗ ) (1,µ) Ω(1,µ+1) ← Dβ ∗ \{β1∗ , β2∗ } A1() else D1 end if else C1 end if else C1 end if else C1 end if end function function C1 S if ω + V [ {β () () () () () (m) (m) µ−1 1 , β2 }] m=0 (1,µ) ∗ i∗ F (1,µ) ←F ∪ {i } k = 2µ + 1 B 1 = {i1 , . . . , ik } m = 0, . . . , µ − 1 (m) im+1 ← β1 (m) ik−m ← β2 for b 1 ] + V [B b 2 ])/2 > (V [B do end for L1() else D1 end if end function function D1 if µ 6= 0 then () () F (1,µ) ← ∅ Q(1,µ) ← ∅ µ←µ−1 B1() else 18 then

Êîíåö ïåðåáîðà end if end function function L1 () (2,0) Ω = {i ∈ Im \}B 1 : i ∈ Ei (φ)} ν←0 Q(2,0) ← ∅ X1() end function function X1 if thenΩ () (2,ν) (2,ν) D(i,j) (2,ν) 6 ∅ = ← Ei (φ) ∩ Hj (φ) ∩ Ω(2,ν) , i, j ∈ Ω(2,ν) (2,ν) S ← {γ = (i, j) ∈ Ω(2,ν) , i 6= j : {i, j} ⊂ Dγ (2,ν) ωi∗ = max ωi : i ∈ Ω(2,ν) Y1() else if ν = 0 then b 1 | = |Ω(1,0) | |B b2 ← ∅ B Êîíåö ïåðåáîðà else k = 2ν B 2 = {i1 , . . . , ik } m = 0, 1, . . . , ν − 1 (m) im+1 = α1 (m) ik−m = α2 for do end for b1 ← B1 B b2 ← B2 B b 1 ] + V [B b 2 ] = V [Ω(1,0) ] V [B if else V1 end if end if end if end function function Y1 Êîíåö ïåðåáîðà () () 19 then (φ)}

if S then (2,ν) \Q(2,ν) 6= ∅ (2,ν) (2,ν) V [Dα∗ = max V [Dα ] : α∗ , α ∈ S (2,ν) \Q(2,ν) (2,ν) (2,ν) V [Dα∗ > ωi∗ S (2,ν) (m) (m) b1 b2 V [B 1 ]+V [Dα∗ ]+V [ ν−1 m=0 {α1 , α2 }] > V [B ]+V [B ] Q(2,ν) ← Q(2,ν) ∪ {α∗ } α(ν) ← α∗ = (α1∗ , α2∗ ) (2,ν) Ω(2,ν+1) ← Dα∗ \{α1∗ , α2∗ } ν ←ν+1 Q(2,ν) ← ∅ X1() if then if else V1 end if else P1 end if else V1 end if end function function P1 if V [B ] + V [ω then () () () () 1 (2,ν) α∗ ] S (m) (m) b1 b2 + V [ ν−1 m=0 {α1 , α2 }] > V [B ] + V [B ] k = 2ν + 1 B 2 = {i1 , . . . , ik } m = 0, 1, . . . , ν − 1 (m) im+1 = α1 (m) ik−m = α2 for do end for iν+1 = i∗ b1 ← B1 B b2 ← B2 B b 1 ] + V [B b 2 ] = V [Ω(1,0) ] V [B if else V1 end if else end if end function Êîíåö ïåðåáîðà then () 20 then

function V1 if ν 6= 0 then () Q(2,ν) ← ∅ ν ←ν−1 Y1() else B1 end if end function () 21

Ïðèìåð ïðèìåíåíèÿ àëãîðèòìà Ïðè ðàññìîòðåíèè êðóïíîìàñøòàáíûõ êîëåáàíèé ðîòàöèîíî ñèììåòðè÷íûõ ñèñòåì çàäà÷à ñâîäèòñÿ ê èíòåãðèðîâàíèþ ñèñòåìû: x d2 x = K − 3 , dt2 (2x + z) 2 d2 z z = L − 3 , dt2 (2x + z) 2 dK 1 dx =− , 3 dt (2x + z) 2 dt 1 dz dL =− , 3 dt (2x + z) 2 dt (17) ãäå x áåçðàçìåðíûé ìîìåíò èíåðöèè ñèñòåìû îòíîñèòåëüíî îñè âðà- z áåçðàçìåðíûé ìîìåíò èíåðöèè îòíîñèòåëüíî ýêâàòîðèàëüíîé ùåíèÿ; K êèíåòè÷åñêàÿ ýíåðãèÿ äâèæåíèé ïàðàëëåëüíî ýêâàòîðèàëü- íîé ïëîñêîñòè; L êèíåòè÷åñêàÿ ýíåðãèÿ äâèæåíèé â âåðòèêàëüîì íàïðàâ- ïëîñêîñòè; ëåíèè. Èñïîëüçîâàíèå íîâûõ ïåðåìåííûõ K, y6 = L y1 = x, y2 = x0 , y3 = z, y4 = z 0 , y5 = ïîçâîëÿåò ïðèâåñòè ñèñòåìó (17) ê âèäó: y10 = y2 = φ1 (t, y2 ), y20 = φ2 (t, y1 , y3 , y5 ), y30 = y4 = φ3 (t, y4 ), y40 = φ4 (t, y1 , y3 , y6 ), y50 = φ5 (t, y1 , y2 , y3 ), y60 = φ6 (t, y1 , y3 , y4 ). (18) Ñòðóêòóðàÿ ìàòðèöà ñèñòåìû (18):     A(φ) =     Òàê êàê ìíîæåñòâî åò ïåðåñòàíîâêà π∗, 0 1 0 1 1 1 1 0 0 0 1 0 0 1 0 1 1 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0     .    (19) Ω(1,0) = {1, 2, 3, 4, 5, 6} íå ïóñòî, òî íà Ip ñóùåñòâó- ñîãëàñíî êîòîðîé äëèíà ïðåäåëüíîé íóëü-ñòðóêòóðû 22

|ZSπp∗ φ [l, n, r]| > 0 (âåñîâûå áîé: ω1 = · · · = ω6 = 1). êîýôôèöèåíòû ïîëàãàåì ðàâíûìè ìåæäó ñî- Äëÿ ñòàðòà àëãîðèòìà ïîñòðîèì ãîðèçîíòàëüíûå è âåòðèêàëüíûå ìíîæåñòâà: E1 (F ) = {1, 3, 4, 5, 6}, E2 (F ) = {2, 4, 6}, E3 (F ) = {1, 2, 3, 5, 6}, E4 (F ) = {2, 4, 5}, E5 (F ) = {4, 5, 6}, E6 (F ) = {2, 5, 6}, H1 (F ) = {1, 3}, H2 (F ) = {2, 3, 4, 5, 6}, H3 (F ) = {1, 3}, H4 (F ) = {1, 2, 4, 5}, H5 (F ) = {1, 3, 4, 5, 6}, H6 (F ) = {1, 2, 3, 5, 6}. Äàëåå ñòðîèì ìíîæåñòâà (1,0) D(i,j) = Ei (F ) ∩ Hj (F ) ∩ Ω(1,0) , i, j ∈ Ω(1,0) , i 6= j è ðàñïîëîæèì èõ â ïîðÿäêå óáûâàíèÿ ìîùíîñòåé: (1,0) D1,5 (1,0) D1,6 (1,0) D4,2 (1,0) D2,4 (1,0) D4,5 (1,0) D6,5 = {1, 3, 4, 5, 6}, = {1, 3, 5, 6}, = {2, 4, 5}, = {2, 4}, = {4, 5}, = {6, 5}. (1,0) D3,5 (1,0) D3,2 (1,0) D6,2 (1,0) D2,6 (1,0) D5,4 = {1, 3, 5, 6}, = {2, 3, 5, 6}, = {2, 5, 6}, = {2, 6}, = {5, 4}, (1,0) D3,6 (1,0) D1,4 (1,0) D1,3 (1,0) D3,1 (1,0) D5,6 = {1, 2, 3, 5, 6}, = {1, 4, 5}, = {1, 3}, = {1, 3}, = {5, 6}, Âûïèøåì ìíîæåñòâî âîçìîæíûõ ïðîäîëæåíèé íóëåâîãî øàãà (óðîâíÿ): S (1,0) = {(1, 5), (3, 5), (3, 6), (1, 6), (3, 2), (1, 4), (4, 2), (6, 2), (1, 3), (2, 4), (2, 6), (3, 1), (4, 5), (5, 4), (5, 6), (6, 5)} Äàëüøå ïðîõîä ïî äåðåâó áóäåì âåñòè ñõåìàòè÷íî: µ = 0, β (0) = (1, 5) =⇒ (1,0) (0) (0) µ = 1, Ω(1,1) = Ω(1,0) ∩ D(1,5) \{β1 , β2 } = {3, 4, 6}, S (1,1) = {(3, 6)}, β (1) = (3, 6) =⇒ Ω(1,2) = ∅ =⇒ B 1 = {1, 3, 6, 5}, Ω(2,0) = Ω(1,0) \B 1 = {2, 4}, ν = 0, S (2,0) = {(4, 2), (2, 4)}, α(0) = (4, 2) =⇒ Ω(2,1) = ∅ b 1 | + |B b 2 | =⇒ =⇒ B 2 = {4, 2}, |B 1 | + |B 2 | = 6 > |B b 1 = B 1 = {1, 3, 6, 5}, B b 2 = B 2 = {4, 2}. B 23

Çàòåì ïåðåõîäèì ê ïóíòêó V àëãîðèòìà(ðàçáèåíèþ íà êëàññû). 1. Ïîëàãàåì, ÷òî {1} ∈ ω1 , è òàê êàê {1} ∈ E3 , òî ω1 = {1, 3}. {1, 3} ∈ ω1 , íî {1, 3} 6∈ E6 (F ), è çíà÷èò ω2 = {6}. {6} ∈ ω2 , è 6 ∈ b 1 (ω1 , ω2 ) = {1, 3, 6, 5}, |ω1 | = E5 (F ), è çíà÷èò ω2 = {6, 5}. Òàêèì îáðàçîì, B |ω2 | = 2. Äàëåå b 2 : {4} ∈ ω3 , è òàê êàê{4} ∈ E2 (F ), B b 2 (ω3 ) = {4, 2}, |ω3 | = 2. B 2. Àíàëîãè÷íî ïðîèçâîäèì ðàçáèåíèå òî ω3 = {4, 2}. Òàêèì îáðàçîì, Òåïåðü â ñîîòâåòñòâèè ñ ∗ π = (1, 3, 6, 5, 4, 2), çàìå÷àíèåì 4 ìîæíî ïîñòðîèòü ïåðåñòàíîâêó íà êîòîðîé ÑÎÄÓ (π ∗ z)0 = πφ(x, π ∗ z) èìååò íóëü-ñòðóêòóðó 6 [2, 3, r], r = (0, 2, 2, 2). ZSπ∗φ Îíà ÿâëÿåòñÿ ïðå- äåëüíîé. Äåéñòâèòåëüíî, èñïîëüçóÿ äàííóþ ïåðåñòàíîâêó, ïîñëå ïåðåáîðà çíà÷åíèÿ ξ1 = x, ξ2 = z, ξ3 = L, ξ4 = K, ξ5 = z 0 , ξ6 = x0 . èñõîäíàÿ ñèñòåìà ïåðâîãî ïîðÿäêà ïðèìåò âèä ξ10 ξ20 ξ30 ξ40 ξ50 ξ60 = ξ1 = φ1 (t, ξ6 ), = ξ3 = φ3 (t, ξ5 ), = φ6 (t, ξ1 , ξ2 , ξ5 ), = φ5 (t, ξ1 , ξ2 , ξ6 ), = φ4 (t, ξ1 , ξ2 , ξ3 ), = φ2 (t, ξ1 , ξ2 , ξ4 ), (20) à å¼ ñòðóêòóðíàÿ ìàòðèöà     ∗ A(π φ) =     0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 0 0     .    (21) Òàêèì îáðàçîì, âûäåëåíû 2 ãðóïïû óðàâåíåíèé, èìåþùèõ íóëü-ñòðóêòóðó (îáùàÿ ãðóïïà îòñóòñòâóåò). 24

Èñïîëüçóåìûå òåõíîëîãèè Îñíîâíûå èñïîëüçóåìûå òåõíîëîãèè äëÿ ïðîãðàììíîé ðåàëèçàöèè îáùåå: REST, Êîìïîíåíòíî-îðèåíòèðîâàííîå ïðîãðàììèðîâàíèå, ñåðâåð: C#, ASP.NET Web-API, êëèåíò: HTML, JavaScript, CSS, jQuery, AJAX. C# C# (ïðîèçíîñèòñÿ ¾ñè øàðï¿) îáúåêòíî-îðèåíòèðîâàííûé ÿçûê ïðîãðàììèðîâàíèÿ. Ðàçðàáîòàí â 19982001 ãîäàõ ãðóïïîé èíæåíåðîâ ïîä ðóêîâîäñòâîì Àíäåðñà Õåéëñáåðãà â êîìïàíèè Microsoft êàê ÿçûê ðàçðàáîòêè ïðèëîæåíèé äëÿ ïëàòôîðìû Microsoft .NET Framework. C# îòíîñèòñÿ ê ñåìüå ÿçûêîâ ñ C-ïîäîáíûì ñèíòàêñèñîì, èç íèõ åãî ñèíòàêñèñ íàèáîëåå áëèçîê ê C++ è Java. ßçûê èìååò ñòàòè÷åñêóþ òèïèçàöèþ, ïîääåðæèâàåò ïîëèìîðôèçì, ïåðåãðóçêó îïåðàòîðîâ (â òîì ÷èñëå îïåðàòîðîâ ÿâíîãî è íåÿâíîãî ïðèâåäåíèÿ òèïà), äåëåãàòû, àòðèáóòû, ñîáûòèÿ, ñâîéñòâà, îáîáù¼ííûå òèïû è ìåòîäû, èòåðàòîðû, àíîíèìíûå ôóíêöèè ñ ïîääåðæêîé çàìûêàíèé, LINQ, èñêëþ÷åíèÿ, êîììåíòàðèè â ôîðìàòå XML. ASP.NET Web-API ASP.NET Web-API ôóíêöèÿ ïëàòôîðìû ASP.NET, ïîçâîëÿþ- ùàÿ ëåãêî è áûñòðî ñîçäàâàòü âåá-ñëóæáû, êîòîðûå ïðåäîñòàâëÿþò API äëÿ HTTP-êëèåíòîâ (èçâåñòíûå êàê Web API). Ôóíêöèÿ Web API èìååò òó æå îñíîâó, ÷òî è îáû÷íûå ïðèëîæåíèÿ MVC Framework, íî íå ÿâëÿåòñÿ ÷àñòüþ MVC. Microsoft äóáëèðîâàëà íåêîòîðûå êëþ÷åâûå êëàññû è õàðàêòåðèñòèêè, ñâÿçàííûå ñ ïðîñòðàíñòâîì èìåí System.Web.Mvc, â ïðîñòðàíñòâî èìåí System.Web.Http. Òàêèì îáðàçîì, Web API ÿâëÿåòñÿ ÷àñòüþ ÿäðà ïëàòôîðìû ASP.NET è ìîæåò èñïîëüçîâàòüñÿ â äðóãèõ òèïàõ âåá-ïðèëîæåíèé èëè ðàáîòàòü êàê àâòîíîìíûé äâèæîê âåá-ñëóæá. API (èíòåðôåéñ ïðîãðàììèðîâàíèÿ ïðèëîæåíèé, èíòåðôåéñ ïðèêëàä- íîãî ïðîãðàììèðîâàíèÿ) (àíãë. application programming interface) íàáîð 25

ãîòîâûõ êëàññîâ, ïðîöåäóð, ôóíêöèé, ñòðóêòóð è êîíñòàíò, ïðåäîñòàâëÿåìûõ ïðèëîæåíèåì (áèáëèîòåêîé, ñåðâèñîì) èëè îïåðàöèîííîé ñèñòåìîé äëÿ èñïîëüçîâàíèÿ âî âíåøíèõ ïðîãðàììíûõ ïðîäóêòàõ. Èñïîëüçóåòñÿ ïðîãðàììèñòàìè ïðè íàïèñàíèè âñåâîçìîæíûõ ïðèëîæåíèé. HTML HTML (îò àíãë. HyperText Markup Language ¾ÿçûê ãèïåðòåêñòî- âîé ðàçìåòêè¿) ñòàíäàðòíûé ÿçûê ðàçìåòêè äîêóìåíòîâ âî Âñåìèðíîé ïàóòèíå. ßçûê HTML èíòåðïðåòèðóåòñÿ áðàóçåðàìè; ïîëó÷åííûé â ðåçóëüòàòå èíòåðïðåòàöèè ôîðìàòèðîâàííûé òåêñò îòîáðàæàåòñÿ íà ýêðàíå ìîíèòîðà êîìïüþòåðà èëè ìîáèëüíîãî óñòðîéñòâà. JavaScript JavaScript ïðîòîòèïíî-îðèåíòèðîâàííûé ñöåíàðíûé ÿçûê ïðî- ãðàììèðîâàíèÿ. ßâëÿåòñÿ ðåàëèçàöèåé ÿçûêà ECMAScript. CSS CSS (àíãë. Cascading Style Sheets êàñêàäíûå òàáëèöû ñòèëåé) ôîðìàëüíûé ÿçûê îïèñàíèÿ âíåøíåãî âèäà äîêóìåíòà, íàïèñàííîãî ñ èñïîëüçîâàíèåì ÿçûêà ðàçìåòêè. jQuery jQuery áèáëèîòåêà JavaScript, ôîêóñèðóþùàÿñÿ íà âçàèìîäåé- ñòâèè JavaScript è HTML. Áèáëèîòåêà jQuery ïîìîãàåò ëåãêî ïîëó÷àòü äîñòóï ê ëþáîìó ýëåìåíòó DOM, îáðàùàòüñÿ ê àòðèáóòàì è ñîäåðæèìîìó ýëåìåíòîâ DOM, ìàíèïóëèðîâàòü èìè. Òàêæå áèáëèîòåêà jQuery ïðåäîñòàâëÿåò óäîáíûé API äëÿ ðàáîòû ñ AJAX. DOM (îò àíãë. Document Object Model ¾îáúåêòíàÿ ìîäåëü äîêó- ìåíòà¿) ýòî íå çàâèñÿùèé îò ïëàòôîðìû è ÿçûêà ïðîãðàììíûé èíòåðôåéñ, ïîçâîëÿþùèé ïðîãðàììàì è ñêðèïòàì ïîëó÷èòü äîñòóï ê ñîäåðæèìîìó HTML, XHTML è XML-äîêóìåíòîâ, à òàêæå èçìåíÿòü ñîäåðæèìîå, ñòðóêòóðó è îôîðìëåíèå òàêèõ äîêóìåíòîâ. AJAX AJAX (îò àíãë. Asynchronous Javascript and XML ¾àñèíõðîííûé JavaScript è XML¿) ïîäõîä ê ïîñòðîåíèþ èíòåðàêòèâíûõ ïîëüçîâàòåëüñêèõ èíòåðôåéñîâ âåá-ïðèëîæåíèé, çàêëþ÷àþùèéñÿ â ¾ôîíîâîì¿ îáìåíå 26

äàííûìè áðàóçåðà ñ âåá-ñåðâåðîì. Â ðåçóëüòàòå, ïðè îáíîâëåíèè äàííûõ âåá-ñòðàíèöà íå ïåðåçàãðóæàåòñÿ ïîëíîñòüþ, è âåá-ïðèëîæåíèÿ ñòàíîâÿòñÿ áûñòðåå è óäîáíåå. REST REST (ñîêð. îò àíãë. Representational State Transfer ¾ïåðåäà÷à ñîñòîÿíèÿ ïðåäñòàâëåíèÿ¿) àðõèòåêòóðíûé ñòèëü âçàèìîäåéñòâèÿ êîìïîíåíòîâ ðàñïðåäåë¼ííîãî ïðèëîæåíèÿ â ñåòè. REST ïðåäñòàâëÿåò ñîáîé ñîãëàñîâàííûé íàáîð îãðàíè÷åíèé, ó÷èòûâàåìûõ ïðè ïðîåêòèðîâàíèè ðàñïðåäåë¼ííîé ãèïåðìåäèà-ñèñòåìû. Â îïðåäåë¼ííûõ ñëó÷àÿõ (èíòåðíåòìàãàçèíû, ïîèñêîâûå ñèñòåìû, ïðî÷èå ñèñòåìû, îñíîâàííûå íà äàííûõ) ýòî ïðèâîäèò ê ïîâûøåíèþ ïðîèçâîäèòåëüíîñòè è óïðîùåíèþ àðõèòåêòóðû. Â øèðîêîì ñìûñëå êîìïîíåíòû â REST âçàèìîäåéñòâóþò íàïîäîáèå âçàèìîäåéñòâèÿ êëèåíòîâ è ñåðâåðîâ âî Âñåìèðíîé ïàóòèíå. Â ñåòè Èíòåðíåò âûçîâ óäàë¼ííîé ïðîöåäóðû ìîæåò ïðåäñòàâëÿòü ñîáîé îáû÷íûé HTTP-çàïðîñ (îáû÷íî GET èëè POST; òàêîé çàïðîñ íàçûâàþò REST-çàïðîñ), à íåîáõîäèìûå äàííûå ïåðåäàþòñÿ â êà÷åñòâå ïàðàìåòðîâ çàïðîñà. 27

Êîìïîíåíòíî-îðèåíòèðîâàííîå ïðîãðàììèðîâàíèå Êîìïîíåíò (îò ëàò. ñomponent - ñîñòàâëÿþùèé)- ñîñòàâíàÿ ÷àñòü, ýëåìåíò ÷åãî-ëèáî. Â ïðîãðàììèðîâàíèè êîìïîíåíò ýòî êèðïè÷èê ïðîãðàììû, ñîñòîÿùèé èç òèé ñâîéñòâ (properties), ìåòîäîâ (methods) è ñîáû- (events). Ñâîéñòâà äàþò âîçìîæíîñòü óïðàâëÿòü âèäîì è ïîâåäåíèåì êîìïîíåíòà, ìåòîäû èñïîëüçîâàòü âîçìîæíîñòè, ïðåäîñòàâëÿåìûå êîìïîíåíòîì, à ñîáûòèÿ ðåàãèðîâàòü íà ïðîèñõîäÿùèå âíóòðè êîìïîíåíòà ñîáûòèÿ, ïðîãðàììèðîâàòü ðåàêöèþ êîìïîíåíòà íà âíåøíèå ñîáûòèÿ è ò. ä. Ðàçðàáîòêà ïðîãðàììû ñ ïîìîùüþ êîìïîíåíòîâ íàçûâàåòñÿ êîìïîíåíòíîîðèåíòèðîâàííûì ïðîãðàììèðîâàíèåì. Íà÷íåì ñ îïðåäåëåíèÿ òåðìèíà êîìïîíåíò â ïðîãðàììèðîâàíèè . Êîìïîíåíò ýòî íåçàâèñèìûé ìîäóëü, ïðåäíàçíà÷åííûé äëÿ ìíîãîêðàòíîãî èñïîëüçîâàíèÿ è ïðåäîñòàâëÿåìûé ïîëüçîâàòåëþ â äâîè÷íîì ôîðìàòå. Ýòî îïðåäåëåíèå îïèñûâàåò ÷åòûðå êëþ÷åâûõ õàðàêòåðèñòèêè êîìïîíåíòà. Ðàññìîòðèì èõ ïî î÷åðåäè. Êîìïîíåíò îïðåäåëåí êàê íåçàâèñèìûé ìîäóëü. Ýòî îçíà÷àåò, ÷òî êàæäûé êîìïîíåíò âïîëíå ñàìîäîñòàòî÷åí. Äðóãèìè ñëîâàìè, êîìïîíåíò îáåñïå÷èâàåò ïîëíûé íàáîð ôóíêöèé. Åãî âíóòðåííÿÿ ðàáîòà çàêðûòà äëÿ âíåøíåãî ìèðà, íî ïðè ýòîì ðåàëèçàöèÿ ìîæåò áûòü èçìåíåíà áåç ïîñëåäñòâèé äëÿ êîäà, â êîòîðîì èñïîëüçóåòñÿ ýòîò êîìïîíåíò. Êîìïîíåíò ïðåäíàçíà÷åí äëÿ ìíîãîêðàòíîãî ïðèìåíåíèÿ. Ýòî îçíà- ÷àåò, ÷òî êîìïîíåíò ìîæåò èñïîëüçîâàòü ëþáàÿ ïðîãðàììà, êîòîðîé òðåáóþòñÿ åãî ôóíêöèè. Ïðîãðàììà, êîòîðàÿ èñïîëüçóåò êîìïîíåíò, íàçûâàåòñÿ êëèåíòîì. Òàêèì îáðàçîì, êîìïîíåíò ìîæåò ðàáîòàòü ñ ëþáûì êîëè÷åñòâîì êëèåíòîâ. Êîìïîíåíò ïðåäñòàâëÿåò ñîáîé îòäåëüíûé ìîäóëü. Ýòî î÷åíü âàæ- íî. Ñ òî÷êè çðåíèÿ êëèåíòà êîìïîíåíò âûïîëíÿåò êîíêðåòíóþ ôóíêöèþ èëè íàáîð ôóíêöèé. Ôóíêöèÿìè êîìïîíåíòà, ìîæåò âîñïîëüçîâàòüñÿ ëþáîå ïðèëîæåíèå, íî ñàì êîìïîíåíò íå ÿâëÿåòñÿ àâòîíîìíîé ïðîãðàììîé. Íàêîíåö, êîìïîíåíò äîëæåí áûòü ïðåäñòàâëåí â äâîè÷íîì ôîðìàòå. Ýòî ïðèíöèïèàëüíî âàæíî. Õîòÿ èñïîëüçîâàòü êîìïîíåíò ìîãóò ìíîãèå êëèåíòû, îíè íå èìåþò äîñòóïà ê åãî èñõîäíîìó êîäó. Ôóíêöèîíàëüíîñòü êîìïîíåíòà îòêðûòà äëÿ êëèåíòîâ òîëüêî ïîñðåäñòâîì åãî public-÷ëåíîâ. Äðóãèìè ñëîâàìè, èìåííî êîìïîíåíò óïðàâëÿåò òåì, êàêèå ôóíêöèè îñòàâ28

ëÿòü îòêðûòûìè äëÿ êëèåíòîâ, à êàêèå äåðæàòü ïîä çàìêîì. Êîìïîíåíòíî-îðèåíòèðîâàííàÿ ðàçðàáîòêà èìååò ñâîè ñèëüíûå è ñëàáûå ñòîðîíû. Íåñîìíåííûìè äîñòîèíñòâàìè ÿâëÿåòñÿ ïîâòîðíàÿ èñïîëüçóåìîñòü êîäà, ñîãëàñîâàííîñòü ïîëüçîâàòåëüñêîãî èíòåðôåéñà, âîçìîæíîñòü áûñòðîé è ïðîäóêòèâíîé ðàçðàáîòêè ïðîãðàìì. Èìåííî êîìïîíåíòû ïîçâîëÿþò ïðîãðàììèñòàì ñîñòàâëÿòü êîíå÷íûé ïðîäóêò èç êèðïè÷èêîâ, íå âäàâàÿñü â äåòàëè ðåàëèçàöèè êîíêðåòíîãî êîìïîíåíòà. Êîíå÷íî, íàáîðû êëàññîâ, èñïîëüçóåìûå ïðè îáúåêòíî-îðèåíòèðîâàííîì ïîäõîäå, òîæå äàþò âîçìîæíîñòü ïîâòîðíîãî èñïîëüçîâàíèÿ êîäà, íî êîìïîíåíòû äåëàþò ïîâòîðíîå èñïîëüçîâàíèå êîäà ñîâåðøåííî åñòåñòâåííûì. Åñëè ïðè ðàçðàáîòêå ñèñòåìû âñå ïðîãðàììèñòû êîìàíäû ïîëüçóþòñÿ îäíèì è òåì æå íàáîðîì âèçóàëüíûõ êîìïîíåíòîâ, òî, ñàìî ñîáîé, èíòåðôåéñ ó ïðîãðàììû áóäåò âûïîëíåí â åäèíîì ñòèëå. Áîëåå òîãî, ïîìåíÿâ, íàïðèìåð, âèä îäíîãî èç êîìïîíåíòîâ, ìû èçìåíèì åãî âèä âåçäå, ãäå îí èñïîëüçóåòñÿ. Êîìïîíåíòû äàþò âîçìîæíîñòü íåçàâèñèìîé ðàçðàáîòêè ÷àñòåé èíòåðôåéñà. Èçìåíåíèÿ âíóòðè êîìïîíåíòà íå çàòðàãèâàþò êîä ìîäóëåé, â êîòîðûõ îí èñïîëüçóåòñÿ. Ðàçðàáîòêà íåñêîëüêèõ íåçàâèñèìûõ êëàññîâ äàåò ïðèìåðíî òå æå ðåçóëüòàòû, çà èñêëþ÷åíèåì îäíîé ïðîáëåìû.Ñðåäè ïðîãðàììèñòîâ ñðåäíåé êâàëèôèêàöèè íàáëþäàåòñÿ òåíäåíöèÿ ïåðåìåøèâàòü ôóíêöèîíàëüíîñòü êëàññîâ, ïóòàÿ ìåòîäû îäíîãî êëàññà ñ äðóãèì. Êîìïîíåíòû ðàçäåëÿþò êîä áîëåå êà÷åñòâåííî. Ñâîéñòâà êîìïîíåíòîâ ïîçâîëÿþò íàèáîëåå ýôôåêòèâíî îáúÿñíèòü äðóãîìó ïðîãðàììèñòó, êàê èñïîëüçîâàòü êîìïîíåíò. Ñïåöèàëüíûå ðåäàêòîðû ñâîéñòâ ïîçâîëÿþò áûñòðî íàñòðîèòü âèä è ïîâåäåíèå êîìïîíåíòîâ. Íàêîïèâ äîñòàòî÷íîå êîëè÷åñòâî êîìïîíåíòîâ, ìîæíî äåéñòâèòåëüíî áûñòðî ñîçäàòü âèçóàëüíûé èíòåðôåéñ ïðîãðàììû, ôàêòè÷åñêè, íå íàïèñàâ áîëåå íè ñòðî÷êè êîäà! 29

Îïèñàíèå ñåðâåðíîé ÷àñòè SMethodComponent äàííûé êîìïîíåíò ðåàëèçóåò àëãîðèòì âû- Calculate â êà÷åñòâå ñòðóêòóðíóþ-ìàòðèöó (bool[,]) è ìàññèâ äåëåíèÿ ñòðóêòóðíûõ îñîáåííîñòåé. Îòêðûòûé ìåòîä âõîäíûõ ïàðàìåòðîâ ïðèíèìàåò âåñîâ (double[]). Âîçâðàùàåìûì ðåçóëüòàòîì ôóíêöèè ÿâëÿåòñÿ àññîöèàòèâíûé ìàññèâ(Dictionary< int,List<int> >), ãäå 0-îé ïîçèöèè ñîîòâåñòâóåò 0- îé áëîê ïåðåñòàíîâîê, 1-îé 1-ûé, 2-îé ïîçèöèè, ñîîòâåòñâåííî, 2-îé áëîê. ApplyPermsComponent íîëü-îäèí ìàòðèöà íàçíà÷åíèåì ýòîãî êîìïîíåíòà ÿâëÿåò- ñÿ ïðèìåíåíèå ïåðåñòàíîâêè. Îòêðûòûé ìåòîä íûå ApplyPerms, âõîäíûå äàí- (bool[,]) è ïåðåñòàíîâêà(int[]). Âîçâðàùàåìîå çíà÷åíèå ôóíêöèè ïîëó÷åííàÿ ìàòðèöà ïîñëå ïðèìåíåíèÿ ïåðåñòàíîâêè. SMController matrix ñòðóêòóðíàÿ ìàòðèöà ApplyPermsController ApplyPermsComponent matrix perms perms ïåðåñòàíîâêà SMethodComponent matrix weights weights âåñà ìåòîä Post èñïîëüçóåò . Òåëî çàïðîñà äîëæíî ñîäåðæàòü JS îáúåêò, êîòîðîå èìååò 2 ïîëÿ: ãäå , à ìåòîä , , . Post èñïîëüçóåò . Òåëî çàïðîñà äîëæíî ñîäåðæàòü JS îáúåêò, êî- òîðîå èìååò 2 ïîëÿ: , , ãäå . 30 matrix èñõîäíàÿ ìàòðèöà , à

Îáùàÿ ñõåìà ñåðâåðíîé ÷àñòè Ðèñ. 1: Îáùàÿ ñõåìà ñåðâåðà 31

Îïèñàíèå êëèåíòñêîé ÷àñòè Ðèñ. 2: Êëèåíò Êëèåíò ñîñòîèò èç äâóõ áëîêîâ: áëîê ââîäà áëîêà ðåçóëüòàòîâ è , êîòîðûé âûâîäèòñÿ ïîñëå óñïåøíîãî çàïðîñà. Áëîê ââîäà ñîäåðæèò ïîëÿ äëÿ ââîäà âåñîâ, è äëÿ ââîäà ñòðóêòóðíîé ìàòðèöû. Òàêæå äàííûé èíòåðôåéñ ïîçâîëÿåò âûáðàòü ðàçìåðíîñòü. Êíîïêà Íàéòè ïåðåñòàíîâêó îòïðàâëÿåò äâà ïîñëåäîâàòåëüíûõ HTTP-çàïðîñà SMController íà ñåðâåð. Ïåðâûé çàïðîñ ïîëó÷åíèå ïåðåñòàíîâêè( ), ïðè åãî óñïåøíîñòè îòïðàâëÿåò âòîðîé çàïðîñ íà ïðèìåíåíèå ïåðåñòàíîâêè ApplyPermsController áëîê ðåçóëüòàòîâ ( ). Ïðè óñïåøíîì ïîñëåäíåì çàïðîñå ðåçóëüòàò îòîá- ðàæàåòñÿ â . Áëîê îáùåé ãðóïïû óðàâíåíèé ïîìå÷åí êðàñíûì, äðóãèå áëîêè(1 è 2) ñèíèì è æ¼ëòûì, ñîîòâåòñòâåííî. 32

Îáùàÿ ñõåìà êëèåíòñêîé ÷àñòè Ðèñ. 3: Îáùàÿ ñõåìà êëèåíòñêîé ÷àñòè 33

Çàêëþ÷åíèå Òàêèì îáðàçîì, â äàííîé ðàáîòå áûë ðåàëèçîâàí àëãîðèòì âûäåëåíèÿ ñòðóêòóðíûõ îñîáåííîñòåé íà áàçå êëèåíò-ñåðâåðíûõ òåõíîëîãèé. Äàííûé àëãîðèòì ïðèìåíèì äëÿ ïðåäâàðèòåëüíîãî ïðèâåäåíèÿ ñèñòåìû äèôôåðåíöèàëüíûõ óðàâíåíèé ê êàíîíè÷åñêîìó âèäó, ÷òîáû óìåíüøèòü çàòðàòû íà ïîñëåäóþùåå èíòåãðèðîâàíèå. Ïîõîæèé íà VK-API, Twitter-API, è äð., äàííûé ñåðâèñ ìîæåò ïîìî÷ü ïðè íàïèñàíèÿ ïðèëîæåíèé ÷èñëåííîãî èíòåãðèðîâàíèÿ. Òàêèì îáðàçîì, ïåðåêëàäûâàÿ ÷àñòü âû÷èñëèòåëüíûõ ðåñóðñîâ íà ñåðâåð. 34

Ñïèñîê ëèòåðàòóðû [1] Îëåìñêîé È. Â. Ìåòîäû èíòåãðèðîâàíèÿ ñèñòåì ñòðóêòóðíî ðàçäåëåííûõ äèôôåðåíöèàëüíûõ óðàâíåíèé. ÑÏá.: Èçä-âî Ñ.-Ïåòåðá. óí-òà, 2009. 180 ñ. [2] Ãåðáåðò Øèëäò. C# 4.0. Ïîëíîå ðóêîâîäñòâî. Èçä-âî Âèëüÿìñ, 2011. 1056 ñ. [3] Freeman Adam, Sanderson Steven. Pro ASP.NET MVC 4, 4th Edition Apress, 2012. 756 ñ. [4] Ïîíÿòèå êîìïîíåíòà, êîìïîíåíòíîé ìîäåëè, îðèåíòèðîâàííîãî ïðîãðàììèðîâàíèÿ. http://5fan.ru/wievjob.php?id=50580 [5] LaTeX on Wikibooks. http://en.wikibooks.org/wiki/LaTeX [6] jQuery API. http://api.jquery.com/ [7] REST. https://ru.wikipedia.org/wiki/REST [8] API. https://ru.wikipedia.org/wiki/API [9] JavaScript. https://ru.wikipedia.org/wiki/JavaScript [10] CSS. https://ru.wikipedia.org/wiki/CSS [11] HTML. https://ru.wikipedia.org/wiki/HTML [12] AJAX. https://ru.wikipedia.org/wiki/AJAX [13] Document Object Model. https://ru.wikipedia.org/wiki/Document_Object_Model 35 êîìïîíåíòíî-

Ïðèëîæåíèå SMethodComp.cs using using using using using namespace internal static class public static S t r u c t u r a l M e t h o d . Models ; System ; System . C o l l e c t i o n s . G e n e r i c ; System . ComponentModel ; System . L i n q ; StructuralMethod { Extensions { I L i s t <T> C l o n e<T>( listToClone ) { return where T : this I L i s t <T> ICloneable l i s t T o C l o n e . S e l e c t ( i t e m => (T) i t e m . Clone ( ) ) . ToList ( ) ; } } public class private private private int private private private bool public SMethodComponent : Component { Set [ ] Set _b ; _temp_b ; [] Set _curLvl = _topUni ; new int [] { 0, 0 }; L i s t <P a i r > _ t o p S e t s ; _isFound = int double Dictionary< [ ,] { if matrix , false int ; , List< [] ( matrix . Length >> C a l c u l a t e ( weights ) != w e i g h t s . Length ∗ bool weights . Length ) throw new ArgumentException ( " I n v a l i d dimensions ! " ) ; var u n i v e r s e = BuildTopUni ( matrix , var sets = BuildTopSets ( matrix , 36 weights ) ; weights ,

universe ) ; SortByWeights ( s e t s ) ; _b = new Set [ 2 ] weights ) }; new _topUni = new { Set ( weights ) , new Set ( Set ( u n i v e r s e ) ; _topSets = s e t s ; BuildFirstBlock ( sets , universe , weights ) , weights ) ; } return new Set ( B u i l d R e s u l t ( w e i g h t s . Length ) ; private void for S o r t B y W e i g h t s ( L i s t <P a i r > sets ) { ( var i = 0; i < s e t s . Count ; i ++) { var maxWeightPos = i ; var maxWeight = s e t s [ i ] . PermSet . FullWeight ; for { ( var if j = i +1; j < ( maxWeight < s e t s . Count ; j ++) s e t s [ j ] . PermSet . FullWeight ) { maxWeightPos = j ; maxWeight = s e t s [ j ] . PermSet . FullWeight ; } } if ( i != maxWeightPos ) { var temp = sets [ i ] sets [ i ] ; = s e t s [ maxWeightPos ] ; s e t s [ maxWeightPos ] } } } 37 = temp ;

private void uni , Set B u i l d F i r s t B l o c k ( L i s t <P a i r > s e t s , double curTempSet , { [] Set weights ) L i s t <P a i r > n e x t S e t s ; Set nextUni ; Set nextCurTempSet ; Set centrElems = int if new Set ( uni ) ; c e n t r = u n i . Max ( ) ; ( u n i . Count == 0 ) { _temp_b = curTempSet ; n e x t U n i = _topUni . E x c e p t ( curTempSet ) ; nextSets = S i f t S e t s ( _topSets , BuildSecondBlock ( nextSets , Set ( weights ) , nextUni ) ; nextUni , weights ) ; new } else { if { ( s e t s . Count foreach if != ( var 0) in set { sets ) ( s e t . PermSet . F u l l W e i g h t > weights [ centr ] ) { if ( s e t . PermSet . F u l l W e i g h t + curTempSet . F u l l W e i g h t > 0.5 ∗ (_b [ 0 ] . F u l l W e i g h t + _b [ 1 ] . F u l l W e i g h t ) ) { nextCurTempSet = curTempSet ) ; new Set ( nextCurTempSet . I n s e r t T w o ( curTempSet . Count s e t . Perm . From , / 2, set . Perm . To ) ; nextUni = new PermSet ) ; 38 Set ( s e t .

n e x t U n i . Remove ( s e t . Perm . From ) ; n e x t U n i . Remove ( s e t . Perm . To ) ; _curLvl [ 0 ] + + ; nextSets = SiftSets ( sets , nextUni ) ; BuildFirstBlock ( nextSets , nextUni , nextCurTempSet , weights ) ; } else { _curLvl [0] − −; } return ; } else { if ( weights [ centr ] + curTempSet . F u l l W e i g h t > 0.5 ∗ (_b [ 0 ] . F u l l W e i g h t + _b [ 1 ] . F u l l W e i g h t ) ) { nextCurTempSet = curTempSet ) ; new Set ( nextCurTempSet . I n s e r t ( curTempSet . Count / 2, centr ) ; _temp_b = nextCurTempSet ; n e x t U n i = _topUni . E x c e p t ( nextCurTempSet ) ; nextSets = _topSets , SiftSets ( nextUni ) ; BuildSecondBlock ( nextSets 39

, nextUni , weights ) , new Set ( weights ) ; } else { _curLvl [0] − −; } return ; } if { } ( _isFound ) return ; } } else { while if ( c e n t r E l e m s . Count != 0) { ( weights [ centr ] + curTempSet . FullWeight > 0.5 ∗ (_b [ 0 ] . F u l l W e i g h t + _b [ 1 ] . FullWeight ) ) { nextCurTempSet = curTempSet ) ; new Set ( nextCurTempSet . I n s e r t ( curTempSet . Count / 2, centr ) ; _temp_b = nextCurTempSet ; n e x t U n i = _topUni . E x c e p t ( nextCurTempSet ) ; nextSets = S i f t S e t s ( _topSets , nextUni ) ; c e n t r E l e m s . Remove ( c e n t r ) ; c e n t r = c e n t r E l e m s . Max ( ) ; BuildSecondBlock ( nextSets , 40

nextUni , new Set ( weights ) , weights ) ; } else { _curLvl [0] − −; return } ; } } if ( _isFound ) { return } ; } } private void Set uni , B u i l d S e c o n d B l o c k ( L i s t <P a i r > s e t s , Set curTempSet , { double [] weights ) L i s t <P a i r > n e x t S e t s ; Set nextUni ; Set nextCurTempSet ; Set usedCentrElems = int if { new Set ( weights ) ; c e n t r = u n i . Max ( ) ; ( u n i . Count == 0 ) if ( _curLvl [ 1 ] > 0) { _b [ 0 ] = _temp_b ; _b [ 1 ] = curTempSet ; if (_b [ 0 ] . F u l l W e i g h t + _b [ 1 ] . F u l l W e i g h t == _topUni . F u l l W e i g h t ) { _isFound = } else return ; true { _curLvl [1] − −; return 41 ; ;

} } { else if ( _temp_b . Count != 0) { _b [ 0 ] = _temp_b ; _b [ 1 ] = new } Set ( weights ) ; } } else { if { ( s e t s . Count foreach if != ( var { 0) set in sets ) ( s e t . PermSet . F u l l W e i g h t > weights [ centr ] ) { if ( _temp_b . F u l l W e i g h t + curTempSet . F u l l W e i g h t + s e t . PermSet . F u l l W e i g h t > _b [ 0 ] . F u l l W e i g h t + _b [ 1 ] . FullWeight ) { nextCurTempSet = curTempSet ) ; new Set ( nextCurTempSet . I n s e r t T w o ( curTempSet . Count s e t . Perm . From , / 2, set . Perm . To ) ; nextUni = new Set ( s e t . PermSet ) ; n e x t U n i . Remove ( s e t . Perm . From ) ; n e x t U n i . Remove ( s e t . Perm . To ) ; _curLvl [ 1 ] + + ; nextSets = SiftSets ( sets , nextUni ) ; 42

BuildSecondBlock ( nextSets , nextUni , nextCurTempSet , weights ) ; } else { _curLvl [1] − −; return ; } } else { if ( _temp_b . F u l l W e i g h t + weights [ centr ] + curTempSet . F u l l W e i g h t > _b [ 0 ] . F u l l W e i g h t + _b [ 1 ] . FullWeight ) { nextCurTempSet = curTempSet ) ; new Set ( nextCurTempSet . I n s e r t ( curTempSet . Count / 2, centr ) ; u s e d C e n t r E l e m s . Add ( c e n t r ) ; _b [ 0 ] = _temp_b ; _b [ 1 ] = nextCurTempSet ; if (_b [ 0 ] . F u l l W e i g h t + _b [ 1 ] . F u l l W e i g h t == _topUni . F u l l W e i g h t ) { _isFound = } return } _curLvl [1] − −; 43 ; true ;

return } ; } } else { if ( _temp_b . F u l l W e i g h t + w e i g h t s [ centr ] + curTempSet . F u l l W e i g h t > _b [ 0 ] . F u l l W e i g h t + _b [ 1 ] . FullWeight ) { nextCurTempSet = curTempSet ) ; new Set ( nextCurTempSet . I n s e r t ( curTempSet . Count / 2, centr ) ; u s e d C e n t r E l e m s . Add ( c e n t r ) ; _b [ 0 ] = _temp_b ; _b [ 1 ] = nextCurTempSet ; if (_b [ 0 ] . F u l l W e i g h t + _b [ 1 ] . F u l l W e i g h t == _topUni . FullWeight ) { _isFound = return } ; true ; } _curLvl [1] − −; } return ; } } private L i s t <P a i r > S i f t S e t s ( L i s t <P a i r > s e t s , uni ) { var if result = new L i s t <P a i r >() ; ( u n i . Count <= 1 ) return result ; 44 Set

foreach ( var in pair { var if sets ) temp = p a i r . PermSet . I n t e r s e c t ( u n i ) ; ( temp . C o n t a i n s ( p a i r . Perm . From ) && temp . C o n t a i n s ( p a i r . Perm . To ) ) { r e s u l t . Add ( { new Pair () Perm = p a i r . Perm , PermSet = ( S e t ) temp }) ; } } SortByWeights ( r e s u l t ) ; } return private int result ; int Dictionary< n) { var result = ; if new , int List< >> B u i l d R e s u l t ( int Dictionary< (_b [ 0 ] . Count + _b [ 1 ] . Count { var for { temp = ( var if { i new = 0; int List< i < n; , != int List< n) >() ; i ++) ( ! _b [ 0 ] . C o n t a i n s ( i ) && ! _b [ 1 ] . Contains ( i ) ) if else ( _topUni . C o n t a i n s ( i ) ) temp . Add ( i ) ; temp . I n s e r t ( 0 , } } r e s u l t . Add ( 0 , } 45 temp ) ; i ) ; >>()

if (_b [ 0 ] . Count != { new r e s u l t . Add ( 1 , if 0) (_b [ 1 ] . Count != r e s u l t . Add ( 2 , } } return private double int List< 0) new int List< >(_b [ 1 ] ) ) ; result ; L i s t <P a i r > B u i l d T o p S e t s ( [] >(_b [ 0 ] ) ) ; weights , Set bool [ ,] matrix , universe ) { var v S e t s = BuildVSets ( matrix , weights , universe ) ; var hSets = BuildHSets ( matrix , universe ) ; var result = foreach foreach if ( var { i new in ( var L i s t <P a i r >() ; h S e t s . Keys ) j in continue v S e t s . Keys ) { var weights , ( i == j ) ; tempSet = h S e t s [ i ] . I n t e r s e c t ( vSets [ j ] ) ; if ( t e m p S e t . C o n t a i n s ( i ) && t e m p S e t . Contains ( j ) ) { var tempPair = { Perm = new new Pair () Permutation ( ) From = i , To = j PermSet = t e m p S e t }; r e s u l t . Add ( t e m p P a i r ) ; } } } 46 }, {

} return private int Dictionary< matrix , { var result ; double result foreach ( var bool [ ,] universe ) int i ( var Set Dictionary< , S e t >() ; universe ) tempSet = foreach if Set> B u i l d H S e t s ( weights , new in = { var [] , j { new in Set ( weights ) ; universe ) ( ! matrix [ i , j ]) t e m p S e t . Add ( j ) ; } r e s u l t . Add ( i , tempSet ) ; } } return private int Dictionary< matrix , { var result ; double result foreach = ( var { var [] Set> B u i l d V S e t s ( weights , new in j { ( ! matrix [ j , universe ) i ]) t e m p S e t . Add ( j ) ; r e s u l t . Add ( i , } } S e t >() ; Set ( weights ) ; } return , universe ) new in result ; 47 tempSet ) ; bool universe ) int i ( var Set Dictionary< tempSet = foreach if , [ ,]

private Set BuildTopUni ( weights ) { new var result var n = w e i g h t s . Length ; for { ( var if = bool i = 0; [ ,] matrix , double [] Set ( weights ) ; i < n; ( ! matrix [ i , i ++) i ]) r e s u l t . Add ( i ) ; } } return result ; } } using using using using using namespace internal class public public public object Pair.cs System ; System . C o l l e c t i o n s . G e n e r i c ; System . L i n q ; System . Text ; System . T h r e a d i n g . T a s k s ; S t r u c t u r a l M e t h o d . Models { Pair : ICloneable { Permutation Set PermSet ; Clone ( ) { var Perm ; result = new Pair () ; r e s u l t . Perm = ( P e r m u t a t i o n ) r e s u l t . PermSet = ( S e t ) } return result ; 48 this this . Perm . C l o n e ( ) ; . PermSet . C l o n e ( ) ;

} } Permutation.cs using using namespace internal struct public int public int public object return new this System ; System . C o l l e c t i o n s . G e n e r i c ; S t r u c t u r a l M e t h o d . Models { Permutation : ICloneable { From { To { get ; get ; set ; set ; } } Clone ( ) { Permutation ( ) To = . To { From = }; this . From , } } } using using namespace internal struct public int public int public object return new this Set.cs System ; System . C o l l e c t i o n s . G e n e r i c ; S t r u c t u r a l M e t h o d . Models { Permutation : ICloneable { From { To { get ; get ; set ; set ; } } Clone ( ) { Permutation ( ) To = . To }; } } } 49 { From = this . From ,

ApplyPermsComponent.cs using using namespace public class public bool System ; System . ComponentModel ; ApplyPermsComp { ApplyPermsComponent { [ ,] ApplyPerms ( matrix ) { if ( perms . L e n g t h ∗ int : Component [] perms , perms . L e n g t h != bool [ ,] matrix . Length ) throw new ArgumentException ( " I n v a l i d demensions ! " ) ; var n = perms . L e n g t h ; var result for { ( var for i = new bool = 0; ( var i < n; j = 0; [n, n]; i ++) j < n; j ++) { result [ i , j ] = m a t r i x [ perms [ i ] , [ j ]]; } } } return result ; } } using using using using using using SMController.cs System ; System . C o l l e c t i o n s . G e n e r i c ; System . Web . Http ; StructuralMethod ; Newtonsoft . Json . Linq ; System . Web . Http . C o r s ; 50 perms

namespace ServerSide . Controllers { [ EnableCors ( o r i g i n s : headers : "∗" , public class " http :// l o c a l h o s t :51161 " , methods : "∗" ) ] SMController : ApiController { public IHttpActionResult P o s t ( [ FromBody ] JObject input ) { bool double try [ ,] matrix ; [] weights ; { bool m a t r i x = i n p u t [ " m a t r i x " ] . ToObject< [ ,] >() ; w e i g h t s = i n p u t [ " w e i g h t s " ] . ToObject< double } catch return [] >() ; ( Exception exc ) { BadRequest ( e x c . Message ) ; } int Dictionary< using int , List< result ( SMethodComponent sm = SMethodComponent ( ) ) { >> try new = null { result = sm . C a l c u l a t e ( m a t r i x , ) ; } { } catch return ( Exception } e) BadRequest ( e . Message ) ; } return ; Ok ( r e s u l t ) ; } } 51 weights

using using using using using namespace ApplyPermsController.cs Newtonsoft . Json . Linq ; System ; System . Web . Http ; ApplyPermsComp ; System . Web . Http . C o r s ; ServerSide . Controllers { [ EnableCors ( o r i g i n s : headers : "∗" , public class public " http :// l o c a l h o s t :51161 " , "∗" ) ] methods : ApplyPermsController : ApiController { IHttpActionResult P o s t ( [ FromBody ] J O b j e c t input ) { bool int bool try [ ,] [] matrix ; perms ; [ ,] result = null ; { bool int m a t r i x = i n p u t [ " m a t r i x " ] . ToObject< [ ,] >() ; perms = i n p u t [ " perms " ] . ToObject< } { } catch return ( Exception using ( var exc ) BadRequest ( e x c . Message ) ; comp = { result } new ApplyPermsComponent ( ) ) = comp . ApplyPerms ( perms , } return [] >() ; Ok ( r e s u l t ) ; } } 52 matrix ) ;

index.html <!DOCTYPE html> <html> <head> < t i t l e >Âûäåëåíèå î ñ î á å í í î ñ ò å é </ t i t l e > c h a r s e t=" u t f −8" /> <meta <l i n k ñòðóêòóðíûõ r e l =" s t y l e s h e e t " t y p e=" t e x t / c s s " h r e f=" s t y l e / − 2 . 2 . 2 . min . j s "></ s c r i p t > main . c s s "> <s c r i p t s r c=" s c r i p t s / j q u e r y <s c r i p t s r c=" s c r i p t s / main . j s "></ s c r i p t > <s c r i p t s r c=" s c r i p t s / q u e r i e s . j s "></ s c r i p t > </head> <body> <d i v i d=" h e a d e r "> <h1>Âûäåëåíèå ñòðóêòóðíûõ î ñ î á å í í î ñ ò å é </h1> </ d i v > <d i v i d=" body "> <d i v i d=" i n p u t _ f o r m "> <d i v i d=" div_params_num "> Ðàçìåðíîñòü <s e l e c t i d="params_num" o n c h a n g e=" params_num_changed ( ) "> </ s e l e c t > </ d i v > Âåñà<d i v i d=" i n p u t _ w e i g h t s "></d i v > <b r /> <p i d=" i n p u t _ m a t r i x _ l a b e l ">Ñòðóêòóðíàÿ ìàòðèöà</p> <d i v i d=" i n p u t _ t a b l e "> <t a b l e i d=" i n p u t _ m a t r i x "></ t a b l e > </ d i v ><b r/> <b u t t o n o n c l i c k=" o n c l i c k _ c a l c u l a t e ( ) ">Íàéòè ï å ð å ñ ò à í î â ê ó </b u t t o n > </ d i v > <b r/> <d i v i d=" o u t p u t _ f o r m "> </ d i v > </ d i v > <d i v i d=" f o o t e r "> <h3>Ãàðìàøîâ Ê . Ñ &c o p y ; </ d i v > 53 2016 </ h3>

</body> </html> body main.css { margin : 0; } #h e a d e r { float : left ; width : 100%; top : 0 ; left :0; b a c k g r o u n d−c o l o r : #08876C ; f o n t −f a m i l y : Courier f o n t −w e i g h t : bold ; box−shadow : 0 1 0 px New , 10 px Courier , monospace ; rgba ( 0 , 0 , 0 , 0 . 5 ) ; b o r d e r −bottom− l e f t −r a d i u s : 10 px ; b o r d e r −bottom−r i g h t − r a d i u s : 1 0 px ; } #h e a d e r h1 { t e x t −a l i g n : c e n t e r ; f o n t −w e i g h t : b o l d ; t e x t −shadow : 0 0 25 px rgba ( 2 4 5 , 2 4 5 , 2 4 5 , 0 . 7 ) ; } #body { t e x t −a l i g n : c e n t e r ; b a c k g r o u n d−c o l o r : #69BAA9 ; b o r d e r − r a d i u s : 1 0 px ; box−shadow : −5px 10 px 1 0 px width :70%; float : left ; m a r g i n −t o p : 3 0 px ; m a r g i n− l e f t : 15%; m a r g i n− r i g h t : 15%; m a r g i n −bottom : 8 0 px ; padding : 20 px ; } 54 rgba ( 0 , 0 , 0 , 0 . 5 ) ;

#f o o t e r { box−shadow : 0 −5px 10 px rgba ( 0 , 0 , 0 , 0 . 5 ) ; m a r g i n −t o p : 3 0 px ; position : bottom : 0; fixed ; left :0; width : 100%; height : 30 px ; b a c k g r o u n d−c o l o r : #08876C ; b o r d e r −t o p − l e f t −r a d i u s : 10 px ; b o r d e r −t o p −r i g h t − r a d i u s : 1 0 px ; p a d d i n g −bottom : 2 0 px ; } #f o o t e r h3 { float : right ; f o n t −w e i g h t : bold ; m a r g i n− r i g h t : 1 5 % ; m a r g i n −t o p : vertical 1 5 px ; −a l i g n : central ; } #i n p u t _ f o r m ,# o u t p u t _ f o r m { i n l i n e −b l o c k ; display : t e x t −a l i g n : c e n t e r ; } #i n p u t _ f o r m input { d i s p l a y : i n l i n e −b l o c k ; } #i n p u t _ t a b l e { d i s p l a y : i n l i n e −b l o c k ; m a r g i n− l e f t : a u t o ; m a r g i n− r i g h t : a u t o ; } #i n p u t _ m a t r i x width : input { 2em ; } 55

i n p u t : : − w e b k i t −i n n e r −s p i n −b u t t o n { #i n p u t _ w e i g h t s d i s p l a y : none ; } #i n p u t _ w e i g h t s width : input { 4 0 px ; m a r g i n− l e f t : 5 px ; } #i n p u t _ f o r m button { m a r g i n −t o p : 5 px ; } #i n p u t _ w e i g h t s display : { inline ; } #o u t p u t _ f o r m margin : { 10 px ; } #perms_output padding : th , #r e s u l t _ m a t r i x 5 px 15 px ; } #r e s u l t _ m a t r i x { m a r g i n : 1 0 px ; } #r e s u l t _ m a t r i x border : { 1 px solid ; } #div_params_num { m a r g i n −bottom : 10 px ; } #perms_output { p a d d i n g : 1 0 px ; } 56 th {

main.js var colors var selected_num = 7 ; var max_matrix_dim = 2 0 ; function for = [ ' red ' , ' blue ' , ' yellow ' ] ; create_num_params_selector ( n ) ( var var i = 2; i <= n ; i ++) { o p t = document . c r e a t e E l e m e n t ( ' o p t i o n ' ) ; opt . innerText = if { i ; ( i == s e l e c t e d _ n u m ) opt . s e t A t t r i b u t e ( ' s e l e c t e d ' , ' s e l e c t e d ' ) ; $ ( '# params_num ' ) . append ( o p t ) ; } } function create_input_matrix (n) { $ ( "#i n p u t _ m a t r i x " ) . t e x t ( ' ' ) ; for ( var var for i = 0; i < n; i ++) { t r = document . c r e a t e E l e m e n t ( " t r " ) ; ( var j = 0; j < n; j ++) { var t d = document . c r e a t e E l e m e n t ( " t d " ) ; var i n p u t = document . c r e a t e E l e m e n t ( " i n p u t " ) ; i n p u t . s e t A t t r i b u t e ( ' type ' , ' number ' ) ; i n p u t . s e t A t t r i b u t e ( ' min ' , 0) ; i n p u t . s e t A t t r i b u t e ( ' max ' , 1) ; input . setAttribute ( ' size ' , 1) ; i n p u t . s e t A t t r i b u t e ( ' maxlength ' , input . s e t A t t r i b u t e ( ' value ' , Math . r o u n d ( Math . random ( ) ) ) ; i n p u t . onkeydown = check_number ; i n p u t . o nk ey up = c h e c k _ l e n ; td . appendChild ( i n p u t ) ; t r . appendChild ( td ) ; } $ ( "#i n p u t _ m a t r i x " ) . append ( t r ) ; } 57 1) ;

} function create_input_weights (n) { $ ( "#i n p u t _ w e i g h t s " ) . t e x t ( ' ' ) ; for ( var var i = 0; i < n; i ++) { i n p u t = document . c r e a t e E l e m e n t ( " i n p u t " ) ; i n p u t . s e t A t t r i b u t e ( ' type ' , ' number ' ) ; input . s e t A t t r i b u t e ( ' value ' , 1) ; input . onkeypress = no_letters ; $ ( "#i n p u t _ w e i g h t s " ) . append ( i n p u t ) ; } } function var create_output_label () label { = document . c r e a t e E l e m e n t ( ' p ' ) ; label . setAttribute ( ' class ' , ' label ' ) ; l a b e l . i n n e r T e x t = " Ðåçóëüòàò " ; $ ( '# output_form ' ) . append ( l a b e l ) ; } function c r e a t e _ o u t p u t _ p e r m u t a t i o n s ( perms ) { var counter = 0; var p e r m s _ t a b l e = document . c r e a t e E l e m e n t ( " t a b l e " ) ; perms_table . s e t A t t r i b u t e ( ' id ' , ' perms_output ' ) ; var p o s _ t r = document . c r e a t e E l e m e n t ( ' t r ' ) ; var v a l u e _ t r = document . c r e a t e E l e m e n t ( ' t r ' ) ; for ( var for in prop ( var i perms ) = 0; { i < perms [ p r o p ] . l e n g t h ; i ++, c o u n t e r ++) { var b l o c k _ p o s = document . c r e a t e E l e m e n t ( ' th ' ) ; block_pos . s e t A t t r i b u t e ( ' class ' , ' el ' block_pos . s e t A t t r i b u t e ( ' b g c o l o r ' , + prop ) ; c o l o r s [ prop ]) ; block_pos . innerText = c o u n t e r ; var b l o c k _ v a l u e = document . c r e a t e E l e m e n t ( " t h " ) ; block_value . s e t A t t r i b u t e ( ' 58 class ' , ' el ' + prop

) ; block_value . s e t A t t r i b u t e ( ' bgcolor ' , colors [ prop ] ) ; b l o c k _ v a l u e . i n n e r T e x t = perms [ p r o p ] [ i ] ; pos_tr . appendChild ( block_pos ) ; value_tr . appendChild ( block_value ) ; } } perms_table . appendChild ( pos_tr ) ; perms_table . appendChild ( value_tr ) ; $ ( '# output_form ' ) . append ( p e r m s _ t a b l e ) ; } function var create_output_matrix ( matrix , perms ) { m a t r i x _ t a b l e = document . c r e a t e E l e m e n t ( ' t a b l e ' ) ; matrix_table . s e t A t t r i b u t e ( ' id ' , ' result_matrix ' ) ; $ ( '# output_form ' ) . append ( m a t r i x _ t a b l e ) ; var cur_pos = 0 ; var k e y s = O b j e c t . k e y s ( perms ) ; var left_top_corner = 0; var cur_dim = perms [ k e y s [ c u r _ p o s ] ] . l e n g t h ; for ( var var for i = 0; i < matrix . length ; i ++) { t r = document . c r e a t e E l e m e n t ( ' t r ' ) ; ( var var if j = 0; j < matrix . length ; j ++) { t h = document . c r e a t e E l e m e n t ( ' th ' ) ; ( i >= l e f t _ t o p _ c o r n e r && i < l e f t _ t o p _ c o r n e r + cur_dim && j >= l e f t _ t o p _ c o r n e r && j < l e f t _ t o p _ c o r n e r + cur_dim ) th . s e t A t t r i b u t e ( ' bgColor ' , { c o l o r s [ keys [ cur_pos ] ] ) ; } th . innerText = matrix [ i ] [ j ] t r . appendChild ( th ) ; } 59 ? 1 : 0;

if ( l e f t _ t o p _ c o r n e r + cur_dim == i + 1 != keys . length ) + 1 && c u r _ p o s { c u r _ p o s++; l e f t _ t o p _ c o r n e r += cur_dim ; cur_dim = perms [ k e y s [ c u r _ p o s ] ] . l e n g t h ; } matrix_table . appendChild ( t r ) ; } } function no_letters ( e ) return { ! ( / [ À−ßà−ÿA−Za−z ] / . t e s t ( S t r i n g . fromCharCode ( e . charCode ) ) ) ; } function // if check_number ( event ) { backspace , d e l e t e , tab è escape event event // C t r l+A event ( . keyCode == 46 . keyCode == 9 ( || event event event || . keyCode == 27 . keyCode == 65 && || . keyCode == 8 || || . c t r l K e y === true ) // home , end , âëåâî , âïðàâî event // Íè÷åãî return ( . keyCode >= 35 && íå äåëàåì event . keyCode <= 3 9 ) ) { ; } else { if event event (( } . keyCode < 4 8 || . preventDefault () ; event . keyCode > 4 9 ) ) } } function check_len ( if this this ( event ) { . value . length > 1) { . v a l u e = S t r i n g . fromCharCode ( 60 event . keyCode ) ; {

} } function params_num_changed ( ) { s e l e c t e d _ n u m = document . g e t E l e m e n t B y I d ( ' params_num ' ) . value ; $ ( '# output_form ' ) . t e x t ( " " ) ; create_input_weights ( selected_num ) ; create_input_matrix ( selected_num ) ; } queries.js var host = " http :// l o c a l h o s t :57776/ " ; var _perms = null ; $ ( document ) . r e a d y ( f u n c t i o n () { c r e a t e _ n u m _ p a r a m s _ s e l e c t o r ( max_matrix_dim ) ; create_input_matrix ( selected_num ) ; create_input_weights ( selected_num ) ; }) ; function onclick_calculate () { var w = parse_weights ( ) ; var m = parse_matrix ( ) ; get_perms_query (m, w, get_perms_success , get_perms_error ) ; } function var for to_array ( obj ) result ( var for i = in ( var { []; obj ) j = 0; { j < obj [ i ] . length ; r e s u l t . push ( o b j [ i ] [ j ] ) ; } } } return result ; 61 j ++) {

var line for ( var = []; j = 0; j < tds . length ; j ++) { l i n e . p u s h ( $ ( t d s [ j ] ) . c h i l d r e n ( ) [ 0 ] . v a l u e == 0 ? false } : true ) ; r e s u l t _ m a t r i x . push ( l i n e ) ; } } return function result_matrix ; a p p l y _ q u e r y (m, p, onsuccess , onerror ) { $ . ajax ({ url : host + " a p i / applyperms /" , type : 'POST' , data : JSON . s t r i n g i f y ( { matrix : perms : m, p }) , contentType : success : error : " application / json " , onsuccess , onerror }) ; } function get_perms_query (m, w , o n s u c c e s s , $ . ajax ({ url : h o s t + " a p i /sm/ " , type : data : 'POST' , JSON . s t r i n g i f y ( { matrix : weights : m, w }) , contentType : success : error : " application / json " , onsuccess , onerror }) ; } 63 onerror ) {

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв