Диссертация (1103424), страница 11
Текст из файла (страница 11)
Äëÿ ýòîãî, âî-ïåðâûõ, íóæíî çàïóñòèòü ïåðå÷èñëèòåëü Sb,s−1 (ò.å.çàïóñòèòü âñå ïðîãðàììû äëèíû íå áîëüøå k íà âõîäå b íà ïàìÿòè s − 1) èïðîâåðèòü, íå âñòðå÷àåòñÿ ëè òàì x. Âî-âòîðûõ, íóæíî çàïóñòèòü âñå ïðîãðàììû îò 0 äî z −1 íà ïàìÿòè s è ïðîâåðèòü, ÷òî íè îäíà èç íèõ íå âûäà¼òx.
Òîëüêî åñëè îáå ïðîâåðêè ïðîéäåíû, íóæíî äîáàâèòü x â ïåðå÷èñëåíèå.Ïðèâåä¼ì òàêæå íåìíîãî îïòèìèçèðîâàííûé ïñåâäîêîä:Âõîä: Ñëîâî b, ÷èñëî kÐåçóëüòàò: Ïåðå÷èñëåíèå Sb = {x | C(x|b) < k} áåç ïîâòîðåíèé1234567891011121314151617äëÿ s = 1 äî ∞ âûïîëíèòüäëÿ êàæäîãî z ∈ {0, 1}<k âûïîëíèòüÇàïóñòèòü U (z, b) íà çîíå s ñ êîíòðîëåì çàöèêëèâàíèÿ;åñëè U (z, b) êîððåêòíî çàâåðøèëîñü òîx := U (z, b);äëÿ êàæäîãî w ∈ {0, 1}<k âûïîëíèòüåñëè w < z òî q := s;èíà÷å q := s − 1;Çàïóñòèòü U (w, b) íà çîíå q ñ êîíòðîëåì çàöèêëèâàíèÿ;åñëè U (w, b) êîððåêòíî çàâåðøèëîñü è âåðíóëî x òîïðîäîëæèòü öèêë ïî z ;êîíåö óñëîâèÿêîíåö öèêëàâûâåñòè x ;/* Âûïîëíÿåòñÿ, òîëüêî åñëè ïðîøëèïðîâåðêè äëÿ âñåõ w */êîíåö óñëîâèÿêîíåö öèêëàêîíåö öèêëàÀëãîðèòì 4.1:Ïåðå÷èñëåíèå Sb â íóæíîì ïîðÿäêå áåç ïîâòîðåíèéÌîæíî ïîñòðîèòü ýòî ïåðå÷èñëåíèå òàêèì îáðàçîì, ÷òî ê ìîìåíòó, êîãäàïåðå÷èñëåíû âñå ýëåìåíòû Sb,s , èñïîëüçîâàíà òîëüêî ïàìÿòü O(s + n): äëÿ53ýòîãî íóæíî êàæäûé ðàç çàïóñêàòü î÷åðåäíóþ ïðîãðàììó íà îäíîé è òîéæå ïàìÿòè, õðàíÿ ìåæäó çàïóñêàìè òîëüêî x, z è ñ÷¼ò÷èêè äëÿ ïðîâåðêèòîãî, ÷òî x íå âñòðå÷àëîñü ðàíåå.
Ðàçóìååòñÿ, äëÿ íîâîé ïðîâåðêè íóæíîòàêæå èñïîëüçîâàòü ñòàðûé ñ÷¼ò÷èê. Òàêèì îáðàçîì, ê ìîìåíòó ïåðå÷èñëåíèÿ âñåãî Sb,s áóäåò èñïîëüçîâàíî O(s) ÿ÷ååê ðàáî÷åé ïàìÿòè è O(n) ÿ÷ååêäëÿ õðàíåíèÿ ñ÷¼ò÷èêîâ.2(i)Áîëåå òîãî, ìîæíî àíàëîãè÷íûì îáðàçîì ïåðå÷èñëèòü ìíîæåñòâà Sb(i)(i−1)äëÿ âñåõ i. (Çäåñü Sb ìíîæåñòâî âñåõ îïàñíûõ ñëîâ äëÿ Sbâ ýêñ(0)(i)òðàêòîðå Extki−1 , à Sb = Sb ). Äåéñòâèòåëüíî, ïîñêîëüêó ìíîæåñòâî Sb,sïåðå÷èñëèìî íà ïàìÿòè O(s + n) ïðè âñåõ i, ìîæíî çàïóñòèòü ïîëíîñòüþàíàëîãè÷íóþ êîíñòðóêöèþ.
Ïðèâåä¼ì ñîîòâåòñòâóþùèé ïñåâäîêîä:Âõîä: Ñëîâî b, ÷èñëà k , iÐåçóëüòàò: Ïåðå÷èñëåíèå Sb(i) áåç ïîâòîðåíèé1 åñëè i=0 òî2Çàïóñòèòü àëãîðèòì 4.1èíà÷åäëÿ êàæäîãî z èç ïåðå÷èñëåíèÿ Sb(i−1) âûïîëíèòüåñëè z îïàñíî â ýêñòðàêòîðå Extki−1 òî âûâåñòè z ;êîíåö öèêëàêîíåö óñëîâèÿ34567Àëãîðèòì 4.2:(i)Ïåðå÷èñëåíèå Sb â íóæíîì ïîðÿäêå áåç ïîâòîðåíèéÅñëè ïåðå÷èñëåíèå ïîñòðîåíî èìåííî òàêèì îáðàçîì, òî íåò íóæäûçíàòü s, ÷òîáû âîññòàíîâèòü a ïî b è p. Äåéñòâèòåëüíî, a ïðîñòî çàäà¼òñÿñâîèì íîìåðîì â ïåðå÷èñëåíèè ñîñåäåé p âíóòðè Sb . Ê òîìó ìîìåíòó, êîãäàa áóäåò íàéäåíî, ïåðå÷èñëåíèå (÷àñòè) Sb èñïîëüçóåò ïàìÿòü O(s + n). Äîáàâëÿÿ ïðîñòðàíñòâî äëÿ âû÷èñëåíèÿ çíà÷åíèé ýêñòðàêòîðà (÷òîáû îñòàâèòü â ïåðå÷èñëåíèè òîëüêî ñîñåäåé p) è õðàíåíèÿ ïðîìåæóòî÷íûõ ðåçóëüòàòîâ, ïîëó÷èì çàÿâëåííóþ îöåíêó O(s + q + n2 ).
Òàêèì îáðàçîì, òåîðåìàâ èñõîäíîé ôîðìóëèðîâêå äîêàçàíà.Çàìåòèì, ÷òî äëÿ îïàñíûõ ñëîâ äëèíà ïðîãðàììû p ïîëó÷èëàñü ãàðàíòèðîâàííî ìåíüøåé Cs (a|b). Ýòî ÿâëåíèå â íåêîòîðîì ðîäå àíàëîãè÷íî òîìó,÷òî áåç îãðàíè÷åíèÿ íà ïàìÿòü a íå ìîãëî áûòü îïàñíûì.Çàâåðøèì ðàçäåë ñëåäñòèåì äëÿ èçâåñòíîé êîíñòðóêöèè ýêñòðàêòîðîâ.Çàìåòèì, ÷òî õðàíèòü âñå óæå ïåðå÷èñëåííûå ñëîâà è ïðîãðàììû, êîòîðûìè îíè ïîëó÷åíû, íåâîçìîæíî, ïîýòîìó ïðèõîäèòñÿ çàíîâî èõ ãåíåðèðîâàòü.254Ñëåäñòâèå 4.2.
Ïóñòü äàíû äâîè÷íûå ñëîâà a è b, à òàêæå ÷èñëà n, k ès, äëÿ êîòîðûõ âåðíî Cs (a) < n è Cs (a|b) < k . Òîãäà ñóùåñòâóåò òàêîåñëîâî p, ÷òî:• CO(s+poly(n)) (a|p, b) 6 O(log3 n);• |p| 6 k + O(log n);• Cpoly(n) (p|a) 6 O(log3 n).Äîêàçàòåëüñòâî. Óòâåðæäåíèå ïîëó÷àåòñÿ íåïîñðåäñòâåííîé ïîäñòàíîâêîé ýêñòðàêòîðà èç ñëåäñòâèÿ 2.22 â òåîðåìó 4.1.Çàìå÷àíèå 4.3. Êàê è äëÿ òåîðåìû áåç ðåñóðñíûõ îãðàíè÷åíèé, ìîæíîäîáèòüñÿ, ÷òîáû p áûëî äëèíû ðîâíî k , ëèáî ÷òîáû CO(s+poly(n)) (a|p, b) 6O(1), íî ïðè ýòîì |p| 6 k + O(log3 n).  îáîèõ ñëó÷àÿõ ðàñò¼ò Cpoly(n) (p|a),îñòàâàÿñü ïîðÿäêà log3 n.4.2Äîêàçàòåëüñòâî ïðè ïîìîùè ãåíåðàòîðà ÍèñàíàÂèãäåðñîíàÄîêàçàòåëüñòâî òåîðåìû Ìó÷íèêà äëÿ ñëîæíîñòè áåç îãðàíè÷åíèé èñïîëüçîâàëî âåðîÿòíîñòíûé ìåòîä: áûëî äîêàçàíî, ÷òî ñëó÷àéíûé äâóäîëüíûé ãðàô îáëàäàåò îïðåäåë¼ííûì ñâîéñòâîì (à èìåííî, ÿâëÿåòñÿ ýêñòðàêòîðîì, åù¼ òî÷íåå áåçîïàñíûì ãðàôîì) ñ ïîëîæèòåëüíîé âåðîÿòíîñòüþ.Ýòî ñîîáðàæåíèå íåëüçÿ èñïîëüçîâàòü äëÿ äîêàçàòåëüñòâà òåîðåìû ñ ïîëèíîìèàëüíûì îãðàíè÷åíèåì íà ïàìÿòü, ïîñêîëüêó ïåðåáîð âñåõ ãðàôîâ òðåáóåò ýêñïîíåíöèàëüíîé ïàìÿòè.
 ðàçäåëå 4.1 ìû ïîêàçàëè, êàê èñïîëüçîâàòü äëÿ äîêàçàòåëüñòâà òåîðåìû ÿâíóþ êîíñòðóêöèþ.  ýòîì ðàçäåëå ìûïîêàæåì, êàê äåðàíäîìèçèðîâàòü èñõîäíóþ êîíñòðóêöèþ, çàìåíèâ ñëó÷àéíûé ãðàô íà ïñåâäîñëó÷àéíûé. Ïðè ýòîì âñå íåâÿçêè â óñëîâèÿõ òåîðåìûâíîâü ïðèìóò âèä O(log n).Èäåÿ ñîñòîèò â òîì, ÷òîáû èñïîëüçîâàòü ãåíåðàòîð ïñåâäîñëó÷àéíûõ ÷èñåë ÍèñàíàÂèãäåðñîíà, ñóùåñòâóþùèé ïî ñëåäñòâèþ 2.36.
Äëÿ òîãî, ÷òîáû ïðèìåíèòü ëåììó 2.37, íóæíî ïîñòðîèòü ñõåìó êîíñòàíòíîé ãëóáèíû,ðàñïîçíàþùóþ ñâîéñòâî, êîòîðîå ìîæíî èñïîëüçîâàòü äëÿ âûâîäà òåîðåìû Ìó÷íèêà.  ðàáîòå [62] àâòîðîì áûëî èñïîëüçîâàíî äîâîëüíî ñëîæíîåñâîéñòâî, ñëåäóþùåå èç ñâîéñòâà ýêñòðàêòîðà ïî ëåììå 3.2. Áûëî ïîêàçàíî,÷òî ýòî ñâîéñòâî ìîæíî ðàñïîçíàòü ñõåìîé êîíñòàíòíîé ãëóáèíû. Îäíàêî,55âïîñëåäñòâèè áëàãîäàðÿ ñîâåòó Ðîíåíà Øàëòèåëÿ áûëî ïîëó÷åíî ãîðàçäîáîëåå ïðîñòîå ñâîéñòâî, êîòîðîå ñòîëü æå óñïåøíî ìîæíî èñïîëüçîâàòüâ äîêàçàòåëüñòâå.
Áîëåå òîãî, äâóäîëüíûå ãðàôû (ò.å. íàáîðû ôóíêöèé)áîëüøå íå ïîíàäîáÿòñÿ, äîñòàòî÷íî áóäåò èñïîëüçîâàòü îäíó ôóíêöèþ èç{0, 1}n â {0, 1}k .Ïëàí äàëüíåéøåãî èçëîæåíèÿ òàêîâ: âíà÷àëå ìû ñôîðìóëèðóåì ýòîñâîéñòâî, çàòåì äîêàæåì, ÷òî ñëó÷àéíàÿ ôóíêöèÿ îáëàäàåò ýòèì ñâîéñòâîìñ îòäåë¼ííîé îò íóëÿ âåðîÿòíîñòüþ, çàòåì äîêàæåì, ÷òî ýòî ñâîéñòâî ìîæíî ðàñïîçíàòü ñõåìîé èç ôóíêöèîíàëüíûõ ýëåìåíòîâ êîíñòàíòíîé ãëóáèíû.Èç ýòîãî áóäåò ñëåäîâàòü, ÷òî íàøå ñâîéñòâî ñ ïîëîæèòåëüíîé âåðîÿòíîñòüþ âñòðå÷àåòñÿ ñðåäè îáðàçîâ ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà. Çàòåì ìûïîêàæåì, ÷òî àðãóìåíò ãåíåðàòîðà, ÿâëÿþùèéñÿ ïðîîáðàçîì ôóíêöèè ñýòèì ñâîéñòâîì, ìîæíî íàéòè àëãîðèòìè÷åñêè, èñïîëüçóÿ íåáîëüøîå êîëè÷åñòâî ïàìÿòè.
Íàêîíåö, ìû ñôîðìóëèðóåì è äîêàæåì âàðèàíò òåîðåìûÌó÷íèêà, êîòîðûé ìîæíî ïîëó÷èòü èç ýòîé êîíñòðóêöèè.4.2.1Ôîðìóëèðîâêà íóæíîãî ñâîéñòâà è äîêàçàòåëüñòâî ñóùåñòâîâàíèÿÏóñòü äàíà ôóíêöèÿ F : {0, 1}n → {0, 1}k . Ïóñòü S ñèñòåìà ïîäìíîæåñòâ {0, 1}n , ñîñòîÿùàÿ èç íå áîëåå ÷åì 2n+k ïîäìíîæåñòâ, êàæäîå èçêîòîðûõ èìååò ðàçìåð íå áîëüøå 2k . Ñêàæåì, ÷òî F èìååò ìåíüøå m êîëëèçèé îòíîñèòåëüíî S , åñëè äëÿ ëþáîãî x ∈ {0, 1}k è äëÿ ëþáîãî S ∈ Sýëåìåíò x èìååò ìåíåå m ïðîîáðàçîâ âíóòðè S .Çàìåòèì, ÷òî âåðõíåå îãðàíè÷åíèå íà ðàçìåð ñèñòåìû S íå òðèâèàëüíî:îáùåå êîëè÷åñòâî ïîäìíîæåñòâ {0, 1}n ðàçìåðà íå áîëüøå 2k èìååò ïîðÿäîêkáîëüøå 22 , ÷òî áîëüøå 2n+k .Òåîðåìà 4.4.
Ñóùåñòâóåò ïîëèíîì p(n), òàêîé ÷òî äëÿ ëþáûõ n > 1è k 6 n è ëþáîé ñèñòåìû S , ñîñòîÿùåé èç íå áîëåå ÷åì 2n+k ïîäìíîæåñòâ {0, 1}n , êàæäîå èç êîòîðûõ èìååò ðàçìåð íå áîëüøå 2k , õîòÿ áûïîëîâèíà âñåõ ôóíêöèé F : {0, 1}n → {0, 1}k èìåþò ìåíüøå p(n) êîëëèçèéîòíîñèòåëüíî S .Äîêàçàòåëüñòâî. Äëÿ äîêàçàòåëüñòâà èñïîëüçóåì âåðîÿòíîñòíûé ìåòîä.Ðàññìîòðèì ñëó÷àéíóþ ôóíêöèþ F , çíà÷åíèÿ êîòîðîé âûáðàíû ðàâíîìåðíî è íåçàâèñèìî. Îöåíèì ñâåðõó ÷èñëî α âåðîÿòíîñòü òîãî, ÷òî F èìååò56íå ìåíüøå p(n) êîëëèçèé îòíîñèòåëüíî S , è ïîêàæåì, ÷òî ýòà îöåíêà ìåíüøå îäíîé âòîðîé ïðè ïðàâèëüíîì âûáîðå ïîëèíîìà p(n). Èç òàêîé îöåíêèñðàçó ñëåäóåò óòâåðæäåíèå òåîðåìû.Åñëè F èìååò íå ìåíüøå m êîëëèçèé, òî õîòÿ áû äëÿ îäíîãî ýëåìåíòàx ∈ {0, 1}k íàéä¼òñÿ õîòÿ áû m ïðîîáðàçîâ ýòîãî ýëåìåíòà âíóòðè õîòÿ áûîäíîãî ìíîæåñòâà S ∈ S .
Ïîñêîëüêó âåðîÿòíîñòü îáúåäèíåíèÿ ñîáûòèé íåmïðåâîñõîäèò ñóììû âåðîÿòíîñòåé, α íå ïðåâîñõîäèò 2n+k · 2k · C2mk · 21k .Çäåñü 2n+k êîëè÷åñòâî âñåâîçìîæíûõ S , 2k êîëè÷åñòâî âñåâîçìîæíûõx, C2mk îöåíêà ñâåðõó êîëè÷åñòâà âñåâîçìîæíûõ m-ýëåìåíòíûõ ïîäìíîmæåñòâ ìíîæåñòâà S , 21k âåðîÿòíîñòü òîãî, ÷òî îáðàçû âñåõ m ýëåìåíòîâm(2k )n+2k3n< m! , ïîëó÷àåì, ÷òî α < 2 m! 6 2m! . Åñëè âçÿòüðàâíû x. Ïîñêîëüêóm = 3n, òî ïîëó÷èì α < 1/2 ïðè âñåõ n > 1 è k 6 n.
Èç ïîëó÷åííîé îöåíêèñëåäóåò óòâåðæäåíèå òåîðåìû.C2mk4.2.2Ðàñïîçíàâàíèå ìàëîãî ÷èñëà êîëëèçèé ïðè ïîìîùè ñõåìûêîíñòàíòíîé ãëóáèíûÔóíêöèþ èç {0, 1}n â {0, 1}k ìîæíî îïèñàòü ñëîâîì èç íóëåé è åäèíèö äëèíû k2n : äëÿ êàæäîãî èç 2n àðãóìåíòîâ íóæíî óêàçàòü îäíî çíà÷åíèå äëèíû k . Òàêèì îáðàçîì, îñìûñëåíåí âîïðîñ î òîì, ìîæíî ëè òî èëèèíîå ñâîéñòâî òàêîé ôóíêöèè ðàñïîçíàòü íåêîòîðîé ñõåìîé èç ôóíêöèîíàëüíûõ ýëåìåíòîâ ñî âõîäîì äëèíû k2n è îäíèì âûõîäîì.
Ìû ïîêàæåì,÷òî ìàëîñòü ÷èñëà êîëëèçèé ìîæíî ðàñïîçíàòü ñõåìîé èç ôóíêöèîíàëüíûõ ýëåìåíòîâ êîíñòàíòíîé ãëóáèíû. Ôîðìàëüíî ìû äîêàæåì ñëåäóþùóþòåîðåìó:Òåîðåìà 4.5. Ñóùåñòâóåò êîíñòàíòà d, òàêàÿ ÷òî äëÿ âñåõ k 6 n è ëþáîãî ñåìåéñòâà S , ñîñòîÿùåãî èç íå áîëåå ÷åì 2n+k ïîäìíîæåñòâ ðàçìåðàíå áîëüøå 2k , ñóùåñòâóåò ñõåìà èç ôóíêöèîíàëüíûõ ýëåìåíòîâ CS ðàçìåðà 2O(n) è ãëóáèíû d, ïîëó÷àþùàÿ íà âõîä êîä ôóíêöèè F : {0, 1}n → {0, 1}kè âûäàþùàÿ 1 òîãäà è òîëüêî òîãäà, êîãäà ôóíêöèÿ F èìååò íå áîëüøå3n êîëëèçèé îòíîñèòåëüíî S .Äîêàçàòåëüñòâî. Îïèñàíèå ôóíêöèè F áóäåì ïîäàâàòü íà âõîä ñõåìå êàêñïèñîê çíà÷åíèé F íà âñåõ âõîäàõ. (Âõîäû áóäóò óïîðÿäî÷åíû, íàïðèìåð,ëåêñèêîãðàôè÷åñêè).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
