Диссертация (1103424), страница 21
Текст из файла (страница 21)
Èç ïåðâîãî ñîîòíîøåíèÿ ïîëó÷àåì m 6 2k − log n − O(1),à èç âòîðîãî d 6 k − 21 log n − O(1), îòêóäà δ 6 k − O(log n), ÷òî è òðåáóåòñÿ â óñëîâèè òåîðåìû 6.2. Äëÿ óñèëåííûõ êîëìîãîðîâñêèõ ýñòðàêòîðîâ â ñèëó òåîðåìû 6.5 ïîëó÷àåì òðåáîâàíèå 2k > (max{m, n})2 2m , îòêóäà m 6 k − 2 log n − O(1). Ïîñêîëüêó m − d > 0, ïîëó÷àåì, ÷òîd 6 k − 2 log n − O(1), îòêóäà δ 6 k − O(log n), ÷òî òàêæå ñîîòâåòñòâóåò óñëîâèþ òåîðåìû 6.2.6.4Ïðèìåíåíèå ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà ýòîì ðàçäåëå ìû îïèøåì îñëàáëåíèå ñâîéñòâ ïåñòðîòû è ðàâíîìåðíîéïåñòðîòû è ïîêàæåì, ÷òî òàáëèöû ñ ýòèìè ñâîéñòâàìè âñòðå÷àþòñÿ ñðåäèçíà÷åíèé ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà.Èäåÿ, íà êîòîðîé îñíîâàíî ïðèìåíåíèå ãåíåðàòîðà, òà æå, ÷òî è â ðàçäåëàõ 4.2 è 4.3.2: ìû ñôîðìóëèðóåì íåêîòîðîå ñâîéñòâî, ñëåäóþùåå èç (ðàâíîìåðíîé) ïåñòðîòû òàáëèöû è ïðè ýòîì ðàñïîçíàþùååñÿ ñõåìàìè èç ôóíêöèîíàëüíûõ ýëåìåíòîâ êîíñòàíòíîé ãëóáèíû.
Ïðèìåíèâ ëåììó 2.37, ìûïîëó÷èì, ÷òî ñðåäè çíà÷åíèé ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà âñòðå÷àþòñÿòàáëèöû ñ ýòèì ñâîéñòâîì. Íà÷í¼ì ñ ôîðìóëèðîâêè ýòîãî ñâîéñòâà, ïðåäâàðèòåëüíî äàâ âñïîìîãàòåëüíîå îïðåäåëåíèå.102Îïðåäåëåíèå 6.7. Ïóñòü çàäàíû íàòóðàëüíûå ÷èñëà k < n è q < m. Ñýòîãî ìîìåíòà è äî êîíöà ðàçäåëà áóäåì íàçûâàòü k -ðåëåâàíòíûìè ñèñòåìû ïàð âèäà (S, l), ãäå S ïîäìíîæåñòâî {0, 1}n , à l öåëîå ÷èñëî èçîòðåçêà [k, n], òàêèå ÷òî â ëþáîé ïàðå ìíîæåñòâî S ñîäåðæèò íå áîëüøå2l ýëåìåíòîâ, à âñÿ ñèñòåìà ñîäåðæèò 2poly(n) ïàð.2 Òàêæå áóäåì íàçûâàòüq -ðåëåâàíòíûìè ïîäìíîæåñòâà {0, 1}m , ñîäåðæàùèå íå áîëüøå 2q ýëåìåíòîâ.Îïðåäåëåíèå 6.8.
Ïóñòü b ïîëîæèòåëüíîå äåéñòâèòåëüíîå ÷èñëî, àk < n è q < m ñóòü íàòóðàëüíûå ÷èñëà. Ïóñòü çàäàíû k -ðåëåâàíòíàÿñèñòåìà ïàð S è q -ðåëåâàíòíîå ìíîæåñòâî Q. Áóäåì ãîâîðèòü, ÷òî òàáëèöà T (ò.å. ôóíêöèÿ T : {0, 1}n × {0, 1}n → {0, 1}m ) ÿâëÿåòñÿ (k, q, b, Q, S)ï¼ñòðîé, åñëè äëÿ ëþáûõ (S1 , l1 ) è (S2 , l2 ) èç S êîëè÷åñòâî ÿ÷ååê â S1 × S2 ,ïîêðàøåííûõ â öâåòà èç Q, ìåíüøå 2l1 +l2 +q−m+b .Ïàðàìåòð b íå íåñ¼ò ñîäåðæàòåëüíîé íàãðóçêè è ââåä¼í ïî òåõíè÷åñêèìïðè÷èíàì: îí íóæåí äëÿ äîêàçàòåëüñòâà òîãî, ÷òî òàáëèöû ñ ýòèì ñâîéñòâîì âñòðåòÿòñÿ ñðåäè çíà÷åíèé ãåíåðàòîðà.  íàøèõ óòâåðæäåíèÿõ îíáóäåò ïðèìåðíî ðàâåí 1.
Çàìåòèì, ÷òî ïðè ðîñòå b îïðåäåëåíèå îñëàáëÿåòñÿ, ò.å. âñ¼ áîëüøå òàáëèö ñòàíîâÿòñÿ (k, q, b, Q, S)-ï¼ñòðûìè.Íåòðóäíî ïðîâåðèòü ñïðàâåäëèâîñòü ñëåäóþùåãî óòâåðæäåíèÿ:Óòâåðæäåíèå 6.9. Ïðîèçâîëüíàÿ (2k , 2q )-ï¼ñòðàÿ òàáëèöà ÿâëÿåòñÿ(k, q, 1, Q, S)-ï¼ñòðîé ïðè ëþáîì âûáîðå ðåëåâàíòíûõ Q è S .Äîêàçàòåëüñòâî. Ðàññìîòðèì êðàéíèé ñëó÷àé: ðàçìåð S1 â òî÷íîñòè ðàâåí2l1 , ðàçìåð S2 â òî÷íîñòè ðàâåí 2l2 , ðàçìåð Q â òî÷íîñòè ðàâåí 2q è ïðè ýòîìöâåòà èç ìíîæåñòâà Q âñòðå÷àþòñÿ â S1 ×S2 ÷àùå îñòàëüíûõ öâåòîâ.  ýòîìñëó÷àå äîëÿ ÿ÷ååê èç S1 × S2 , ïîêðàøåííûõ â öâåòà èç Q, íå ïðåâîñõîäèòq2 · 22m = 21+q−m , îòêóäà êîëè÷åñòâî òàêèõ ÿ÷ååê íå ïðåâîñõîäèò 2l1 · 2l2 ·21+q−m = 2l1 +l2 +q−m+1 .
 îñòàëüíûõ ñëó÷àÿõ ðàçìåðû ìíîæåñòâ S1 , S2 èëèQ ìåíüøå ïðåäåëüíûõ èëè öâåòà èç Q íå ñàìûå ÷àñòûå, ïîýòîìó êîëè÷åñòâîòàêèõ ÿ÷ååê áóäåò åù¼ ìåíüøå, çíà÷èò òðåáóåìàÿ â îïðåäåëåíèè 6.8 îöåíêàáóäåò âûïîëíåíà.Òåïåðü ñôîðìóëèðóåì âàðèàíò äëÿ ðàâíîìåðíî ï¼ñòðûõ òàáëèö. äîêàçàòåëüñòâå îñíîâíîé òåîðåìû òàêèå áîëüøèå ñèñòåìû íå ïîíàäîáÿòñÿ, áóäåò äîñòàòî÷íîâñåãî ëèøü ñèñòåìû ðàçìåðà O(n), íî âñïîìîãàòåëüíûå ôàêòû âåðíû è äëÿ òàêèõ áîëüøèõ ñèñòåì, àóìåíüøåíèå ðàçìåðà íå äàñò íèêàêîãî âûèãðûøà â îñíîâíîé òåîðåìå.2103Îïðåäåëåíèå 6.10.
Ïóñòü çàäàíû íàòóðàëüíûå ÷èñëà k < n è q < m.Ñ ýòîãî ìîìåíòà è äî êîíöà ðàçäåëà áóäåì íàçûâàòü (k ,q )-ðåëåâàíòíûìèñèñòåìû êîðòåæåé âèäà (Q1 , . . . , Q2l ), òàêèå ÷òî l öåëîå ÷èñëî èç îòðåçêà[k, n], êàæäîå Qi êàæäîãî êîðòåæà ñîäåðæèò ìåíåå 2q ýëåìåíòîâ, à âñÿñèñòåìà ñîäåðæèò 2poly(n) êîðòåæåé.3Îïðåäåëåíèå 6.11. Ïóñòü b, k è q òàêèå æå, êàê â îïðåäåëåíèè 6.8.Ïóñòü òàêæå çàäàíû k -ðåëåâàíòíàÿ ñèñòåìà ïàð S è (k ,q )-ðåëåâàíòíàÿ ñèñòåìà êîðòåæåé R. Äëÿ ôèêñèðîâàííûõ (S1 , l1 ) è (S2 , l2 ) èç S , à òàêæåQ = (Q1 , .
. . , Q2l1 ) ∈ R îïðåäåëèì ïðîöåäóðó ïîìåòêè ÿ÷ååê S1 × S2 : äëÿêàæäîãî i ∈ 1, |S1 | ïîìåòèì ÿ÷åéêè èç ñòîëáöà {vi } × S2 , ïîêðàøåííûå âöâåò èç Qi (çäåñü S1 = {v1 , . . . , v|S1 | }). Íàçîâ¼ì ñòîëáåö íàñûùåííûì, åñëèîí ñîäåðæèò áîëåå 2l2 +q−m+b ïîìå÷åííûõ ÿ÷ååê. Íàêîíåö, íàçîâ¼ì òàáëèöó(k, q, b, R, S)-ðàâíîìåðíî ïî ñòîëáöàì ï¼ñòðîé, åñëè äëÿ ëþáûõ (S1 , l1 ) è(S2 , l2 ) èç S è Q = (Q1 , . . . , Q2l1 ) ∈ R îáùåå êîëè÷åñòâî ïîìå÷åííûõ êëåòîê â íàñûùåííûõ ñòîëáöàõ S1 × S2 íå áîëüøå 2l2 +q−m+k+b . Àíàëîãè÷íîîïðåäåëèì (k, q, b, R, S)-ðàâíîìåðíî ïî ñòðîêàì ï¼ñòðóþ òàáëèöó è áóäåìãîâîðèòü, ÷òî òàáëèöà (k, q, b, R, S)-ðàâíîìåðíî ï¼ñòðàÿ, åñëè îíà ðàâíîìåðíî ï¼ñòðàÿ îäíîâðåìåííî ïî ñòðîêàì è ïî ñòîëáöàì.Çàìå÷àíèå 6.12.
Èç îïðåäåëåíèÿ 6.11 ñëåäóåò, ÷òî îáùåå êîëè÷åñòâî íàñûùåííûõ ñòðîê èëè ñòîëáöîâ íå áîëüøå 2l2 +q−m+k+b /2l2 +q−m+b = 2k .Àíàëîãè÷íî óòâåðæäåíèþ 6.9 äîêàæåì ñëåäóþùååÓòâåðæäåíèå 6.13. Ïðîèçâîëüíàÿ (2k , 2q )-ðàâíîìåðíî ï¼ñòðàÿ òàáëèöàÿâëÿåòñÿ (k, q, 1, R, S)-ðàâíîìåðíî ï¼ñòðîé ïðè ëþáîì âûáîðå ðåëåâàíòíûõ R è S .Äîêàçàòåëüñòâî. Ïðîâåä¼ì ðàññóæäåíèå òîëüêî äëÿ ðàâíîìåðíî ïî ñòîëáöàì ï¼ñòðûõ òàáëèö, äëÿ ðàâíîìåðíî ïî ñòðîêàì ï¼ñòðûõ ðàññóæäåíèå áóäåò àíàëîãè÷íûì.Ïóñòü òàáëèöà T ÿâëÿåòñÿ (2k , 2q )-ðàâíîìåðíî ïî ñòîëáöàì ï¼ñòðîé.Ïóñòü ðàçìåð S1 â òî÷íîñòè ðàâåí 2l1 , à â êà÷åñòâå Qi âûáðàíû 2q íàèáîëåå ÷àñòûõ öâåòîâ â ñòîëáöå {vi } × S2 .
Ïîñêîëüêó b = 1, òî íàñûùåííûìèáóäóò ñòîëáöû, ñîäåðæàùèå áîëåå 2 · 2l2 +q−m îòìå÷åííûõ ÿ÷ååê. Ðàññìîòðèì íåêîòîðîå ïîäìíîæåñòâî S10 ⊂ S1 , òàêîå ÷òî |S10 | = 2k è ëèáî âñå åãî3Çäåñü òàêæå â ïðèëîæåíèè áóäåò äîñòàòî÷íî ñóùåñòâåííî ìåíüøèõ ñèñòåì.104ýëåìåíòû ÿâëÿþòñÿ íàñûùåííûìè ñòîëáöàìè, ëèáî îíî ñîäåðæèò âñå íàñûùåííûå ñòîëáöû â S1 .
 ñèëó ðàâíîìåðíîé ïåñòðîòû äîëÿ ïîìå÷åííûõâåðøèí â ïðÿìîóãîëüíèêå S10 × S2 ìåíüøå 2 · 2q /2m = 21+q−m , îòêóäà ÷èñëîòàêèõ âåðøèí ìåíüøå 2k ·2l2 ·21+q−m = 2l2 +q−m+k+1 . Îòñþäà ÷èñëî íàñûùåííûõ ñòîëáöîâ ìåíüøå 2l2 +q−m+k+1 /2l2 +q−m+1 = 2k . Çíà÷èò, âñå íàñûùåííûåñòîëáöû ñîäåðæàòñÿ â ìíîæåñòâå S10 , à ïîòîìó ÷èñëî îòìå÷åííûõ âåðøèíâ íàñûùåííûõ ñòîëáöàõ ìåíüøå 2l2 +q−m+k+1 , ÷òî è òðåáîâàëîñü.Òåïåðü àíàëîãè÷íî ðàçäåëó 4.2.2 ïîñòðîèì ñõåìó êîíñòàíòíîé ãëóáèíû, ðàñïîçíàþùóþ ìîäèôèöèðîâàííûå ñâîéñòâà ïåñòðîòû. Íà âõîä ñõåìå áóäåò ïîäàâàòüñÿ ïîëíàÿ òàáëèöà, ò.å.
ðàçìåð âõîäà ðàâåí m22n . ×òîáû àðãóìåíò ãåíåðàòîðà îñòàâàëñÿ ïîëèíîìèàëüíûì, íóæíî, ÷òîáû ðàçìåðñõåìû áûë ýêñïîíåíöèàëüíûì, ò.å. 2poly(n) . Òàêîé ñõåìû äîñòàòî÷íî äëÿäîêàçàòåëüñòâà ñóùåñòâîâàíèÿ íóæíîé òàáëèöû ñðåäè çíà÷åíèé ãåíåðàòîðà. Äåéñòâèòåëüíî, ïî òåîðåìå 6.5 ñ ó÷¼òîì çàìå÷àíèÿ 6.6 ïðîèçâîëüíàÿòàáëèöà ñ âûáðàííûìè ïàðàìåòðàìè ÿâëÿåòñÿ (ðàâíîìåðíî) ï¼ñòðîé ñ ïîëîæèòåëüíîé îòäåë¼ííîé îò íóëÿ âåðîÿòíîñòüþ.  ñèëó óòâåðæäåíèé 6.9è 6.13 (ðàâíîìåðíî) ï¼ñòðûå òàáëèöû ÿâëÿþòñÿ òàêîâûìè è â ñìûñëå îïðåäåëåíèé 6.8 è 6.11. Çíà÷èò, ïðîèçâîëüíàÿ òàáëèöà ÿâëÿåòñÿ (ðàâíîìåðíî)ï¼ñòðîé â ñìûñëå ýòèõ îïðåäåëåíèé òàêæå ñ ïîëîæèòåëüíîé îòäåë¼ííîé îòíóëÿ âåðîÿòíîñòüþ.
Åñëè ìû äîêàæåì, ÷òî ìîäèôèöèðîâàííàÿ (ðàâíîìåðíàÿ) ïåñòðîòà ðàñïîçíà¼òñÿ ñõåìîé êîíñòàíòíîé ãëóáèíû è ðàçìåðà 2poly(n) ,òî ïî ëåììå 2.37 ñëó÷àéíàÿ òàáëèöà, ïîëó÷åííàÿ ïðè ïîìîùè ãåíåðàòîðàÍèñàíàÂèãäåðñîíà, òàêæå ÿâëÿåòñÿ (ðàâíîìåðíî) ï¼ñòðîé â ìîäèôèöèðîâàííîì ñìûñëå ñ ïîëîæèòåëüíîé âåðîÿòíîñòüþ. Òàêèì îáðàçîì, íóæíàÿòàáëèöà ñðåäè çíà÷åíèé ãåíåðàòîðà áóäåò ñóùåñòâîâàòü, ÷òî è òðåáóåòñÿ. Êñîæàëåíèþ, â ÷èñòîì âèäå ýòîò ïëàí íå ñðàáàòûâàåò, ïîýòîìó ìû äîêàæåì÷óòü áîëåå ñëàáîå óòâåðæäåíèå, ãäå áóäåò èñïîëüçîâàí ïàðàìåòð b.Òåîðåìà 6.14.
Ïóñòü çàäàíû íàòóðàëüíûå ÷èñëà k < n è q < m. Ïóñòüòàêæå çàäàíû k -ðåëåâàíòíàÿ ñèñòåìà ïàð S , q -ðåëåâàòíîå ìíîæåñòâîQ è (k , q )-ðåëåâàòíàÿ ñèñòåìà êîðòåæåé R. Òîãäà ñóùåñòâóþò ñõåìû èçôóíêöèîíàëüíûõ ýëåìåíòîâ BT è RBT ñ m22n âõîäàìè è îäíèì âûõîäîì,êîíñòàíòíîé ãëóáèíû è ðàçìåðà 2poly(n) , òàêèå ÷òî:• Ñõåìà BT (ñîîòâ., RBT ) ïðèíèìàåò êîä ëþáîé (k, q, 1, Q, S)ï¼ñòðîé (ñîîòâ., (k, q, 1, R, S)-ðàâíîìåðíî ï¼ñòðîé) òàáëèöû;105• Åñëè ñõåìà BT (ñîîòâ., RBT ) ïðèíèìàåò êîä íåêîòîðîé òàáëèöû, òî ýòà òàáëèöà ÿâëÿåòñÿ (k, q, 1.01, Q, S)-ï¼ñòðîé (ñîîòâ.,(k, q, 1.01, R, S)- ðàâíîìåðíî ï¼ñòðîé).Äîêàçàòåëüñòâî. Ïîñòðîèì óêàçàííûå ñõåìû íåïîñðåäñòâåííî. Îíè íåîáÿçàíû áûòü ðàâíîìåðíûìè, ïîýòîìó ìíîæåñòâî Q è ñèñòåìû S è R ìîæíî çàïàÿòü â ñõåìó.
Òî åñòü, ìîæíî ïîñòðîèòü ñõåìó äëÿ êîíêðåòíîãî íàáîðà (S1 , S2 , l1 , l2 , Q), ãäå (S1 , l1 ), (S2 , l2 ) ∈ S , (èëè íàáîðà (S1 , S2 , l1 , l2 , Q),ãäå Q ∈ R) è âçÿòü êîíúþíêöèþ 2poly(n) êîïèé ýòîé ñõåìû äëÿ ðàçíûõíàáîðîâ. Îïèøåì ñõåìó äëÿ êîíêðåòíîãî íàáîðà.Ëåãêî ïðîâåðèòü, ÿâëÿåòñÿ ëè äàííàÿ ÿ÷åéêà ïîìå÷åííîé. Äîñòàòî÷íîñðàâíèòü å¼ öâåò ñ êàæäûì öâåòîì èç Q (èëè Qi äëÿ ñòðîêè i) è âçÿòüäèçúþíêöèþ ïîëó÷åííûõ çíà÷åíèé. Ñëîæíåå ïîñ÷èòàòü êîëè÷åñòâî ïîìå÷åííûõ ÿ÷ååê è ñðàâíèòü ýòî ÷èñëî ñ ïîðîãîì.
Òàêîé ïîäñ÷¼ò íåâîçìîæíîâûïîëíèòü òî÷íî, íî âîçìîæíî ñäåëàòü ïðèáëèæ¼ííî, ÷òî áóäåò äîñòàòî÷íîäëÿ íàøèõ öåëåé.Ìû áóäåì èñïîëüçîâàòü ñõåìó, ñóùåñòâóþùóþ ïî òåîðåìå 2.32. Äëÿ ï¼ñòðûõ òàáëèö ìû èñïîëüçóåì ñõåìó ñ |S1 | · |S2 | àðãóìåíòàìè, êîòîðàÿ ïðèíèìàåò ñâîé âõîä, åñëè ÷èñëî åäèíèö ñðåäè àðãóìåíòîâ ìåíüøå 2l1 +l2 +q−m+1 ,è îòâåðãàåò ñâîé âõîä, åñëè ÷èñëî åäèíèö áîëüøå 2l1 +l2 +q−m+1.01 (åñëè ÷èñëî åäèíèö ïðîìåæóòî÷íîå, òî ñõåìà ìîæåò êàê ïðèíÿòü, òàê è îòâåðãíóòüâõîä). Äëÿ ðàâíîìåðíî ï¼ñòðûõ òàáëèö ìû èñïîëüçóåì äâå ïîäîáíûõ ñõåìû ïîñëåäîâàòåëüíî. Ïåðâàÿ ñõåìà èìååò |S2 | àðãóìåíòîâ, ïðèíèìàåò ñâîéâõîä, åñëè ñðåäè àðãóìåíòîâ áîëüøå 2l2 +q−m+1.01 åäèíèö, è îòâåðãàåò ñâîéâõîä, åñëè ñðåäè àðãóìåíòîâ ìåíüøå 2l2 +q−m+1 åäèíèö.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
