Диссертация (1103424)
Текст из файла
ÔÃÁÎÓ ÂÏÎ Ìîñêîâñêèé ãîñóäàðñòâåííûéóíèâåðñèòåò èìåíè Ì. Â. ËîìîíîñîâàÌåõàíèêî-ìàòåìàòè÷åñêèé ôàêóëüòåòÍà ïðàâàõ ðóêîïèñèÌóñàòîâ Äàíèèë Âëàäèìèðîâè÷Êîìáèíàòîðíûå ìåòîäûâ òåîðèè êîëìîãîðîâñêîé ñëîæíîñòèñ îãðàíè÷åíèåì íà ðåñóðñû01.01.06 ìàòåìàòè÷åñêàÿ ëîãèêà, àëãåáðà è òåîðèÿ ÷èñåëÄÈÑÑÅÐÒÀÖÈßíà ñîèñêàíèå ó÷åíîé ñòåïåíèêàíäèäàòà ôèçèêî-ìàòåìàòè÷åñêèõ íàóêÍàó÷íûé ðóêîâîäèòåëü:äîêòîð ôèçèêî-ìàòåìàòè÷åñêèõ íàóê,ïðîôåññîð Íèêîëàé Êîíñòàíòèíîâè÷ ÂåðåùàãèíÌîñêâà 2014Îãëàâëåíèå1 Ââåäåíèå41.1 Àêòóàëüíîñòü òåìû è öåëè ðàáîòû1.2 Îñíîâíûå ðåçóëüòàòû . . . . .
. .1.3 Àïðîáàöèÿ ðàáîòû . . . . . . . . .1.4 Ïëàí äàëüíåéøåãî èçëîæåíèÿ . . .1.5 Èñïîëüçóåìûå îáîçíà÷åíèÿ . . . .Áëàãîäàðíîñòè . . . . . . . . . . . . . ...........................................................................................2 Îáçîð îñíîâíûõ ïîíÿòèé2.12.22.32.42.52.62.74899111314Êîëìîãîðîâñêàÿ ñëîæíîñòü .
. . . . .Ýêñòðàêòîðû . . . . . . . . . . . . . .Êîëìîãîðîâñêèå ýêñòðàêòîðû . . . . .Ñõåìû èç ôóíêöèîíàëüíûõ ýëåìåíòîâÃåíåðàòîðû ïñåâäîñëó÷àéíûõ ÷èñåë .Âû÷èñëèòåëüíàÿ XOR-Ëåììà . . . . .Îòäåëüíûå èñïîëüçóåìûå íåðàâåíñòâà...........................................................................................141824262729303 Ïðèìåíåíèå ýêñòðàêòîðîâ äëÿ äîêàçàòåëüñòâà òåîðåìûÌó÷íèêà îá óñëîâíîé ñëîæíîñòè323.13.23.3Ôîðìóëèðîâêà òåîðåìû è èäåÿ äîêàçàòåëüñòâà . . . .
. . . .Ïðèìåíåíèå ýêñòðàêòîðîâ äëÿ äîêàçàòåëüñòâà òåîðåìû . . .Òåîðåìà Ìó÷íèêà äëÿ íåñêîëüêèõ óñëîâèé è ïðåôèêñíûå ýêñòðàêòîðû . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23337414 Òåîðåìà Ìó÷íèêà äëÿ ñëîæíîñòè ñ îãðàíè÷åíèåì íà ïàìÿòü484.14.24.3Äîêàçàòåëüñòâî ïðè ïîìîùè ÿâíîãî ýêñòðàêòîðà . . .
. . . .Äîêàçàòåëüñòâî ïðè ïîìîùè ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà4.2.1 Ôîðìóëèðîâêà íóæíîãî ñâîéñòâà è äîêàçàòåëüñòâî ñóùåñòâîâàíèÿ . . . . . . . . . . . . . . . . . . . . . . .4.2.2 Ðàñïîçíàâàíèå ìàëîãî ÷èñëà êîëëèçèé ïðè ïîìîùèñõåìû êîíñòàíòíîé ãëóáèíû . . . . . . . . . . . . .
. .4.2.3 Ïîèñê àðãóìåíòà ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà, ïîðîæäàþùåãî ôóíêöèþ ñ ìàëûì ÷èñëîì êîëëèçèé . .4.2.4 Ôîðìóëèðîâêà è äîêàçàòåëüñòâî âàðèàíòà òåîðåìûÌó÷íèêà . . . . . . . . . . . . . . . . . . . . . . . . . .Òåîðåìà ñ îãðàíè÷åíèåì íà ïàìÿòü äëÿ íåñêîëüêèõ óñëîâèé4.3.1 Äîêàçàòåëüñòâî ïðè ïîìîùè ÿâíîãî ýêñòðàêòîðà . . .4.3.2 Äîêàçàòåëüñòâî ïðè ïîìîùè ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà . . . . .
. . . . . . . . . . . . . . . . . . .4.3.3 Êîìïèëÿöèÿ äâóõ ïîäõîäîâ è òåîðåìà äëÿ ïîëèíîìèàëüíîãî ÷èñëà óñëîâèé . . . . . . . . . . . . . . . . . .485556575962646468715 Òåîðåìà Ìó÷íèêà äëÿ CAM-ñëîæíîñòè ñ îãðàíè÷åíèåì íàâðåìÿ775.15.25.35.4Ôîðìóëèðîâêà òåîðåìû . . . . . . . . . . .Îïèñàíèå êîíñòðóêöèè . . . . . . . . . . . .Äîêàçàòåëüñòâî êîððåêòíîñòè êîíñòðóêöèèÎ òåîðåìå äëÿ íåñêîëüêèõ óñëîâèé .
. . . .........................................6 Êîëìîãîðîâñêèå ýêñòðàêòîðû ñ îãðàíè÷åíèåì íà ïàìÿòü6.16.26.36.46.56.6Îïðåäåëåíèÿ è ôîðìóëèðîâêè òåîðåì . . . . .ϼñòðûå òàáëèöû . . . . . . . . . . . . . . . . .Èäåÿ äîêàçàòåëüñòâà îñíîâíîé òåîðåìû . . . .Ïðèìåíåíèå ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà .Çàâåðøåíèå äîêàçàòåëüñòâà îñíîâíîé òåîðåìûÒåîðåìà äëÿ ìàëûõ îãðàíè÷åíèé íà ïàìÿòü . ...........................................7778829093......9394100102111118Çàêëþ÷åíèå120Ëèòåðàòóðà1223Ãëàâà 1Ââåäåíèå1.1Àêòóàëüíîñòü òåìû è öåëè ðàáîòûÏîíÿòèå êîëìîãîðîâñêîé ñëîæíîñòè ïîÿâèëîñü â 1960-õ ãîäàõ â ðàáîòàõ Êîëìîãîðîâà [6], Ñîëîìîíîâà [45] è ×åéòèíà [14; 15]. Êîëìîãîðîâñêóþñëîæíîñòü ìîæíî îïðåäåëÿòü äëÿ ëþáûõ êîíå÷íûõ îáúåêòîâ, íî äîñòàòî÷íî ðàññìàòðèâàòü äâîè÷íûå ñëîâà, ò.å.
êîíå÷íûå ïîñëåäîâàòåëüíîñòèèç íóëåé è åäèíèö. Íåôîðìàëüíî ãîâîðÿ, ñëîæíîñòü ñëîâà åñòü ñëîæíîñòüåãî àëãîðèòìè÷åñêîãî îïèñàíèÿ, ò.å. äëèíà êðàò÷àéøåé ïðîãðàììû, êîòîðàÿ ïå÷àòàåò ýòî ñëîâî íà ïóñòîì âõîäå. Òàêæå ðàññìàòðèâàþò óñëîâíóþñëîæíîñòü îäíîãî ñëîâà îòíîñèòåëüíî äðóãîãî, ò.å. äëèíó êðàò÷àéøåé ïðîãðàììû, ïå÷àòàþùåé ïåðâîå ñëîâî ïîñëå ïîëó÷åíèÿ íà âõîä âòîðîãî. Ðàçóìååòñÿ, ýòè îïðåäåëåíèÿ çàâèñÿò îò òîãî, êàêîé ÿçûê ïðîãðàììèðîâàíèÿèñïîëüçóåòñÿ äëÿ îïèñàíèÿ, íî ñîãëàñíî òåîðåìå ÊîëìîãîðîâàÑîëîìîíîâàñóùåñòâóåò îïòèìàëüíûé ÿçûê ïðîãðàììèðîâàíèÿ, ïðè êîòîðîì ñëîæíîñòèâñåõ ñëîâ ìèíèìàëüíû ñ òî÷íîñòüþ äî àääèòèâíîé êîíñòàíòû. Ýòî ïîçâîëÿåò íå ññûëàòüñÿ íà êîíêðåòíûé ÿçûê ïðîãðàììèðîâàíèÿ è ïðè ýòîì ôîðìóëèðîâàòü ðàçëè÷íûå óòâåðæäåíèÿ î ñâÿçè ñëîæíîñòåé ðàçëè÷íûõ ñëîâ.Ýòè óòâåðæäåíèÿ ôîðìóëèðóþòñÿ ñ òî÷íîñòüþ äî àääèòèâíîé êîíñòàíòû,çàâèñÿùåé òîëüêî îò âûáîðà îïòèìàëüíîãî ÿçûêà ïðîãðàììèðîâàíèÿ è íåçàâèñÿùåé îò êîíêðåòíûõ ñëîâ.
 ôîðìóëèðîâêàõ ýòà êîíñòàíòà òðàäèöèîííî îáîçíà÷àåòñÿ ÷åðåç O(1). (Íåêîòîðûå óòâåðæäåíèÿ ôîðìóëèðóþòñÿ ñòî÷íîñòüþ äî äðóãîãî àääèòèâíîãî ñëàãàåìîãî: O(log n), O(log3 n) è ò.ï.)Ê ñîæàëåíèþ, äî ñèõ ïîð íå ñëîæèëîñü åäèíîãî îáîçíà÷åíèÿ äëÿ ñëîæíîñòè.  äèññåðòàöèè ñëîæíîñòü ñëîâà x îáîçíà÷àåòñÿ ÷åðåç C(x), à óñëîâíàÿñëîæíîñòü ñëîâà x îòíîñèòåëüíî y ÷åðåç C(x|y).Òàêæå ðàññìàòðèâàþò êîëìîãîðîâñêóþ ñëîæíîñòü ñ îãðàíè÷åíèåì íà ðå4ñóðñû [28].
 ýòîì ñëó÷àå ïðîãðàììà, ãåíåðèðóþùàÿ ñëîâî, äîëæíà áûòüíå òîëüêî êîðîòêîé, íî è èñïîëüçóþùåé îãðàíè÷åííûå âû÷èñëèòåëüíûåðåñóðñû, à èìåííî âðåìÿ ðàáîòû è ïàìÿòü. Ðàçóìååòñÿ, ïðè íàëîæåíèè äîïîëíèòåëüíûõ îãðàíè÷åíèé ñëîæíîñòü íå óìåíüøàåòñÿ. Âàæíî, ÷òî â îòëè÷èå îò ñëîæíîñòè áåç îãðàíè÷åíèé ñëîæíîñòü ñ îãðàíè÷åíèÿìè ÿâëÿåòñÿâû÷èñëèìîé ôóíêöèåé.Äëÿ äîêàçàòåëüñòâà òîãî, ÷òî ñëîæíîñòü íåêîòîðîãî ñëîâà ìàëà, ÷àñòîèñïîëüçóþò ñëåäóþùèé ïðèíöèï, âîñõîäÿùèé ê Ñèïñåðó [43]: ýëåìåíòû ëþáîãî íåáîëüøîãî ïåðå÷èñëèìîãî ìíîæåñòâà ïðîñòû.
Áîëåå òî÷íî: åñëè ïåðå÷èñëèìîå ìíîæåñòâî S ñîäåðæèò íå áîëüøå K ñëîâ äëèíû n, òî âñå ýòèñëîâà èìåþò ñëîæíîñòü íå áîëüøå log K +log n+O(1). Äåéñòâèòåëüíî, êàæäîå èç íèõ ìîæíî çàäàòü ïåðå÷èñëÿþùèì àëãîðèòìîì, äëèíîé n è íîìåðîìâ ïåðå÷èñëåíèè ñëîâ äàííîé äëèíû. Ýòî íàáëþäåíèå ïîçâîëÿåò äîêàçûâàòüðàçëè÷íûå óòâåðæäåíèÿ î êîëìîãîðîâñêîé ñëîæíîñòè ÷åðåç êîìáèíàòîðíûå êîíñòðóêöèè: ñíà÷àëà ñòðîèòñÿ íåêîòîðîå ïåðå÷èñëèìîå ìíîæåñòâî,çàòåì êîìáèíàòîðíûìè ìåòîäàìè äîêàçûâàåòñÿ âåðõíÿÿ îöåíêà íà åãî ðàçìåð, è, íàêîíåö, äåëàåòñÿ âûâîä î ìàëîé ñëîæíîñòè ëþáîãî âõîäÿùåãî âíåãî ñëîâà.
Áîëåå òîãî, åñëè ïåðå÷èñëÿþùèé àëãîðèòì âû÷èñëèòåëüíî ýôôåêòèâåí, òî ñëîæíîñòü ñ îãðàíè÷åíèåì íà ðåñóðñû òàêæå ìàëà.  äèññåðòàöèè èçó÷àþòñÿ äâà ïðèìåðà òàêîãî ïîäõîäà.Âî-ïåðâûõ, èçó÷àåòñÿ òåîðåìà Ìó÷íèêà îá óñëîâíîì êîäèðîâàíèè [30].Îíà ãëàñèò, ÷òî äëÿ ëþáûõ ñëîâ a è b, òàêèõ ÷òî C(a|b) < k , íàéä¼òñÿ ñëîâî p äëèíû k , äëÿ êîòîðîãî îäíîâðåìåííî âåðíû ñîîòíîøåíèÿC(a|b, p) = O(log n) è C(p|a) = O(log n), ãäå n = C(a). Èíûìè ñëîâàìè,ñðåäè âñåõ îïèñàíèé a ïðè èçâåñòíîì b íàéä¼òñÿ p, ïðîñòîå îòíîñèòåëüíî a.Ïðèíöèï äîêàçàòåëüñòâà òàêîé: ðàññìàòðèâàåòñÿ íåêîòîðîå ñåìåéñòâî õåøôóíêöèé, îòîáðàæàþùèõ ñëîâà äëèíû n â ñëîâà äëèíû k . Ñëîâî p ñòðîèòñÿêàê îáðàç ñëîâà a, ïîýòîìó äëÿ åãî îïèñàíèÿ òðåáóåòñÿ ëèøü çàäàòü íîìåðõåø-ôóíêöèè. Äëÿ òîãî, ÷òîáû a ìîæíî áûëî âîññòàíîâèòü ïî b è p, íóæíî ÷òîáû p ìîãëî áûòü âûáðàíî êàê õåø-çíà÷åíèå ó íå ñëèøêîì áîëüøîãî÷èñëà ñëîâ, èìåþùèõ ñëîæíîñòü íå áîëüøå k ïðè óñëîâèè b.
Ýòîãî ìîæíîäîáèòüñÿ, íàëîæèâ ñïåöèàëüíûå êîìáèíàòîðíûå òðåáîâàíèÿ íà ñåìåéñòâîôóíêöèé. Ñàì Ìó÷íèê èñïîëüçîâàë ñâîéñòâî ýêñïàíäåðà, À.Øåíü [42] èñïîëüçîâàë ñâîéñòâî ñóùåñòâîâàíèÿ îíëàéí-ïàðîñî÷åòàíèé, à â íàñòîÿùåéðàáîòå ïîêàçàíî, ÷òî ìîæíî ðàññìîòðåòü ñâîéñòâî ýêñòðàêòîðà.Ïîíÿòèå ýêñòðàêòîðà áûëî ââåäåíî â íà÷àëå 1990-õ ãîäîâ â ðàáîòå Íè5ñàíà è Öóêåðìàíà [35] êàê òåõíè÷åñêèé èíñòðóìåíò.
Íåôîðìàëüíî ãîâîðÿ,ýêñòðàêòîð ýòî ôóíêöèÿ, êîòîðàÿ ïîëó÷àåò íà âõîä äâå íå î÷åíü õîðîøèå ñëó÷àéíûå âåëè÷èíû è ïðåâðàùàåò èõ â ïî÷òè ñëó÷àéíûå. Âïîñëåäóþùèå ãîäû áûëî ðàçðàáîòàíî ìíîæåñòâî êîíñòðóêöèé è ïðèëîæåíèé ýêñòðàêòîðîâ [40; 41; 50], ê êîòîðûì íàñòîÿùàÿ ðàáîòà äîáàâëÿåò åù¼îäíî.Ìó÷íèê òàêæå äîêàçàë âàðèàöèþ òåîðåìû äëÿ äâóõ óñëîâèé. Îíà ãëàñèò, ÷òî äëÿ ëþáûõ ñëîâ a, b è c, òàêèõ ÷òî C(a|b) < k è C(a|c) < l, ãäål 6 k , íàéä¼òñÿ ñëîâî p äëèíû k , òàêîå ÷òî äëÿ íåãî âåðíû ñîîòíîøåíèÿC(a|b, p) = O(log n) è C(p|a) = O(log n), à äëÿ åãî íà÷àëà q äëèíû l âåðíîC(a|c, q) = O(log n). Ìîæíî îáîáùèòü ýòó òåîðåìó íà ëþáîå êîíñòàíòíîå èäàæå ïîëèíîìèàëüíîå ÷èñëî óñëîâèé.
Èíûìè ñëîâàìè, ïðîãðàììû, ïðåâðàùàþùèå ðàçíûå ñëîâà â a, íå òîëüêî ïðîñòû îòíîñèòåëüíî a, íî è ÿâëÿþòñÿïðåôèêñàìè îäíîé è òîé æå äëèííîé ïðîãðàììû ñ òî÷íîñòüþ äî íåáîëüøèõäîáàâîê ëîãàðèôìè÷åñêîé äëèíû. Ïðèíöèï äîêàçàòåëüñòâà ýòîé òåîðåìûòàêîé æå, íî êîìáèíàòîðíîå óñëîâèå íà ñåìåéñòâî ôóíêöèé áóäåò íåñêîëüêî äðóãèì.  íàñòîÿùåé ðàáîòå ââîäèòñÿ ïîíÿòèå ïðåôèêñíîãî ýêñòðàêòîðàè ïîêàçûâàåòñÿ, êàê ïðè ïîìîùè íåãî äîêàçàòü òåîðåìó äëÿ äâóõ óñëîâèé.Âòîðûì ïðèìåðîì ïàðàëëåëèçìà ìåæäó ñëîæíîñòíûìè è êîìáèíàòîðíûìè óòâåðæäåíèÿìè ÿâëÿþòñÿ òåîðåìû î ñóùåñòâîâàíèè êîëìîãîðîâñêèõýêñòðàêòîðîâ (îáû÷íûõ è óñèëåííûõ). Êîëìîãîðîâñêèì ýêñòðàêòîðîì íàçûâàåòñÿ ôóíêöèÿ äâóõ àðãóìåíòîâ, çíà÷åíèå êîòîðîé èìååò ìåíüøèé äåôåêò ñëó÷àéíîñòè, ò.å.
ðàçíîñòü ìåæäó äëèíîé è ñëîæíîñòüþ, ÷åì êàæäûé èç å¼ àðãóìåíòîâ. Åñëè óñëîâíûé äåôåêò ñëó÷àéíîñòè, ò.å. ðàçíîñòüìåæäó äëèíîé è óñëîâíîé ñëîæíîñòüþ çíà÷åíèÿ ôóíêöèè ïðè óñëîâèè îäíîãî èç àðãóìåíòîâ, òàêæå óìåíüøàåòñÿ, òî òàêàÿ ôóíêöèÿ íàçûâàåòñÿ óñèëåííûì êîëìîãîðîâñêèì ýêñòðàêòîðîì. Êîëìîãîðîâñêèå ýêñòðàêòîðû áûëè îïðåäåëåíû Äæ. Õè÷êîêîì è ñîàâòîðàìè [18; 22] è çàòåì èçó÷àëèñü Ì.Çèìàíäîì [5355]. Çèìàíä îïðåäåëèë êîìáèíàòîðíûå ïîíÿòèÿ ï¼ñòðûõ èðàâíîìåðíî ï¼ñòðûõ òàáëèö, äîêàçàë èõ ñóùåñòâîâàíèå è ïîêàçàë, ÷òî îíèÿâëÿþòñÿ êîëìîãîðîâñêèìè ýêñòðàêòîðàìè (îáû÷íûìè è óñèëåííûìè).Îñíîâíîé òåìîé äèññåðòàöèè ÿâëÿåòñÿ ðàñïðîñòðàíåíèå èçâåñòíûõ ðåçóëüòàòîâ î êîëìîãîðîâñêîé ñëîæíîñòè íà ñëîæíîñòü ñ îãðàíè÷åíèåì íàðåñóðñû. Äîñòèæåíèé â ýòîì íàïðàâëåíèè íå òàê ìíîãî.
Ìîæíî îòìåòèòüðåçóëüòàò Ëè è Ðîìàùåíêî î ñèììåòðèè èíôîðìàöèè [27], à òàêæå ðàáîòóÁþðìàíà, Ëè è âàí Ìåëêåáååêà î ñæàòèè ÿçûêîâ [13]. Äëÿ ñëîæíîñòè ñ6îãðàíè÷åíèåì íà ðåñóðñû ñòàíîâèòñÿ âàæíà ìîäåëü âû÷èñëåíèé: èñïîëüçîâàíèå íåäåòåðìèíèçìà è/èëè ñëó÷àéíîñòè ìîæåò ñóùåñòâåííî óìåíüøèòüñëîæíîñòü.  ÷àñòíîñòè, èçó÷àþò CAM-ñëîæíîñòü äëÿ íåäåòåðìèíèðîâàííûõ âåðîÿòíîñòíûõ âû÷èñëåíèé. Ýòà ìîäåëü áûëà ââåäåíà Ëàñëî Áàáàåì [11] è ïîëó÷èëà ìåòàôîðè÷åñêîå íàçâàíèå èãð ÀðòóðàÌåðëèíà.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
