Диссертация (1103424), страница 15
Текст из файла (страница 15)
Òîãäà pi ïðè èçâåñòíîì aîïèñûâàåòñÿ íîìåðîì èòåðàöèè è íîìåðîì pi ñðåäè ñîñåäåé a â ýêñòðàêòîðå,à ñëîâî a ïðè èçâåñòíûõ pi è bi îïèñûâàåòñÿ ñâîèì íîìåðîì â ïåðå÷èñëåíèè(j)ñîñåäåé pi â ìíîæåñòâå Sbi ,s .Îòìåòèì, ÷òî ïðè èñïîëüçîâàíèè èçâåñòíûõ ÿâíûõ ýêñòðàêòîðîâ äëÿïîëèíîìèàëüíîé ïàìÿòè óñëîâíûå ñëîæíîñòè âî âòîðîì è ÷åòâ¼ðòîì óñëîâèÿõ ïîëó÷àòñÿ ðàâíûìè O(log3 n).72Ïðè ïîìîùè æå ãåíåðàòîðîâ ïñåâäîñëó÷àéíûõ ÷èñåë ìîæíî äîêàçàòüòàêóþ òåîðåìó:Òåîðåìà 4.18. Ïóñòü äàíû ÷èñëà n, s è r = poly(n) è äâîè÷íîå ñëîâà a,òàêèå ÷òî Cs (a) < n.
Òîãäà ñóùåñòâóåò ñëîâî p äëèíû n, äëÿ êîòîðîãîâûïîëíåíû ñëåäóþùèå óñëîâèÿ:• CO(s)+poly(n) (a|pb , b) 6 O(log log s) + O(log n) ïðè ëþáîì b äëèíû íåáîëüøå r, ãäå pb ïðåôèêñ p äëèíû Cs (a|b);• CO(s)+poly(n) (p|a) 6 O(log log s) + O(log n).Òàêèì îáðàçîì, ïðèìåíåíèå ãåíåðàòîðîâ íå òîëüêî óìåíüøàåò ñO(log3 n) äî O(log n) îöåíêè íà óñëîâíûå ñëîæíîñòè ïðè ïîëèíîìèàëüíîìîãðàíè÷åíèè íà ïàìÿòü, íî è óâåëè÷èâàåò ìàêñèìàëüíîå ÷èñëî óñëîâèé ñïîëèíîìèàëüíîãî äî ýêñïîíåíöèàëüíîãî (âñå ñëîâà äëèíû poly(n)).
Òàêîãî ýôôåêòà íåò ïðè ñëîæíîñòè áåç îãðàíè÷åíèé, ïîñêîëüêó ñëîæíîñòü áåçîãðàíè÷åíèé íå âû÷èñëèìà. Ïðîâåäÿ äîêàçàòåëüñòâî, ìû åù¼ ðàç îáñóäèì,ïî÷åìó îíî íå ïðîõîäèò äëÿ ñëîæíîñòè áåç ðåñóðñíûõ îãðàíè÷åíèé.Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî ñîñòîèò èç ñòàíäàðòíûõ øàãîâ. Âîïåðâûõ, ìû îïðåäåëèì íóæíîå ñâîéñòâî õåø-ôóíêöèè è äîêàæåì âåðîÿòíîñòíûì ìåòîäîì, ÷òî òàêèå ôóíêöèè ñóùåñòâóþò.
Âî-âòîðûõ, ìû äîêàæåì, ÷òî ýòî ñâîéñòâî ìîæíî ðàñïîçíàòü ñõåìîé êîíñòàíòíîé ãëóáèíû. Èçýòîãî ìû ñäåëàåì âûâîä, ÷òî ôóíêöèè, îáëàäàþùèå ýòèì ñâîéñòâîì, ìîæíî ïîðîäèòü ãåíåðàòîðîì ÍèñàíàÂèãäåðñîíà. Â-òðåòüèõ, ìû äîêàæåì, ÷òîíóæíûé àðãóìåíò ãåíåðàòîðà ìîæíî íàéòè, èñïîëüçóÿ íåáîëüøóþ ïàìÿòü.Íàêîíåö, â-÷åòâ¼ðòûõ, ìû âûâåäåì äîêàçàòåëüñòâî òåîðåìû èç ýòîé êîíñòðóêöèè.Íóæíîå ñâîéñòâî õåø-ôóíêöèè ñôîðìóëèðóåì òàê: äëÿ âñåõ ñëîâ bäëèíû íå áîëüøå r è âñåõ k 6 n ðàçìåð âñåõ êîëëèçèé â ìíîæåñòâåSb,k,s = {x | Cs (x|b) < k} íå áîëüøå m. Ïðè ýòîì ïîä êîëëèçèåé áóäåìïîíèìàòü íàáîð {x1 , . .
. , xµ }, òàêîé ÷òî ïðåôèêñû äëèíû k ñîâïàäàþò óâñåõ F (xi ).Ñóùåñòâîâàíèå ôóíêöèé ñ çàäàííûì ñâîéñòâîì äîêàçûâàåòñÿ ñòàíäàðòíûì ïðèìåíåíèåì âåðîÿòíîñòíîãî ìåòîäà. Âåðîÿòíîñòü êîëëèçèè ðàçìåðàmm â îäíîì ìíîæåñòâå Sb,k,s íå ïðåâîñõîäèò C2mk 21k . Ýòà âåðîÿòíîñòü îöå1íèâàåòñÿ ñâåðõó âåëè÷èíîé m!< 2−m . Åñëè âçÿòü m äîñòàòî÷íî áîëüøèì,íàïðèìåð áîëüøå r + log n, òî è ñóììà òàêèõ âåðîÿòíîñòåé ïî âñåì b è k73áóäåò ìåíüøå 1. Çíà÷èò, ñ ïîëîæèòåëüíîé âåðîÿòíîñòüþ ñëó÷àéíàÿ õåøôóíêöèÿ íå ñîäåðæèò êîëëèçèé ðàçìåðà m íè â îäíîì èç ìíîæåñòâ Sb,k,s .Ñóùåñòâîâàíèå ñõåìû êîíñòàíòíîé ãëóáèíû, ïðîâåðÿþùåé ìàëûé ðàçìåð êîëëèçèé â êîíêðåòíîì ìíîæåñòâå, ìû óæå äîêàçûâàëè. Âàæíî, ÷òîäëèíà b îãðàíè÷åíà poly(n), ïîýòîìó ÷èñëî âñåâîçìîæíûõ ïàð (b, k) ðàâíî 2poly(n) .
Ýòî áîëüøå, ÷åì ïîëèíîì îò äëèíû çàïèñè ôóíêöèè, êîòîðàÿ åñòü n2n , íî ìîæíî èñêóññòâåííî äîïîëíèòü êîä ôóíêöèè íåíóæíûìèñèìâîëàìè, ÷òîáû åãî äëèíà ñòàëà ðàâíà 2poly(n) . Òîãäà ðàçìåð ñõåìû êîíúþíêöèè ðàíåå ïîñòðîåííûõ ñõåì ñòàíåò ïîëèíîìèàëüíûì îò äëèíû âõîäà, à ãëóáèíà îñòàíåòñÿ êîíñòàíòíîé. Äëèíà àðãóìåíòà ãåíåðàòîðàÍèñàíàÂèãäåðñîíà áóäåò ðàâíà O (log(2poly(n) ))2d+6 = O poly(n)2d+6 =poly(n).4Ïðèìåíÿÿ ëåììó 2.37, ïîëó÷àåì, ÷òî ñðåäè çíà÷åíèé ãåíåðàòîðàÍèñàíàÂèãäåðñîíà íà àðãóìåíòàõ ïîëèíîìèàëüíîé äëèíû åñòü êîä ôóíêöèè ñ ìàëûì ÷èñëîì êîëëèçèé âî âñåõ ìíîæåñòâàõ Sb,k,s .Äàëåå, íóæíûé àðãóìåíò ãåíåðàòîðà ìîæíî íàéòè, èñïîëüçóÿ ïàìÿòüO(s) + poly(n). Ýêâèâàëåíòíî, ïî àðãóìåíòó ãåíåðàòîðà ìîæíî ðàñïîçíàòü,ÿâëÿåòñÿ ëè çíà÷åíèå íà í¼ì êîäîì ôóíêöèè ñ ìàëûì ÷èñëîì êîëëèçèé.Äåéñòâèòåëüíî, áóäåì ïåðåáèðàòü âñå ñëîâà b äëèíû íå áîëüøå r è âñå÷èñëà k 6 n. Äëÿ êàæäîé ïàðû (b, k) áóäåì ïåðå÷èñëÿòü Sb,k,s è äëÿ êàæäîãî âíîâü ïîëó÷åííîãî ñëîâà âû÷èñëÿòü ðàçìåð êîëëèçèè ñ åãî ó÷àñòèåì.Äëÿ ýòîãî íóæíî âû÷èñëèòü çíà÷åíèå ñãåíåðèðîâàííîé ôóíêöèè íà ýòîìñëîâå è ñîõðàíèòü ïðåôèêñ ýòîãî çíà÷åíèÿ äëèíû k .
Çàòåì íóæíî âíîâüçàïóñòèòü ïåðå÷èñëåíèå Sb,k,s , íà ïîëó÷àåìûõ ñëîâàõ âû÷èñëÿòü çíà÷åíèåôóíêöèè è ïðîâåðÿòü, ñîâïàäàåò ëè åãî ïðåôèêñ äëèíû k ñ ñîõðàí¼ííûì. ñëó÷àå ñîâïàäåíèÿ íóæíî óâåëè÷èòü ñ÷¼ò÷èê êîëëèçèé íà åäèíèöó. Åñëèõîòÿ áû äëÿ îäíîé ïàðû (b, k) õîòÿ áû äëÿ îäíîãî ýëåìåíòà Sb,k,s ñ÷¼ò÷èêïðåâûñèò m, òî àðãóìåíò ãåíåðàòîðà ñëåäóåò îòâåðãíóòü. Åñëè æå äëÿ âñåõïàð (b, k) è âñåõ ýëåìåíòîâ Sb,k,s ñ÷¼ò÷èê îñòàëñÿ ìåíüøå m, òî àðãóìåíòíóæíî ïðèíÿòü.
Ïðè ýòîì âû÷èñëåíèÿ, òðåáóþùèå çîíû O(s), ìîæíî âåñòèíà îäíîì è òîì æå ó÷àñòêå ïàìÿòè, à âñå íàêëàäíûå ðàñõîäû òðåáóþò çîíûpoly(n). Òàêèì îáðàçîì, ëåêñèêîãðàôè÷åñêè ïåðâûé àðãóìåíò ãåíåðàòîðà,ïîðîæäàþùèé íóæíóþ ôóíêöèþ, èìååò ñëîæíîñòü O(log n + log log s) ïðèîãðàíè÷åíèè íà ïàìÿòü O(s) + poly(n). Äîáàâêà O(log log s) ïðîèñõîäèò îò4Àíàëîãè÷íî ìîæíî óñèëèòü ôîðìóëèðîâêè òåîðåì 4.9, 4.10, 4.15 è 4.16, çàìåíèâ óñëîâèÿ |b| < n èíà |b| < poly(n) è |c| < poly(n), ñîîòâåòñòâåííî.|c| < n74òîãî, ÷òî äëÿ íàõîæäåíèÿ ýòîãî àðãóìåíòà íóæíî çíàòü s ñ òî÷íîñòüþ äîóìíîæåíèÿ íà 2.Òåïåðü ïîêàæåì, êàê äîêàçàòü óòâåðæäåíèå òåîðåìû.  êà÷åñòâå p íóæíî âçÿòü F (a), ãäå F ôóíêöèÿ, ïîëó÷åííàÿ ïðè ïîìîùè ãåíåðàòîðà èçíóæíîãî àðãóìåíòà.
Âòîðîå óñëîâèå ñîáëþäåíî, ïîñêîëüêó àðãóìåíò ãåíåðàòîðà, ïîðîæäàþùèé ôóíêöèþ F , èìååò ëîãàðèôìè÷åñêóþ ñëîæíîñòü.Åñëè èçâåñòíû ýòîò àðãóìåíò è a, òî p íàõîäèòñÿ íà ïîëèíîìèàëüíîé ïàìÿòè. Ïåðâîå æå óñëîâèå âûïîëíåíî â ñèëó óñëîâèÿ íà ìàëîñòü ÷èñëà êîëëèçèé ó F . Ïîìèìî b è pb , äëÿ íàõîæäåíèÿ a íóæíî çàäàòü àðãóìåíò ãåíåðàòîðà, ïîðîæäàþùèé F , è íîìåð a ñðåäè ýëåìåíòîâ Sb,kb ,s , îáðàçû êîòîðûõíà÷èíàþòñÿ ñ pb . (Ìû îáîçíà÷àåì ÷åðåç kb âåëè÷èíó C(a|b)).  ñèëó ìàëîãî÷èñëà êîëëèçèé âíóòðè Sb,kb ,s äëÿ çàïèñè ýòîãî íîìåðà äîñòàòî÷íî ëîãàðèôìè÷åñêîãî ÷èñëà áèòîâ. Ïàìÿòè O(s) + poly(n) áóäåò äîñòàòî÷íî è äëÿïîèñêà íóæíîãî àðãóìåíòà ãåíåðàòîðà, è äëÿ íàõîæäåíèÿ a: íà òàêîé ïàìÿòè ìîæíî ïåðå÷èñëÿòü Sb,kb ,s è ñ÷èòàòü çíà÷åíèÿ F íà âñåõ ïåðå÷èñëåííûõýëåìåíòàõ. Ñîîòâåòñòâåííî, ìîæíî ïåðå÷èñëÿòü è òå ýëåìåíòû Sb,kb ,s , çíà÷åíèå F íà êîòîðûõ íà÷èíàåòñÿ ñ pb .
Ñëîâî a îïðåäåëèòñÿ íîìåðîì â ýòîìïåðå÷èñëåíèè.Îáñóäèì, ïî÷åìó àíàëîãè÷íîå ðàññóæäåíèå íå ïîäîéä¼ò äëÿ èñõîäíîéòåîðåìû. Ïåðâûå äâà øàãà äîêàçàòåëüñòâà îñòàíóòñÿ â ñèëå: íàéä¼òñÿ õåøôóíêöèÿ ñ ìàëûì ÷èñëîì êîëëèçèé âî âñåõ ìíîæåñòâàõ Sb,k = {x | C(x|b) <k}, è å¼ ìîæíî ðàñïîçíàòü ñõåìîé êîíñòàíòíîé ãëóáèíû.
Îäíàêî, òðåòèéøàã ïðîâåñòè íå ïîëó÷èòñÿ: íåïîíÿòíî, ïî÷åìó îäíà èç òàêèõ ñõåì èìååòìàëóþ ñëîæíîñòü. Èç-çà òîãî, ÷òî ôóíêöèÿ C íå âû÷èñëèìà, ïî ìíîæåñòâóíåëüçÿ àëãîðèòìè÷åñêè ïîíÿòü, èìååò îíî âèä Sb,k èëè íå èìååò. Ïîýòîìóíåëüçÿ ïðîâåðèòü ìàëîñòü ðàçìåðà êîëëèçèé òîëüêî íà ìíîæåñòâàõ Sb,k ,ðàçðåøèâ êîëëèçèÿì íà äðóãèõ ìíîæåñòâàõ áûòü áîëüøèìè. Èç-çà ýòîãîïðèõîäèòñÿ ââîäèòü íåñêîëüêî õåø-ôóíêöèé, òðåáîâàòü ìàëîãî ÷èñëà êîëëèçèé âî âñåõ ìíîæåñòâàõ, è âîçíèêàåò èñõîäíàÿ êîíñòðóêöèþ Ìó÷íèêà.Îòìåòèì, ÷òî òåîðåìó 4.18 ìîæíî íåôîðìàëüíî èíòåðïðåòèðîâàòü êàêñïîñîá óíèâåðñàëüíîãî êîäèðîâàíèÿ: ïî ñëîâó a ïîëó÷àåòñÿ ñëîâî p, òàêîå÷òî äëÿ ëþáîãî íå ñëèøêîì äëèííîãî b äîñòàòî÷íî ïðî÷åñòü ïåðâûå Cs (a|b)áèòîâ p, ÷òîáû çàòåì âîññòàíîâèòü a.
 òåðìèíàõ êîììóíèêàöèè ñ ïîäñêàçêàìè ìîæíî ñêàçàòü, ÷òî Àëèñà íå íóæäàåòñÿ â ïîäñêàçêå, çàâèñÿùåé îò b,à äîëæíà ëèøü çíàòü ìàêñèìàëüíî âîçìîæíóþ äëèíó b è øèðèíó êàíàëà75d2aÀëèñàÁîákabÐèñ. 4.4: Ñõåìà êîììóíèêàöèè ñ ïîäñêàçêîé äëÿ Áîáà: Àëèñà ïðîèçâîäèò óíèâåðñàëüíûéêîä p, Áîá ïîëó÷àåò ïåðâûå k áèòîâ ýòîãî êîäà, ñëîâî b è ïîäñêàçêó d2 è âîññòàíàâëèâàåòa.(ñì. ðèñ. 4.4).Òàêæå ìîæíî ñôîðìóëèðîâàòü òåîðåìó â òåðìèíàõ èçâëå÷åíèÿ ñëó÷àéíîñòè: ïî ñëîâó a ïîëó÷àåòñÿ íå ïðîñòî íåñæèìàåìîå íà ïîëèíîìèàëüíîéïàìÿòè îïèñàíèå p, à òàêîå, ÷òî äëÿ ëþáîãî ñëîâà b ïðåôèêñ p äëèíû Cs (a|b)òàêæå íå ñæèìàåì ïðè èçâåñòíîì b.Çàâåðøèì ðàçäåë ìåòàôîðè÷åñêèì îïèñàíèåì òåîðåìû, ïðèíàäëåæàùèì À.Øåíþ. Äîêëàä÷èê äåëàåò äîêëàä äëÿ àóäèòîðèè ñ ðàçíûì óðîâíåì ïîäãîòîâêè.
Ðàçíûå ñëóøàòåëè óæå çíàþò íåêîòîðóþ ÷àñòü òîãî, ÷òîäîêëàä÷èê õî÷åò ðàññêàçàòü. Òîãäà äîêëàä ìîæåò áûòü âûñòðîåí òàêèì îáðàçîì, ÷òîáû êàæäûé ñëóøàòåëü ìîã óéòè, ïðîñëóøàâ ìèíèìàëüíî íåîáõîäèìóþ ÷àñòü äîêëàäà è ïîñëå íåáîëüøîé ïîäñêàçêè âîññòàíîâèòü âñþèñõîäíóþ èíôîðìàöèþ.76Ãëàâà 5Òåîðåìà Ìó÷íèêà äëÿCAM-ñëîæíîñòèñ îãðàíè÷åíèåì íà âðåìÿÂðåìÿ êàê âû÷èñëèòåëüíûé ðåñóðñ îòëè÷àåòñÿ îò ïàìÿòè îäíèì ñóùåñòâåííûì íåäîñòàòêîì: åãî íåëüçÿ èñïîëüçîâàòü âòîðè÷íî.
Ïîýòîìó íèêàêèå ïåðåáîðíûå êîíñòðóêöèè íå ìîãóò ñðàáîòàòü ïðè äîêàçàòåëüñòâå òåîðåìû ñ îãðàíè÷åíèåì íà âðåìÿ, ìîæíî èñïîëüçîâàòü òîëüêî ÿâíûå êîíñòðóêöèè. Òåì íå ìåíåå, äàæå ñ èñïîëüçîâàíèåì ÿâíûõ êîíñòðóêöèé íå óäà¼òñÿïîëó÷èòü âàðèàíò òåîðåìû Ìó÷íèêà äëÿ îáû÷íîé ñëîæíîñòè. Çàòî ìîæíîïîëó÷èòü âàðèàíò òåîðåìû Ìó÷íèêà äëÿ CAM-ñëîæíîñòè. Çäåñü èñïîëüçóåòñÿ ÿâíàÿ êîíñòðóêöèÿ ýêñòðàêòîðîâ Òðåâèñàíà [49], à ñàìî ðàññóæäåíèåâî ìíîãîì èñïîëüçóåò èäåè, èçëîæåííûå â ñòàòüå [13]. Ïîñêîëüêó ìû áóäåìãîâîðèòü òîëüêî îá îãðàíè÷åíèÿõ íà âðåìÿ, òî âåðõíèé èíäåêñ â îáîçíà÷åíèÿõ äëÿ ñëîæíîñòè â ýòîé è òîëüêî ýòîé ãëàâå áóäåò îçíà÷àòü îãðàíè÷åíèåíà âðåìÿ, à íå íà ïàìÿòü.5.1Ôîðìóëèðîâêà òåîðåìûÌû äîêàæåì ñëåäóþùåå óòâåðæäåíèå:Òåîðåìà 5.1. Äëÿ ëþáîãî ïîëèíîìà t1 (n) ñóùåñòâóåò ïîëèíîì t2 (n), äëÿêîòîðîãî âûïîëíåíî ñëåäóþùåå ñâîéñòâî.
Ïóñòü äàíû ÷èñëà n è k , ñëîâîa äëèíû ìåíüøå n è ñëîâî b, òàêèå ÷òî Ct1 (n) (a|b) < k . Òîãäà ñóùåñòâóåòñëîâî p, óäîâëåòâîðÿþùåå ñëåäóþùèì óñëîâèÿì:• CAMt2 (n) (a|b, p) = O(log3 n);• |p| 6 k + O(log3 n);• Ct2 (n) (p|a) = O(log3 n).77d1 O(log3 n)and2 O(log3 n)pÀëèñà3k + O(log n)ÁîáaÑëó÷àéíûå áèòû èìàãèÿ ÌåðëèíàbÐèñ. 5.1: Ñõåìà êîììóíèêàöèè â òåîðåìå äëÿ CAM-ñëîæíîñòè. òåðìèíàõ çàäà÷è î ïåðåäà÷å èíôîðìàöèè ýòó òåîðåìó ìîæíî èíòåðïðåòèðîâàòü òàê: îïòèìàëüíîå óñëîâíîå êîäèðîâàíèå âîçìîæíî, åñëè êîäèðîâùèê è äåêîäèðîâùèê ïîëèíîìèàëüíî îãðàíè÷åíû, íî îáà ìîãóò ïîëó÷àòü ïîäñêàçêè äëèíû O(log3 n), à äåêîäèðîâùèê ìîæåò ê òîìó æå èñïîëüçîâàòü ñëó÷àéíûå áèòû è ìàãèþ Ìåðëèíà (ñì.
ðèñ. 5.1).Ìîæíî çàìåòèòü, ÷òî â íåêîòîðûõ ìåñòàõ O(log3 n) ìîæíî çàìåíèòü íàO(1). Òàê, áèòû, íåîáõîäèìûå äëÿ äåêîäèðîâàíèÿ a ïî b è p, ìîæíî âêëþ÷èòü â ïðîãðàììó p è ïåðåäàâàòü êîäèðîâùèêó ïðè ïîñòðîåíèè p. Èç-çàýòîãî óâåëè÷àòñÿ êîíñòàíòû â O(·)-îáîçíà÷åíèÿõ âî âòîðîì è òðåòüåì ñîîòíîøåíèÿõ, à â ïåðâîì O(log3 n) çàìåíèòñÿ íà O(1). Ìîæíî ñäåëàòü íàîáîðîò: ëèøíèå áèòû â ñëîâå p ïåðåíåñòè â îïèñàíèå a ïðè èçâåñòíûõ bè p.
Òîãäà ñëîâî p áóäåò èìåòü äëèíó ðîâíî k , à êîíñòàíòû â îñòàëüíûõO(·)-îáîçíà÷åíèÿõ óâåëè÷àòñÿ. Òîëüêî ñëîæíîñòü p ïðè èçâåñòíîì a íåëüçÿóìåíüøèòü â äàííîé êîíñòðóêöèè.5.2Îïèñàíèå êîíñòðóêöèèÂíà÷àëå äàäèì íåñêîëüêî îïðåäåëåíèé, êîòîðûå èñïîëüçóþòñÿ ïðè ïîñòðîåíèè ôóíêöèè Òðåâèñàíà.Îïðåäåëåíèå 5.2. Ïóñòü l è d ñóòü íàòóðàëüíûå ÷èñëà, à Si ⊂ {1, .
. . , d}äëÿ i = 1, . . . , m. Ñèñòåìà ìíîæåñòâ {S1 , . . . , Sm } íàçûâàåòñÿ (l, d)-ñëàáûìäèçàéíîì, åñëè êàæäîå Si ñîñòîèò èç l ýëåìåíòîâ è äëÿ êàæäîãî i > 1i−1P |Si ∩Sj |ñóììà2íå ïðåâîñõîäèò m − 1.j=1Òåîðåìà 5.3 ( [37]). Ñóùåñòâóåò àëãîðèòì, ðàáîòàþùèé ïîëèíîìèàëüíîå îò l + m âðåìÿ è ãåíåðèðóþùèé (l, d)-ñëàáûé äèçàéí äëÿ d =O(l2 log m).78Äëÿ äàëüíåéøåãî ìû çàôèêñèðóåì íåêîòîðûé ñëàáûé äèçàéí, ïîðîæä¼ííûé ýòèì àëãîðèòìîì.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
