Диссертация (1103424), страница 7
Текст из файла (страница 7)
ñïåöèàëüíî ïîäîáðàííîé(è çàâèñÿùåé îò a è b) èíôîðìàöèè, ïîñòóïàþùåé èçâíå (ñì. ðèñ. 3.2).Òåîðåìà Ìó÷íèêà óñòàíàâëèâàåò ïàðàëëåëè ìåæäó ðàçëè÷íûìè îáëàñòÿìè òåîðåòè÷åñêîé èíôîðìàòèêè. Òàê, óòâåðæäåíèå òåîðåìû àíàëîãè÷íî òåîðåìå ÂîëüôàÑëåïÿíà ( [44]) â øåííîíîâñêîé òåîðèè èíôîðìàöèè.Òåîðåìà ÂîëüôàÑëåïÿíà ôîðìàëèçóåò òó æå ñàìóþ êîììóíèêàöèîííóþñèòóàöèþ â ñëó÷àå, êîãäà êîëè÷åñòâî èíôîðìàöèè ìåðÿåòñÿ êàê øåííîíîâñêàÿ ýíòðîïèÿ, è ïîëó÷àåò àíàëîãè÷íîå íåîáõîäèìîå è äîñòàòî÷íîå óñëîâèå.Êðîìå òîãî, ðàçëè÷íûå äîêàçàòåëüñòâà òåîðåìû Ìó÷íèêà ïîçâîëÿþò ñâÿçàòü òåîðåòèêî-ñëîæíîñòíîå óòâåðæäåíèå ñ ðàçëè÷íûìè êîìáèíàòîðíûìè32aÀëèñàÁîákabÐèñ. 3.1: Ñõåìà êîììóíèêàöèè: Àëèñà ïîëó÷àåò ñëîâî a è äîëæíà ïåðåñëàòü ñîîáùåíèåäëèíîé íå áîëüøå k áèòîâ, òàê ÷òîáû Áîá, ïîëó÷èâøèé ñëîâî b, ìîã âîññòàíîâèòü a.d1ad2ÀëèñàÁîákabÐèñ.
3.2: Ñõåìà êîììóíèêàöèè ñ ïîäñêàçêàìè: Àëèñà è Áîá ìîãóò ïîëó÷àòü êîðîòêèåïîäñêàçêè d1 è d2 , çàâèñÿùèå è îò a, è îò b.óòâåðæäåíèÿìè. ðàçäåëå 3.1 ìû ïðèâåä¼ì ñòðîãóþ ôîðìóëèðîâêó òåîðåìû è îïèøåìîáùóþ èäåþ äîêàçàòåëüñòâà, â òîì ÷èñëå ñîøë¼ìñÿ íà êîìáèíàòîðíûåóòâåðæäåíèÿ, ñâÿçàííûå ñî ñëîæíîñòíûìè.  ðàçäåëå 3.2 ìû ïîäðîáíî îïèøåì íîâóþ òåõíèêó äîêàçàòåëüñòâà, èñïîëüçóþùèé ýêñòðàêòîðû.  ðàçäåëå 3.3 ìû ñôîðìóëèðóåì è äîêàæåì íîâûì ñïîñîáîì îáîáùåíèå òåîðåìûÌó÷íèêà íà ñëó÷àé íåñêîëüêèõ óñëîâèé, ïðè ýòîì â äîêàçàòåëüñòâå áóäåòèñïîëüçîâàòüñÿ ïîíÿòèå ïðåôèêñíîãî ýêñòðàêòîðà, îáîáùàþùåå ïîíÿòèåîáû÷íîãî.3.1Ôîðìóëèðîâêà òåîðåìû è èäåÿ äîêàçàòåëüñòâàÌû áóäåì äîêàçûâàòü òåîðåìó â ñëåäóþùåé ôîðìóëèðîâêå:Òåîðåìà 3.1. Ïóñòü äàíû ñëîâà èç íóëåé è åäèíèö a è b è ÷èñëà n è k ,òàêèå ÷òî C(a) < n è C(a|b) < k .
Òîãäà ñóùåñòâóåò òàêîå ñëîâî p, ÷òî:• C(a|p, b) 6 O(log n);• C(p) 6 k + O(log n);• C(p|a) 6 O(log n),33d1 O(log n)and2 O(log n)pÀëèñàk + O(log n)ÁîáabÐèñ. 3.3: Èëëþñòðàöèÿ ê òåîðåìå Ìó÷íèêà: åñëè Àëèñà è Áîá ìîãóò ïîëó÷àòü ïîäñêàçêèëîãàðèôìè÷åñêîé äëèíû, çàâèñÿùèå è îò a, è îò b, òî ïåðåäà÷à èíôîðìàöèè âîçìîæíà.Ñâåðõó/ñëåâà îò ñòðåëîê ïîäïèñàíû íàçâàíèÿ ñëîâ, à ñíèçó/ñïðàâà èõ äëèíû.ãäå êîíñòàíòû â O(·)-îáîçíà÷åíèÿõ íå çàâèñÿò îò a, b, n, k , íî ìîãóòçàâèñåòü îò âûáðàííîãî ñïîñîáà îïèñàíèÿ â îïðåäåëåíèè C. òåðìèíàõ êîììóíèêàöèè ìåæäó Àëèñîé è Áîáîì òåîðåìà Ìó÷íèêàóòâåðæäàåò, ÷òî êîììóíèêàöèÿ âîçìîæíà, åñëè øèðèíà êàíàëà ñîñòàâëÿåòk + O(log n) áèòîâ, à Àëèñà è Áîá ïîëó÷àþò ïîäñêàçêè ëîãàðèôìè÷åñêîéäëèíû (ñì.
ðèñ. 3.3).Ñðàçó ìîæíî ñäåëàòü íåñêîëüêî íåñëîæíûõ çàìå÷àíèé ïî ôîðìóëèðîâêå:1. Âî âòîðîì íåðàâåíñòâå ìîæíî çàìåíèòü ñëîæíîñòü ïðîãðàììû C(p) íàå¼ äëèíó |p|, òåì ñàìûì óñèëèâ ôîðìóëèðîâêó. Äåéñòâèòåëüíî, âìåñòîñàìîé ïðîãðàììû ìîæíî èñïîëüçîâàòü å¼ êðàò÷àéøåå îïèñàíèå: ïåðâîå íåðàâåíñòâî îñòàíåòñÿ â ñèëå, ïîñêîëüêó ïðîãðàììó ìîæíî ïîëó÷èòü ïî å¼ êðàò÷àéøåìó îïèñàíèþ, à òðåòüå ïîñêîëüêó êðàò÷àéøååîïèñàíèå ìîæíî ïîëó÷èòü, çíàÿ ïðîãðàììó è å¼ ñëîæíîñòü. Åñëè åñòüíåñêîëüêî êðàò÷àéøèõ îïèñàíèé, òî íóæíî âçÿòü ëåêñèêîãðàôè÷åñêèïåðâîå. Äâîè÷íàÿ çàïèñü ñëîæíîñòè èìååò äëèíó íå áîëüøå log n, êîòîðàÿ ïðèáàâèòñÿ ê ïðàâîé ÷àñòè è ëèøü óâåëè÷èò êîíñòàíòó â O(·)îáîçíà÷åíèè.2. Ìîæíî ñ÷èòàòü, ÷òî k = C(a|b) + 1: ýòî ìèíèìàëüíî âîçìîæíîå çíà÷åíèå k , áîëüøåå C(a|b).
Åñëè òåîðåìà âåðíà äëÿ òàêîãî k , òî äëÿâñåõ áîëüøèõ îíà âåðíà òåì áîëåå. Ïîýòîìó ìîæíî çàìåíèòü âî âòîðîì íåðàâåíñòâå k + O(log n) íà C(a|b) + O(log n). Òàêèì îáðàçîì, ìûïîëó÷èì íåðàâåíñòâî |p| 6 C(a|b) + O(log n). Àíàëîãè÷íî ìîæíî ïîëîæèòü n = C(a) + 1.343. Ìîæíî îòáðîñèòü ïîñëåäíèå O(log n) áèòîâ ïðîãðàììû p è äîïèñàòüèõ ê O(log n) áèòàì, çàäàþùèì a ïðè èçâåñòíûõ p è b. Òàêèì îáðàçîì, ïåðâîå íåðàâåíñòâî îñòàíåòñÿ â ñèëå. Òðåòüå íåðàâåíñòâî ïðèýòîì òîæå ñîõðàíèòñÿ.  èòîãå ìû ïîëó÷èì ñëåäóþùóþ ýêâèâàëåíòíóþ ôîðìóëèðîâêó: äëÿ ëþáûõ äâîè÷íûõ ñëîâ a è b ñóùåñòâóåò ñòðîêà p äëèíû íå áîëüøå C(a|b), òàêàÿ ÷òî C(a|p, b) 6 O(log C(a)) èC(p|a) 6 O(log C(a)).4.
Ìîæíî, íàîáîðîò, äîáèòüñÿ âûïîëíåíèÿ óñëîâèÿ C(a|p, b) 6 O(1). Äëÿýòîãî íóæíî âêëþ÷èòü O(log n) áèòîâ, îïèñûâàþùèõ a ïðè èçâåñòíûõp è b â èñõîäíîé ôîðìóëèðîâêå, â ñîñòàâ ïðîãðàììû p è â ñîñòàâ îïèñàíèÿ p ïðè èçâåñòíîì a. Ïðè ýòîì, ðàçóìååòñÿ, äëèíó p óæå íåëüçÿáóäåò óìåíüøèòü äî k , à êîíñòàíòà â îöåíêå C(p|a) âîçðàñò¼ò.5. Ïî ïðè÷èíàì, óêàçàííûì â ïåðâîì çàìå÷àíèè, äîñòàòî÷íî äîêàçàòüòåîðåìó äëÿ ñëó÷àÿ, êîãäà íå òîëüêî ñëîæíîñòü, íî è äëèíà a ìåíüøån: çàìåíà ñëîâà a íà åãî êðàò÷àéøåå îïèñàíèå èçìåíÿåò âñå ñëîæíîñòè,ñîäåðæàùèå a, íå áîëåå, ÷åì íà O(log n).Îáùèé ìåòîä äîêàçàòåëüñòâà åñòåñòâåííûì îáðàçîì âûòåêàåò èç ôîðìóëèðîâêè.
Íåðàâåíñòâî C(p|a) 6 O(log n) îçíà÷àåò, ÷òî ñëîâó a êàêèìòî âû÷èñëèìûì îáðàçîì ñîïîñòàâëåíû 2O(log n) = poly(n) ñëîâ (áóäåì íàçûâàòü èç îáðàçàìè a), ñðåäè êîòîðûõ íóæíî âûáðàòü p. ÍåðàâåíñòâîC(p) 6 k + O(log n) îçíà÷àåò, ÷òî êàæäîå èç ýòèõ ñëîâ èìååò ñëîæíîñòü(èëè äëèíó) íå áîëüøå k + O(log n). Çàäà÷à ñîñòîèò â ïîñòðîåíèè òàêîéêîíñòðóêöèè, ÷òîáû õîòÿ áû äëÿ îäíîãî èç ñëîâ p áûëî âûïîëíåíî íåðàâåíñòâî C(a|p, b) 6 O(log n). Åñòåñòâåííûé ñïîñîá ýòîãî äîáèòüñÿ òàêîâ:çàìåòèì, ÷òî ïðè èçâåñòíîì b ìîæíî ïåðå÷èñëÿòü ýëåìåíòû ìíîæåñòâàSb = {x | C(x|b) < k}.  ýòîì ìíîæåñòâå çàâåäîìî ëåæèò a. Êðîìå òîãî, ìîæíî ïåðå÷èñëÿòü ýëåìåíòû Sb , êîòîðûì ñîïîñòàâëåíî ñëîâî p (ò.å.ïðîîáðàçû p): ñëîâî a òàêæå ëåæèò ñðåäè íèõ.
Åñëè òàêèõ ýëåìåíòîâ ïîëèíîìèàëüíîå êîëè÷åñòâî, òî ñëîâî a ìîæåò áûòü çàäàíî ñâîèì íîìåðîìñðåäè íèõ. Òàêèì îáðàçîì, òðåáóåòñÿ, ÷òîáû õîòÿ áû ó îäíîãî îáðàçà aáûëî ïîëèíîìèàëüíîå ÷èñëî ïðîîáðàçîâ âíóòðè Sb .Ìû ïîëó÷èëè, ÷òî äëÿ äîêàçàòåëüñòâà òåîðåìû Ìó÷íèêà äîñòàòî÷íîäîêàçàòü ñóùåñòâîâàíèå ôóíêöèè f : {0, 1}<n × {0, 1}d → {0, 1}k , ãäå d =O(log n), ñî ñëåäóþùèì ñâîéñòâîì: äëÿ âñåõ äâîè÷íûõ ñëîâ a è b, òàêèõ35Sb = {x : C(x|b) < k}p{0, 1}<n{0, 1}kaÐèñ. 3.4: Îáùàÿ ñõåìà äîêàçàòåëüñòâà òåîðåìû Ìó÷íèêà: ñëîâî p âûáèðàåòñÿ êàê ñîñåäa â íåêîòîðîì ãðàôå, òàê ÷òîáû âíóòðè ìíîæåñòâî Sb ìàëî âåðøèí òàêæå èìåëè p âêà÷åñòâå ñîñåäà.÷òî |a| < n, C(a) = n − 1 è C(a|b) = k − 1,1 ñóùåñòâóåò i, òàêîå ÷òî óf (a, i) èìååòñÿ ïîëèíîìèàëüíîå ÷èñëî ïðîîáðàçîâ â Sb = {x | C(x|b) < k}.Cëîæíîñòü ýòîé ôóíêöèè íå äîëæíà ïðåâûøàòü O(log n).
Äåéñòâèòåëüíî,òîãäà C(p|a) 6 O(log n) âûïîëíåíî, ò.ê. O(log n) áèòîâ íóæíî äëÿ îïèñàíèÿôóíêöèè f è åù¼ O(log n) áèòîâ äëÿ çàäàíèÿ i. À íåðàâåíñòâî C(a|p, b) 6O(log n) âûïîëíåíî, ïîñêîëüêó O(log n) áèòîâ íóæíî òàê æå äëÿ îïèñàíèÿf è åù¼ O(log n) áèòîâ äëÿ çàäàíèÿ íîìåðà a ñðåäè ïðîîáðàçîâ p âíóòðèSb . Äëÿ óäîáñòâà è â ñèëó òðàäèöèè â äàëüíåéøåì ìû áóäåì ãîâîðèòü íåî ôóíêöèÿõ äâóõ àðãóìåíòîâ, à î äâóäîëüíûõ ãðàôàõ òèïà (n, k, d), êàê âðàçäåëå 2.2. Ñõåìà äîêàçàòåëüñòâà ïðîèëëþñòðèðîâàíà íà ðèñóíêå 3.4.Ðàçíûå ñïîñîáû äîêàçàòåëüñòâà îòëè÷àþòñÿ äðóã îò äðóãà òåì, êàê èìåííî äîêàçûâàåòñÿ ñóùåñòâîâàíèå ãðàôà ñ íåîáõîäèìûì ñâîéñòâîì.
Êàê ïðàâèëî, âûáèðàåòñÿ íåêîòîðîå áîëåå ñèëüíîå, íî ïðè ýòîì ðàçðåøèìîå ñâîéñòâî, èç êîòîðîãî ñëåäóåò íóæíîå. Ïðè ïîìîùè âåðîÿòíîñòíîãî ìåòîäà äîêàçûâàåòñÿ ñóùåñòâîâàíèå ãðàôà ñ ýòèì áîëåå ñèëüíûì ñâîéñòâîì, è äåëàåòñÿ âûâîä î òîì, ÷òî îäèí èç ýòèõ ãðàôîâ èìååò ìàëåíüêóþ ñëîæíîñòü. Àèìåííî, ïîñêîëüêó ñâîéñòâî ðàçðåøèìî, ìîæíî â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå ïåðåáðàòü âñå ãðàôû ñ çàÿâëåííûìè ðàçìåðàìè äîëåé è ñòåïåíÿìèâåðøèí ëåâîé äîëè, ïðîâåðèòü äëÿ êàæäîãî èç íèõ âûïîëíåíèå ñâîéñòâà èâçÿòü ïåðâûé, äëÿ êîòîðîãî ñâîéñòâî âûïîëíåíî. îðèãèíàëüíîé ñòàòüå [30] Àí. Ìó÷íèê â êà÷åñòâå îïðåäåëÿþùåãî ñâîé1Çäåñü ìû èñïîëüçóåì ñäåëàííûå âûøå çàìå÷àíèÿ ïðî ñëîæíîñòè è äëèíó a.36,S |S| < 2kÏëîõèå âåðøèíû{0, 1}<nÓ êàæäîé âåðøèíû D ñîñåäåé{0, 1}kÐèñ.
3.5: Äîêàçàòåëüñòâî òåîðåìû Ìó÷íèêà: ïëîõèå âåðøèíû â ïðàâîé äîëå ãðàôà.ñòâà áðàë ñâîéñòâî ýêñïàíäåðà. À. Øåíü èñïîëüçîâàë ñâîéñòâî ñóùåñòâîâàíèÿ îíëàéí-ïàðîñî÷åòàíèé [42; 63; 64].  ñëåäóþùåì ðàçäåëå ìû ïîêàæåì,êàê â êà÷åñòâå îïðåäåëÿþùåãî ñâîéñòâà èñïîëüçîâàòü ñâîéñòâî ýêñòðàêòîðà. (Íà ñàìîì äåëå, ãðàô ñî ñâîéñòâîì ýêñòðàêòîðà ìîæíî ïðåîáðàçîâàòüâ ãðàô, äîïóñêàþùèé îíëàéí-ïàðîñî÷åòàíèÿ, íî ìû ïðîâåä¼ì ïðÿìîå ðàññóæäåíèå).3.2Ïðèìåíåíèå ýêñòðàêòîðîâ äëÿ äîêàçàòåëüñòâà òåîðåìû ýòîì ðàçäåëå ìû âíà÷àëå ñôîðìóëèðóåì ïðîìåæóòî÷íîå ñâîéñòâî, êîòîðîå ñëåäóåò èç ñâîéñòâà ýêñòðàêòîðà, è èç êîòîðîãî ñëåäóåò ñâîéñòâî,íóæíîå â òåîðåìå Ìó÷íèêà, à çàòåì äîêàæåì îáå èìïëèêàöèè.Ïóñòü çàäàí äâóäîëüíûé ãðàô G òèïà (n, m, d), à òàêæå íåêîòîðîå ÷èñëîk < n è ïîäìíîæåñòâî ëåâîé äîëè S ⊂ {0, 1}<n ðàçìåðà íå áîëüøå K =2k .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
