Диссертация (1103424), страница 20
Текст из файла (страница 20)
Íà ðèñóíêåâ) ñîîòâåòñòâóþùèå êëåòêè ïîìå÷åíû ñåðûì. Âñåãî îòìå÷åíî 49 êëåòîê, ÷òî ìåíüøå2Q/2m = 1/2 îò îáùåãî êîëè÷åñòâà. Òàêèì îáðàçîì, óñëîâèå ðàâíîìåðíîé ïî ñòðîêàìïåñòðîòû äëÿ äàííîãî ïðÿìîóãîëüíèêà âûïîëíåíî.97ïåðü ìåòêè ðàññòàâèòü íå îòíîñèòåëüíî S1 × S2 , à îòíîñèòåëüíî S10 × S20 , òîêîëè÷åñòâî (è äîëÿ) îòìå÷åííûõ âåðøèí â S10 × S20 íå óìåíüøèòñÿ. Çíà÷èò,â ïðÿìîóãîëüíèêå S10 × S20 óñëîâèå òàêæå íàðóøèòñÿ. Çíà÷èò, äîñòàòî÷íî ïîòðåáîâàòü âûïîëíåíèÿ óñëîâèÿ òîëüêî äëÿ ïðÿìîóãîëüíèêîâ ðàçìåðàK × K , êàê è áûëî çàÿâëåíî.Çèìàíä â ðàáîòàõ [53; 55] äîêàçàë âåðîÿòíîñòíûì ìåòîäîì ñóùåñòâîâàíèå ï¼ñòðûõ è ðàâíîìåðíî ï¼ñòðûõ òàáëèö ñ îïðåäåë¼ííûìè ïàðàìåòðàìè. ñèëó òîãî, ÷òî íàøå îïðåäåëåíèå íåñêîëüêî îòëè÷àåòñÿ îò îðèãèíàëüíîãî, â òîì ÷èñëå âûáîðîì ïàðàìåòðîâ, ìû ïðèâåä¼ì òåîðåìû ñóùåñòâîâàíèÿâìåñòå ñ äîêàçàòåëüñòâàìè.Òåîðåìà √6.5.
Ïðè âñåõ äîñòàòî÷íîáîëüøèõ n è m, è âñåõ K >√max{m, n} 2m è Q > max{m, n} 2m ñóùåñòâóåò (K , Q)-ï¼ñòðàÿ òàáëèöà. Òàêæå äëÿ âñåõ K > (max{m, n})2 2m è ëþáîãî Q ñóùåñòâóåò (K ,Q)-ðàâíîìåðíî ï¼ñòðàÿ òàáëèöà.Äîêàçàòåëüñòâî.  ñèëó ñäåëàííûõ âûøå çàìå÷àíèé äîñòàòî÷íî äîêàçàòü√òåîðåìó äëÿ K = Q = max{n, m} 2m â ñëó÷àå ï¼ñòðûõ òàáëèö è K =(max{m, n})2 2m è Q = 1 â ñëó÷àå ðàâíîìåðíî ï¼ñòðûõ.Äîêàçàòåëüñòâî ñòðîèòñÿ ñòàíäàðòíûì ïðèìåíåíèåì âåðîÿòíîñòíîãî ìåòîäà.
Âîçüì¼ì ñëó÷àéíóþ òàáëèöó äàííîãî ðàçìåðà è äîêàæåì, ÷òî îíà ñïîëîæèòåëüíîé âåðîÿòíîñòüþ ÿâëÿåòñÿ (ðàâíîìåðíî) ï¼ñòðîé. Ïîä ñëó÷àéíîñòüþ òàáëèöû áóäåì ïîíèìàòü, ÷òî öâåòà âñåõ å¼ ÿ÷ååê âûáðàíû ðàâíîìåðíî è íåçàâèñèìî äðóã îò äðóãà. Ïðîâåä¼ì îòäåëüíûå ðàññóæäåíèÿ äëÿï¼ñòðûõ è ðàâíîìåðíî ï¼ñòðûõ òàáëèö.Îöåíèì âåðîÿòíîñòü òîãî, ÷òî òàáëèöà íå ÿâëÿåòñÿ ï¼ñòðîé. Ýòî îçíà÷àåò, ÷òî äëÿ íåêîòîðûõ S1 è S2 ðàçìåðà K äîëÿ ÿ÷ååê, ïîêðàøåííûõ âQ ñàìûõ ÷àñòûõ öâåòîâ, íå ìåíüøå 2Q/2m . Çíà÷èò, íàéäóòñÿ Q öâåòîâ è2QK 2 /2m ÿ÷ååê, ïîêðàøåííûõ â ýòè öâåòà. Âåðîÿòíîñòü ýòîãî ñîáûòèÿ íå2Qïðåâûøàåò C2Kn · C2m · Pr ñóììà K 2 íåçàâèñèìûõ áåðíóëëèåâñêèõ ñëó2÷àéíûõ âåëè÷èí ñî ñðåäíèì 2Qm áîëüøå, ÷åì 2QK2m .  ýòîì ïðîèçâåäåíèè2QC2Kn ÷èñëî ñïîñîáîâ âûáðàòü S1 è S2 , C2m ÷èñëî ñïîñîáîâ âûáðàòüQ öâåòîâ, à óïîìÿíóòàÿ áåðíóëëèåâñêàÿ ñëó÷àéíàÿ âåëè÷èíà ðàâíà åäèíèöå, åñëè äàííàÿ ÿ÷åéêà ïîêðàøåíà â îäèí èç Q âûáðàííûõ öâåòîâ.
Â2n 2KQñèëó íåðàâåíñòâà (2.5) âåëè÷èíà C2Kn ìåíüøå e2K, à âåëè÷èíà C2m m Qìåíüøå e2Q. Äàëåå, â ñèëó ñëåäñòâèÿ 2.41 òðåòèé ìíîæèòåëü íå ïðåâû1 Q2øàåò e− 3 2m K . Òàêèì îáðàçîì, âåðîÿòíîñòü òîãî, ÷òî òàáëèöà íå ï¼ñòðàÿ, íå98ïðåâûøàåòe2n 2KKe2mQQ1 Q21 QK2· e− 3 2m K = e2K(1+n ln 2−ln K)+Q(1+m ln 2−ln Q)− 3 2m .√Åñëè âçÿòü K = Q = max{m, n} 2m , òî ïîëîæèòåëüíûå ñëàãàåìûå â ïîêà√çàòåëå áóäóò èìåòü ïîðÿäîê (max{m, n})2 2m , à ïîñëåäíåå îòðèöàòåëüíîå√ñëàãàåìîå áóäåò èìåòü ïîðÿäîê (max{m, n})3 2m . Òàêèì îáðàçîì, ïðè äîñòàòî÷íî áîëüøèõ m è n ïîêàçàòåëü áóäåò îòðèöàòåëüíûì, à âñÿ âåëè÷èíàáóäåò ìåíüøå åäèíèöû. Çíà÷èò, âåðîÿòíîñòü òîãî, ÷òî òàáëèöà íå ï¼ñòðàÿ,ìåíüøå åäèíèöû, ïîýòîìó ï¼ñòðûå òàáëèöû ñóùåñòâóþò.Òåïåðü äîêàæåì ñóùåñòâîâàíèå ðàâíîìåðíî ï¼ñòðûõ òàáëèö ñ óêàçàííûìè ïàðàìåòðàìè. Äëÿ ýòîãî äîêàæåì, ÷òî âåðîÿòíîñòü òîãî, ÷òî ñëó÷àéíàÿ òàáëèöà çàäàííîãî ðàçìåðà íå ÿâëÿåòñÿ (K , Q)-ðàâíîìåðíî ïî ñòðîêàìï¼ñòðîé, ìåíüøå 1/2.
Àíàëîãè÷íî ïîëó÷èì òàêóþ æå îöåíêó äëÿ ñòîëáöîâ, à çíà÷èò, ñëó÷àéíàÿ òàáëèöà áóäåò ðàâíîìåðíî ï¼ñòðîé ñ ïîëîæèòåëüíîé âåðîÿòíîñòüþ. Åñëè äàííàÿ òàáëèöà íå ÿâëÿåòñÿ (K , Q)-ðàâíîìåðíîïî ñòðîêàì ï¼ñòðîé, òî íàéäóòñÿ S1 è S2 ðàçìåðà â òî÷íîñòè K , äîëÿ ïîìå÷åííûõ òî÷åê â êîòîðûõ áóäåò ïðåâûøàòü 2Q/2m .
Ýòî çíà÷èò, ÷òî âêàæäîé ñòðîêå íàéäóòñÿ Q âûäåëåííûõ öâåòîâ, òàêèå ÷òî 2QK 2 /2m ÿ÷ååê ïîêðàøåíû â âûäåëåííûå öâåòà äëÿ ñîîòâåòñòâóþùèõ ñòðîê. Âåðîÿò2 KKQíîñòü ýòîãî ñîáûòèÿ íå ïðåâûøàåò C2n · C2m· Pr ñóììà K 2 íåçà·âèñèìûõ áåðíóëëèåâñêèõ ñëó÷àéíûõ âåëè÷èí ñî ñðåäíèì 2Qm áîëüøå, ÷åìQ2QK 2, ÷òî îòëè÷àåòñÿ îò îöåíêè äëÿ ï¼ñòðûõ òàáëèö ëèøü çàìåíîé C2m íàm2KQC2m , ïîñêîëüêó òåïåðü ñâîè Q öâåòîâ âûáèðàþòñÿ äëÿ êàæäîé èç Kñòðîê. Èñïîëüçóÿ òå æå íåðàâåíñòâà, ÷òî è ðàíüøå, ìû ïîëó÷èì âåðõíþþ m KQ2e2n 2Ke22K(1+n ln 2−ln K)+KQ(1+m ln 2−ln Q)− 13 QK− 31 2Qm K 2m2.îöåíêó K= e· Q·eÅñëè âçÿòü K = (max{m, n})2 2m è Q = 1, òî ïîëîæèòåëüíûå ñëàãàåìûå áóäóò èìåòü ïîðÿäîê (max{m, n})3 2m , à îòðèöàòåëüíûå ïîðÿäîê(max{m, n})4 2m .
Òàêèì îáðàçîì, ïðè äîñòàòî÷íî áîëüøèõ n è m ïîêàçàòåëü áóäåò ìåíüøå − ln 2, à âñÿ âåëè÷èíà áóäåò ìåíüøå 1/2, ÷òî è òðåáîâàëîñü. Çíà÷èò, ðàâíîìåðíî ï¼ñòðûå òàáëèöû ñ óêàçàííûìè ïàðàìåòðàìèñóùåñòâóþò.Íà ýòîì òåîðåìà ñóùåñòâîâàíèÿ ï¼ñòðûõ è ðàâíîìåðíî ï¼ñòðûõ òàáëèöäîêàçàíà.Çàìå÷àíèå 6.6.
Çàìåòèì, ÷òî èç äîêàçàòåëüñòâà âèäíî, ÷òî ïðè óêàçàííûõ ïàðàìåòðàõ è äîñòàòî÷íî áîëüøèõ m è n (ðàâíîìåðíî) ï¼ñòðûå òàáëèöû íå òîëüêî ñóùåñòâóþò, íî è çàíèìàþò îòäåë¼ííóþ îò íóëÿ (è äàæå99ñòðåìÿùóþñÿ ê åäèíèöå) äîëþ ñðåäè âñåõ òàáëèö. Ýòî ïîçâîëèò âïîñëåäñòâèè ïðèìåíèòü ëåììó 2.37.6.3Èäåÿ äîêàçàòåëüñòâà îñíîâíîé òåîðåìû ýòîì ðàçäåëå ìû ïåðåñêàæåì äîêàçàòåëüñòâî òåîðåìû 2.30, ïðèíàäëåæàùåå Çèìàíäó, è ïîêàæåì, ãäå åãî íåîáõîäèìî äîïîëíèòü äëÿ äîêàçàòåëüñòâà òåîðåìû 6.2.Ôàêòè÷åñêè ìû ïîêàæåì, ÷òî íåêîòîðàÿ ï¼ñòðàÿ òàáëèöà T ÿâëÿåòñÿêîëìîãîðîâñêèì ýêñòðàêòîðîì, à íåêîòîðàÿ ðàâíîìåðíî ï¼ñòðàÿ òàáëèöà óñèëåííûì êîëìîãîðîâñêèì ýêñòðàêòîðîì. Âïîñëåäñòâèè, ÷òîáû äîêàçàòüñóùåñòâîâàíèå êîëìîãîðîâñêèõ ýêñòðàêòîðîâ ñ îãðàíè÷åíèåì íà ïàìÿòü,ìû îñëàáèì îïðåäåëåíèå ï¼ñòðîé òàáëèöû, òàê ÷òîáû òàáëèöà ïî-ïðåæíåìóáûëà íóæíûì ýêñòðàêòîðîì, íî ïðè ýòîì íàõîäèëàñü áû íà îãðàíè÷åííîéïàìÿòè.Îïèøåì ñõåìó äîêàçàòåëüñòâà äëÿ êîëìîãîðîâñêèõ ýêñòðàêòîðîâ.
Äîêàçàòåëüñòâî áóäåò ñòðîèòüñÿ îò ïðîòèâíîãî: ìû ïîëó÷èì ïðîòèâîðå÷èåìåæäó ñëîæíîñòüþ ïàðû (x, y) è ïðîñòîòîé çíà÷åíèÿ T (x, y). Äåéñòâèòåëüíî, â ñèëó ïåñòðîòû òàáëèöû â íåé íåìíîãî ÿ÷ååê ïîêðàøåíû â öâåòàìàëîé ñëîæíîñòè, à çíà÷èò, è ñàìè ýòè ÿ÷åéêè áóäóò èìåòü íåáîëüøóþñëîæíîñòü. Îïèøåì êîíñòðóêöèþ ïîäðîáíåå, óêàçàâ ïàðàìåòðû. Íàïîìíèì, ÷òî ïî óñëîâèþ ñëîæíîñòü êàæäîãî èç ñëîâ x è y íå ìåíüøå k , àçàâèñèìîñòü ìåæäó íèìè íå áîëüøå δ . Ïîëîæèì d = δ+c log n, ãäå êîíñòàíòà c áóäåò îïðåäåëåíà ïîçäíåå, è ðàññìîòðèì (2k , 2m−d )-ï¼ñòðóþ òàáëèöóT : {0, 1}n × {0, 1}n → {0, 1}m (îöåíêîé ïàðàìåòðîâ çàéì¼ìñÿ ïîçæå, ïîêà÷òî ïðåäïîëîæèì, ÷òî òàêàÿ òàáëèöà ñóùåñòâóåò). Îïðåäåëèì ìíîæåñòâàBx = {z ∈ {0, 1}n | Cs (z) 6 Cs (x)}, By = {z ∈ {0, 1}n | Cs (z) 6 Cs (y)} èA = {w ∈ {0, 1}m | Cs (w) < m − d}.
Î÷åâèäíî, (x, y) ∈ Bx × By . Ðàñøèðèìsïðîèçâîëüíûì îáðàçîì ìíîæåñòâà Bx è By äî ìíîæåñòâ ðàçìåðîâ 2C (x)+1 ès2C (y)+1 ñîîòâåòñòâåííî. Òåïåðü ê ðàñøèðåííîìó ìíîæåñòâó Bx × By ìîæíîïðèìåíèòü ñâîéñòâî ïåñòðîòû è ïîëó÷èòü, ÷òî ìåíååss2 · 2C (x)+1 2C (y)+1 /2d(6.1)ÿ÷ååê èç ýòîãî ìíîæåñòâà ïîêðàøåíû â öâåò èç ìíîæåñòâà A (äåéñòâèòåëüíî, ìåíüøå òàêîãî êîëè÷åñòâà ÿ÷ååê ïîêðàøåíî â 2m−d ñàìûõ ÷àñòûõ öâåòîâ, ïîòîìó åù¼ ìåíüøå áóäåò ïîêðàøåíî â |A| < 2m−d ïðîèçâîëüíûõ öâå100òîâ).
Çíà÷èò, äëÿ èñõîäíîãî ìíîæåñòâà Bx ×By áóäåò âåðíà òà æå îöåíêà (ïîàáñîëþòíîé âåëè÷èíå, à íå äîëå). Çíà÷èò, ÿ÷åéêà (x, y), ïîêðàøåííàÿ â öâåòèç ìíîæåñòâà A, ìîæåò áûòü îïèñàíà òàáëèöåé T , ìíîæåñòâàìè Bx , By è A,à òàêæå ïîðÿäêîâûì íîìåðîì ÿ÷åéêè (x, y) ñðåäè âñåõ ÿ÷ååê ïðÿìîóãîëüíèêà Bx × By , ïîêðàøåííûõ â öâåòà èç ìíîæåñòâà A.  ñèëó îöåíêè (6.1)ïîñëåäíèé ïîðÿäêîâûé íîìåð òðåáóåò íå áîëåå Cs (x) + Cs (y) − d + 3 áèòîâ,à äëÿ îïèñàíèÿ ìíîæåñòâ Bx , By è A äîñòàòî÷íî óêàçàòü n, m, d, Cs (x)è Cs (y), ò.å. O(log n) áèòîâ.
Ïðè ýòîì ïî ýòèì äàííûì ìíîæåñòâà ìîãóòáûòü ïåðå÷èñëåíû íà ïàìÿòè O(s). Åñëè áû ñóùåñòâîâàëà ï¼ñòðàÿ òàáëèöàT ñëîæíîñòè O(log n), âû÷èñëèìàÿ íà ïàìÿòè O(s), òî ìû áû ïîëó÷èëè,÷òî CO(s) (x, y) < Cs (x) + Cs (y) − d + O(log n), ÷òî ïðè íàäëåæàùåì âûáîðåµ è c âñòóïèëî áû â ïðîòèâîðå÷èå ñ óñëîâèåì Cµs > Cs (x) + Cs (y) − δ . Ê ñîæàëåíèþ, òàêîé òàáëèöû íàéòè íå óäà¼òñÿ.
Âìåñòî ýòîãî ìû â ðàçäåëå 6.4íàéä¼ì òàáëèöó, êîòîðàÿ âû÷èñëèìà íà ïàìÿòè O(s) è îáëàäàåò íåêîòîðûì áîëåå ñëàáûì ñâîéñòâîì, äîñòàòî÷íûì äëÿ äîêàçàòåëüñòâà òåîðåìû,êîòîðîå ìû ïðèâåä¼ì â ðàçäåëå 6.5.Òåïåðü îïèøåì ñõåìó äîêàçàòåëüñòâà äëÿ óñèëåííûõ êîëìîãîðîâñêèõýêñòðàêòîðîâ. Çäåñü èäåÿ äîêàçàòåëüñòâà òàêîâà: â ñèëó ðàâíîìåðíîé ïåñòðîòû, â ëþáîì ïðÿìîóãîëüíèêå áóäåò íåìíîãî ÿ÷ååê ñ öâåòàìè ìàëîé ñëîæíîñòè óñëîâíî íà íîìåð ñòîëáöà (ñòðîêè), â êîòîðîì (-îé) îíè ëåæàò. Çíà÷èò, âñå òàêèå ÿ÷åéêè áóäóò èìåòü íåáîëüøóþ ñëîæíîñòü, ÷òî âîéä¼ò âïðîòèâîðå÷èå ñ òåì, ÷òî ïàðà (x, y) ñëîæíà. Áîëåå ïîäðîáíî, ìû âîçüì¼ì ðàâíîìåðíî ï¼ñòðóþ òàáëèöó ñ ïàðàìåòðàìè (2k , Q = 2m−d ), ãäå âíîâüd = δ + c log n (ðàçóìååòñÿ, òåïåðü òàáëèöà áóäåò ñóùåñòâîâàòü ïðè èíûõçíà÷åíèÿõ ïàðàìåòðîâ, íî è â óòâåðæäåíèè òåîðåìû ïàðàìåòðû òîæå äðóãèå; òî÷íîé îöåíêîé ïàðàìåòðîâ çàéì¼ìñÿ ïîçæå).
Îïðåäåëèì ìíîæåñòâàBx è By òàê æå, êàê è ðàíüøå. Êðîìå òîãî, äëÿ êàæäîãî ñëîâà v ðàññìîòðèììíîæåñòâî Av = {w | Cs (w|v) < m − d}. ßñíî, ÷òî îíî ñîäåðæèò ìåíüøå Qýëåìåíòîâ. Íàçîâ¼ì ñëîâî v ïëîõèì, åñëè äîëÿ ÿ÷ååê â ñòîëáöå {v} × By ,ïîêðàøåííûõ â öâåò èç Av , ïðåâûøàåò 2 · 2−d . Äîëÿ ÿ÷ååê, ïîêðàøåííûõ âQ ñàìûõ ÷àñòûõ öâåòîâ, áóäåò íå ìåíüøå, ïîýòîìó ïëîõèõ ñòîëáöîâ áóäåòíå áîëüøå K , èíà÷å â ïðÿìîóãîëüíèêå {ïëîõèå ñòîëáöû} × By áóäåò íàðóøåíî óñëîâèå ðàâíîìåðíîé ïåñòðîòû ïî ñòîëáöàì.
Åñëè áû ïëîõèå ñòîëáöûìîæíî áûëî ïåðå÷èñëèòü íà ïàìÿòè s, òî êàæäûé ïëîõîé ñòîëáåö èìåë áûñëîæíîñòü íå áîëüøå k , è ïîòîìó x íå áûëî áû ïëîõèì ñòîëáöîì. Åñëèäîïîëíèòåëüíî ïðåäïîëîæèòü, ÷òî íåêîòîðàÿ ðàâíîìåðíî ï¼ñòðàÿ òàáëèöà101T èìååò ñëîæíîñòü O(log n) è âû÷èñëèìà íà ïàìÿòè O(s), òî ìîæíî ñâåñòèê ïðîòèâîðå÷èþ ïðåäïîëîæåíèå î òîì, ÷òî T (x, y) ∈ Ax . Äåéñòâèòåëüíî,â ýòîì ñëó÷àå ïðè èçâåñòíîì x ìîæíî îïèñàòü y ñëåäóþùèìè äàííûìè:òàáëèöåé T , ìíîæåñòâàìè By è Ax , à òàêæå ïîðÿäêîâûì íîìåðîì ÿ÷åéêè(x, y) ñðåäè âñåõ ÿ÷ååê â ñòîëáöå {x} × By , ïîêðàøåííûõ â öâåò èç ìíîæåñòâà Ax .
Ïîñêîëüêó x íå ïëîõîé, òî ýòîò ïîðÿäêîâûé íîìåð çàïèñûâàåòñÿíå áîëåå ÷åì Cs (y) − d + 1 áèòàìè. Ìíîæåñòâà By è Ax ïðè èçâåñòíîì xïîëíîñòüþ îïèñûâàþòñÿ ïàðàìåòðàìè n, m, d è Cs (y), ïðè÷¼ì èõ ìîæíîïåðå÷èñëèòü íà ïàìÿòè O(s). Òàêèì îáðàçîì, ñëîæíîñòü CO(s) (y|x) áóäåòìåíüøå Cs (y)−d+O(log n), îòêóäà CO(s) (x, y) < Cs (x)+Cs (y)−d+O(log n),÷òî ïðîòèâîðå÷èò óñëîâèþ Cµs (x, y) > Cs (x) + Cs (y) − δ ïðè äîñòàòî÷íîáîëüøèõ c è µ. Ê ñîæàëåíèþ, íàéòè òðåáóåìóþ òàáëèöó òàêæå íå óäà¼òñÿ,ïîýòîìó ìû äîêàæåì òåîðåìó ñ èñïîëüçîâàíèåì áîëåå ñëàáîãî ñâîéñòâà.Íàêîíåö, îöåíèì ïàðàìåòðû êîëìîãîðîâñêèõ ýêñòðàêòîðîâ, êîòîðûå ïîëó÷àòñÿ èç ýòèõ êîíñòðóêöèé. Äëÿ îáû÷íûõ êîëìîãîðîâñêèõ ýêñòðàêòîðîââ ñèëó òåîðåìû 6.5 ïîëó÷àåì òðåáîâàíèå 2k > max{n, m}2m/2 è 2m−d >max{n, m}2m/2 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
