Диссертация (1103424), страница 23
Текст из файла (страница 23)
Äåéñòâèòåëüíî, óñëîâèÿ íà ðàçìåðû âûïîëíåíû:• Ñèñòåìà S ñîäåðæèò ïî îäíîé ïàðå äëÿ êàæäîãî l ∈ [k, n], ò.å. âñåãî íåáîëüøå n ïàð. Êàæäàÿ ïàðà èìååò âèä (S, l), ãäå ìíîæåñòâî S ñîäåðæèò ìåíüøå 2l ýëåìåíòîâ, ïîñêîëüêó âñå åãî ýëåìåíòû èìåþò ñëîæíîñòü ìåíüøå l.• Ìíîæåñòâî Q ñîäåðæèò ìåíüøå 2q ýëåìåíòîâ, ïîñêîëüêó âñå åãî ýëåìåíòû èìåþò ñëîæíîñòü ìåíüøå q .• Ñèñòåìà R ñîäåðæèò ïî îäíîìó êîðòåæó äëÿ êàæäîé ïàðû (S, l) ∈ S ,ïîýòîìó å¼ ðàçìåð òàêæå íå áîëüøå n.
Äëèíà ñîîòâåòñòâóþùåãî êîðòåæà ðàâíà 2l ïî ïîñòðîåíèþ, à êàæäîå ìíîæåñòâî èç êîðòåæà ñîäåðæèòìåíüøå 2q ýëåìåíòîâ, ïîñêîëüêó âñå åãî ýëåìåíòû èìåþò óñëîâíóþñëîæíîñòü ìåíüøå q .Óòâåðæäåíèå î ïåðå÷èñëèìîñòè ñëåäóåò èç òîãî, ÷òî ìíîæåñòâî âñåõñëîâ, ó êîòîðûõ (óñëîâíàÿ) ñëîæíîñòü ñ îãðàíè÷åíèåì íà ïàìÿòü s ìåíüøåôèêñèðîâàííîãî ÷èñëà, ïåðå÷èñëèìî íà ïàìÿòè O(s + n).
Äåéñòâèòåëüíî,ñëîæíîñòü Cs ìîæíî âû÷èñëèòü íà ïàìÿòè O(s + n), ïîýòîìó äëÿ ïåðå÷èñëåíèÿ âñåõ ñëîâ çàäàííîé äëèíû, èìåþùèõ ñëîæíîñòü íå áîëüøå ôèêñèðîâàííîé, äîñòàòî÷íî ïåðå÷èñëÿòü âñå ñëîâà çàäàííîé äëèíû, ñ÷èòàòüñëîæíîñòü ó êàæäîãî èç íèõ è îñòàâëÿòü òîëüêî íóæíûå. Ïîäðîáíåå:• Äëÿ S : ïîñêîëüêó l ïðîáåãàåò âñå èíäåêñû îò k äî n, òî âòîðóþ êîìïîíåíòó ïàðû íîìåð i ìîæíî ïîëîæèòü ðàâíîé k + i − 1.
Äëÿ ôèêñèðîâàííîãî i íóæíî ïåðå÷èñëÿòü âñå ñëîâà äëèíû n, èìåþùèå ñëîæíîñòüìåíüøå k + i − 1.• Äëÿ Q: íóæíî ïåðå÷èñëÿòü âñå ñëîâà äëèíû m, èìåþùèå ñëîæíîñòüìåíüøå q .• Äëÿ R: ïî i è j íàõîäèòñÿ ñëîâî vj èç ñîîòâåòñòâóþùåãî ìíîæåñòâà, çàòåì ïåðå÷èñëÿþòñÿ âñå ñëîâà äëèíû m, èìåþùèå óñëîâíóþ ñëîæíîñòüîòíîñèòåëüíî vj ìåíüøå q .Òåïåðü äîêàæåì, ÷òî àðãóìåíò ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà, ïîðîæäàþùèé íóæíóþ òàáëèöó, ìîæíî íàéòè íà íåáîëüøîé ïàìÿòè:112Òåîðåìà 6.18. Ïóñòü ôèêñèðîâàíû ÷èñëà k < n è q < m, à ñèñòåìûS è R è ìíîæåñòâî Q çàäàíû â ñîîòâåòñòâèè ñ îïðåäåëåíèåì 6.16.2nÏóñòü Gn : {0, 1}r(n) → {0, 1}m2 åñòü ãåíåðàòîð, ñóùåñòâóþùèé â ñîîòâåòñòâèè ñî ñëåäñòâèåì 2.36. Òîãäà íàéä¼òñÿ àëãîðèòì, ïîëó÷àþùèéíà âõîä ïàðàìåòðû n, m, k , q , ðàáîòàþùèé íà ïàìÿòè O(s) + poly(n) èâîçâðàùàþùèé ñëîâà uBT è uRBT äëèíû r(n), äëÿ êîòîðûõ:• Gn (uBT ) åñòü êîä íåêîòîðîé (k, q, 1.01, Q, S)-ï¼ñòðîé òàáëèöû;• Gn (uRBT ) åñòü êîä íåêîòîðîé (k, q, 1.01, R, S)-ðàâíîìåðíî ï¼ñòðîéòàáëèöû.Äîêàçàòåëüñòâî.
Ïîñêîëüêó äëÿ âû÷èñëåíèé ñ îãðàíè÷åíèåì íà ïàìÿòüçàäà÷à ïîèñêà ýêâèâàëåíòíà çàäà÷å ðàñïîçíàâàíèÿ, òî ìû îïèøåì, êàêïî ñëîâó u ∈ {0, 1}r(n) ðàñïîçíàòü, ÿâëÿåòñÿ ëè Gn (u) êîäîì íåêîòîðîé (ðàâíîìåðíî) ï¼ñòðîé òàáëèöû. Êëþ÷åâàÿ îñîáåííîñòü ãåíåðàòîðàÍèñàíàÂèãäåðñîíà, êîòîðàÿ áóäåò èñïîëüçîâàíà ïðè äîêàçàòåëüñòâå ýòîâîçìîæíîñòü âû÷èñëèòü ëþáîé çàäàííûé áèò âûõîäà, èñïîëüçóÿ ïàìÿòüpoly(r(n)) = poly(n).Âíà÷àëå ïðîâåä¼ì ðàññóæäåíèå äëÿ (k, q, 1.01, Q, S)-ï¼ñòðûõ òàáëèö.Ïóñòü çàäàíî ñëîâî u ∈ {0, 1}r(n) .
Îáîçíà÷èì ÷åðåç T òàáëèöó, çàêîäèðîâàííóþ ñëîâîì Gn (u). Òðåáóåòñÿ ïðîâåðèòü, ÷òî äëÿ ëþáûõ ïàð (S1 , l1 )è (S2 , l2 ) èç S êîëè÷åñòâî ÿ÷ååê â S1 × S2 , ïîêðàøåííûõ â öâåò èç ìíîæåñòâà Q, ìåíüøå 2l1 +l2 +q−m+1.01 . Ïîñêîëüêó ïðè íàøåì âûáîðå S ìíîæåñòâàS1 è S2 îäíîçíà÷íî îïðåäåëÿþòñÿ ÷èñëàìè l1 è l2 , ðàñïîçíàþùèé àëãîðèòìáóäåò ïåðåáèðàòü âñå ïàðû (l1 , l2 ) è ïðîâåðÿòü âûïîëíåíèÿ óñëîâèÿ äëÿêàæäîé ïàðû. Äëÿ ýòîãî àëãîðèòì çàâåä¼ò ñ÷¼ò÷èê c è áóäåò ïåðå÷èñëÿòüìíîæåñòâî S1 × S2 (ýòî ìîæíî ñäåëàòü, ïîñêîëüêó S1 è S2 ïåðå÷èñëèìû),äëÿ êàæäîé ïîëó÷åííîé ïàðû (x, y) ∈ S1 × S2 âû÷èñëÿòü T (x, y) è ñ÷èòàòüñëîæíîñòü Cs (T (x, y)). Åñëè ñëîæíîñòü áóäåò ìåíüøå q (ýòî îçíà÷àåò, ÷òîÿ÷åéêà (x, y) ïîêðàøåíà â öâåò èç Q), òî îí óâåëè÷èò ñ÷¼ò÷èê c íà åäèíèöó.Åñëè â êîíöå ïåðåáîðà ñ÷¼ò÷èê íå ïðåâûñèë 2l1 +l2 +q−m+1.01 , òî ïàðà (S1 , S2 )ïðîøëà òåñò, è àëãîðèòì ïåðåõîäèò ê ñëåäóþùåé ïàðå.
Èíà÷å öèêë çàêàí÷èâàåòñÿ è òàáëèöà T è ïîðîäèâøåå å¼ ñëîâî u îòâåðãàþòñÿ. Åñëè æå âñåïàðû (S1 , S2 ) ïðîøëè òåñò, òî T è u ïðèíèìàþòñÿ. Àëãîðèòì 6.1 ïîêàçûâàåòïñåâäîêîä.Êîððåêòíîñòü àëãîðèòìà ñëåäóåò èç êîíñòðóêöèè. Ïðîâåðèì, ÷òî îãðàíè÷åíèå íà ïàìÿòü ñîáëþäàåòñÿ. Äåéñòâèòåëüíî, ìåæäó øàãàìè (âíóòðåí113Âõîä:12345678910×èñëà n, m, k è qÂûõîä: Ñëîâî u, òàêîå ÷òî Gn (u) êîäèðóåò (k, q, 1.01, Q, S)-ï¼ñòðóþ òàáëèöór := O(n2d+6 );/* Òî÷íîå çíà÷åíèå êàê â ñëåäñòâèè 2.36 */räëÿ êàæäîãî u ∈ {0, 1} âûïîëíèòü2äëÿ êàæäîãî (l1 , l2 ) ∈ [k, n] âûïîëíèòücount := 0;n 2äëÿ êàæäîãî (x, y) ∈ ({0, 1} ) âûïîëíèòüsssåñëè C (x) < l1 , C (y) < l2 è C (T (x, y)) < q òî count ++;/* Äëÿ âû÷èñëåíèÿ T áåðóòñÿ íóæíûå áèòû Gn (u)*/êîíåö öèêëàåñëècount > 2l1 +l2 +q−m+1.01òî ïðîäîëæèòü öèêëïî u;êîíåö öèêëàâîçâðàòèòücount 6 2u;/* Âûïîëíÿåòñÿ, òîëüêî åñëè äëÿ âñåõ l1 è l2 âûïîëíåíî*/l1 +l2 +q−m+1.0111êîíåö öèêëàÏîèñê àðãóìåíòà ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà äëÿ ïîëó÷åíèÿï¼ñòðîé òàáëèöû.Àëãîðèòì 6.1:íåãî) öèêëà òðåáóåòñÿ õðàíèòü òîëüêî çíà÷åíèå ñ÷¼ò÷èêà è òåêóùèå çíà÷åíèÿ l1 , l2 , x, y , ò.å.
poly(n) áèòîâ. Êàæäóþ ñëåäóþùóþ ïàðó èç S1 ×S2 ìîæíîíàéòè íà ïàìÿòè O(s + n) â ñèëó óòâåðæäåíèÿ 6.17. Äàëåå, T (x, y) âû÷èñëÿåòñÿ íà ïàìÿòè poly(n) â ñèëó ñâîéñòâ ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà:äëÿ âû÷èñëåíèÿ T (x, y) íóæíî íàéòè m áèòîâ Gn (u), êàæäûé èç êîòîðûõìîæíî íàéòè íà ïàìÿòè poly(n). Íàêîíåö, ñëîæíîñòü Cs (T (x, y)) òàêæåâû÷èñëÿåòñÿ íà ïàìÿòè O(s + n). Òàêèì îáðàçîì, âñå âû÷èñëåíèÿ òðåáóþòïàìÿòè O(s) + poly(n), ÷òî è òðåáîâàëîñü.Òåïåðü ïðîâåä¼ì ðàññóæäåíèå äëÿ (k, q, 1.01, R, S)- ðàâíîìåðíî ï¼ñòðûõ òàáëèö.
Ìû ïðîâåä¼ì ðàññóæäåíèå òîëüêî äëÿ ðàâíîìåðíî ïî ñòîëáöàì ï¼ñòðûõ òàáëèö, ïîñêîëüêó ðàññóæäåíèå äëÿ ðàâíîìåðíî ïî ñòðîêàìï¼ñòðûõ òàáëèö ïîëíîñòüþ àíàëîãè÷íî. Êàê è ïðåæäå, çàäàäèìñÿ ñëîâîìu ∈ {0, 1}r(n) è îáîçíà÷èì ÷åðåç T òàáëèöó, çàêîäèðîâàííóþ ñëîâîì Gn (u).Êàê è ïðåæäå, äîñòàòî÷íî îïèñàòü ïðîöåäóðó äëÿ êîíêðåòíûõ ïàð (S1 , l1 )è (S2 , l2 ) è êîðòåæà Q, çàäàííîãî S1 . Òðåáóåòñÿ ïîñ÷èòàòü êîëè÷åñòâî îòìå÷åííûõ ÿ÷ååê â íàñûùåííûõ ñòîëáöàõ è ñðàâíèòü ýòî ÷èñëî ñ 2l2 +q−m+k+1.01 .Äëÿ ýòîãî àëãîðèòì çàâîäèò ñ÷¼ò÷èê c1 , ïîñëåäîâàòåëüíî ïåðåáèðàåò âñåñòîëáöû (ò.å. ýëåìåíòû x ∈ S1 ), ñ÷èòàåò îòìå÷åííûå ÿ÷åéêè â êàæäîìñòîëáöå è, åñëè ýòî ÷èñëî ïðåâûñèëî 2l2 +q−m+1.01 , äîáàâëÿåò ýòî ÷èñëî êñ÷¼ò÷èêó c1 .
Ïîäñ÷¼ò îòìå÷åííûõ ÿ÷ååê â îäíîì ñòîëáöå ïðîâîäèòñÿ òàê:çàâîäèòñÿ åù¼ îäèí ñ÷¼ò÷èê c2 , ïåðåáèðàþòñÿ âñå y ∈ S2 , äëÿ êàæäîãî âû114Âõîä:123456789×èñëà n, m, k è qÂûõîä: Ñëîâî u, òàêîå ÷òî Gn (u) êîäèðóåò (k, q, 1.01, R, S)-ï¼ñòðóþ òàáëèöór := O(n2d+6 );/* Òî÷íîå çíà÷åíèå êàê â ñëåäñòâèè 2.36 */räëÿ êàæäîãî u ∈ {0, 1} âûïîëíèòü2äëÿ êàæäîãî (l1 , l2 ) ∈ [k, n] âûïîëíèòücount1 := 0;näëÿ êàæäîãî x ∈ {0, 1} âûïîëíèòüsåñëè C (x) < l1 òîcount2 := 0;näëÿ êàæäîãî y ∈ {0, 1} âûïîëíèòüssåñëè C (y) < l2 è C (T (x, y)|x) < q òî count2 + +;/* Äëÿ âû÷èñëåíèÿ T áåðóòñÿ íóæíûå áèòû Gn (u)*/10111213141516êîíåö öèêëàåñëècount2 > 2l2 +q−m+1.01òîcount1 + = count2 ;êîíåö óñëîâèÿêîíåö öèêëàåñëècount1 > 2l2 +q−m+k+1.01òî ïðîäîëæèòü öèêëïî u;êîíåö öèêëàâîçâðàòèòücount 6 2u;/* Âûïîëíÿåòñÿ, òîëüêî åñëè äëÿ âñåõ l1 è l2 âûïîëíåíî*/l2 +q−m+k+1.0117êîíåö öèêëàÏîèñê àðãóìåíòà ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà äëÿ ïîëó÷åíèÿðàâíîìåðíî ï¼ñòðîé òàáëèöû.Àëãîðèòì 6.2:÷èñëÿþòñÿ çíà÷åíèå T (x, y) è ñëîæíîñòü Cs (T (x, y)|x).
Åñëè ýòà ñëîæíîñòüìåíüøå q , òî ñ÷¼ò÷èê c2 óâåëè÷èâàåòñÿ íà 1. Àëãîðèòì 6.2 ïîêàçûâàåò ïñåâäîêîä.Êîððåêòíîñòü ýòîãî àëãîðèòìà âíîâü ñëåäóåò èç êîíñòðóêöèè. Îãðàíè÷åíèå íà ïàìÿòü òàêæå ñîáëþäàåòñÿ: ìåæäó øàãàìè (âíóòðåííåãî) öèêëàòðåáóåòñÿ õðàíèòü òîëüêî çíà÷åíèÿ ñ÷¼ò÷èêîâ è òåêóùèå çíà÷åíèÿ l1 , l2 , x,y , ò.å. poly(n) áèòîâ. (Âûáîð l1 è l2 îäíîçíà÷íî îïðåäåëÿåò íå òîëüêî S1 èS2 , íî è Q). Ñëåäóþùèå ïî î÷åðåäè x è y ìîæíî íàéòè íà ïàìÿòè O(s + n)â ñèëó óòâåðæäåíèÿ 6.17; T (x, y) âû÷èñëÿåòñÿ íà ïàìÿòè poly(n) â ñèëóñâîéñòâ ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà; ñëîæíîñòü Cs (T (x, y)) òàêæå âû÷èñëÿåòñÿ íà ïàìÿòè O(s + n).
Òàêèì îáðàçîì, âñå âû÷èñëåíèÿ òðåáóþòïàìÿòè O(s) + poly(n), ÷òî è òðåáîâàëîñü.Îñòàëîñü äîêàçàòü, ÷òî íàéäåííûå â òåîðåìå 6.18 òàáëèöû Gn (uBT ) èGn (uRBT ) ÿâëÿþòñÿ êîëìîãîðîâñêèìè ýêñòðàêòîðàìè (ïîñëåäíÿÿ â ñèëüíîì ñìûñëå). Ýòî çàâåðøèò äîêàçàòåëüñòâî òåîðåìû 6.2.115Òåîðåìà 6.19. Ñóùåñòâóþò ïîëèíîì p(n) è êîíñòàíòà c, äëÿ êîòîðûõâåðíî ñëåäóþùåå.
Äëÿ δ = m − q − c log n è ëþáîé êîíñòðóèðóåìîé ïî ïàìÿòè ôóíêöèè s(n) > p(n) ïîñòðîåííàÿ â òåîðåìå 6.18 (k, q, 1.01, Q, S)ï¼ñòðàÿ òàáëèöà Gn (uBT ) ÿâëÿåòñÿ (k , δ )-êîëìîãîðîâñêèì ýêñòðàêòîðîìäëÿ îãðàíè÷åíèÿ íà ïàìÿòü s = s(n), à ïîñòðîåííàÿ â òîé æå òåîðåìå(k, q, 1.01, R, S)- ðàâíîìåðíî ï¼ñòðàÿ òàáëèöà Gn (uRBT ) ÿâëÿåòñÿ (k , δ )êîëìîãîðîâñêèì ýêñòðàêòîðîì â ñèëüíîì ñìûñëå äëÿ òîãî æå îãðàíè÷åíèÿ íà ïàìÿòü.Äîêàçàòåëüñòâî. Âî-ïåðâûõ, çàìåòèì, ÷òî ýòè òàáëèöû âû÷èñëèìû íà ïàìÿòè O(s(n)): ïðè âûáîðå äîñòàòî÷íî áîëüøîãî p(n) ýòîé ïàìÿòè äîñòàòî÷íî êàê äëÿ ïîèñêà ñëîâ uBT è uRBT (â ñèëó òåîðåìû 6.18), òàê è äëÿâû÷èñëåíèÿ öâåòîâ ÿ÷ååê ñîîòâåòñòâóþùèõ òàáëèö, ò.å.
îòäåëüíûõ áèòîâGn (uBT ) è Gn (uRBT ) (â ñèëó ñâîéñòâà ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà).Âî-âòîðûõ, äîêàæåì, ÷òî äëÿ T = Gn (uBT ) âûïîëíåíî ñâîéñòâî êîëìîãîðîâñêîãî ýêñòðàêòîðà. Äåéñòâèòåëüíî, ïóñòü äàíû ñëîâà x è y äëèíû n,äëÿ êîòîðûõ Cs (x) = l1 > k , Cs (y) = l2 > k è Cµs (x, y) > l1 + l2 − δ .(Êîíñòàíòà µ íå çàâèñèò îò x è y è áóäåò âûáðàíà ïîçäíåå). Ïðåäïîëîæèì,÷òî äëÿ ýòèõ ñëîâ ñâîéñòâî êîëìîãîðîâñêîãî ýêñòðàêòîðà íå âûïîëíåíî, ò.å.Cs (T (x, y)) 6 m − δ − Ω(log n). Ìîæíî ñ÷èòàòü, ÷òî êîíñòàíòà, ñêðûòàÿ âΩ(log n), áîëüøå c, ïîýòîìó Cs (T (x, y)) < q .  ýòîì ñëó÷àå T (x, y) ∈ Qïî îïðåäåëåíèþ Q. Äàëåå, ââåä¼ì îáîçíà÷åíèÿ S1 = {z | Cs (z) < l1 },S2 = {w | Cs (w) < l2 }.
Ïî ïîñòðîåíèþ ïàðû (S1 , l1 ) è (S2 , l2 ) ëåæàò âS , ïîýòîìó â ñèëó (k, q, 1.01, Q, S)-ïåñòðîòû T â ïðÿìîóãîëüíèêå S1 × S2íå áîëüøå 2l1 +l2 +q−m+1.01 ÿ÷ååê, ïîêðàøåííûõ â öâåò èç Q. Ïðè ýòîì â ñèëó íàøåãî ïðåäïîëîæåíèÿ ÿ÷åéêà (x, y) îòíîñèòñÿ ê ÷èñëó ýòèõ ÿ÷ååê. Ýòîçíà÷èò, ÷òî ÿ÷åéêó (x, y) ìîæíî îïèñàòü, çàäàâ ÷èñëà n, l1 , l2 , q è å¼ ïîðÿäêîâûé íîìåð ñðåäè âñåõ ÿ÷ååê, îáëàäàþùèõ äàííûì ñâîéñòâîì. Äåéñòâèòåëüíî, ïî n ìîæíî íàéòè uBT , çàòåì ïî l1 è l2 ìîæíî ïåðå÷èñëÿòüS1 × S2 è, íàêîíåö, ïî q ïðîâåðÿòü, âåðíî ëè ÷òî Cs (T (x, y)) < q , è ïåðå÷èñëÿòü òå ïàðû, äëÿ êîòîðûõ ýòî âåðíî. Ïîðÿäêîâûé íîìåð â ïåðå÷èñëåíèèçàäàñò íóæíóþ ïàðó.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
