Диссертация (1103424), страница 2
Текст из файла (страница 2)
Ìåòàôîðà îáúÿñíÿåòñÿ òàê: âû÷èñëåíèÿ ïðîâîäèò Àðòóð, áåñåäóþùèé ñ ìàãîìÌåðëèíîì. Àðòóð ìîæåò áðîñàòü ìîíåòêó (ò.å. ïîëó÷àòü ñëó÷àéíûå áèòû) è ñîâåðøàòü ïîëèíîìèàëüíûå âû÷èñëåíèÿ. Ìåðëèí ìîæåò âû÷èñëÿòüëþáûå ôóíêöèè (äàæå íå âû÷èñëèìûå àëãîðèòìè÷åñêè) è ìãíîâåííî óçíà¼ò ñëó÷àéíûå áèòû Àðòóðà. Âçàèìîäåéñòâèå óñòðîåíî òàê: ñíà÷àëà Àðòóðêèäàåò ìîíåòêó íåîáõîäèìîå ÷èñëî ðàç, çàòåì Ìåðëèí óçíà¼ò ðåçóëüòàòûè ïîñûëàåò íåêîòîðîå ñîîáùåíèå, çàòåì Àðòóð ïðîâîäèò ïîëèíîìèàëüíûåâû÷èñëåíèÿ è âûäà¼ò îòâåò.
Îòâåòîì ìîæåò áûòü ëèáî äâîè÷íîå ñëîâî, ëèáî ñèìâîë îøèáêè ⊥. Ñëîâî x íàçûâàåòñÿ ðåçóëüòàòîì ðàáîòû ïðîãðàììû,åñëè ñ âåðîÿòíîñòüþ õîòÿ áû 23 îäíîâðåìåííî âûïîëíåíû äâà óñëîâèÿ: âîïåðâûõ, Àðòóð âûäàñò x ïðè íåêîòîðûõ ñîîáùåíèÿõ Ìåðëèíà; âî-âòîðûõ,ïðè ëþáûõ äðóãèõ ñîîáùåíèÿõ Ìåðëèíà Àðòóð âûäàñò ëèáî òî æå x, ëèáî⊥.Âàæíûì òåõíè÷åñêèì èíñòðóìåíòîì, èñïîëüçóåìûì â äèññåðòàöèè, ÿâëÿåòñÿ ãåíåðàòîð ïñåâäî-ñëó÷àéíûõ ÷èñåë ÍèñàíàÂèãäåðñîíà [32; 34].Ýòîò ãåíåðàòîð îáìàíûâàåò âñå ñõåìû èç ôóíêöèîíàëüíûõ ýëåìåíòîâïîëèíîìèàëüíîãî ðàçìåðà è êîíñòàíòíîé ãëóáèíû, ò.å. òàêèå ñõåìû âûäàþò àñèìïòîòè÷åñêè îäèíàêîâûé ðåçóëüòàò íà ñëó÷àéíîì ñëîâå è íà ñëó÷àéíîì çíà÷åíèè ãåíåðàòîðà.  äèññåðòàöèè ãåíåðàòîð èñïîëüçóåòñÿ íàèâíûì îáðàçîì, ñðîäíè ðàáîòå Ðîìàùåíêî [39]: âìåñòî ñëó÷àéíîãî êîìáèíàòîðíîãî îáúåêòà ðàññìàòðèâàåòñÿ ïñåâäîñëó÷àéíûé, ÷òî ñóùåñòâåííîóìåíüøàåò îáëàñòü ïåðåáîðà è ïîçâîëÿåò äîêàçàòü òåîðåìû äëÿ îãðàíè÷åííûõ ðåñóðñîâ.Èòàê, îñíîâíîé çàäà÷åé ðàáîòû ÿâëÿåòñÿ èçó÷åíèå ñâÿçåé ìåæäó êîìáèíàòîðíûìè êîíñòðóêöèÿìè è óòâåðæäåíèÿìè î êîëìîãîðîâñêîé ñëîæíîñòèè èñïîëüçîâàíèå ýòèõ ñâÿçåé äëÿ ðàñïðîñòðàíåíèÿ èçâåñòíûõ òåîðåì î êîëìîãîðîâñêîé ñëîæíîñòè íà ñëîæíîñòü ñ îãðàíè÷åíèåì íà âû÷èñëèòåëüíûåðåñóðñû.71.2Îñíîâíûå ðåçóëüòàòûÐàáîòà ñîäåðæèò ÷åòûðå îñíîâíûõ ðåçóëüòàòà.Âî-ïåðâûõ, óñòàíîâëåíà ñâÿçü òåîðåìû Ìó÷íèêà îá óñëîâíîì êîäèðîâàíèè è òåîðèè ýêñòðàêòîðîâ.
Ñ èñïîëüçîâàíèåì òåîðåìû èç [12] â ðàçäåëå 3.2äîêàçàíî, ÷òî êîìáèíàòîðíîå ñâîéñòâî ýêñòðàêòîðà ïîçâîëÿåò äîêàçàòü òåîðåìó Ìó÷íèêà îá óñëîâíîì êîäèðîâàíèè. Òàêæå â ðàçäåëå 3.3 ïîêàçàíî, ÷òîàíàëîãè÷íîé òåõíèêîé ìîæíî ïîëó÷èòü òåîðåìó Ìó÷íèêà äëÿ íåñêîëüêèõóñëîâèé (âïëîòü äî ïîëèíîìèàëüíîãî ÷èñëà).Âî-âòîðûõ, äîêàçàíû àíàëîãè òåîðåìû Ìó÷íèêà äëÿ ñëîæíîñòè ñ îãðàíè÷åíèåì íà ïàìÿòü.
Ïðèìåíÿþòñÿ äâå òåõíèêè: èñïîëüçîâàíèå ÿâíûõ ýêñòðàêòîðîâ (òåîðåìà 4.1) è íàèâíàÿ äåðàíäîìèçàöèÿ ñ èñïîëüçîâàíèåìãåíåðàòîðîâ ïñåâäîñëó÷àéíûõ ÷èñåë (òåîðåìà 4.2). Êîìáèíàöèåé äâóõ ïîäõîäîâ ïîëó÷åí àíàëîã òåîðåìû äëÿ ëîãàðèôìè÷åñêîé òî÷íîñòè ïðè ëþáîìîãðàíè÷åíèè íà ïàìÿòü (òåîðåìà 4.10). Òàêæå äîêàçàíû àíàëîãè òåîðåìûÌó÷íèêà äëÿ íåñêîëüêèõ èñòî÷íèêîâ (òåîðåìà 4.16 è òåîðåìà 4.17). Ïðèìåíåíèå íàèâíîé äåðàíäîìèçàöèè ïîçâîëèëî äîêàçàòü òåîðåìó íå òîëüêîäëÿ ïîëèíîìèàëüíîãî, íî è äëÿ ýêñïîíåíöèàëüíîãî ÷èñëà óñëîâèé ïðè ïîëèíîìèàëüíîì îãðàíè÷åíèè íà ïàìÿòü (òåîðåìà 4.18).Â-òðåòüèõ, äîêàçàí àíàëîã òåîðåìû Ìó÷íèêà äëÿ CAM-ñëîæíîñòè ñîãðàíè÷åíèåì íà âðåìÿ (òåîðåìà 5.1).
Ïðè äîêàçàòåëüñòâå èñïîëüçîâàëàñüòåõíèêà, ðàçðàáîòàííàÿ äëÿ äîêàçàòåëüñòâà CAM-òåîðåìû î ñæàòèè ÿçûêîâ [13]. Çäåñü êîäèðîâàíèå îñóùåñòâëÿåòñÿ îáû÷íûì ïîëèíîìèàëüíûì àëãîðèòìîì, à äåêîäèðîâàíèå ïðîèñõîäèò ïðè ïîìîùè àëãîðèòìà èç êëàññàAM. Òàêæå ñôîðìóëèðîâàíà ãèïîòåçà, îáîáùàþùàÿ íà CAM-ñëîæíîñòüòåîðåìó äëÿ äâóõ óñëîâèé (ãèïîòåçà 5.8), è ïðîàíàëèçèðîâàíû òðóäíîñòè ñîáîáùåíèåì êîíñòðóêöèè íà ýòîò ñëó÷àé.Â-÷åòâ¼ðòûõ, îïðåäåëåíû è ïîñòðîåíû îáû÷íûå è óñèëåííûå êîëìîãîðîâñêèå ýêñòðàêòîðû ñ îãðàíè÷åíèåì íà ïàìÿòü (òåîðåìà 6.2). Êîíñòðóêöèè Çèìàíäà, äîêàçûâàþùèå ñóùåñòâîâàíèå òàêèõ ýêñòðàêòîðîâ ñ îïòèìàëüíûìè ïàðàìåòðàìè, óïðîùåíû è ïåðåëîæåíû äëÿ íîâûõ îïðåäåëåíèé.Èñïîëüçîâàíà ðàçðàáîòàííàÿ ïðè äîêàçàòåëüñòâå àíàëîãîâ òåîðåìû Ìó÷íèêà òåõíèêà íàèâíîé äåðàíäîìèçàöèè.81.3Àïðîáàöèÿ ðàáîòûÎñíîâíûå ðåçóëüòàòû, ïîëó÷åííûå â ðàáîòå, áûëè èçëîæåíû íà ìåæäóíàðîäíûõ êîíôåðåíöèÿõ Computer Science in Russia â Íîâîñèáèðñêå â2009 ãîäó, â Ñàíêò-Ïåòåðáóðãå â 2011 ãîäó è â Íèæíåì Íîâãîðîäå â 2012 ãîäó, îïóáëèêîâàíû â ñáîðíèêàõ òðóäîâ ýòèõ êîíôåðåíöèé' [60; 62; 64] (ñåðèÿLecture Notes in Computer Science, âõîäèò â ñèñòåìó Scopus) è ñïåöèàëüíûõâûïóñêàõ æóðíàëà Theory of Computing Systems [59; 61; 63].
 ñîâìåñòíûõ ñòàòüÿõ [64] è [63] àâòîðó ïðèíàäëåæàò ìåòîä äîêàçàòåëüñòâà òåîðåìûÌó÷íèêà ïðè ïîìîùè ýêñòðàêòîðîâ è òåîðåìà äëÿ CAM-ñëîæíîñòè.Êðîìå òîãî, ðåçóëüòàòû áûëè äîëîæåíû íà ñëåäóþùèõ íàó÷íûõ êîíôåðåíöèÿõ è ñåìèíàðàõ:• 8-àÿ ìåæäóíàðîäíàÿ êîíôåðåíöèÿ ïî âû÷èñëèìîñòè, ñëîæíîñòè è ñëó÷àéíîñòè (CCR), Ìîñêâà, 2013• 56-ÿ íàó÷íàÿ êîíôåðåíöèÿ ÌÔÒÈ, ñåêöèÿ äèñêðåòíîé ìàòåìàòèêè,Äîëãîïðóäíûé, 2013• 55-ÿ íàó÷íàÿ êîíôåðåíöèÿ ÌÔÒÈ, ñåêöèÿ äèñêðåòíîé ìàòåìàòèêè,Äîëãîïðóäíûé, 2012 [65]• Êîëìîãîðîâñêèé ñåìèíàð ïî ñëîæíîñòè âû÷èñëåíèé è ñëîæíîñòè îïðåäåëåíèé, ìåõàíèêî-ìàòåìàòè÷åñêèé ôàêóëüòåò ÌÃÓ èì.Ì.Â.Ëîìîíîñîâà• Êàôåäðàëüíûé ñåìèíàð êàôåäðû äèñêðåòíîé ìàòåìàòèêè ôàêóëüòåòàèííîâàöèé è âûñîêèõ òåõíîëîãèé ÌÔÒÈ(ÃÓ)• Ñåìèíàð ïî äèñêðåòíîé ìàòåìàòèêå Ïåòåðáóðãñêîãî îòäåëåíèÿ ìàòåìàòè÷åñêîãî èíñòèòóòà èì.
Â.À.Ñòåêëîâà ÐÀÍ• Ñåìèíàð Äàâèäà Ãàìàðíèêà â Ìàññà÷óñåòñêîì Òåõíîëîãè÷åñêîì èíñòèòóòå (ÑØÀ)1.4Ïëàí äàëüíåéøåãî èçëîæåíèÿÄàëüíåéøèé òåêñò îðãàíèçîâàí ñëåäóþùèì îáðàçîì.  ãëàâå 2 äàíûñòðîãèå îïðåäåëåíèÿ âñåõ èñïîëüçóåìûõ îáúåêòîâ è äàí îáçîð ðåçóëüòàòîâ,êîòîðûå èñïîëüçóþòñÿ â ðàáîòå.
Òàêæå ïðèâåäåíû èñïîëüçóåìûå ñëåäñòâèÿ9èç èçâåñòíûõ òåîðåì è äîêàçàòåëüñòâà ýòèõ ñëåäñòâèé. Ïîñëåäóþùèå ãëàâûîðãàíèçîâàíû ñîãëàñíî ïîëó÷åííûì ðåçóëüòàòàì. ãëàâå 3 èçëàãàåòñÿ äîêàçàòåëüñòâî òåîðåìû Ìó÷íèêà îá óñëîâíîì êîäèðîâàíèè ïðè ïîìîùè ýêñòðàêòîðîâ. Ñíà÷àëà äà¼òñÿ ôîðìóëèðîâêà òåîðåìû, äåëàþòñÿ íåñëîæíûå çàìå÷àíèÿ ïî íåé è èçëàãàåòñÿ èäåÿ äîêàçàòåëüñòâà. Çàòåì ôîðìóëèðóåòñÿ ñâîéñòâî, ñëåäóþùåå èç ñâîéñòâà ýêñòðàêòîðàè âëåêóùåå òåîðåìó Ìó÷íèêà, è äîêàçûâàþòñÿ îáå èìïëèêàöèè.
Íàêîíåö,ìåòîä ðàñïðîñòðàíÿåòñÿ íà òåîðåìó Ìó÷íèêà äëÿ íåñêîëüêèõ óñëîâèé, äëÿ÷åãî ââîäèòñÿ ïîíÿòèå ïðåôèêñíîãî ýêñòðàêòîðà. ãëàâå 4 ôîðìóëèðóþòñÿ è äîêàçûâàþòñÿ ðàçëè÷íûå àíàëîãè òåîðåìûÌó÷íèêà äëÿ ñëîæíîñòè ñ îãðàíè÷åíèåì íà ïàìÿòü. Ïåðâûé àíàëîã îïèðàåòñÿ íà ñóùåñòâîâàíèå ÿâíûõ ýêñòðàêòîðîâ. Äëÿ ñóùåñòâóþùèõ ÿâíûõêîíñòðóêöèé è ñóáýêñïîíåíöèàëüíûõ îãðàíè÷åíèé íà ïàìÿòü ýòîò ìåòîääà¼ò òåîðåìó ñ òî÷íîñòüþ O(log3 n) âìåñòî O(log n). Âòîðîé àíàëîã äîêàçûâàåò òåîðåìó äëÿ ñóáýêñïîíåíöèàëüíûõ îãðàíè÷åíèé ñ èñõîäíîé òî÷íîñòüþ. Äëÿ íåãî èñïîëüçóåòñÿ òåõíèêà íàèâíîé äåðàíäîìèçàöèè ïðèïîìîùè ãåíåðàòîðîâ ïñåâäîñëó÷àéíûõ ÷èñåë ÍèñàíàÂèãäåðñîíà, êîòîðàÿïîäðîáíî îïèñûâàåòñÿ.
Äàëåå äâà ïîäõîäà êîìáèíèðóþòñÿ äëÿ ïîëó÷åíèÿòåîðåìû ñ ëîãàðèôìè÷åñêîé òî÷íîñòüþ äëÿ ëþáîãî îãðàíè÷åíèÿ. Íàêîíåö,îáà ïîäõîäà ïðèìåíÿþòñÿ äëÿ äîêàçàòåëüñòâà òåîðåìû äëÿ ñëîæíîñòè ñîãðàíè÷åíèåì íà ïàìÿòü äëÿ íåñêîëüêèõ óñëîâèé. ãëàâå 5 òåõíèêà èç ñòàòüè [13] ïðèìåíÿåòñÿ äëÿ äîêàçàòåëüñòâà âàðèàíòà òåîðåìû Ìó÷íèêà äëÿ CAM-ñëîæíîñòè. Èäåÿ ñîñòîèò â òîì, ÷òîáûâìåñòî ïðîèçâîëüíîãî ÿâíîãî ýêñòðàêòîðà âçÿòü ýêñòðàêòîð Òðåâèñàíà [49],êîòîðûé ïîçâîëÿåò áûñòðî îñóùåñòâëÿòü êàê êîäèðîâàíèå, òàê è äåêîäèðîâàíèå. Ìû ôîðìóëèðóåì òåîðåìó, ïîäðîáíî èçëàãàåì êîíñòðóêöèþ Òðåâèñàíà è äîêàçûâàåì, ÷òî îíà êîððåêòíî ðàáîòàåò. Äàëåå ôîðìóëèðóåòñÿãèïîòåçà îá àíàëîãè÷íîì óòâåðæäåíèè äëÿ íåñêîëüêèõ óñëîâèé è àíàëèçèðóþòñÿ ïðåïÿòñòâèÿ ê ðàñøèðåíèþ êîíñòðóêöèè íà ýòîò ñëó÷àé.Íàêîíåö, â ãëàâå 6 òåõíèêà íàèâíîé äåðàíäîìèçàöèè ïðèìåíÿåòñÿ êòåîðèè êîëìîãîðîâñêèõ ýêñòðàêòîðîâ, à èìåííî äîêàçûâàåòñÿ ñóùåñòâîâàíèå îïòèìàëüíûõ îáû÷íûõ è óñèëåííûõ êîëìîãîðîâñêèõ ýêñòðàêòîðîâ ñîãðàíè÷åíèåì íà ïàìÿòü.
Âíà÷àëå äàþòñÿ ïîäðîáíûå îïðåäåëåíèÿ è ôîðìóëèðîâêè òåîðåì. Çàòåì, ñëåäóÿ Çèìàíäó, ìû ââîäèì ïîíÿòèÿ ï¼ñòðûõ èðàâíîìåðíî ï¼ñòðûõ òàáëèö (íàøè îïðåäåëåíèÿ äðóãèå, õîòÿ è ýêâèâàëåíòíûå) è äîêàçûâàåì ñóùåñòâîâàíèå ýòèõ îáúåêòîâ ñ îïðåäåë¼ííûìè ïà10ðàìåòðàìè. Äàëåå îïðåäåëåíèÿ ñëåãêà ìîäèôèöèðóþòñÿ äëÿ ïðèìåíåíèÿòåõíèêè íàèâíîé äåðàíäîìèçàöèè. Íàêîíåö, ïîäðîáíî äîêàçûâàåòñÿ, ïî÷åìó (ìîäèôèöèðîâàííûå) ï¼ñòðûå òàáëèöû ÿâëÿþòñÿ êîëìîãîðîâñêèìèýêñòðàêòîðàìè ñ îãðàíè÷åíèåì íà ïàìÿòü, à (ìîäèôèöèðîâàííûå) ðàâíîìåðíî ï¼ñòðûå òàáëèöû óñèëåííûìè êîëìîãîðîâñêèìè ýêñòðàêòîðàìè ñîãðàíè÷åíèåì íà ïàìÿòü.Ðàáîòà çàêàí÷èâàåòñÿ íåáîëüøèì çàêëþ÷åíèåì, êîòîðîå îáðèñîâûâàåòêîíòóðû äàëüíåéøèõ èññëåäîâàíèé, è ñïèñêîì ëèòåðàòóðû, ñîäåðæàùèì65 íàèìåíîâàíèé, â òîì ÷èñëå 7 ðàáîò àâòîðà ïî òåìå äèññåðòàöèè.1.5Èñïîëüçóåìûå îáîçíà÷åíèÿ ëèòåðàòóðå ïî êîëìîãîðîâñêîé ñëîæíîñòè íåò åäèíîé ñèñòåìû îáîçíà÷åíèé, ïîýòîìó ìû ïðèâåä¼ì ñïèñîê èñïîëüçóåìûõ îáîçíà÷åíèé ÿâíî:• Âñå ëîãàðèôìû ïî óìîë÷àíèþ áåðóòñÿ ïî îñíîâàíèþ 2.• Äâîè÷íûå ñëîâà ìû áóäåì îáîçíà÷àòü ìàëåíüêèìè ëàòèíñêèìè áóêâàìè, îáû÷íî a, b, c, p, x, y , z .
Ñëó÷àéíîå ñëîâî áóäåì îáîçíà÷àòüáóêâîé r. Ìíîæåñòâî äâîè÷íûõ ñëîâ äëèíû l áóäåì îáîçíà÷àòü ÷åðåç{0, 1}l , ìíîæåñòâî äâîè÷íûõ ñëîâ äëèíû ìåíüøå l ÷åðåç {0, 1}<l , àìíîæåñòâî âñåõ äâîè÷íûõ ñëîâ ÷åðåç {0, 1}∗ . Ïóñòîå ñëîâî áóäåìîáîçíà÷àòü ÷åðåç ε.
Äëèíó ñëîâà x áóäåì îáîçíà÷àòü ÷åðåç |x|.• Êîíå÷íûå ìíîæåñòâà áóäåì îáîçíà÷àòü áîëüøèìè ëàòèíñêèìè áóêâàìè, íàïðèìåð P , Q, R, S . Êîëè÷åñòâî ýëåìåíòîâ â ìíîæåñòâå P áóäåìîáîçíà÷àòü ÷åðåç |P |. Êîðòåæè áóäåì îáîçíà÷àòü ïîëóæèðíûì øðèôòîì, íàïðèìåð Q. Äëÿ ñèñòåì ìíîæåñòâ áóäåì èñïîëüçîâàòü êàëëèãðàôè÷åñêèå áóêâû, òàêèå êàê Q, R, S .• Ñëó÷àéíûå âåëè÷èíû áóäåì îáîçíà÷àòü ãðå÷åñêèìè áóêâàìè ξ , η è ò.ï.• Âñå ðàñïðåäåëåíèÿ âåðîÿòíîñòåé ïî óìîë÷àíèþ ñ÷èòàþòñÿ ðàâíîìåðíûìè íà äâîè÷íûõ ñëîâàõ ñîîòâåòñòâóþùåé äëèíû. ×åðåç Ul ìû áóäåìîáîçíà÷àòü ðàâíîìåðíî ðàñïðåäåë¼ííóþ ñëó÷àéíóþ âåëè÷èíó íà ñëîâàõ äëèíû l.
Ïîä çàïèñüþ Prr∈{0,1}n [A] áóäåì ïîíèìàòü âåðîÿòíîñòüñîáûòèÿ A â âåðîÿòíîñòíîì ïðîñòðàíñòâå, ãäå r ðàñïðåäåëåíî ðàâíîìåðíî íà {0, 1}n . Åñëè äëèíà r ÿñíà èç êîíòåêñòà, òî óêàçàíèå íà íå¼ìîæåò áûòü îïóùåíî: Prr [A].11• C(x|y) îáîçíà÷àåò óñëîâíóþ êîëìîãîðîâñêóþ ñëîæíîñòü ñëîâà x ïðèèçâåñòíîì y .• C(x) îáîçíà÷àåò áåçóñëîâíóþ êîëìîãîðîâñêóþ ñëîæíîñòü ñëîâà x, ò.å.C(x) = C(x|ε).• C(x, y) îáîçíà÷àåò áåçóñëîâíóþ êîëìîãîðîâñêóþ ñëîæíîñòü ïàðû(x, y).• dep(x, y) îáîçíà÷àåò çàâèñèìîñòü (âçàèìíóþ èíôîðìàöèþ) ìåæäó ñëîâàìè x è y , ò.å. âåëè÷èíó C(x) + C(y) − C(x, y).• Cs,t (x) îáîçíà÷àåò êîëìîãîðîâñêóþ ñëîæíîñòü ñëîâà x äëÿ îãðàíè÷åíèé s íà èñïîëüçóåìóþ ïàìÿòü è t íà âðåìÿ ðàáîòû ïðîãðàììû.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
