Диссертация (1103424), страница 22
Текст из файла (страница 22)
Êîïèè ýòîé ñõåìûìû ïðèìåíÿåì ê ìåòêàì â êàæäîì ñòîëáöå {vi } × S2 . Äàëåå, íóæíî ïîäñ÷èòàòü ñóììàðíîå ÷èñëî åäèíèö â ñòîëáöàõ, ãäå ïåðâàÿ ñõåìà ïðèíÿëà ñâîéâõîä. Äëÿ ýòîãî ìû áåð¼ì êîíúþíêöèè àðãóìåíòîâ ïðåäûäóùåé ñõåìû ñ å¼çíà÷åíèÿìè â ñîîòâåòñòâóþùèõ ñòîëáöàõ. Çàòåì ê ïîëó÷èâøèìñÿ |S1 | · |S2 |çíà÷åíèÿì ìû ïðèìåíèì ñõåìó, êîòîðàÿ ïðèíèìàåò ñâîé âõîä, åñëè ñðåäèå¼ àðãóìåíòîâ ìåíüøå 2l1 +q−m+k+1 åäèíèö, è îòâåðãàåò åãî, åñëè ñðåäè å¼àðãóìåíòîâ áîëüøå 2l1 +q−m+k+1.01 åäèíèö.
Ïàðàëëåëüíî âñþ êîíñòðóêöèþíóæíî ïîâòîðèòü äëÿ ñòðîê è âçÿòü êîíúþíêöèþ äâóõ ðåçóëüòàòîâ.Îïèøåì êîíñòðóêöèþ åù¼ ðàç, òàê ÷òîáû èç îïèñàíèÿ áûëî ÿñíî, ÷òîãëóáèíà ñõåìû åñòü êîíñòàíòà, à ðàçìåð ðàâåí 2poly(n) . Âíà÷àëå îïèøåì êîíñòðóêöèþ ñõåìû, ðàñïîçíàþùåé ïåñòðîòó. Àðãóìåíòû ñõåìû çàäàþò öâåòàâñåõ 22n ÿ÷ååê â òàáëèöå. Êðîìå òîãî, äîáàâèì â ñõåìó êîíñòàíòû äëÿ âñå106âîçìîæíûõ öâåòîâ èç Q. Ñõåìà ñîñòîèò èç 2poly(n) îäèíàêîâî óñòðîåííûõáëîêîâ. Êàæäûé áëîê èìååò äâå ãðóïïû âõîäîâ. Ïåðâàÿ ãðóïïà çàäà¼òöâåòà âñåõ ÿ÷ååê â êîíêðåòíîì ïðÿìîóãîëüíèêå S1 × S2 .
Âòîðàÿ ãðóïïàçàäà¼ò íàáîð öâåòîâ Q. Ðàçíûå áëîêè ïîäêëþ÷àþòñÿ ê ðàçíûì âõîäàì ñõåìû (ïåðâàÿ ãðóïïà âõîäîâ áëîêà) è ê îäíîìó è òîìó æå íàáîðó öâåòîâQ. Êàæäûé áëîê ñîñòîèò èç òð¼õ óðîâíåé. Íà ïåðâîì óðîâíå ê êàæäîéïàðå öâåòîâ èç ïåðâîé è èç âòîðîé ãðóïïû ïðèìåíÿåòñÿ ñõåìà, ïðîâåðÿþùàÿ, ñîâïàäàþò ëè äâà öâåòà. Ïðè ïðîñòåéøåé ðåàëèçàöèè òàêàÿ ñõåìàèìååò ðàçìåð O(m) è ãëóáèíó 4.
À èìåííî, ìû çàïèøåì ñõåìîé ôîðìóëóVf (σ1 , . . . , σm ; τ1 , . . . , τm ) = mi=1 ((σi ∧ τi ) ∨ (¬σi ∧ ¬τi )). Âñåãî òàêèõ ñõåìáóäåò íå áîëüøå 2l1 +l2 +q , ïîñêîëüêó |S1 × S2 | 6 2l1 +l2 , à |Q| 6 2q . Ïîñêîëüêóâñå òðè ïàðàìåòðà l1 , l2 , q íå ïðåâîñõîäÿò n, òî îáùèé ðàçìåð ïåðâîãî óðîâíÿ ñîñòàâèò O(m23n ) = 2poly(n) . À ïîñêîëüêó âñå ñõåìû íà ïåðâîì óðîâíåïðèìåíÿþòñÿ ïàðàëëåëüíî, îáùàÿ ãëóáèíà îñòàíåòñÿ ðàâíîé 4. Íà âòîðîìóðîâíå äëÿ êàæäîãî ýëåìåíòà S1 × S2 áåð¼òñÿ äèçúþíêöèÿ âñåõ |Q| ðåçóëüòàòîâ ïåðâîãî óðîâíÿ. Ýòî îñòàâëÿåò ðàçìåð ïîëèíîìèàëüíûì, à ãëóáèíàóâåëè÷èâàåòñÿ íà 1.
Íà òðåòüåì óðîâíå êî âñåì ðåçóëüòàòàì âòîðîãî óðîâíÿ ïðèìåíÿåòñÿ ñõåìà äëÿ ïðèáëèæ¼ííîãî ïîäñ÷¼òà ÷èñëà åäèíèö. Êàê óæåáûëî ñêàçàíî, ýòà ñõåìà ïðèíèìàåò ñâîé âõîä, åñëè ÷èñëî åäèíèö ñðåäè àðãóìåíòîâ ìåíüøå 2l1 +l2 +q−m+1 , è îòâåðãàåò åãî, åñëè ÷èñëî åäèíèö áîëüøå2l1 +l2 +q−m+1.01 . Ýòà ñõåìà èìååò êîíñòàíòíóþ ãëóáèíó è ðàçìåð, ïîëèíîìèàëüíûé îò |S1 | · |S2 | · |Q|, ò.å. ñîñòàâëÿþùèé 2poly(n) . Çíà÷èò, áëîê â öåëîìòàêæå èìååò êîíñòàíòíóþ ãëóáèíó è ðàçìåð 2poly(n) , ÷òî è òðåáîâàëîñü. Ïîñêîëüêó âñåãî áëîêîâ òîæå 2poly(n) , âñå îíè ïðèìåíÿþòñÿ ïàðàëëåëüíî, à íàïîñëåäíåì ýòàïå áåð¼òñÿ ïðîñòî êîíúþíêöèÿ ðåçóëüòàòîâ âñåõ áëîêîâ, òî èðàçìåð âñåé ñõåìû áóäåò ñîñòàâëÿòü 2poly(n) , à ãëóáèíà å¼ áóäåò íåêîòîðîéêîíñòàíòîé. Ýñêèç ñõåìû ïîêàçàí íà ðèñ. 6.2.Äîêàæåì êîððåêòíîñòü ïîñòðîåííîé ñõåìû.
Ïóñòü åé íà âõîä ïîäàí êîä(k, q, 1, Q, S)-ï¼ñòðîé òàáëèöû. Òîãäà â êàæäîì ìíîæåñòâå S1 × S2 ìåíüøå2l1 +l2 +q−m+1 ÿ÷ååê, ïîêðàøåííûõ â öâåòà èç Q. Òîëüêî äëÿ ÿ÷ååê, ïîêðàøåííûõ â òàêèå öâåòà, õîòÿ áû îäíà èç ≡-ñõåì íà ïåðâîì âûäàñò 1, à çíà÷èòòîëüêî äëÿ òàêèõ ÿ÷ååê äèçúþíêöèÿ íà âòîðîì óðîâíå âûäàñò 1. Ðàç òàêèõÿ÷ååê ìåíüøå 2l1 +l2 +q−m+1 , òî ïîðîãîâàÿ ñõåìà íà òðåòüåì óðîâíå âûäàñò 1.Ïîñêîëüêó òàêîå ïðîèñõîäèò äëÿ âñåõ ïðÿìîóãîëüíèêîâ S1 × S2 , òî è âñÿñõåìà âûäàñò 1.Òåïåðü ïóñòü, íàïðîòèâ, ñõåìà âûäàëà 1.
Çíà÷èò, äëÿ âñåõ ïðÿìîóãîëüíè107T (x1 , y1 )≡T (x1 , y2 )...≡T (x1 , y3 ) . . . T (xK , yK )≡≡q1...≡∨∨...q2...≡...Ïîðîãîâàÿ ñõåìà:1, åñëè < 2l +l +q−m+1 åäèíèö0, åñëè > 2l +l +q−m+1.01 åäèíèö0 èëè 1, èíà÷å1212qM...∧S1 ,S2Ðèñ. 6.2: Ýñêèç ñõåìû, ïðîâåðÿþùåé ïåñòðîòó òàáëèöû.êîâ S1 × S2 ñîîòâåòñòâóþùàÿ ñõåìà âûäàëà 1. Çíà÷èò, âñå ïîðîãîâûå ñõåìûíàñ÷èòàëè íå áîëüøå 2l1 +l2 +q−m+1.01 åäèíèö íà âòîðîì óðîâíå.
Íî ýòî è çíà÷èò, ÷òî â êàæäîì S1 × S2 íå áîëüøå 2l1 +l2 +q−m+1.01 ÿ÷ååê ïîêðàøåíû âöâåòà èç Q, ÷òî è îçíà÷àåò (k, q, 1.01, Q, S)-ïåñòðîòó òàáëèöû.Ïåðåéä¼ì ê îïèñàíèþ êîíñòðóêöèè äëÿ ðàâíîìåðíî ï¼ñòðûõ òàáëèö. Ïîñêîëüêó òåïåðü ïàëèòð ìíîãî, äîáàâèì â ñõåìó êîíñòàíòû äëÿ âñåõ âîçìîæíûõ öâåòîâ èç {0, 1}m . Ñõåìà ïðåäñòàâëÿåò ñîáîé êîíúþíêöèþ äâóõ ïîäñõåì, óñòàíàâëèâàþùèõ ðàâíîìåðíóþ ïåñòðîòó ïî ñòðîêàì è ïî ñòîëáöàì.Ïîñêîëüêó ýòè ïîäñõåìû ñèììåòðè÷íû, îïèøåì òîëüêî ïîäñõåìó äëÿ ñòðîê.Îíà òàêæå ðàçáèâàåòñÿ íà 2poly(n) îäèíàêîâî óñòðîåííûõ áëîêîâ, ïðèìåíÿþùèõñÿ ïàðàëëåëüíî. Êàæäûé áëîê ñîñòîèò èç ïÿòè óðîâíåé è ïðèìåíÿåòñÿ ê öâåòàì ÿ÷ååê ïðÿìîóãîëüíèêà S1 × S2 è íàáîðó ïàëèòð Q.
Ïåðâûéóðîâåíü ïðîâåðÿåò ñîâïàäåíèå ïàð öâåòîâ: ñîîòâåòñòâóþùàÿ ñõåìà ïðèìåíÿåòñÿ ê êàæäîé ïàðå âèäà (öâåò ÿ÷åéêè èç ñòðîêè S1 × {yi }, öâåò èç Qi ).Íà âòîðîì óðîâíå äëÿ êàæäîãî ýëåìåíòà S1 × S2 áåð¼òñÿ äèçúþíêöèÿ âñåõ108|Qi | ðåçóëüòàòîâ, ñîîòâåòñòâóþùèõ ýòîìó ýëåìåíòó. Íà òðåòüåì óðîâíå äëÿêàæäîãî i ïðèìåíÿåòñÿ ñõåìà äëÿ ïðèáëèæ¼ííîãî ïîäñ÷¼òà ÷èñëà åäèíèö íàâòîðîì óðîâíå, îòíîñÿùèõñÿ ê ñòðîêå S1 × {yi }.
Ýòà ñõåìà ïðèíèìàåò ñâîéâõîä, åñëè ÷èñëî åäèíèö â í¼ì ïðåâûøàåò 2l1 +q−m+1.01 , è îòâåðãàåò åãî, åñëè÷èñëî åäèíèö â í¼ì ìåíüøå 2l1 +q−m+1 . Íà ÷åòâ¼ðòîì óðîâíå áåðóòñÿ êîíúþíêöèè ðåçóëüòàòîâ âòîðîãî è òðåòüåãî óðîâíåé (åäèíèöà áóäåò îçíà÷àòü,÷òî ÿ÷åéêà ïîìå÷åíà è ñòðîêà íàñûùåíà). Íà ïÿòîì óðîâíå ïðèìåíÿåòñÿñõåìà äëÿ ïðèáëèæ¼ííîãî ïîäñ÷¼òà ÷èñëà åäèíèö íà ÷åòâ¼ðòîì óðîâíå: îíàïðèíèìàåò âõîä, åñëè îí ñîäåðæèò ìåíüøå 2l2 +q−m+k+1 åäèíèö, è îòâåðãàåòåãî, åñëè ñðåäè å¼ àðãóìåíòîâ áîëüøå 2l2 +q−m+k+1.01 åäèíèö.
Ïîñêîëüêó âñåóðîâíè èìåþò êîíñòàíòíóþ ãëóáèíó è ðàçìåð 2poly(n) , òî è âñÿ ñõåìà îáëàäàåò ýòèì ñâîéñòâîì, ÷òî è òðåáîâàëîñü ïîëó÷èòü. Ýñêèç ñõåìû ïîêàçàí íàðèñ. 6.3.Äîêàæåì êîððåêòíîñòü ïîñòðîåííîé ñõåìû. Ïðîâåä¼ì ðàññóæäåíèå äëÿîäíîãî áëîêà, ïîñòðîåííîãî äëÿ êîíêðåòíîé òðîéêè (S1 , S2 , Q). Ïóñòü îíïîëó÷èë íà âõîä êîä (k, q, 1, R, S)-ðàâíîìåðíî ï¼ñòðîé òàáëèöû. Çíà÷èò,îáùåå êîëè÷åñòâî ÿ÷ååê â íàñûùåííûõ ñòðîêàõ â S1 × S2 íå áîëüøå2l1 +q−m+k+1 .
Åñëè ñòðîêà yi íàñûùåíà, òî â íåé áîëüøå 2l1 +q−m+1 ÿ÷ååê ïîêðàøåíû â öâåòà èç Qi . Äëÿ íåíàñûùåííûõ ñòðîê ïîðîãîâàÿ ñõåìà íà òðåòüåì óðîâíå òî÷íî âûäàñò 0, à äëÿ íàñûùåííûõ 1 èëè 0 (ïîñëåäíåå âîçìîæíî, åñëè ïîìå÷åííûõ ÿ÷ååê áîëüøå 2l1 +q−m+1 , íî ìåíüøå 2l1 +q−m+1.01 ).Äàëåå, åäèíèöû íà ÷åòâ¼ðòîì óðîâíå ñîîòâåòñòâóåò ïîìå÷åííûì ÿ÷åéêàì,ïðî ñòðîêè êîòîðûõ ïðåäûäóùàÿ ñõåìà âûäàëà 1. Âñå ýòè ÿ÷åéêè ïîìå÷åíû è íàõîäÿòñÿ â íàñûùåííûõ ñòðîêàõ, çíà÷èò èõ íå áîëüøå 2l1 +q−m+k+1 .Çíà÷èò, ïîñëåäíÿÿ ïîðîãîâàÿ ñõåìà âûäàñò 1, ÷òî è òðåáîâàëîñü.Ïóñòü, íàîáîðîò, ñõåìà âûäàëà 1. Çíà÷èò, åäèíèö íà ÷åòâ¼ðòîì óðîâíå íåáîëüøå 2l1 +q−m+k+1.01 . Êàæäàÿ åäèíèöà ñîîòâåòñòâóåò ïîìå÷åííîé ÿ÷åéêå,ðàñïîëîæåííîé â ñòðîêå, ïðî êîòîðóþ ñõåìà íà òðåòüåì óðîâíå âûäàëà 1.Âñå íàñûùåííûå (äëÿ b = 1.01) ñòðîêè â ýòî ñïèñîê ïîïàëè, ò.ê.
äëÿ íèõïîðîãîâàÿ ñõåìà íà òðåòüåì óðîâíå òî÷íî âûäà¼ò 1. Çíà÷èò, ïîìå÷åííûõÿ÷ååê â íàñûùåííûõ ñòðîêàõ íå áîëüøå 2l1 +q−m+k+1.01 . Ïîñêîëüêó ýòî âåðíî äëÿ âñåõ òðîåê (S1 , S2 , Q), òàáëèöà ÿâëÿåòñÿ (k, q, 1, R, S)-ðàâíîìåðíîï¼ñòðîé ïî ñòðêîàì. Àíàëîãè÷íî äîêàçûâàåòñÿ (k, q, 1, R, S)-ðàâíîìåðíàÿïåñòðîòà ïî ñòîëáöàì.Òàêèì îáðàçîì, çàÿâëåííûå ñõåìû BT è RBT ïîñòðîåíû.109T (x1 , y1 )T (x1 , y2 ) . . . T (x2 , y1 ) . . . T (xK , yK )q11...q12q21≡...≡≡≡...≡∨≡≡∨...q22...≡q2M≡...∨Ïîðîãîâàÿ ñõåìà:1, åñëè > 2l +q−m+1.01 åäèíèö0, åñëè < 2l +q−m+1 åäèíèö0 èëè 1, èíà÷åÏîðîãîâàÿ ñõåìà:1, åñëè > 2l +q−m+1.01 åäèíèö0, åñëè < 2l +q−m+1 åäèíèö0 èëè 1, èíà÷å111∧q1M1∧∧Ïîðîãîâàÿ ñõåìà:1, åñëè 6 2l +q−m+k+1 åäèíèö0, åñëè > 2l +q−m+k+1.01 åäèíèö0 èëè 1, èíà÷å11∧S1 ,S2 ,QÐèñ.
6.3: Ýñêèç ñõåìû, ïðîâåðÿþùåé ðàâíîìåðíóþ ïåñòðîòó òàáëèöû.Ïðèìåíèâ ëåììó 2.37, ïîëó÷àåì ñëåäóþùååÑëåäñòâèå 6.15. Äëÿ çàäàííûõ ðàíåå çíà÷åíèé ïàðàìåòðîâ è ëþáûõ ðåëåâàíòíûõ ñèñòåì R è S è ìíîæåñòâà Q ñðåäè çíà÷åíèé ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà íàéäóòñÿ êîäû (k, q, 1.01, Q, S)-ï¼ñòðîé è(k, q, 1.01, R, S)-ðàâíîìåðíî ï¼ñòðîé òàáëèö.1106.5Çàâåðøåíèå äîêàçàòåëüñòâà îñíîâíîé òåîðåìû ýòîì ðàçäåëå ìû îïèøåì, êàê íàéòè òàáëèöû, îïèñàííûå â ïðåäûäóùåì ðàçäåëå (òî÷íåå, àðãóìåíòû ãåíåðàòîðà, êîòîðûå íóæíû äëÿ èõ ïîðîæäåíèÿ), è ïîêàæåì, ÷òî íàéäåííûå òàáëèöû äåéñòâèòåëüíî ÿâëÿþòñÿêîëìîãîðîâñêèìè ýêñòðàêòîðàìè. Çäåñü íàì ïîòðåáóåòñÿ îïðåäåëèòü êîíêðåòíûå ñèñòåìû R è S è ìíîæåñòâî Q, äëÿ êîòîðûõ ìû áóäåì ïðîâîäèòüðàññóæäåíèÿ.Îïðåäåëåíèå 6.16. Ïóñòü ôèêñèðîâàíû ÷èñëà k < n è q < m. Çäåñü èäàëåå áóäåì ïîëàãàòü, ÷òî:• S åñòü ñèñòåìà âñåõ ïàð ({z ∈ {0, 1}n | Cs (z) < l}, l) äëÿ s = s(n) èâñåõ l ∈ [k, n];• Q = {w ∈ {0, 1}m | Cs (w) < q} äëÿ s = s(n);• R åñòü ñèñòåìà âñåõ êîðòåæåé w ∈ {0, 1}m | Cs (w|v1 ) < q , .
. . , w ∈ {0, 1}m | Cs (w|vL ) < q , ∅, . . . , ∅| {z }2l −Løòóê(6.2)äëÿ s = s(n) è âñåõ {v1 , . . . , vL }, l ∈ S , ãäå ïîðÿäîê v1 , . . . , vL ñ÷èòàåòñÿ ôèêñèðîâàííûì ïðè âûáîðå ñîîòâåòñòâóþùåãî ìíîæåñòâà.Óòâåðæäåíèå 6.17. Çàäàííûå â îïðåäåëåíèè 6.16 ñèñòåìû S è R è ìíîæåñòâî Q óäîâëåòâîðÿþò òðåáîâàíèÿì îïðåäåëåíèé 6.7 è 6.10. Êðîìåòîãî, âñå ýòè ñèñòåìû ïåðå÷èñëèìû íà ïàìÿòè O(s + n), ò.å. ñóùåñòâóþò àëãîðèòìû, ðàáîòàþùèå íà ïàìÿòè O(s + n) è äåëàþùèå ñëåäóþùåå:• Äëÿ S : âî-ïåðâûõ, ïî èíäåêñó i àëãîðèòì âîçâðàùàåò âòîðóþ êîìïîíåíòó i-îé ïàðû èç S ; âî-âòîðûõ, ïî èíäåêñàì i è j àëãîðèòì âîçâðàùàåò j -ûé ýëåìåíò ïåðâîé êîìïîíåíòû i-îé ïàðû èç S .• Äëÿ Q: ïî èíäåêñó j àëãîðèòì âîçâðàùàåò j -ûé ýëåìåíò Q.• Äëÿ R: ïî èíäåêñàì i, j è k àëãîðèòì âîçâðàùàåò k -ûé ýëåìåíò j -îéêîìïîíåíòû i-ãî êîðòåæà èç R.Âî âñåõ ñëó÷àÿõ àëãîðèòì âîçâðàùàåò ñèìâîë îøèáêè, åñëè õîòÿ áû îäèíèç èíäåêñîâ ïðåâûñèë ðàçìåð ñîîòâåòñòâóþùåãî ìíîæåñòâà.111Äîêàçàòåëüñòâî.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
