Диссертация (1103424), страница 19
Текст из файла (страница 19)
Àíàëîãè÷íîäëÿ óñëîâèÿ c ÷èñëî i0 áóäåò ïðèìåðíî ðàâíî m0 = k 0 +d+1. Òàêèì îáðàçîì,ïðè ñóùåñòâåííîì îòëè÷èè k îò k 0 ÷èñëà i è i0 òîæå ñêîðåå âñåãî ïîëó÷àòñÿðàçíûìè.Äàæå åñëè ÷èñëà k è k 0 ñîâïàäàþò, âñ¼ ðàâíî äëÿ òîãî, ÷òîáû ÷èñëà i èi0 ãàðàíòèðîâàííî ñîâïàëè, íóæíî áîëåå ñëîæíîå ðàññóæäåíèå, ÷åì ìåòîäãèáðèäèçàöèè. Ïîêà ÷òî òàêîãî ðàññóæäåíèÿ íàéòè íå ïîëó÷àåòñÿ. Âîçìîæíî, òðåáóåòñÿ ñóùåñòâåííî äðóãàÿ êîìáèíàòîðíàÿ êîíñòðóêöèÿ. Òàêèìîáðàçîì, àíàëîã òåîðåìû Ìó÷íèêà äëÿ CAM-ñëîæíîñòè äëÿ äâóõ óñëîâèéïîêà ÷òî îñòà¼òñÿ ãèïîòåçîé.1m.92Ãëàâà 6Êîëìîãîðîâñêèå ýêñòðàêòîðû ñîãðàíè÷åíèåì íà ïàìÿòü ýòîé ãëàâå ìû ïðèìåíèì òåõíèêó íàèâíîé äåðàíäîìèçàöèè â ñèòóàöèè, ñóùåñòâåííî îòëè÷íîé îò òåîðåìû Ìó÷íèêà.
À èìåííî, ìû ïåðåëîæèìäëÿ ñëîæíîñòè ñ îãðàíè÷åíèåì íà ïàìÿòü òåîðåìó 2.30 î ñóùåñòâîâàíèèîáû÷íûõ è óñèëåííûõ êîëìîãîðîâñêèõ ýêñòðàêòîðîâ.  ðàçäåëå 6.1 ìû äàäèì íåîáõîäèìûå îïðåäåëåíèÿ è ñôîðìóëèðóåì òåîðåìó ñóùåñòâîâàíèÿ. Âðàçäåëå 6.2 ìû îïðåäåëèì ãëàâíûé êîìáèíàòîðíûé îáúåêò, èñïîëüçóþùèéñÿ â äîêàçàòåëüñòâå ï¼ñòðûå è ðàâíîìåðíî ï¼ñòðûå òàáëèöû.1 Çàòåì, âðàçäåëå 6.3, ìû ïåðåñêàæåì äîêàçàòåëüñòâî Çèìàíäà òåîðåìû 2.30, èñïîëüçóþùåå ï¼ñòðûå òàáëèöû, è ïîêàæåì, êàêèå èçìåíåíèÿ íóæíî ñäåëàòü äëÿäîêàçàòåëüñòâà íàøåé òåîðåìû.
 ðàçäåëå 6.4 ìû îïèøåì òåõíè÷åñêèå êîíñòðóêöèè, èñïîëüçóåìûå äëÿ äîêàçàòåëüñòâà íîâîé òåîðåìû, à â ðàçäåëå 6.5ïðîâåä¼ì ñàìî äîêàçàòåëüñòâî. Âñå ýòàïû áóäóò ïðîâîäèòüñÿ ïàðàëëåëüíîäëÿ îáû÷íûõ è óñèëåííûõ êîëìîãîðîâñêèõ ýêñòðàêòîðîâ.6.1Îïðåäåëåíèÿ è ôîðìóëèðîâêè òåîðåì ðàçäåëå 2.3 ìû îïðåäåëèëè ïîíÿòèÿ îáû÷íîãî è óñèëåííîãî êîëìîãîðîâñêîãî ýêñòðàêòîðà, à òàêæå ñôîðìóëèðîâàëè ðåçóëüòàòû êàñàòåëüíîèõ ñóùåñòâîâàíèÿ, ïîëó÷åííûå Çèìàíäîì.  ýòîì ðàçäåëå ìû ðàñïðîñòðàíèì îïðåäåëåíèÿ íà ñëîæíîñòü ñ îãðàíè÷åíèåì íà ïàìÿòü è ñôîðìóëèðóåìíîâûå ðåçóëüòàòû.Îñíîâíàÿ òðóäíîñòü ñîñòîèò â ðàñøèðåíèè íà ïîëèíîìèàëüíóþ ïàìÿòü îðèãèíàëå Çèìàíä íàçûâàåò èõ ñáàëàíñèðîâàííûìè (balanced) è ðàäóæíî ñáàëàíñèðîâàííûìè (rainbow balanced) òàáëèöàìè. Íàì ïðåäñòàâëÿåòñÿ, ÷òî, ïîñêîëüêó ðå÷ü ïîéä¼ò î öâåòàõ ÿ÷ååê,òåðìèí ïåñòðîòà áîëåå óäà÷íî ïåðåäà¼ò íà ðóññêîì ÿçûêå ñóòü ÿâëåíèÿ.193ïîíÿòèÿ çàâèñèìîñòè äâóõ ñëîâ.
Äåëî â òîì, ÷òî âåëè÷èíû Cs (x) − Cs (x|y)è Cs (x) + Cs (y) − Cs (x, y) íå ìîíîòîííû ïî s. Ïîýòîìó èñïîëüçîâàíèå ïîäîáíûõ âåëè÷èí äëÿ ôîðìàëèçàöèè ñèòóàöèè çàâèñèìîñòü äâóõ ñëîâ íåáîëüøå çàäàííîé âåëè÷èíû çàòðóäíèòåëüíî. Âìåñòî ýòîãî ìû áóäåì çàäàâàòü îòäåëüíûå îãðàíè÷åíèÿ íà ïàìÿòü äëÿ ñëîæíîñòåé ñëîâ x, y è ïàðû(x, y).Îïðåäåëåíèå 6.1.
Ïóñòü s : N → N êîíñòðóèðóåìàÿ ïî ïàìÿòè ôóíêöèÿ, à m : N → N, k : N → N è δ : N → N ôóíêöèè, âû÷èñëèìûå íà ïàìÿòè s(n). Áóäåì ãîâîðèòü, ÷òî ñåìåéñòâî ôóíêöèé KExtn : {0, 1}n ×{0, 1}n →{0, 1}m(n) ÿâëÿåòñÿ (k , δ )-êîëìîãîðîâñêèì ýêñòðàêòîðîì ñ îãðàíè÷åíèåì íàïàìÿòü s = s(n), åñëè KExtn âû÷èñëèìà íà ïàìÿòè O(s(n)) è äëÿ íåêîòîðîé êîíñòàíòû µ > 1 äëÿ âñåõ n è âñåõ ñëîâ x è y äëèíû n èç óñëîâèéCs (x) > k(n), Cs (y) > k(n) è Cµs (x, y) > Cs (x) + Cs (y) − δ(n) ñëåäóåò,÷òî Cs (KExtn (x, y)) > m(n) − δ(n) − O(log n). Åñëè, áîëåå òîãî, äëÿ âñåõòàêèõ x è y âûïîëíåíû óñëîâèÿ Cs (KExtn (x, y)|x) > m(n) − δ(n) − O(log n)è Cs (KExtn (x, y)|y) > m(n) − δ(n) − O(log n), òî áóäåì íàçûâàòü òàêîéýêñòðàêòîð óñèëåííûì.Íàäî îòìåòèòü, ÷òî â ðàáîòå [18] âñ¼-òàêè èñïîëüçîâàëàñü çàâèñèìîñòüìåæäó x è y â ÿâíîì âèäå, íî ïðè ýòîì äëÿ C(x) è C(x|y) áûëè çàäàíûðàçíûå îãðàíè÷åíèÿ íà ïàìÿòü.
Ýòè îãðàíè÷åíèÿ ñîîòâåòñòâóþò s è µs âíàøåì îïðåäåëåíèè.Ìû äîêàæåì ñëåäóþùèé àíàëîã ðåçóëüòàòà Çèìàíäà 2.30:Òåîðåìà 6.2. Ñóùåñòâóåò ïîëèíîì p(n), òàêîé ÷òî äëÿ ëþáîé ôóíêöèès(n) > p(n), êîíñòðóèðóåìîé ïî ïàìÿòè, è ëþáûõ ôóíêöèé 1 < k(n) < nè 1 < δ(n) < k(n) − O(log n), âû÷èñëèìûõ íà ïàìÿòè s(n), ñóùåñòâóþò (k , δ )-êîëìîãîðîâñêèé ýêñòðàêòîð äëÿ îãðàíè÷åíèÿ íà ïàìÿòü s(n) ñîçíà÷åíèÿìè äëèíû m = 2k(n) − O(log n), à òàêæå (k , δ )-êîëìîãîðîâñêèéýêñòðàêòîð â ñèëüíîì ñìûñëå äëÿ îãðàíè÷åíèÿ íà ïàìÿòü s(n) ñî çíà÷åíèÿìè äëèíû m = k(n) − O(log n).6.2ϼñòðûå òàáëèöû ýòîì ðàçäåëå ìû îïðåäåëèì ïîíÿòèÿ ï¼ñòðûõ è ðàâíîìåðíî ï¼ñòðûõòàáëèö. Ýòî îñíîâíîé êîìáèíàòîðíûé èíñòðóìåíò, èñïîëüçîâàííûé Çèìàíäîì äëÿ äîêàçàòåëüñòâà òåîðåìû 2.30.
Äëÿ ïîëíîòû èçëîæåíèÿ ìû íå òîëü94êî äàäèì îïðåäåëåíèÿ (êîòîðûå áóäóò ñëåãêà îòëè÷àòüñÿ îò çèìàíäîâñêèõ,îñòàâàÿñü ýêâèâàëåíòíûìè èì), íî è ïðèâåä¼ì äîêàçàòåëüñòâà ñóùåñòâîâàíèÿ ýòèõ îáúåêòîâ.Êâàäðàòíîé òàáëèöåé ìû áóäåì íàçûâàòü ôóíêöèþ èç {0, 1}n × {0, 1}nâ {0, 1}m . Ïðè ýòîì ïåðâûé àðãóìåíò ìû áóäåì ïîíèìàòü êàê íîìåð ñòîëáöà, âòîðîé êàê íîìåð ñòðîêè, à çíà÷åíèå êàê öâåò ñîîòâåòñòâóþùåéÿ÷åéêè.Îïðåäåëåíèå6.3. Íàçîâ¼ì (K , Q)-ï¼ñòðîé òàáëèöåé ôóíêöèþBT : {0, 1}n × {0, 1}n → {0, 1}m , îáëàäàþùóþ ñëåäóþùèì ñâîéñòâîì: â ëþáîì ïðÿìîóãîëüíèêå S1 × S2 , ãäå Si ⊂ {0, 1}n è |Si | > K , äîëÿ ÿ÷ååê,ïîêðàøåííûõ â Q ñàìûõ ÷àñòûõ â ýòîì ïðÿìîóãîëüíèêå öâåòîâ, ìåíüøå2Q/2m .Ýòî ñâîéñòâî ïîõîæå íà îïðåäåëåíèå 2.23 ýêñòðàêòîðîâ ñ äâóìÿ èñòî÷íèêàìè ïðè ïîìîùè ðàñêðàñîê òàáëèö.
Óñëîâèå ïåñòðîòû ñëàáåå ñâîéñòâàýêñòðàêòîðà ïðè áîëüøèõ Q, à èìåííî ïðè Q > ε2m , è ñèëüíåå åãî ïðè ìàëåíüêèõ Q, ò.å. ïðè Q < ε2m . Ïðè ýòîì ìîæíî çàìåòèòü, ÷òî åñëè òàáëèöàÿâëÿåòñÿ (K , Q)-ï¼ñòðîé, òî îíà ÿâëÿåòñÿ è (K , Q0 )-ï¼ñòðîé ïðè Q0 > Q.Äåéñòâèòåëüíî, åñëè äîëÿ ÿ÷ååê, ïîêðàøåííûõ â Q ñàìûõ ÷àñòûõ öâåòîâ,ìåíüøå, ÷åì 2Q/2m , òî ñðåäíÿÿ äîëÿ ÿ÷ååê ýòèõ öâåòîâ ìåíüøå 2/2m , à çíà÷èò è äîëÿ ÿ÷ååê ëþáîãî îñòàâøåãîñÿ öâåòà ìåíüøå 2/2m . Òàêèì îáðàçîì,ïðè óâåëè÷åíèè Q íà åäèíèöó äîëÿ ÿ÷ååê, ïîêðàøåííûõ â Q ñàìûõ ÷àñòûõöâåòîâ, âîçðàñò¼ò ìåíüøå, ÷åì íà 2/2m , à âåðõíÿÿ îöåíêà (ò.å. 2Q/2m ) ðîâíî íà 2/2m .
Ñëåäîâàòåëüíî, íåðàâåíñòâî ñîõðàíèòñÿ.Òàêæå ìîæíî çàìåòèòü, ÷òî ñâîéñòâî äîñòàòî÷íî ïðîâåðèòü äëÿ âñåõ S1è S2 ðàçìåðà â òî÷íîñòè K . Äåéñòâèòåëüíî, ïóñòü ñâîéñòâî íàðóøàåòñÿ,ò.å. äëÿ íåêîòîðûõ S1 è S2 äîëÿ ÿ÷ååê â ïðÿìîóãîëüíèêå S1 × S2 , ïîêðàøåííûõ â Q íàèáîëåå ÷àñòûõ öâåòîâ, íå ìåíüøå 2Q/2m . Ýòà äîëÿ ðàâíàñðåäíåé äîëå ÿ÷ååê, ïîêðàøåííûõ â ýòè Q öâåòîâ, ñðåäè âñåõ ïðÿìîóãîëüíèêîâ S10 × S20 , ãäå Si0 ⊂ Si è |Si0 | = K , i = 1, 2. Çíà÷èò, â êàêîì-òî ïðÿìîóãîëüíèêå S10 × S20 , ãäå |Si0 | = K , äîëÿ ÿ÷ååê, ïîêðàøåííûõ â ýòè Q öâåòîâ,íå ìåíüøå 2Q/2m . Çíà÷èò, äîëÿ ÿ÷ååê, ïîêðàøåííûõ â Q íàèáîëåå ÷àñòûõâ ýòîì ïðÿìîóãîëüíèêå öâåòîâ, òåì áîëåå íå ìåíüøå 2Q/2m .
Òàêèì îáðàçîì, åñëè ñâîéñòâî íàðóøàåòñÿ äëÿ êàêèõ-òî ìíîæåñòâ, òî îíî íàðóøàåòñÿè äëÿ íåêîòîðûõ ìíîæåñòâ ðàçìåðà â òî÷íîñòè K . Çíà÷èò, äîñòàòî÷íî ïîòðåáîâàòü åãî âûïîëíåíèÿ äëÿ ìíîæåñòâ ðàçìåðà â òî÷íîñòè K , ÷òî è áûëî95çàÿâëåíî.Íàì òàêæå ïîòðåáóåòñÿ óñèëåííîå îïðåäåëåíèå, â êîòîðîì ñàìûå ÷àñòûåöâåòà âûáèðàþòñÿ íå âî âñ¼ì ïðÿìîóãîëüíèêå, à â îòäåëüíûõ ñòðîêàõ èñòîëáöàõ.Îïðåäåëåíèå 6.4. Íàçîâ¼ì (K , Q)-ðàâíîìåðíî ïî ñòîëáöàì ï¼ñòðîéòàáëèöåé ôóíêöèþ RBT : {0, 1}n × {0, 1}n → {0, 1}m , òàêóþ ÷òî äëÿ ëþáîãî ïðÿìîóãîëüíèêà S1 × S2 , ãäå Si ⊂ {0, 1}n è |Si | > K , âûïîëíåíî ñëåäóþùåå ñâîéñòâî.
Ïóñòü äëÿ âñåõ x ∈ S1 â ñòîëáöå {x} × S2 îòìå÷åíû ÿ÷åéêè,ïîêðàøåííûå â Q íàèáîëåå ÷àñòûõ öâåòîâ â ýòîì ñòîëáöå. Òîãäà äîëÿ âñåõîòìå÷åííûõ ÿ÷ååê â S1 × S2 ìåíüøå, ÷åì 2Q/2m .Àíàëîãè÷íî îïðåäåëèì (K , Q)-ðàâíîìåðíî ïî ñòðîêàì ï¼ñòðóþ òàáëèöó è íàçîâ¼ì òàáëèöó (K , Q)-ðàâíîìåðíî ï¼ñòðîé, åñëè îíà ðàâíîìåðíîï¼ñòðàÿ îäíîâðåìåííî ïî ñòðîêàì è ïî ñòîëáöàì.
Îïðåäåëåíèå ïðîèëëþñòðèðîâàíî íà ðèñ. 6.1.Äëÿ ðàâíîìåðíî ï¼ñòðûõ òàáëèö âåðíû òå æå çàìå÷àíèÿ, ÷òî è äëÿ ï¼ñòðûõ. Âî-ïåðâûõ, åñëè òàáëèöà ÿâëÿåòñÿ (K , Q)-ðàâíîìåðíî ï¼ñòðîé, òî îíàáóäåò è (K , Q0 )-ðàâíîìåðíî ï¼ñòðîé ïðè Q0 > Q. Äåéñòâèòåëüíî, îïðåäåëåíèå ðàâíîìåðíîé ïåñòðîòû (ïî îäíîìó èçìåðåíèþ, íàïðèìåð, ïî ñòðîêàì)ìîæíî ïîíèìàòü òàêèì îáðàçîì: ïóñòü êàæäàÿ ÿ÷åéêà ïîìå÷åíà ÷èñëîìîò 1 äî 2m , êîòîðîå ïîêàçûâàåò å¼ ðàíã ïî ÷àñòîòå öâåòà â ñîîòâåòñòâóþùåé ñòðîêå ïðÿìîóãîëüíèêà S1 × S2 (ñàìîìó ÷àñòîìó öâåòó ñîîòâåòñòâóåò1, ñàìîìó ðåäêîìó 2m , ïðè ðàâåíñòâå ÷àñòîò ïðèîðèòåò îòäà¼òñÿ öâåòóñ ìåíüøèì íîìåðîì).
Òîãäà ÷åì áîëüøå íîìåð ìåòêè, òåì ðåæå îíà âñòðå÷àåòñÿ â òàáëèöå. Òàáëèöà áóäåò ðàâíîìåðíî ï¼ñòðîé, åñëè â ëþáîì ïðÿìîóãîëüíèêå ñî ñòîðîíàìè íå ìåíüøå K äîëÿ ÿ÷ååê, ïîìå÷åííûõ ÷èñëàìè îò1 äî Q, ìåíüøå 2Q/2m . Åñëè ýòî òàê, òî äîëÿ ÿ÷ååê, ïîìå÷åííûõ ÷èñëîìQ, ìåíüøå 2/2m , à çíà÷èò, è äîëÿ ÿ÷ååê, ïîìå÷åííûõ âñåìè áîëüøèìè ÷èñëàìè, òàêæå ìåíüøå 2/2m .
Ñóììèðóÿ ýòè äîëè äî ÷èñëà Q0 , ïîëó÷èì ÷èñëîìåíüøå 2Q0 /2m , ÷òî è òðåáîâàëîñü. Ðàññóæäåíèå äëÿ ñòîëáöîâ ïîëíîñòüþàíàëîãè÷íî, ÷òî è çàâåðøàåò ðàññóæäåíèå.Âî-âòîðûõ, âûïîëíåíèå óñëîâèÿ äîñòàòî÷íî ïîòðåáîâàòü òîëüêî äëÿìíîæåñòâ S1 è S2 ðàçìåðà â òî÷íîñòè K . Äåéñòâèòåëüíî, ïóñòü â íåêîòîðîì ïðÿìîóãîëüíèêå S1 × S2 äîëÿ ÿ÷ååê, ïîìå÷åííûõ ÷èñëàìè îò 1 äî Q,ïðåâûøàåò 2Q/2m . Çíà÷èò, â êàêîì-òî ïðÿìîóãîëüíèêå S10 × S20 , ãäå Si0 ⊂ Siè |Si0 | = K , äîëÿ ïîìå÷åííûõ ÿ÷ååê òàêæå ïðåâûøàåò 2Q/2m .
Íî åñëè òå96à)á)â)Ðèñ. 6.1: Èëëþñòðàöèÿ îïðåäåëåíèÿ (10,2)-ðàâíîìåðíî ï¼ñòðîé ïî ñòðîêàì òàáëèöû äëÿôèêñèðîâàííîãî ïðÿìîóãîëüíèêà S1 × S2 . Íà ðèñóíêå à) ïðèâåäåíà ðàñêðàñêà êâàäðàòàðàçìåðà 10 × 10 â 2m = 8 öâåòîâ è îòìå÷åíû íàèáîëåå ÷àñòûå â ñòðîêàõ öâåòà. Íàðèñóíêå á) îñòàâëåíà ðàñêðàñêà òîëüêî êëåòîê, ïîêðàøåííûõ â ýòè öâåòà.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
