Диссертация (1103424), страница 3
Текст из файла (страница 3)
Åñëè, èñõîäÿ èç êîíòåêñòà, âàæíî òîëüêî îäíî èç ýòèõ îãðàíè÷åíèé, òîâòîðîå ìîæåò îïóñêàòüñÿ. Óñëîâíàÿ ñëîæíîñòü è ñëîæíîñòü ïàðû ñîãðàíè÷åíèÿìè íà ðåñóðñû ââîäÿòñÿ àíàëîãè÷íî.• Ìû èñïîëüçóåì îáîçíà÷åíèÿ CNs,t , CBPs,t , CAMs,t äëÿ ñëîæíîñòè ñîãðàíè÷åíèåì íà ðåñóðñû äëÿ íåäåòåðìíèðîâàííûõ âû÷èñëåíèé, âåðîÿòíîñòíûõ âû÷èñëåíèé è âû÷èñëåíèé â ìîäåëè ÀðòóðàÌåðëèíà ñîîòâåòñòâåííî. Îáû÷íî ìû áóäåì îïóñêàòü èíäåêñ, ñîîòâåòñòâóþùèéîãðàíè÷åíèþ íà ïàìÿòü.• Ìû èñïîëüçóåì ñòàíäàðòíûå àñèìïòîòè÷åñêèå îáîçíà÷åíèÿ:f (n) = O(g(n)), åñëè ∃C ∃N ∀n > N f (n) < Cg(n);f (n) = Ω(g(n)), åñëè ∃c > 0 ∃N ∀n > N f (n) > cg(n);f (n) = poly(g(n)), åñëè ∃c, d ∃N ∀n > N f (n) < c(g(n) + n + 1)d .Ïðè ýòîì åñëè âûðàæåíèå ñ O-, Ω- èëè poly-îáîçíà÷åíèåì âñòðå÷àåòñÿâíóòðè óòâåðæäåíèÿ ñ êâàíòîðàìè, òî öåïî÷êè êâàíòîðîâ èç ïðèâåä¼ííûõ îïðåäåëåíèé äîëæíû áûòü âûíåñåíû â ñàìîå íà÷àëî, òàêèìîáðàçîì êîíñòàíòû C , c, d íå çàâèñÿò îò âñåõ îñòàëüíûõ ïàðàìåòðîâ. îòäåëüíûõ ñëó÷àÿõ ìû áóäåì ïðÿìî óêàçûâàòü, îò ÷åãî çàâèñÿò ýòèêîíñòàíòû.
(Êàê ïðàâèëî, îò ñïîñîáà îïèñàíèÿ, èñïîëüçîâàííîãî ïðèîïðåäåëåíèè êîëìîãîðîâñêîé ñëîæíîñòè).• ×åðåç Cnk ìû îáîçíà÷àåì ÷èñëî ñî÷åòàíèé èç n ïî k , ò.å. êîëè÷åñòâîðàçëè÷íûõ k -ýëåìåíòíûõ ïîäìíîæåñòâ n-ýëåìåíòíîãî ìíîæåñòâà.12ÁëàãîäàðíîñòèÏðåæäå âñåãî, àâòîð âûðàæàåò ãëóáîêóþ áëàãîäàðíîñòü ñâîåìó íàó÷íîìó ðóêîâîäèòåëþ Íèêîëàþ Êîíñòàíòèíîâè÷ó Âåðåùàãèíó çà ïîñòàíîâêóçàäà÷è î êîëìîãîðîâñêèõ ýêñòðàêòîðàõ, ïîñòîÿííîå âíèìàíèå è ïîääåðæêóâ ðàáîòå. Àâòîð òàêæå áëàãîäàðèò ñâîèõ ñîàâòîðîâ è íàñòàâíèêîâ ÀíäðåÿÐîìàùåíêî è Àëåêñàíäðà Øåíÿ çà çíàêîìñòâî ñ òåìàòèêîé, ïîñòàíîâêóçàäà÷è î ïðèìåíåíèè ýêñòðàêòîðîâ ê çàäà÷å óñëîâíîãî êîäèðîâàíèÿ, ìíîãî÷èñëåííûå îáñóæäåíèÿ, ñîâåòû è êîíñòðóêòèâíóþ êðèòèêó ïî òåìàòèêåäèññåðòàöèè. Àâòîð âûðàæàåò îòäåëüíóþ áëàãîäàðíîñòü Àíäðåþ Àëüáåðòîâè÷ó Ìó÷íèêó (19582007) çà îáñóæäåíèå ðåçóëüòàòîâ àâòîðà, ðàçâèâàþùèõ èäåè Àíäðåÿ Àëüáåðòîâè÷à. Áåçâðåìåííàÿ êîí÷èíà Àíäðåÿ Àëüáåðòîâè÷à ñòàëà òÿæ¼ëîé óòðàòîé äëÿ ðîññèéñêîé íàóêè.Àâòîð áëàãîäàðèò ñâîèõ êîëëåã Âèêòîðà Áóëàòîâà, Ýäóàðäà Ãèðøà,Áðþíî Äþðàíà (Bruno Durand), Èëüþ Èðõèíà, Äìèòðèÿ Èöûêñîíà, Ðóñëàíà Èøêóâàòîâà, Þðèÿ Ïðèòûêèíà, Ìèõàèëà Ðàñêèíà è Àíäðåÿ Ðóìÿíöåâà çà îáñóæäåíèå îòäåëüíûõ ðàçäåëîâ ðàáîòû.
Àâòîð áëàãîäàðèò ÐîíåíàØàëòèåëà (Ronen Shaltiel) çà ïîëåçíîå çàìå÷àíèå, ïîçâîëèâøåå ñóùåñòâåííî óïðîñòèòü äîêàçàòåëüñòâî îäíîãî èç óòâåðæäåíèé. Òàêæå àâòîð áëàãîäàðèò ó÷àñòíèêîâ ñåìèíàðîâ êàôåäðû ìàòåìàòè÷åñêîé ëîãèêè è òåîðèèàëãîðèòìîâ ìåõàíèêî-ìàòåìàòè÷åñêîãî ôàêóëüòåòà ÌÃÓ è êàôåäðû äèñêðåòíîé ìàòåìàòèêè ôàêóëüòåòà èííîâàöèé è âûñîêèõ òåõíîëîãèé ÌÔÒÈçà âíèìàíèå è èíòåðåñ ê äîêëàäàì àâòîðà.Àâòîð áëàãîäàðèò îðãêîìèòåò Òóðíèðà Ãîðîäîâ è ëè÷íî Ñåðãåÿ Äîðè÷åíêî çà âêëþ÷åíèå â ñîñòàâ âàðèàíòà îñåííåãî òóðà 2005 ãîäà çàäà÷è, âîçíèêøåé â õîäå ðàáîòû íàä ðåçóëüòàòàìè äèññåðòàöèè.Íàêîíåö, àâòîð ãëóáîêî ïðèçíàòåëåí ñâîåé ñåìüå çà ïîñòîÿííóþ ïîääåðæêó.13Ãëàâà 2Îáçîð îñíîâíûõ ïîíÿòèé2.1Êîëìîãîðîâñêàÿ ñëîæíîñòüÏîíÿòèå êîëìîãîðîâñêîé (àëãîðèòìè÷åñêîé) ñëîæíîñòè îäèí èç ñïîñîáîâ ôîðìàëèçàöèè ïîíÿòèÿ êîëè÷åñòâî èíôîðìàöèè.
 îòëè÷èå îò ýíòðîïèè Øåííîíà, êîëìîãîðîâñêàÿ ñëîæíîñòü èçìåðÿåò êîëè÷åñòâî èíôîðìàöèè íå â ñëó÷àéíûõ âåëè÷èíàõ, à â êîíå÷íûõ äâîè÷íûõ ñëîâàõ.  ýòîìðàçäåëå ìû ïðèâåä¼ì ñòðîãèå îïðåäåëåíèÿ âñåõ ïîíÿòèé è îñíîâíûå ôàêòû,êîòîðûìè áóäåì ïîëüçîâàòüñÿ â äàëüíåéøåì.Îïðåäåëåíèå 2.1. Ïóñòü çàäàíà íåêîòîðàÿ âû÷èñëèìàÿ ôóíêöèÿV : {0, 1}∗ ×{0, 1}∗ → {0, 1}∗ . Óñëîâíîé êîëìîãîðîâñêîé ñëîæíîñòüþ ñëîâàx îòíîñèòåëüíî ñëîâà y ïðè ñïîñîáå îïèñàíèÿ V íàçûâàåòñÿ äëèíà êðàò÷àéøåãî ñëîâà p, òàêîãî ÷òî V (p, y) = x.
Ýòî ÷èñëî áóäåì îáîçíà÷àòü CV (x|y).Ñðåäè âñåõ ñïîñîáîâ îïèñàíèÿ ñóùåñòâóåò àñèìïòîòè÷åñêè îïòèìàëüíûé, êàê ïîêàçûâàåò ñëåäóþùàÿ òåîðåìà:Òåîðåìà 2.2 ( [6]). Ñóùåñòâóåò òàêîé ñïîñîá îïèñàíèÿ U , ÷òî äëÿ ëþáîãî äðóãîãî ñïîñîáà îïèñàíèÿ V ñóùåñòâóåò ÷èñëî c, òàêîå ÷òî ïðè âñåõx è y âûïîëíåíî íåðàâåíñòâî CU (x|y) < CV (x|y) + c.Âî âñåõ äàëüíåéøèõ îïðåäåëåíèÿõ è óòâåðæäåíèÿõ ïðåäïîëàãàåòñÿ, ÷òîíåêîòîðûé àñèìïòîòè÷åñêè îïòèìàëüíûé ñïîñîá îïèñàíèÿ çàôèêñèðîâàí.Ïîýòîìó ìû îïóñêàåì ñîîòâåòñòâóþùèé èíäåêñ è îáîçíà÷àåì óñëîâíóþñëîæíîñòü ÷åðåç C(x|y). Ðàññìàòðèâàþò òàêæå áåçóñëîâíóþ ñëîæíîñòü:Îïðåäåëåíèå 2.3. Êîëìîãîðîâñêîé ñëîæíîñòüþ C(x) ñëîâà x íàçûâàåòñÿóñëîâíàÿ ñëîæíîñòü C(x | ε), ãäå ε ïóñòîå ñëîâî.14 ëèòåðàòóðå âñòðå÷àþòñÿ äðóãèå âàðèàíòû îïðåäåëåíèÿ êîëìîãîðîâñêîé ñëîæíîñòè: ïðåôèêñíàÿ ñëîæíîñòü, ìîíîòîííàÿ ñëîæíîñòü, ëîãàðèôìàïðèîðíîé âåðîÿòíîñòè è äð.
Âñå ýòè ìåðû ñîâïàäàþò ñ îáû÷íîé ñëîæíîñòüþ ñ òî÷íîñòüþ äî àääèòèâíîãî ñëàãàåìîãî ïîðÿäêà O(log n), ãäå n äëèíà x. Ðåçóëüòàòû Ìó÷íèêà è Çèìàíäà, èçó÷àåìûå â ðàáîòå, è òàê ôîðìóëèðóþòñÿ ñ òî÷íîñòüþ äî òàêîãî àääèòèâíîãî ñëàãàåìîãî, òàê ÷òî ïåðåõîä ê äðóãîìó âàðèàíòó ñëîæíîñòè îñòàâèò ýòè ðåçóëüòàòû â ñèëå, ëèøüèçìåíèâ òî÷íîå çíà÷åíèå êîíñòàíò â O(·)-îáîçíà÷åíèÿõ.Ðàññìàòðèâàþò òàêæå êîëìîãîðîâñêóþ ñëîæíîñòü ñ îãðàíè÷åíèåì íàâû÷èñëèòåëüíûå ðåñóðñû.
Çäåñü ñòàíîâèòñÿ âàæíîé êîíêðåòíàÿ ìîäåëü âû÷èñëåíèé. Áóäåì ñ÷èòàòü, ÷òî âñå âû÷èñëåíèÿ ïðîèçâîäÿòñÿ íà äåòåðìèíèðîâàííîé ìíîãîëåíòî÷íîé ìàøèíå Òüþðèíãà ñ âûäåëåííûìè ëåíòàìè äëÿâõîäîâ (òîëüêî äëÿ ÷òåíèÿ) è âûõîäà (òîëüêî äëÿ çàïèñè); âðåìÿ å¼ ðàáîòû èçìåðÿåòñÿ êàê ÷èñëî øàãîâ äî ïðèõîäà â çàâåðøàþùåå ñîñòîÿíèå,à ïàìÿòü êàê ÷èñëî èñïîëüçîâàííûõ ÿ÷ååê íà ðàáî÷èõ ëåíòàõ.
 ñëåäóþùèõ îïðåäåëåíèÿõ ïîä ñïîñîáîì îïèñàíèÿ áóäåì ïîíèìàòü íå ïðîñòîâû÷èñëèìóþ ôóíêöèþ, à ìàøèíó, å¼ âû÷èñëÿþùóþ.Îïðåäåëåíèå 2.4. Óñëîâíîé êîëìîãîðîâñêîé ñëîæíîñòüþ ñëîâà x îòíîñèòåëüíî ñëîâà y ïðè ñïîñîáå îïèñàíèÿ V çà âðåìÿ t íà ïàìÿòè s íàçûâàåòñÿäëèíà êðàò÷àéøåãî ñëîâà p, òàêîãî ÷òî V (p, y) = x, ïðè ýòîì âðåìÿ ðàáîòûV (p, y) íå ïðåâîñõîäèò t, à èñïîëüçîâàííàÿ ïàìÿòü íå áîëüøå s. Ýòî ÷èñëîs,tîáîçíà÷àåòñÿ CV (x|y).Òåîðåìà îá îïòèìàëüíîì ñïîñîáå îïèñàíèÿ â ýòîì ñëó÷àå ïðèíèìàåò òàêîé âèä:Òåîðåìà 2.5 ( [28]).
Ñóùåñòâóåò òàêîé ñïîñîá îïèñàíèÿ U , ÷òî äëÿ ëþáîãî äðóãîãî ñïîñîáà îïèñàíèÿ V ñóùåñòâóþò ÷èñëà c è d, òàêèå ÷òî ïðèlog tâñåõ x è y âûïîëíåíî íåðàâåíñòâî Ccs,ct(x|y) < CV (x|y) + d.UÓ ñëîæíîñòè ñ îãðàíè÷åíèåì íà ðåñóðñû ìû òàêæå áóäåì îïóñêàòü èíäåêñ, ñîîòâåòñòâóþùèé ñïîñîáó îïèñàíèÿ. Áåçóñëîâíàÿ ñëîæíîñòü ñëîâà xñ îãðàíè÷åíèåì íà ðåñóðñû âíîâü îïðåäåëÿåòñÿ êàê ñëîæíîñòü ñ ïóñòûìóñëîâèåì.Äëÿ ñëîæíîñòè ñ îãðàíè÷åíèåì íà ðåñóðñû ñòàíîâÿòñÿ âàæíûìè è äðóãèå àñïåêòû ìîäåëè âû÷èñëåíèé: ïðè èñïîëüçîâàíèè âåðîÿòíîñòíûõ è/èëèíåäåòåðìèíèðîâàííûõ âû÷èñëåíèé íåîáõîäèìûå ðåñóðñû ìîãóò ñóùåñòâåííî óìåíüøèòüñÿ.
Íåäåòåðìèíèðîâàííûå âû÷èñëåíèÿ ìû áóäåì ïîíèìàòü15ñëåäóþùèì îáðàçîì: ìàøèíà ïîëó÷àåò äâà ïàðàìåòðà (âõîä y è ñåðòèôèêàò q ) è âîçâðàùàåò ëèáî ñïåöèàëüíûé ñèìâîë îøèáêè ⊥, ëèáî êàêîå-òîñëîâî x. Áóäåì ñ÷èòàòü, ÷òî ðåçóëüòàò ðàáîòû ìàøèíû íà âõîäå y ðàâåí x,åñëè îíà âîçâðàùàåò ýòî x äëÿ íåêîòîðîãî ñåðòèôèêàòà q , à äëÿ îñòàëüíûõñåðòèôèêàòîâ âîçðàùàåò ëèáî òî æå ñàìîå x, ëèáî ⊥.
Âðåìÿ ðàáîòû ìàøèíû è èñïîëüçîâàííóþ ïàìÿòü áóäåì ñ÷èòàòü êàê ìàêñèìóì ýòèõ âåëè÷èí ïîâñåì ñåðòèôèêàòàì.1  äàëüíåéøåì ïðè ðàññìîòðåíèè íåäåòåðìèíèðîâàííûõ ìàøèí àðãóìåíò q áóäåì îïóñêàòü. Ïî óìîë÷àíèþ âñå ìàøèíû áóäåìñ÷èòàòü äåòåðìèíèðîâàííûìè.Âåðîÿòíîñòíûå âû÷èñëåíèÿ áóäåì ïîíèìàòü ñëåäóþùèì îáðàçîì: ïîìèìî ñòàíäàðòíûõ ëåíò, ìàøèíà èìååò îòäåëüíóþ ëåíòó òîëüêî äëÿ ÷òåíèÿ,çàïîëíåííóþ ñëó÷àéíûìè áèòàìè (â áåñêîíå÷íîì êîëè÷åñòâå). Ïî ìåðå íàäîáíîñòè ìàøèíà ñ÷èòûâàåò è èñïîëüçóåò ñëó÷àéíûå áèòû. Âðåìÿ ðàáîòûíà äàííîì âõîäå áóäåì ñ÷èòàòü êàê ìàêñèìàëüíîå âðåìÿ ïî âñåì ñëó÷àéíûì áèòàì. ßñíî, ÷òî îáùåå ÷èñëî ïðî÷èòàííûõ ñëó÷àéíûõ áèòîâ çàâåäîìîíå ïðåâûñèò âðåìåíè ðàáîòû, ïîýòîìó ðåçóëüòàò çàâèñèò òîëüêî îò íåêîòîðîãî êîíå÷íîãî ó÷àñòêà ñëó÷àéíîé ëåíòû, êîòîðûé ìû áóäåì îáîçíà÷àòüçà r.Äàäèì îïðåäåëåíèÿ òð¼õ ñëîæíîñòåé äëÿ ðàçíûõ ìîäåëåé âû÷èñëåíèé.Âî âñåõ ñëó÷àÿõ ïåðåõîäû ê óíèâåðñàëüíîìó ñïîñîáó îïèñàíèÿ è áåçóñëîâíîé ñëîæíîñòè ïðîâîäÿòñÿ àíàëîãè÷íî ïðåäûäóùåìó.Îïðåäåëåíèå 2.6.
Íåäåòåðìèíèðîâàííîé êîëìîãîðîâñêîé ñëîæíîñòüþñëîâà x îòíîñèòåëüíî ñëîâà y ïðè íåäåòåðìèíèðîâàííîì ñïîñîáå îïèñàíèÿ W çà âðåìÿ t íà ïàìÿòè s íàçûâàåòñÿ äëèíà êðàò÷àéøåãî ñëîâà p,òàêîãî ÷òî W (p, y) = x, ïðè ýòîì âðåìÿ ðàáîòû W (p, y) íå ïðåâîñõîäèò t,à èñïîëüçîâàííàÿ ïàìÿòü íå áîëüøå s. Ýòî ÷èñëî áóäåì îáîçíà÷àòü ÷åðåçCNs,tW (x|y).Îïðåäåëåíèå 2.7. Âåðîÿòíîñòíîé êîëìîãîðîâñêîé ñëîæíîñòüþ ñëîâàx îòíîñèòåëüíî ñëîâà y ïðè ñïîñîáå îïèñàíèÿ V çà âðåìÿ t íà ïàìÿòè síàçûâàåòñÿ äëèíà êðàò÷àéøåãî ñëîâà p, òàêîãî ÷òî Prr [V (p, y, r) = x] > 32 ,ïðè ýòîì âðåìÿ ðàáîòû V (p, y, r) íå ïðåâîñõîäèò t, à èñïîëüçîâàííàÿ ïàìÿòüs,tíå áîëüøå s ïðè âñåõ r. Ýòî ÷èñëî áóäåì îáîçíà÷àòü ÷åðåç CBPV (x|y).×òîáû ýòè ìàêñèìóìû áûëè êîíå÷íûìè, íóæíî ÷òîáû ëèáî äëèíà ñåðòèôèêàòà áûëà îãðàíè÷åíàíåêîòîðîé ôóíêöèåé îò äëèíû y, ëèáî ìàøèíà íå ÷èòàëà ñëèøêîì äëèííûå ñåðòèôèêàòû ïîëíîñòüþ.Ýòî ñòàíäàðòíîå ïðåäïîëîæåíèå äëÿ íåäåòåðìèíèðîâàííûõ âû÷èñëåíèé.116Îïðåäåëåíèå 2.8.
Ñëîæíîñòüþ Àðòóðà-Ìåðëèíà ñëîâà x îòíîñèòåëüíî ñëîâà y ïðè íåäåòåðìèíèðîâàííîì ñïîñîáå îïèñàíèÿ W çà âðåìÿ t íà ïàìÿòè s íàçûâàåòñÿ äëèíà êðàò÷àéøåãî ñëîâà p, òàêîãî ÷òîPrr [W (p, y, r) = x] > 23 , ïðè ýòîì âðåìÿ ðàáîòû W (p, y, r) íå ïðåâîñõîäèò t, à èñïîëüçîâàííàÿ ïàìÿòü íå áîëüøå s ïðè âñåõ r. Ýòî ÷èñëî áóäåìs,tîáîçíà÷àòü ÷åðåç CAMW (x|y).Íàçâàíèå ïîñëåäíåé ñëîæíîñòè âîñõîäèò ê Áàáàþ [11] è îáúÿñíÿåòñÿ ñëåäóþùåé ìåòàôîðîé: âû÷èñëåíèÿ ïðîâîäèò Àðòóð ñ îãðàíè÷åííûìè âû÷èñëèòåëüíûìè ðåñóðñàìè, íî óìåþùèé êèäàòü ìîíåòêó, ïðè ïîìîùè ìàãàÌåðëèíà, äàþùåãî ïîäñêàçêó q .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
